BuK/IIm12/Studenten/siclsche/Thema7
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Aufgabe 1 ==
$$free(e) = \begin{cases} \{v\}, & \text{wenn } e=v \in V \text{ (Variable)};\\
free(e_0) \cup free(e_1), & \text{wenn } e=e_0 e_1 \text{ (Anwendung)};\\
free(e_0) \backslash \{v\}, & \text{wenn } e=\lambda v. e_0 \text{ (Abstraktion)};\end{cases}$$
$$bound(e) = \begin{cases} \emptyset, & \text{wenn } e=v \in V \text{ (Variable)};\\
bound(e_0) \cup bound(e_1), & \text{wenn } e=e_0 e_1 \text{ (Anwendung)};\\
bound(e_0) \cup \{v\}, & \text{wenn } e=\lambda v. e_0 \text{ (Abstraktion)};\end{cases}$$
# Implementieren Sie die Prozedur <tt>free</tt> mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an
# Implementieren Sie die Prozedur <tt>bound</tt> mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an
== Aufgabe 2 ==
Wenden Sie für $((\lambda x. (\lambda y. (x\ y)))(y\ w))$ vor der $\beta$ - Reduktion die $\alpha$ - Konvention an.
Mit Hilfe der $\alpha$ - Konvention wird die gebundene Variable $y$ in $z$ umbenannt, sodass die Reduktion durch die $\beta$ - Regel problemlos erfolgen kann.
$((\lambda x. (\lambda y. (x\ y)))(y\ w))\ \overset{\alpha}{\leftrightarrow}\ ((\lambda x. (\lambda z. (x\ z)))(y\ w))\ \overset{\beta}{\Rightarrow}\ (\lambda z. ((y\ w)\ z))$
== Aufgabe 3 ==
Vereinfachen Sie den Racket-Ausdruck $(\lambda z.((\lambda x.(y \ x))\ z))$.
# Verwenden Sie die obige $\eta$-Regel.
# Verwenden Sie nur die $\beta$-Regel und vergleichen Sie beide Teilaufgaben-Lösungen miteinander.
$\eta$-Regel:
$(\lambda z.((\lambda x.(y \ x))\ z))\ \overset{\eta}{\Rightarrow}\ (\lambda x. \ (y \ x))$
$\beta$-Regel:
$(\lambda z.((\lambda x.(y \ x))\ z))\ \overset{\beta}{\Rightarrow}\ (\lambda z.\ (y\ z))$
== Aufagbe 4 ==
# Zeigen 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))$.
$((\lambda (x) (x\ x))(\lambda (x) x))\ \overset{\beta}{\Rightarrow}\ ((\lambda (x)\ x)(\lambda (x)\ x))\ \overset{\beta}{\Rightarrow}\ (\lambda (x)\ x) $
$((\lambda (x) (x\ x))(\lambda (x) (x\ x)))\ \overset{\beta}{\Rightarrow}\ ((\lambda (x) (x\ x))(\lambda (x) (x\ x)))$
$(Y\ g) = ((\lambda (f) ((\lambda (x) (f (x\ x )))(\lambda (x) (f (x\ x)))))\ g)\ \overset{\beta}{\Rightarrow}\ (\lambda x.\ (g\ (x\ x))(\lambda x.\ (g\ (x\ x)))$
$\overset{\beta}{\Rightarrow}\ (g\ (\lambda x.\ (g\ (x\ x))(\lambda x.\ (g\ (x\ x)))))$
$(g\ (Y\ g)) = (g\ ((\lambda f.\ ((\lambda x. \ (f\ (x\ x)))(\lambda x.\ (f\ (x\ x)))))\ g)\ \overset{\beta}{\Rightarrow}\ (\underbrace{g\ (\lambda x.\ (g\ (x\ x)))(\lambda x.\ (g\ (x\ x))))}_{\text{entspricht } (Y\ g)}$
$\hookrightarrow (Y\ g) = (g\ (Y\ g))$
== Aufagbe 5 ==
1. 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.
Von außen nach innen:
$((\lambda y. \ z)((\lambda x. \ (x \ x))(\lambda x. \ (x \ x)))) \overset{\beta}{\Rightarrow}\ z $
Von innen nach außen:
$((\lambda y. \ z)((\lambda x. \ (x \ x))(\lambda x. \ (x \ x))))\ \overset{\beta}{\Rightarrow}\ ((\lambda y. \ z)((((\lambda x. \ (x x))(\lambda x.(x x))))))$
2. Verwenden Sie zur Berechnung von $((\lambda x. \ ((x \ d)(\lambda y. \ (x \ y)) \ a))) \ b)$ unterschiedliche Reduktionsreihenfolgen.
Von außen nach innen:
$((\lambda x. \ ((x \ d)(\lambda y. \ (x \ y)) \ a))) \ b)\ \overset{\beta}{\Rightarrow}\ ((b \ d)(\lambda y.\ (b \ y))\ a))\ \overset{\beta}{\Rightarrow}\ ((b \ d) (a \ b))$
Von innen nach außen:
$((\lambda x. \ ((x \ d)(\lambda y. \ (x \ y)) \ a))) \ b)\ \overset{\beta}{\Rightarrow}\ ((\lambda x. \ ((x \ d)(x \ a))) \ b)\ \overset{\beta}{\Rightarrow}\ ((b \ d)(a\ b))$
== Aufgabe 6 ==
$ \lambda xy. x$ nennen wir einfach <tt>true</tt>.
$ \lambda xy. y$ nennen wir einfach <tt>false</tt>.
Dann gilt if $\equiv \lambda txy. txy$. (Hinweis: $txy \equiv ((t\ x)y)$)
Berechnen Sie <tt>if true</tt> $e_1\ e_2 = e_1$
<tt>if true</tt> $e_1\ e_2 = (\lambda txy.\ txy\ \lambda xy.\ x\ e_1\ e_2)$
Umkehrung der Klammersparregeln:
$((((\lambda t.\ (\lambda x.\ (\lambda y.\ ((t\ x)\ y)))) \text{ true})\ e_1)\ e_2)$
$\overset{\beta}{\Rightarrow}\ (((\lambda x.\ (\lambda y.\ ((\text{true } x)\ y)))\ e_1)\ e_2)$
$\overset{\beta}{\Rightarrow}\ ((\lambda y.\ ((\text{true } e_1)\ y))\ e_2)$
$\overset{\beta}{\Rightarrow}\ ((\text{true } e_1)\ e_2)$
$\overset{\beta}{\Rightarrow}\ (((\lambda x.\ (\lambda y.\ x))\ e_1) e_2)$
$\overset{\beta}{\Rightarrow}\ ((\lambda y.\ e_1)\ e_2)$
$\overset{\beta}{\Rightarrow}\ e_1$
== Aufagbe 7 ==
Currifizieren Sie $f(x,y,z) = x + y + z$.
$F : X \mapsto (Y \mapsto (Z \mapsto R))$, sodass $F(x)(y)(z) = f(x, y, z)$
<code id="519ddf161665b">
(define add
(lambda (x)
(lambda (y)
(lambda (z)
(+ x y z)))))
</code>
<run id="519ddf16166e2">(((add 2) 3) 4)</run>
== Aufgabe 8 ==
0 R0 = 5
1 R1 = 3
2 R3 = 1
3 IFZERO R1 GOTO 7
4 R2+ = R0 (Vorbelegung der Register mit Null)
5 R1- = R3
6 GOTO 3
7 R0 = R2
8 STOP
Das Programm stoppt beim Erreichen des STOP-Befehls mit dem Ergebnis.
Führen Sie obiges Programmbeispiel per Hand aus.
'''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 ||
|}
== Kreativaufgabe: RAM-Programm ==
Geben Sie mindestens ein RAM-Programm zur Berechnung der Funktion $w:\mathbb{N} \rightarrow \mathbb{N}$ mit $w(n) = \lfloor \sqrt{n} \rfloor$ an.
0 R0 = 3
1 R4 = 1
2 IFZERO R2 GOTO 6
3 R1 += R3
4 R2 -= R4
5 GOTO 2
6 R5 = R0
7 R5 -= R1
8 IFZERO R5 GOTO 13
9 R1 = 0
10 R3 += R4
11 R2 = R3
12 GOTO 2
13 R1 -= R0
14 IFZERO R1 GOTO 16
15 R3 -= R4
16 R0 = R3
17 STOP