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. (+\text{ }x\text{ }3))</math> beliebig umbenannt werden? Geben Sie zwei Antworten: eine konkrete auf den Ausdruck bezogene und eine verallgemeinerte.

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

= 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.

<language>Scheme</language>
<language>Scheme</language>
== Lösung ==
Aus der Funktion <math>f: X \times Y \times Z \rightarrow \mathbb{N}</math> muss durch die Curryfikation folgendes entstehen:

<math>F: X \rightarrow (Y \rightarrow (Z \rightarrow \mathbb{N}))</math>

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

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

<code id="4de4e751e2522">
(define f
  (lambda (x y z)
    (+ x (+ y z))))

(define f-curried
  (lambda (x)
    (lambda (y)
      (lambda (z)
        (+ x (+ y z))))))
</code>

<run id="4de4e751e2595">(f 1 2 3)</run>
<run id="4de4e77e3f681">(((f-curried 1) 2) 3)</run>