Prof. Dr. T. Grust, B. Dietrich, C. Duta, D. Hirn WS 2020/2021
Informatik 1
Forum: https://forum-db.informatik.uni-tuebingen.de/c/ws2021-info1 U ̈bungsblatt 13 (17.02.2021)
Abgabe bis: Mittwoch, 24.02.2021, 14:00 Uhr
v Relevante Videos: bis einschließlich Informatik 1 – Chapter 13 – Video #065. ® https://tinyurl.com/Informatik1-WS2021
Sprachebene ”Die Macht der Abstraktion – fortgeschritten“ Aufgabe 1: [14 Punkte]
In dieser Aufgabe soll das effiziente Sortierverfahren Merge Sort implementiert werden.
(a) Implementiert die Funktion split mit folgender Signatur:
(: split ((list-of %a) -> (tuple-of (list-of %a) (list-of %a)))).
(split xs) teilt die Liste xs in ein Tupel zweier (mo ̈glichst) gleich langer Listen ys und zs. Ob ein Element ys oder zs zugeordnet wird, ist unerheblich. Achtet unbedingt darauf, die Liste xs dabei nur einmal zu durchlaufen.
Beispiele:
(split (list 2 1 8 7)) (make-tuple (list 2 1) (list 8 7)) (split (list 3 2 7)) (make-tuple (list 3 2) (list 7))
(b) Implementiert die Funktion merge-by mit folgender Signatur:
(: merge-by ((%a %a -> boolean) (list-of %a) (list-of %a) -> (list-of %a))).
(merge-by lt? xs ys) fu ̈hrt die bezu ̈glich des Sortierkriteriums lt? bereits sortierten Listen xs und ys so zusammen, dass als Resultat wieder eine sortierte Liste entsteht.
Beispiele:
(merge-by < (list 1 3) (list 1 8)) (list 1 1 3 8)
(c) Implementiert die Funktion mergesort mit folgender Signatur:
(: mergesort ((%a %a -> boolean) (list-of %a) -> (list-of %a))). (mergesort lt? xs) sortiert eine gegebene Liste xs ensprechend eines Sortierkriteriums lt?. Fu ̈r
eine Liste xs mit zwei oder mehr Elementen geht mergesort dazu wie folgt vor:
(i) Nutze split, um xs zu halbieren; erhalte zwei Listen ys und zs als Zwischenergebnis.
(ii) Wende mergesort jeweils rekursiv auf ys und auf zs an. Die beiden entstehenden Listen sind nun sortiert.
(iii) Nutze zuletzt merge-by, um die beiden sortierten Listen wieder zu einer einzelnen (ebenfalls sortierten) Ergebnisliste zusammenzufu ̈gen.
Beispiel:
(mergesort < (list 8 1 3 1)) (list 1 1 3 8)
Aufgabe 2: [16 Punkte] Hinweis: Testfa ̈lle sind fu ̈r diese und die folgende Aufgabe nicht notwendig. Wir stel- len euch eine Datei lambda.rkt zur Verfu ̈gung, in der ihr die relevanten Definitionen aus dem Chapter 13 vorfindet.
In der Vorlesung haben wir bereits einige Literale und Operationen darauf im λ-Kalku ̈l definiert. Jetzt seid ihr gefragt. Baut die folgenden Operationen ganz a ̈hnlich wie im Chapter 13, Slides 20 ff.
(a) Implementiert die beiden Booleschen Operationen (: OR_ λ-term) und (: NOT_ λ-term). Es soll gelten (hier steht a fu ̈r die Darstellung des Booleans a im λ-Kalku ̈l, genau wie auf Slide 20 im Chapter 13 definiert):
(ao (list (list OR_ a) b)) a∨b (ao (list NOT_ a)) ¬a
ao ist die euch bekannte Funktion, die die Applicative Order-Reduktion eines λ-Ausdrucks durchfu ̈hrt.
(b) Implementiert die arithmetische Operation (: EXPT_ λ-term). EXPT_ berechnet die Exponentiation
xy zweier natu ̈rlichen Zahlen x und y, die als Church-Numerale repra ̈sentiert sind. Es soll gelten: (ao (list (list EXPT_ (CHURCH x)) (CHURCH y))) (CHURCH xy)
Spoiler-Warnung: Hinweis auf eine mo ̈gliche Implementation: ((ercrng l ((pheel *) k)) 1).
(c) Implementiert die beiden rekursiven Funktionen (: LENGTH_ λ-term) und (: SUM_ λ-term). Bei- den werden auf Listen in der Repra ̈sentation im λ-Kalku ̈l angewandt, wie sie auf Slide 21 im Chap- ter 13 definiert wurde.
Sei xs ≡ (list->λ-list (list (CHURCH x1) (CHURCH x2) . . . (CHURCH xn))), wobei die xi na- tu ̈rliche Zahlen sind. Es soll gelten:
(no (list LENGTH_ xs)) (CHURCH n)
(no (list SUM_ xs)) (CHURCH (x1 +x2 +···+xn))
Hinweise: Orientiert euch an der Implementation der rekursiven Funktion FAC auf Slide 25. Fu ̈r diese Teilaufgabe beno ̈tigt ihr den Kombinator Y, wie er als Y auf Slide 23 im Chapter 13 definiert wurde. Da Y im Spiel ist, mu ̈sst ihr die vordefinierte Funktion no zur Normal Order-Reduktion einsetzen, um die resultierenden λ-Ausdru ̈cke reduzieren zu ko ̈nnen.
Aufgabe 3: [10 Punkte] Hinweis: Testfa ̈lle sind auch fu ̈r diese Aufgabe nicht notwendig.
Achtung, festhalten! Jede Funktion im λ-Kalku ̈l la ̈sst sich gleichwertig durch einen Ausdruck darstellen, in dem ausschliesslich die drei Kombinatoren S, K, I vorkommen. Da der λ-Kalku ̈l jede u ̈berhaupt berechenbare Funktion ausdru ̈cken kann, sind also alle Programme allein auf eine Kombination von S, K, I zuru ̈ckzufu ̈hren—mind blown!1
Wir haben die drei Kombinatoren2 bereits in Chapter 13 definiert (drei analoge Racket-Definitionen S, K, I—jeweils mit Signatur λ-term—findet ihr ebenfalls im File lambda.rkt):
S ≡ (λx.(λy.(λz.((x z) (y z))))) K ≡ (λx.(λy.x))
I ≡ (λx.x)
Die Transformation T [e] tritt den Beweis fu ̈r die Behauptung oben an: der λ-Ausdruck e wird in einen Ausdruck u ̈bersetzt, der ausschliesslich SKI-Kombinatoren entha ̈lt (insbesondere entha ̈lt das Resultat keine λ-Abstraktionen mehr):
O1 O2 O3 O4 O5 O6
T [(λx.e)] T [(λx.(λy.e))] T [(λx.(e1 e2 ))] T [(λx.x)] T [(e1 e2)] T [x]
→ (K T [e]), falls x keine freie Variable in Ausdruck e ist → T [(λx.T [(λy.e)])]
→ ((S T [(λx.e1 )]) T [(λx.e2 )])
→ I (x ist eine Variable) → (T [e1] T [e2])
→ x
(Die Regeln O2 , O3 , oder O4 kommen nur zum Einsatz, falls O1 nicht zutrifft.)
1Es gibt tatsa ̈chlich Implementationen von Programmiersprachen, die Programme allein nach SKI u ̈bersetzen und diese Kom- binatoren dann mittels eine (der JVM a ̈hnlichen) virtuellen Maschine ausfu ̈hren. Die Programmiersprache Miranda ist ein Beispiel: https://www.cs.kent.ac.uk/people/staff/dat/miranda/.
2Ein Kombinator ist ein Ausdruck des λ-Kalku ̈ls, der keine freien Variablen beinhaltet.
Schreibt eine Funktion (: ski (λ-term -> λ-term)), die die Transformation T implementiert.
ACHTUNG: In eurer Implementation von ski mu ̈sst ihr die Kombinatoren durch die Symbole ’S, ’K und ’I darstellen (Beispiel: Regel O1 wird Code der Form (list ’K . . . ) enthalten). Wir haben die Applicative Order-Reduktion ao im File lambda.rkt so modifiziert, dass die Symbole ’S, ’K und ’I korrekt erkannt und reduziert werden. Ihr ko ̈nnt eure ski-Funktion also beispielsweise debuggen, in dem ihr die Ausgabe von
(ao e) und (ao (ski e))
vergleicht (die resultierenden Terme sollten a ̈quivalent—wenn auch nicht unbedingt identisch—sein).