Frei und gebunden im Lambda-Kalkül

Hier ist etwas aus Slonnegers "Syntax und Semantik von Programmiersprachen":

Eine Variable kann sowohl gebunden als auch frei im selben Lambda-Ausdruck vorkommen: Beispielsweise ist in λx.yλy.yx das erste Auftreten von y frei und die anderen beiden sind gebunden.

Ich gehe davon aus, dass die freie Variable das y direkt nach dem λx ist. und die gebundenen ys sind die λy.y, die ich intuitiv erfassen kann. Also würde ((λx.yλy.yx) a) b) auf (yλy.ya) b) und dann auf bba reduzieren? Kann jemand erklären, wie es dazu kam? Am Ende ist es der Ausdruck b zweimal. Kann jemand vielleicht mehr Beispiele für gebundene und freie Variablen liefern?

lambda-calculus
quelle

Ich denke, Slonneger hat dort kein gutes Beispiel verwendet, da leicht als falsch verstanden werden kann , was normalerweise für . Ich würde ein anderes Beispiel geben: In ist das letzte Vorkommen von frei und die anderen sind gebunden.

λ x . y

$\lambda x.y$

λ x y

$\lambda xy$

λ x . λ y

$\lambda x.\lambda y$

(λ x . λ y . x y x) x

$(\lambda x.\lambda y. xyx)x$

x

$x$

Jay

Antworten:

Ich habe Klammern hinzugefügt, um Das rote ist frei und das blaue ist frei gebunden durch die grüne Abstraktion. Ich denke nicht, dass es Sinn macht zu sagen, dass das grüne gebunden ist, aber es ist zusammen mit dem Lambda ein Bindemittel.

λ x . (y (λ y . (y x)))

$\lambda x.(\color{red}y (\color{green}{\lambda y}.(\color{blue}yx)))$

y

$y$

y

$y$

Wir können die Laufzeit einmal Beta reduzieren

\begin{matrix} λ x . (y (λ y . (y x))) ein b \\ \to_{β} & (y (λ y . (y ein))) b \end{matrix}

$\begin{array}? && \lambda x.(y (\lambda y.(yx)))ab \\ &\to_\beta& (y (\lambda y.(ya)))b \end{array}$

aber nicht weiter, da keine verbleibenden Redexes mehr übrig sind.

quelle