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 12 (10.02.2021)
Abgabe bis: Mittwoch, 17.02.2021, 14:00 Uhr
v Relevante Videos: bis einschließlich Informatik 1 – Chapter 12 – Video #058. ® https://tinyurl.com/Informatik1-WS2021
Aufgabe 1: [10 Punkte]
/\ /\ /\ \
/\
/ /\ / /\ \
/\
/\ \
/ /\ \ / /\ \ \
/\
/ /\ / /\ \
/ / /\ \ … / / /\ \ \
Sprachebene ”Die Macht der Abstraktion“
n=1 n=2 n=3 n=4 n=5 Abbildung 1: Mountain-Peaks: Ausgabe als ASCII-Grafik.
Baut eine Funktion (: mountain-peaks (natural -> (list-of string))), die einen Gebirgszug der gegebenen Gro ̈ße n zeichnet. Die gro ̈ßeren Berge liegen dabei jeweils hinter den vorderen kleineren Bergen (vgl. Abbildung 1).
Hinweise fu ̈r die Implementierung:
• Beachtet, dass sich der Gebirgszug der Gro ̈ße n sehr systematisch aus dem Gebirgszug der Gro ̈ße
n − 1 konstruieren la ̈sst.
• Die Zeichnungen der Gebirge sind aus einzelnen Zeilen zusammengesetzt (bspw. besteht die Zeichnung fu ̈r n = 4 aus vier Zeilen). Stellt eine Zeichnung daher als (list-of string) dar, in der jedes Listenelement eine Zeile darstellt.
• Die Funktionen unlines und print (siehe unten) sind bereits vorgegeben. Der Aufruf von
(print (mountain-peaks n)) erzeugt in der REPL dann das gewu ̈nschte Bild des Gebirges: print gibt eine Liste von Zeilen untereinander aus.
• Das Zeichen \ (backslash) wird in Racket durch den String “\\” notiert.
(: unlines ((list-of string) -> string)) (define unlines
(lambda (ys)
(fold “” (lambda (x xs) (string-append x “\n” xs)) ys)))
(: print ((list-of string) -> %nothing)) (define print
(lambda (ss)
(write -string (unlines ss))))
Diese Aufgabe entstammt direkt aus einer sog. “Code Golfing Challenge”, einer Variante von Programmier-Wettbewerben, in denen die Teilnehmer versuchen, sich in der Ku ̈rze ihrer Lo ̈sungen zu unterbieten: http://codegolf.stackexchange.com/questions/98588/draw-some-mountain-peaks
(Programmla ̈nge ist in unserer Aufgabe aber kein Kriterium.)
Aufgabe 2: [10 Punkte]
In dieser Aufgabe soll eine Funktion implementiert werden, die fu ̈r eine gegebene Liste alle mo ̈glichen
Anordnungen (oder: Permutationen) ihrer Elemente erzeugt.
(a) Schreibe zuerst eine Funktion splits mit der folgenden Signatur:
(: splits ((list-of %a) -> (list-of (tuple-of (list-of %a) (list-of %a))))).
Die Funktion erha ̈lt eine Liste beliebiger Elemente, teilt sie an allen mo ̈glichen Stellen in zwei Listen auf und gibt alle diese Listenpaare zuru ̈ck.
Beispiel:
(splits (list 1 2 3)) (list (make-tuple empty (list 1 2 3)) (make-tuple (list 1) (list 2 3)) (make-tuple (list 1 2) (list 3)) (make-tuple (list 1 2 3) empty))
(b) Schreibe nun eine Funktion permutations, die eine Liste beliebiger Elemente erha ̈lt und basierend darauf alle Permutationen dieser Liste zuru ̈ck gibt. Die Funktion hat folgende Signatur:
(: permutations ((list-of %a) -> (list-of (list-of %a)))).
Nutze hierfu ̈r die in Teilaufgabe (a) implementierte Funktion splits. Eine Liste mit n Elementen hat u ̈brigens n! Permutationen. Die Reihenfolge der Permutationen in der Ergebnisliste spielt keine Rolle.
Beispiele:
(permutations (list 1 2 3)) (list (list 1 3 2) (list 3 1 2) (list 3 2 1) (list 1 2 3) (list 2 1 3)
(list 2 3 1))
(permutations (list “a” “b” “b”)) (list (list “a” “b” “b”) (list “b” “a” “b”) (list “b” “b” “a”) (list “a” “b” “b”) (list “b” “a” “b”)
(list “b” “b” “a”))
Aufgabe 3: [20 Punkte]
In der Vorlesung wurde vorgefu ̈hrt, wie sich arithmetische Ausdru ̈cke mittels Bina ̈rba ̈umen darstellen lassen (Chapter 11, Folie 19). Das funktioniert, ist allerdings recht unflexibel: Die Bina ̈rbaumstruktur eignet sich zwar problemlos fu ̈r bin ̈are Operationen (+, −, . . . ) mit zwei Operanden, macht es aber z.B. nicht mo ̈glich, un ̈are Operationen (Vorzeichen-Minus, Quadratwurzel, . . . ) darzustellen.
Eine in der Praxis wesentlich ma ̈chtigere Repra ̈sentation arithmetischer Ausdru ̈cke ist ein eigens dafu ̈r definierter Abstract Syntax Tree, kurz AST (siehe Abbildung 2).1 Statt nur einer Knotenart (node), besitzt ein solcher AST fu ̈r jede Kategorie von Werten bzw. Operationen eine spezielle Knotenart.
Fu ̈r den Arithmetik-AST term sind das:
• bina ̈re Operationen (binop) mit einem Operator (+, -, *, / oder ^) und zwei Operanden, • una ̈re Operationen (unop) mit einem Operator (-, √ ) und einem Operand,
• Variablen (var) mit einem Variablennamen und
• Zahlen (num) mit einem Wert.
Um bei der Auswertung unserer Arithmetik-ASTs den darin referenzierten Variablen konkrete Werte zuweisen zu ko ̈nnen, werden wir eine Umgebung (evironment) verwenden:
1Hintergrund: ASTs kommen aus der Welt der Programmiersprachen und Compiler. Jedes Mal, wenn du in DrRacket auf “Start” klickst, wird dein Racket-Code zuna ̈chst in einen AST umgewandelt, der dann intern evaluiert wird. (Dieser Racket-AST ist natu ̈rlich wesentlich komplexer als der Arithmetik-AST, mit dem wir uns in dieser Aufgabe befassen.)
BINOP
∗
(: term1 term) (define term1
(make-binop “*” (make-num 2)
(make-unop “-”
(make -var
Abbildung 2: AST fu ̈r den Ausdruck 2 ∗ (−a). (define environment
(signature (list-of (tuple-of string number))))
; Eine Umgebung, die a=7 und b=42 zuweist (: env1 environment)
(define env1
(list (make-tuple “a” 7) (make-tuple “b” 42)))
“a”))))
NUM
2
UNOP
−
VAR
a
In den folgenden Teilaufgaben wirst du vorrangig AST-Transformationen implementieren, die zusammen- genommen eine automatisierte Vereinfachung von arithmetischen Ausdru ̈cken ermo ̈glichen.
Wichtig: Die Datei ast-arithmetic.rkt entha ̈lt:
• Alle fu ̈r die Arbeit mit Arithmetik-ASTs term und der Umgebung environment no ̈tigen Definitionen. • Einen Parser term-parse, der einen als String gegebenen Ausdruck in einen AST u ̈bersetzt.
• Einen Pretty Printer term-prettyprint, der einen AST in einer menschenlesbaren Form ausgibt.
Mache dich nun zuna ̈chst mit den in ast-arithmetic.rkt vorgegebenen Definitionen vertraut. Dabei kannst du den Parser ignorieren, der Pretty Printer kann dir jedoch als Schablone fu ̈r die folgenden Teilaufgaben dienen.
(a) Damit du Arithmetik-ASTs zu einem konkreten Zahlenwert auswerten kannst, muss sich ermitteln lassen, welche Werte die darin enthaltenen Variablen haben. Schreibe also eine Funktion
(: lookup (environment string -> (maybe-of number)))
die in der u ̈bergebenen Umgebung die dem u ̈bergebenen Variablennamen zugeordnete Zahl nach- schla ̈gt. Ist der Variablenname nicht in der Umgebung definiert, soll #f zuru ̈ckgegeben werden – deswegen gibt diese Funktion einen Wert der Signatur (maybe-of number) zuru ̈ck.
Beispiele:
(lookup env1 “b”) 42 (lookup env1 “c”) #f
(b) Formuliere eine Funktion
(: eval (term environment -> number))
die einen AST (Signatur term) auswertet, d.h. den hinter dem arithmetischen Ausdruck stehenden Wert “ausrechnet”. Dabei sollen die den Variablen zugeordneten Werte in der u ̈bergebenen Umgebung (Signatur environment) nachgeschlagen werden. Erzeuge eine violation, falls eine Variable im AST referenziert wird, aber nicht in der Umgebung definiert ist. Andere Fehler, die bei der Berechnung auftreten ko ̈nnen (wie etwa die Division durch 0), mu ̈ssen nicht gesondert behandelt werden. Hinweis: Eine Quadratwurzel √a la ̈sst sich mittels (sqrt a) berechnen, eine Potenz a^b mittels (expt a b).
Beispiele:
(eval term1 env1) -14
(eval term1 (list (make-tuple “a” -21))) 42
(eval term1 empty) (violation “Variable nicht definiert”) √
(eval (term-parse “√(a^2 + b^2)”) env1) 42.579 (eval (term-parse ” (7^2 + 42^2)”) empty) 42.579
(c) Definiere ein Pra ̈dikat
(: constant? (term -> boolean))
das daru ̈ber Aufschluss gibt, ob der u ̈bergebene AST (Signatur term) konstant ist. Das sei genau
dann der Fall, wenn darin keine Variablen referenziert werden (siehe Abbildung 3).
BINOP
/
BINOP
+
BINOP
−
BINOP
∗
BINOP
+
NUM
4
NUM
10
NUM
1
VAR
a
NUM
2
VAR
a
Abbildung 3: AST term2 zum Ausdruck ((4 ∗ 10) + 2)/(a − (1 + a)). Der gru ̈n gestrichelt umrandete Teil- baum (term2-left) ist konstant; der rot gepunktet umrandete Teilbaum (term2-right) nicht, da dort die Variable a refenziert wird.
Beispiele:
(constant? term2 -left) #t (constant? term2 -right) #f
(d) Schreibe eine Funktion
(: constant-folding (term -> term))
die konstante Teilausdru ̈cke/-ba ̈ume eines ASTs mittels eval auswertet und durch einen num-Knoten mit dem Ergebniswert ersetzt.2 Als Umgebung kannst du dabei problemlos empty u ̈bergeben, weil das Pra ̈dikat constant? garantiert, dass keine Variablen referenziert werden. Die Ru ̈ckgabe ist der dabei entstehende (in aller Regel simplere) AST.
Beispiel:
(constant-folding term2) (make-binop “/” (make-num 42) term2-right)
(e) Formuliere eine Funktion
(: normalize (term -> term))
die folgende einfache A ̈quivalenzen ausnutzt, um einen als AST (Signatur term) gegebenen arith-
mentischen Ausdruck zu vereinfachen:
a + 0 ≡ a und 0 + a ≡ a (1) a−0≡a (2) a ∗ 1 ≡ a und 1 ∗ a ≡ a (3) a ∗ 0 ≡ 0 und 0 ∗ a ≡ 0 (4) a/1≡a (5)
Implementiere alle obigen sowie mindestens drei weitere A ̈quivalenzen. Beispiele:
(normalize (term-parse “0 + 1 * (a – 0)”)) (make-var “a”) (normalize (term-parse “0 + (42/1)*1 + 7 * 0”)) (make-num 42)
2Hintergrund: Constant folding ist eine der elementarsten Optimierungen, die ein Compiler durchfu ̈hrt.
(f) Schreibe eine Funktion
(: partial-application (term environment -> term))
die in der Umgebung (Signatur environment) definierte Variablen im AST (Signatur term) einsetzt, d.h. die Referenzierungen der Variablen mit den jeweiligen Zahlenwerten ersetzt, den Term ansonsten aber unvera ̈ndert la ̈sst.
Beispiel:3
(define term-add (make-binop “+” (make-var “a”) (make-var “b”))) (partial-application term-add (list (make-tuple “a” 1)))
(make-binop “+” (make-num 1) (make-var “b”))
(g) Formuliere abschließend eine Funktion
(: simplify (term environment -> term))
die die AST-Transformationen constant-folding, normalize und partial-application kombi- niert, um einen gegebenen AST (Signatur term) basierend auf einer gegebenen Umgebung (Signatur environment) so weit wie mo ̈glich auszuwerten und zu vereinfachen.
Achte darauf, die drei genannten Funktionen in der korrekten Reihenfolge anzuwenden, damit du am Ende einen mo ̈glichst einfachen arithmetischen Ausdruck erha ̈ltst.
Beispiel:
(simplify (term-parse “((-2) + (3*4) + 4/(1/8)) * z * ((x+y)/(x-y)) + (x-x)”) (list (make-tuple “x” 1) (make-tuple “y” 0)))
(make-binop “*” (make-num 42) (make-var “z”))
3Cool: partial-application ist eng verwandt mit der aus der Vorlesung bekannten Funktion curry. Vergleiche das Beispiel mit:
(define add (lambda (a b)
(+ a b)))
((curry add) 1) (lambda (b) (+ 1 b)