Thema7
Aus ProgrammingWiki
Inhaltsverzeichnis |
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 free mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an
- Implementieren Sie die Prozedur bound 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 true. $ \lambda xy. y$ nennen wir einfach false.
Dann gilt if $\equiv \lambda txy. txy$. (Hinweis: $txy \equiv ((t\ x)y)$)
Berechnen Sie if true $e_1\ e_2 = e_1$
if true $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)$
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
| 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
