Thema7

Aus ProgrammingWiki
< BuK < IIm12 < Studenten < siclsche

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}
  1. Implementieren Sie die Prozedur free mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an
  2. 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)).

  1. Verwenden Sie die obige \eta-Regel.
  2. 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

  1. Zeigen Sie ((\lambda (x) (x\ x))(\lambda (x) x)) und ((\lambda (x) (x\ x))(\lambda (x) (x\ x))).
  2. 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 bBefehlAuswirkungnächster Befehl
0R0 = 5R0 := 51
1R1 = 3R1 := 32
2R3 = 1R3 := 13
3IFZERO R1 GOTO 7R1 = 3, also b+14
4R2 += R0R2 := 0 + 5 = 55
5R1 -= R3R1 := 3 - 1 = 26
6GOTO 3b = 33
3IFZERO R1 GOTO 7R1 = 2, also b+14
4R2 += R0R2 := 5 + 5 = 105
5R1 -= R3R1 := 2 - 1 = 16
6GOTO 3b = 33
3IFZERO R1 GOTO 7R1 = 1, also b+14
4R2 += R0R2 := 10 + 5 = 155
5R1 -= R3R1 := 1 - 1 = 06
6GOTO 3b = 33
3IFZERO R1 GOTO 7R1 = 0, also b = 77
7R0 = R2R0 := 158
8STOPend 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