\beta-Konversion

Aufgabenstellung

Reduzieren Sie den \lambda-Ausdruck (\lambda x. x x)((\lambda z. z y) x) durch mehrfache Anwendung der \beta-Regel. Verfolgen Sie alle möglichen Anwendungsstellen (sog. \beta-Redexe).

Lösung

Es gibt zwei Möglichkeiten den gegebenen Ausdruck zu reduzieren.

1. von innen heraus

   (\lambda x.xx)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} (\lambda x.xx)(xy) \stackrel{\beta}{\rightarrow} (xy)(xy)

2. von außen beginnend

   (\lambda x.xx)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} ((\lambda z.zy)x)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} (xy)(xy)

Scheme

Aufgabenstellung

Evaluieren Sie den folgenden Scheme-Ausdruck durch Handrechnung.

Überprüfen Sie das Ergebnis anschließend am Rechner.

Lösung

Umbenennung ungebundener Variablen

Aufgabenstellung

Evaluieren Sie den folgenden Ausdruck: ((\lambda x. (\lambda y. (x y)))(y w)). Hinweis: Falsch wäre (\lambda y. ((y w) y)).

Lösung

Damit der gegebene Ausdruck weiter reduziert werden kann muss zuerst y in z umbenannt werden. Dies ist notwendig, da y sowohl als gebundene und als ungebundene Variable verwendet wird.

Das y in z umbenannt wird, ist zufällig gewählt. Es hätte auch jeder andere Buchstabe genommen werden können. Außnahmen sind in diesem Fall allerdings x,\text{}y,\text{}w, da sie bereits in dem Ausdruck verwendet werden.

1. Umbenennen des Ausdrucks

   ((\lambda x.(\lambda y.(xy)))(yw)) \rightarrow ((\lambda x.(\lambda z.(xz)))(yw))

2. Reduktion des Ausdrucks

   (\lambda z.((yw)z))

\alpha-Konversion

Aufgabenstellung

Kann die gebundene Variable x in (\lambda x. (+\text{ }x\text{ }3)) beliebig umbenannt werden? Geben Sie zwei Antworten: eine konkrete auf den Ausdruck bezogene und eine verallgemeinerte.

Lösung

1. Ja, die Variable kann umbenannt werden, da nirgends eine gebundene Variable x existiert.
2. Eine Lösung wäre: (\lambda y.(+\text{ }y\text{ }3)). Es kann auch jeder andere beliebige Buchstabe gewählt werden.

Curryfication

Aufgabenstellung

Curryfizieren Sie die Funktion f, mit f(x, y, z) = x + y + z, zweimal. Geben Sie die Lösung in mathematischer Notation an und schreiben Sie außerdem eine entsprechende Scheme-Prozedur.

Lösung

Aus der Funktion f: X \times Y \times Z \rightarrow \mathbb{N} muss durch die Curryfikation folgendes entstehen:

Ein entsprechender Aufruf würde folgendermaßen aussehen: F(x)(y)(z).

Nachfolgend ist ein Scheme-Beispiel zusehen. Die Funktion f ist die dreistellige Ausgangsfunktion und die Funktion f-curried die einstellige Funktion nach der Currifikation von f.