BuK-Übung08
Aus ProgrammingWiki
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.
$((\lambda x. (\lambda y. (x y)))(y w)) \leftrightarrow ((\lambda x. (\lambda z. (x z)))(y w)) \xrightarrow{β} (\lambda z. ((y w)) z))$
Semantik: $\eta$-Regel (Daniel Tasche, Jens Heider)
Vereinfachen Sie den Racket-Ausdruck ($\lambda$(z)(($\lambda$(x)($*$ 3 x)) z)).
($\lambda$(z)(($\lambda$(x)($*$ 3 x)) z)) $\Rightarrow$ ($\lambda$(x)($*$ 3 x)).
Reduktion (Raik Bieniek, Max Wielsch)
Reduzieren Sie $((λ(x)(x x))(λ(x) x))$ und $((λ(x)(x x))(λ(x)(x x)))$
1. $((λ(x)(x x))(λ(x) x)) \xrightarrow{β} ((λ(x) x) (λ(x) x)) \xrightarrow{β} (λ(x) x)$
2. $((λ(x)(x x))(λ(x)(x x))) \xrightarrow{β} ((λ(x)(x x))(λ(x)(x x))) \xrightarrow{β} …$
Terminiert nicht
Zeigen Sie, dass für $Y := (λ f. ((λ x. (f (x x)))(λ x. (f (x x)))))$ gilt: $(Y g) = (g (Y g))$
$(Y g) = ((λf.((λx.(f(x x)))(λx.(f(x x)))))g) \xrightarrow{β} ((λx.(g(x x)))(λx.(g(x x)))) \xrightarrow{β} (g ((λx.(g(x x))) (λx.(g(x x)))))$
$(g (Y g)) = (g ((λf.((λx.(f(x x)))(λx.(f(x x)))))g)) \xrightarrow{β} (g ((λx.(g(x x)))(λx.(g(x x)))))$
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.
Linksaußen-Reduktion $\beta_0$: $((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_0} z$
Linksinnen-Reduktion $\beta_i$: $((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_i} ((\lambda y.z)((((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x))))))$
Verwenden Sie zur Berechnung von (($\lambda$x. ((x d)(($\lambda$ y. (x y)) a))) b) unterschiedliche Reduktionsreihenfolgen.
Linksaußen-Reduktion $\beta_0$: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_0}
((b \text{ } d)((\lambda y.(b \text{ } y))a)) \xrightarrow{\beta_0}
((b \text{ } d)(((b \text{ } a))))$
Linksinnen-Reduktion $\beta_i$: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_i} ((\lambda x.((x \text{ } d)(((x \text{ } a))))) b) \xrightarrow{\beta_i} ((b \text{ } d)(((b \text{ } a))))$
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 |
