Aus ProgrammingWiki

Inhaltsverzeichnis 1 β-Konversion 1.1 Aufgabe 1.2 Lösung 2 Scheme 2.1 Aufgabe 2.2 Lösung 3 Umbenennung gebundener Variablen 3.1 Aufgabe 3.2 Lösung 4 α-Konversion 4.1 Aufgabe 4.2 Lösung 5 Curryfication 5.1 Aufgabe 5.2 Lösung 6 Evaluationsstrategien in funktional-applikativen Sprachen 6.1 Aufgabe

β-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):

(λ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)

2 Variante von innen nach außen(leftmost innermost):

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

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.

((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

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.
((λx. (λy. (x y)))(y w)) ((λ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.
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.

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 wird in die einstellige Funktionen transformiert. Der Aufruf der Funktion lautet dann:

Scheme: Die Umsetzung der Funktion f in Scheme ergibt.

(define f (lambda (x y z) (+ x (+ y z))))

(f 2 3 5)

ausführen

Wird die Funktion Curryfiziert ergibt sich das folgende Scheme Programm. Korrekterweise müsste die Addition (+) noch in eine einstellige Funktion überführt werden.

(define F (lambda (x) (lambda (y) (lambda (z) (+ x (+ y z))))))

(((F 2) 3) 5)

ausführen

Evaluationsstrategien in funktional-applikativen Sprachen

Aufgabe

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