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)).
= (\lambda(x)(* 3 x)).
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.
Vorbedingung
\lambda xy. x nennen wir true.
\lambda xy. y nennen wir false.
if\equiv \lambda txy. txy (Hinweis: txy \equiv ((t\text{ }x)\text{ }y)))
Berechnung
((\lambda txy (t(x\text{ } y)))(\lambda xy (x))\text{ } e{1}\text{ } e{2})\equiv ((\lambda xy(x))\text{ } e{1}\text{ } e{2})\text{ }\equiv (e_{1})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
| Befehlszähler b | Befehl | Auswirkung | nächster Befehl |
|---|---|---|---|
| 0 | R0 = 5 | R0 := 5 | 1 |
| 1 | R1 = 3 | R1 := 3 | 2 |
| 2 | R3 = 1 | R3 := 1 | 3 |
| 3 | IFZERO R1 GOTO 7 | R1 = 3, also b+1 | 4 |
| 4 | R2 += R0 | R2 := 0 + 5 = 5 | 5 |
| 5 | R1 -= R3 | R1 := 3 - 1 = 2 | 6 |
| 6 | GOTO 3 | b = 3 | 3 |
| 3 | IFZERO R1 GOTO 7 | R1 = 2, also b+1 | 4 |
| 4 | R2 += R0 | R2 := 5 + 5 = 10 | 5 |
| 5 | R1 -= R3 | R1 := 2 - 1 = 1 | 6 |
| 6 | GOTO 3 | b = 3 | 3 |
| 3 | IFZERO R1 GOTO 7 | R1 = 1, also b+1 | 4 |
| 4 | R2 += R0 | R2 := 10 + 5 = 15 | 5 |
| 5 | R1 -= R3 | R1 := 1 - 1 = 0 | 6 |
| 6 | GOTO 3 | b = 3 | 3 |
| 3 | IFZERO R1 GOTO 7 | R1 = 0, also b = 7 | 7 |
| 7 | R0 = R2 | R0 := 15 | 8 |
| 8 | STOP | end program |