BuK/IIm12/Studenten/siclsche/Thema7

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
# 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))$

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