BuK-Übung08

Semantik: \alpha-Regel (Felix Nitsche, Stefan Lüttke)

• Wenden Sie für ((\lambda x. ( \lambda y. ((x y)))(y w)) vor der \beta-Reduktion die \alpha-Konvention an.

Semantik: \eta-Regel (Daniel Tasche, Jens Heider)

• Vereinfachen Sie den Racket-Ausdruck (\lambda(z)((\lambda(x)(* 3 x)) z)).

Reduktion (Raik Bieniek, Max Wielsch)

• Reduzieren Sie ((\lambda(x)(x x))(\lambda(x) x)) und ((\lambda(x)(x x))(\lambda(x)(x x)))
• Zeigen Sie, dass für  Y := (\lambda f. ((\lambda x. (f (x x)))(\lambda x. (f (x x))))) gilt: (Y g) = (g (Y g))

Reduktionsreihenfolge (Ingo Körner, Christof Ochmann)

• Zeigen Sie dass es von der Reduktionsreihenfolge abhängen kann, ob die für ((\lambda y. z)((\lambda x. (x x))(\lambda x. (x x)))) existierende Normalform z gefunden wird oder nicht.
• Verwenden Sie zur Berechnung von ((\lambdax. ((x d)((\lambda y. (x y)) a))) b) unterschiedliche Reduktionsreihenfolgen.

Boolesche Werte (Stefan Scheumann, Robert Rosenberger)

Berechnen Sie  if true e1 e2 = e1.

Curryfizierung (Ronald Krause, Tobias Salzmann)

Currifizieren Sie  f(x, y, z) = x + y + z

Die Funktion f(x,y,z) besitzt drei Argumente, woraus die Summe derer gebildet werden soll. Bei der Anwendung der Curryfizierung wird die Funktion f mit deren Argumenten so umgewandelt, dass eine Funktion entsteht, welche genau einen Parameter als Eingabe besitzt.

Grund für die Curryfizierung ist die Verwendung von einstelligen Funktionen, wie z.B. im \lambda-Kalkül oder Haskell.

Im Allgemeinen beschreibt folgende mathematische Notation die Umwandlung durch die Curryfizierung:

f: A_1 \times A_2 \times ... \times A_3 \rightarrow R zu F: A_1 \mapsto (A_2 \mapsto (A_3 \mapsto (... \mapsto (A_n \mapsto R)))), sodass f(x,y,z)= F(x)(y)(z).

Beispiel: f(x,y,z)

Folgende Scheme-Prozedur beschreibt das Addieren von drei Argumenten:

Beispiel: F(x)(y)(z)

Folgende Scheme-Prozedur beschreibt die Addition von drei Argumenten nach der Curryfizierung:

Vorgehensweise: F(x)(y)(z)

1. ((\lambda.x~(\lambda.y~(\lambda.z~(+~x~y~z))))~1~2~3)

2. ((\lambda.y~(\lambda.z~(+~1~y~z)))~2~3)

3. ((\lambda.z~(+~1~2~z)~3)

4. (+~1~2~3)

5. 6

Registermaschine(Ronald Krause, Tobias Salzmann)

Führen Sie folgendes Programmbeispiel per Hand aus.

Beispiel:

Das Programm stoppt beim Erreichen des STOP-Befehls mit dem Ergebnis in R0.

Ausführung