Lambda-Kalkül

Aus ProgrammingWiki

(define listvergleich (lambda(l1 l2) (cond [(and (null? l1) (null? l2)) #t] [(not (= (length l1) (length l2))) #f] [(and (list? (car l1)) (list? (car l2))) (if (listvergleich (car l1) (car l2)) (listvergleich (cdr l1) (cdr l2)) #f)] [(not (eq? (car l1) (car l2))) #f] [else (listvergleich (cdr l1) (cdr l2))] ) ) )

Zurück zur Übungsübersicht

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

Inhaltsverzeichnis 1 element? 2 ersetze 3 alpha 4 auto-alpha

element?

Implementieren Sie die Prozedur (element? var ausdr), die mit #t bzw. #f darüber entscheidet, ob ein -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

;Ihre Prozedur element?

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

ausführen

ersetze

Schreiben Sie eine Prozedur (ersetze var1 ausdr var2), die in einem -Ausdruck alle Variablen var1 durch die Variable var2 ersetzt.

Beachten Sie dabei, dass:

• Variablen selbst -Ausdrücke sind und
• -Ausdrücke selbst beliebige -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))))

;Ihre Prozedur ersetze

;Testen Sie hier Ihre Prozedur ersetze (ersetze 'x '(lambda (n) (+ x x)) 'z)

ausführen

alpha

Schreiben Sie eine Prozedur (alpha term neuvar), die auf einen -Ausdruck der Form ( (x) E) die -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 -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)))

;Ihre Prozedur alpha

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

ausführen

auto-alpha

Automatisieren Sie die -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 -Konvention genügt, soll der -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))

;Ihre Prozedur auto-alpha

;Testen Sie hier Ihre Prozedur auto-alpha (auto-alpha '(lambda (y) (* (+ 2 y b) c)) '(a b c d e f))

ausführen

Zurück zur Übungsübersicht