Lambda-Kalkül

Hinweis: Die Lösungen zu den ersten beiden Aufgaben liefern wichtige Hilfsprozeduren für die danach folgenden Aufgaben.

element?

Implementieren Sie die Prozedur (element? var ausdr), die mit #t bzw. #f darüber entscheidet, ob ein \lambda-Ausdruck eine bestimmte Variable enthält oder nicht.
Aufrufbeispiele:

(element? 'x '(lambda (x y) (+ (* x x) x y)))
#t
(element? 'y '(lambda (x y) (+ (* x x) x y)))
#t
(element? 'z '(lambda (x y) (+ (* x x) x y)))
#f

<eval>;Testen Sie hier Ihre Prozedur (element? 'x '(lambda (x y) (+ (* x x) x y)))</eval>

ersetze

Schreiben Sie eine Prozedur (ersetze var1 ausdr var2), die in einem \lambda- Ausdruck alle Variablen var1 durch die Variable var2 ersetzt. Beachten Sie dabei, dass:

• Variablen selbst \lambda-Ausdrucke sind und
• \lambda-Ausdrucke selbst beliebige \lambda-Ausdrücke enthalten können (Repräsentation

als verschachtelte Listen)
Aufrufbeispiele:

> (ersetze 'x 'x 'y)
y
> (ersetze 'x '(lambda (n) (+ x x)) 'y)
(lambda (n) (+ y y))
> (ersetze 'x '(lambda (n) (lambda (x) (lambda (z) (+ z x)))) 'y)
(lambda (n) (lambda (y) (lambda (z) (+ z y))))

<eval>;Testen Sie hier Ihre Prozedur ersetze (ersetze 'x '(lambda (n) (+ x x)) 'z)</eval>

alpha

Schreiben Sie eine Prozedur (alpha term neuvar), die auf einen \lambda-Ausdruck der Form (\lambda (x) E) die \alpha-Konvention anwendet und alle gebundenen Variablen durch eine neue Variable ersetzt. Die neue Variable darf in E nicht frei vorkommen. Ist eine Ersetzung nicht möglich, soll der \lambda-Ausdruck unverändert zurückgegeben werden.

Aufrufbeispiele:

> (alpha '(lambda (y) (+ 2 y x)) 'z)
(lambda (z) (+ 2 z x))
> (alpha '(lambda (x) (a x (b c x))) 'y)
(lambda (y) (a y (b c y)))
> (alpha '(lambda (x) (a x (b c x))) 'b)
(lambda (x) (a x (b c x)))

<eval>;Testen Sie hier Ihre Prozedur alpha (alpha '(lambda (y) (+ 2 y x)) 'z)</eval>