BuK/IIm10/BuK-Übung09 G1

Wiki-Quelltext dieser Seite.

= <math>\beta</math>-Konversion =
== Aufgabenstellung ==
Reduzieren Sie den <math>\lambda</math>-Ausdruck <math>(\lambda x. x x)((\lambda z. z y) x)</math> durch mehrfache Anwendung der <math>\beta</math>-Regel. Verfolgen Sie alle möglichen Anwendungsstellen (sog. <math>\beta</math>-Redexe).

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

# von innen heraus
#:<math>(\lambda x.xx)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} (\lambda x.xx)(xy) \stackrel{\beta}{\rightarrow} (xy)(xy)</math>
# von außen beginnend
#:<math>(\lambda x.xx)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} ((\lambda z.zy)x)((\lambda z.zy)x) \stackrel{\beta}{\rightarrow} (xy)(xy)</math>

= Scheme =
== Aufgabenstellung ==
Evaluieren Sie den folgenden Scheme-Ausdruck durch Handrechnung.

<math>((lambda  (x)  (*  x  (+  2  x)))((lambda  (x)(*  x  x))  3))</math>

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

<language>Scheme</language>
== Lösung ==
<math>((\lambda (x) (*\text{ }x\text{ }(+\text{ }2\text{ }x)))((\lambda (x) (*\text{ }x\text{ }x))3)) \rightarrow (\lambda (x) (*\text{ }x\text{ }(+\text{ }2\text{ }x)))(*\text{ }3\text{ }3)) \rightarrow (*\text{ }(*\text{ }3\text{ }3) (+\text{ }2\text{ }(*\text{ }3\text{ }3))) \rightarrow (*\text{ }9\text{ }(+\text{ }2\text{ }9)) \rightarrow 99</math>


<run id="4de4e3929aaf1">((lambda (x) (* x (+ 2 x)))((lambda (x)(* x x))3))</run>

= Umbenennung ungebundener Variablen =
== Aufgabenstellung ==
Evaluieren Sie den folgenden Ausdruck: <math>((\lambda x. (\lambda y. (x y)))(y w))</math>. Hinweis: Falsch wäre <math>(\lambda y. ((y w) y))</math>.

== Lösung ==
Damit der gegebene Ausdruck weiter reduziert werden kann muss zuerst <math>y</math> in <math>z</math> umbenannt werden. Dies ist notwendig, da <math>y</math> sowohl als gebundene und als ungebundene Variable verwendet wird.

Das <math>y</math> in <math>z</math> 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 <math>x,\text{}y,\text{}w</math>, da sie bereits in dem Ausdruck verwendet werden.

# Umbenennen des Ausdrucks
#: <math>((\lambda x.(\lambda y.(xy)))(yw)) \rightarrow ((\lambda x.(\lambda z.(xz)))(yw))</math>
# Reduktion des Ausdrucks
#: <math>(\lambda z.((yw)z))</math>

= <math>\alpha</math>-Konversion =
== Aufgabenstellung ==
Kann die gebundene Variable <math>x</math> in <math>(\lambda x. (+ x 3))</math> beliebig umbenannt werden? Geben Sie zwei Antworten: eine konkrete auf den Ausdruck bezogene und eine verallgemeinerte.

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

== Lösung ==