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>