β-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)) \rightarrow \atop \alpha ((λ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.

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 entsprechendeScheme-Prozedur.

Evaluationsstrategien in funktional-applikativen Sprachen

Aufgabe

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