Thema7
Inhaltsverzeichnis |
Aufgabe 1
- 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)).
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}\ ((\lambda x. \ (x \ x))(\lambda x. \ (x \ x))) \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))Aufagbe 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
Aufagbe 7
Currifizieren Sie f(x,y,z) = 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.
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.