Prof. Dr. Manfred Schmidt-Schauß Künstliche Intelligenz/Softwaretechnologie Fachbereich Informatik und Mathematik/ Institut für Informatik Goethe-Universität Frankfurt am Main Grundlagen der Programmierung 2 Sommersemester 2016 Aufgabenblatt Nr. 7 Abgabe: Mittwoch 01. Juni 2016 vor! der Vorlesung Aufgabe 1 (35 Punkte) Wie in der Vorlesung und im Skript erläutert, kann die Auswertung einer Stackmaschine mit den Befehlen pop, pushK, push, slide, branchz, jump und mit arithmetischen Operationen +, − und ∗ sowie Marken wie folgt als Funktion I definiert werden: I I I I I I I I I I Programm [] (pop : prest) ((pushK k) : prest) ((push i) : prest) (+ : prest) (− : prest) (∗ : prest) ((slide m n) : prest) (marke : prest) ((branchz marke) : prest) I (jump marke) : prest) Stack stack (a : srest) stack stack (a : b : srest) (a : b : srest) (a : b : srest) stack stack (a : srest) Kopie prg prg prg prg prg prg prg prg prg prg −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ stack prg −→ Nächster Aufruf (Resultat) stack I prest srest prg I prest (k : stack ) prg I prest ((stack !!i) : stack ) prg I prest (b + a : srest) prg I prest (b − a : srest) prg I prest (b ∗ a : srest) prg I prest (take m stack ++ (drop (n + m) stack )) prg I prest stack prg if (0 == a) then I (dropWhile (marke /=) prg) srest prg else I prest srest prg I (dropWhile (marke /=) prg) stack prg a) Führen Sie das Stackmaschinenprogramm (bestehend aus 15 Befehlen) 1 2 3 4 5 pushK pushK -; pushK push 5; 1; 9; 1; marke1; 7 slide 2 1; 8 push 1; 9 push 0; 10 -; 6 11 12 13 14 15 branchz marke2; pushK 3; jump marke1; marke2; pop; beginnend mit leerem Stack per Hand entsprechend der obigen Regeln aus, indem Sie das Programm und den Stack nach Ausführung jedes Befehls angeben. (10 Punkte) b) In dieser Aufgabe soll die Stackmaschine in Haskell implementiert werden. Befehle der Stackmaschine werden durch den folgenden Datentyp Kommando repräsentiert. Für Marken werden dabei Zahlen verwendet und die arithmetischen Operationen werden durch den Datentyp ArithOp zusammengefasst: data Kommando = PushK Int | Pop | Push Int | Op ArithOp | Mark Marke | Jump Marke | Branchz Marke | Slide Int Int deriving (Eq,Show) type Marke = Int data ArithOp = Add | Mult | Sub | Div deriving(Eq,Show) 1 Ein Stackmaschinenprogramm ist eine Liste von Befehlen und der Stack ist eine Liste von Zahlen: type Programm = [Kommando] type Stack = [Int] Implementieren Sie in Haskell eine Funktion runProgramm :: Programm -> Stack, die ein Stackmaschinenprogramm erwartet und den resultierenden Stack als Ergebnis liefert. Implementieren Sie hierfür zunächst eine Hilfsfunktion interpretiere :: Programm -> Stack -> Programm -> Stack die genau die oben angegebene Funktion I in Haskell umsetzt und rufen Sie diese innerhalb von runProgramm auf. (25 Punkte) Aufgabe 2 (65 Punkte) In dieser Aufgabe soll die Schaltung einer Ampel betrachtet werden. Dabei wird jeder Zustand der Ampel wie folgt modelliert: Zustand Rot Rot-Gelb Grün Gelb Oberste Elemente des Stacks 1, 0, 0 1, 1, 0 0, 0, 1 0, 1, 0 Dabei wird der Abschluss eines Schaltvorgangs zwischen je zwei Zuständen mit einer −1 als oberstes Element dargestellt. Das heißt die obersten drei Elemente des Stacks [1, 0, 0, ... repräsentieren einen noch nicht abgeschlossenen Schaltvorgang, während die obersten vier des Stacks [−1, 1, 0, 0, ... einen abgeschlossenen Schaltvorgang darstellen. Bei allen Teilaufgaben ist das oberste Stack-Element anfangs größer −1. Zur Lösung der folgenden Aufgaben kann der Stackmaschinen Simulator nützlich sein: http://www.ki.informatik.uni-frankfurt.de/stackmachine a) Implementieren Sie ein Stackprogramm, das von Rot auf Rot-Gelb schaltet. Hierzu muss nicht geprüft werden, ob die Ampel aktuell rot ist. (5 Punkte) b) Implementieren Sie ein Stackprogramm, das den Stack [1] zurückliefert, wenn die Ampel grün ist, andernfalls soll [0] als Ergebnis berechnet werden. Sie können annehmen, dass der Stack anfangs nur drei beliebige Elemente gemäß der obigen Tabelle enthält. (20 Punkte) c) Implementieren Sie ein Stackprogramm, das den aktuellen Zustand erkennt und den Folgezustand berechnet. Beachten Sie, dass nach dem abgeschlossenen Schaltvorgang −1 oben auf dem Stack liegen muss. (30 Punkte) d) Implementieren Sie ein Stackprogramm, das den Ampelzyklus endlos durchlaufen lässt. Hierzu genügt eine Erweiterung Ihrer Lösung aus Aufgabenteil c). Für diese Teilaufgabe ist die schrittweise Ausführung mit dem Stackmaschinen Simulator zum Testen sinnvoll. (10 Punkte) 2
© Copyright 2024 ExpyDoc
