Lambda-Kalkül

Zurück zur Übungsübersicht

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

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-Ausdrücke sind und
• \lambda-Ausdrücke 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))))

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)))

auto-alpha

Automatisieren Sie die \alpha-Konvention aus der vorherigen Aufgabe, indem Sie mit (auto-alpha term alphabet) eine Prozedur angeben, die aus einem vorgegebenen Alphabet eine geeignete Variable zum Ersetzen auswählt. Nur wenn keine Variable des Alphabets der Bedingung der \alpha-Konvention genügt, soll der \lambda-Ausdruck unverändert zurückgegeben werden.

Aufrufbeispiele:

> (auto-alpha '(lambda (y) (* (+ 2 y b) c)) '(a b c d e f))
(lambda (a) (* (+ 2 a b) c))
> (auto-alpha '(lambda (y) (* (+ 2 y a) b c)) '(a b c d e))
(lambda (d) (* (+ 2 d a) b c))
> (auto-alpha '(lambda (y) (- (* (+ 2 y a) b c) 3 d)) '(a b c d e))
(lambda (e) (- (* (+ 2 e a) b c) 3 d))
> (auto-alpha '(lambda (y) (- (* (+ 2 y a) b c) 3 d e)) '(a b c d e))
(lambda (y) (- (* (+ 2 y a) b c) 3 d e))

Zurück zur Übungsübersicht