BuK/IIm10/BuK-Übung09 G2

Wiki-Quelltext dieser Seite.

=β-Konversion=
== Aufgabe ==
Reduzieren Sie den λ-Ausdruck (λx. x x)((λz. z y) x) durch mehrfache Anwendung der
β-Regel. Verfolgen Sie alle möglichen Anwendungsstellen (sog. β-Redexe).
== Lösung ==
1 Variante von außen nach innen(leftmost outermost):
<pre>
(λx. x x)((λz. z y) x)
((λz. z y) x)((λz. z y) x)
(x y)((λz. z y) x)
(x y)(x y)
</pre>
2 Variante von innen nach außen(leftmost innermost):
<pre>
(λx. x x)((λz. z y) x)
(λx. x x)(x y)
(x y)(x y)
</pre>

=Scheme=
== Aufgabe ==
Evaluieren Sie den folgenden Scheme-Ausdruck durch Handrechnung.
((lambda (x) (* x (+ 2 x)))((lambda (x)(* x x)) 3))
Uberprüfen Sie das Ergebnis anschließend am Rechner.
==Lösung==
Es wird von innen nach außen evaluiert.
<pre>
((lambda (x) (* x (+ 2 x)))((lambda (x)(* x x)) 3))
((lambda (x) (* x (+ 2 x)))((* 3 3)))
((lambda (x) (* x (+ 2 x)))(9))
(* 9 (+ 2 9))
(* 9 (11))
99
</pre>

=Umbenennung gebundener Variablen=
== Aufgabe ==
Evaluieren Sie den folgenden Ausdruck: ((λx. (λy. (x y)))(y w)). Hinweis: Falsch wäre
(λy. ((y w) y)).
== Lösung ==
Hier ist zu beachten, dass die Variable y sowohl ungebunden als auch gebunden vorkommt. Bevor der Ausdruck evaluiert werden kann muss die gebundene Variable umbenannt werden.
<br/>
((λx. (λy. (x y)))(y w)) <math> \rightarrow \atop \alpha </math> ((λx. (λz. (x z)))(y w))

=α-Konversion=
== Aufgabe ==
Kann die gebundene Variable x in (λx. (+ x 3)) beliebig umbenannt werden? Geben Sie
zwei Antworten: eine konkrete auf den Ausdruck bezogene und eine verallgemeinerte.
== Lösung ==
'''Konkret:''' Ja in diesem Fall kann die Variable x in jede Andere umbenannt werden.<br>
'''Verallgemeinert:''' Die Variable kann nur dann umbenannt werden, wenn sie nicht in den Einflußbereich einer gebundenen Variable gelangt. D.h. es darf, in der Applikation, keine gebundene Variable mit demselben Namen existieren.

<language>Scheme</language>
=Curryfication=
== Aufgabe ==
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 ==
'''Mathematische Notation:''' Die mehrstellige Funktion <math>f:X\times Y \times Z \rightarrow \mathbb{N}</math> wird in die einstellige Funktionen <math>F:X\rightarrow (Y \rightarrow (Z \rightarrow \mathbb{N}))</math> transformiert. Der Aufruf der Funktion lautet dann:<br/>
<math>F(x)(y)(z)</math><br/>
'''Scheme:''' Die Umsetzung der Funktion f in Scheme ergibt.
<code id="4ded0cf9523f4">
(define f
  (lambda (x y z)
    (+ x (+ y z))))
</code>
<run id="4ded0cf9524d9">
(f 2 3 5)
</run>
Wird die Funktion Curryfiziert ergibt sich das folgende Scheme Programm. Korrekterweise müsste die Addition (+) noch in eine einstellige Funktion überführt werden.
<code id="4ded0cf952451">
(define F
  (lambda (x)
    (lambda (y)
      (lambda (z)
        (+ x (+ y z))))))
</code>
<run id="4ded0cf952533">
(((F 2) 3) 5)
</run>

=Evaluationsstrategien in funktional-applikativen Sprachen=
== Aufgabe ==
Wiederholen Sie alternative Evaluationsstrategien in funktional-applikativen Sprachen
(eager, lazy, ...) und arbeiten Sie die jeweiligen Eigenschaften heraus.