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

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