BuK/IIm11/BuK-Übung08

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==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 <tt>if true e1 e2 = e1</tt>.'''

===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:

<code id="4fba572141700">
(define addThreeArguments
 (lambda (x y z)
  (+ x y z)))
</code>

<run id="4fba572141778">
(addThreeArguments 1 2 3)
</run>

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

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

<code id="4fba57e47cec9">
(define curryAddThreeArguments
 (lambda (x)
  (lambda (y)
   (lambda (z)
    (+ x y z)))))
</code>

<run id="4fba57e47cf3e">
(((curryAddThreeArguments 1) 2) 3)
</run>

===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:'''

<code id="4fba4bc9c507a">
0     R0=5
1     R1=3
2     R3=1
3     IFZERO R1 GOTO 7
4     R2 += R0
5     R1 -= R3
6     GOTO 3
7     R0 = R2
8     STOP
</code>

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

'''Ausführung'''

{| class="wikitable"
|-
! 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 ||
|}