Lambda-Kalkül

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code hidden>
(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))]
  )
 )
)
</code>
[[Programmierparadigmen_-_Computerübungen|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 <tt>(element? var ausdr)</tt>, die mit <tt>#t</tt> bzw. <tt>#f</tt>
darüber entscheidet, ob ein <math>\lambda</math>-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

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

===ersetze===
Schreiben Sie eine Prozedur <tt>(ersetze var1 ausdr var2)</tt>, die in einem <math>\lambda</math>-
Ausdruck alle Variablen <tt>var1</tt> durch die Variable <tt>var2</tt> ersetzt.

Beachten Sie dabei, dass:
* Variablen selbst <math>\lambda</math>-Ausdrücke sind und
* <math>\lambda</math>-Ausdrücke selbst beliebige <math>\lambda</math>-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))))

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

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

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

<check>(listvergleich (alpha '(lambda (x) (a x (b c x))) 'y) '(lambda (y) (a y (b c y))))</check>

===auto-alpha===
Automatisieren Sie die <math>\alpha</math>-Konvention aus der vorherigen Aufgabe, indem Sie mit
<tt>(auto-alpha term alphabet)</tt> eine Prozedur angeben, die aus einem vorgegebenen Alphabet eine geeignete Variable zum Ersetzen auswählt. Nur wenn keine Variable des Alphabets der Bedingung der <math>\alpha</math>-Konvention genügt, soll der <math>\lambda</math>-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))

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

<check>(listvergleich (auto-alpha '(lambda (y) (* (+ 2 y a) b c)) '(a b c d e)) '(lambda (d) (* (+ 2 d a) b c)))
)
</check>
[[Programmierparadigmen_-_Computerübungen|Zurück zur Übungsübersicht]]