5.8 Programmierprojekt: Schildkrötenzeichner

Organisatorisches

Abgabetermin: Montag, 3. Juli 2023

Aufgaben: Die in diesem Teilkapitel als Testataufgabe gekennzeichneten Aufgaben.

Format: Kompilierfähige Elm-Quelldatei. Ich werde bei jeder Testataufgabe darauf extra eingehen.

Material: Die elm-Dateien, die wir bereits in der Veranstaltung geschrieben haben oder die Sie als Hilfsdateien brauchen werden, finden Sie gezippt in elm-project-sources-for-students.zip. Ihr Code soll/darf auf diesem aufbauen.

Fragen und Probleme: Wenn Sie an einer Stelle nicht weiterkommen, kontaktieren Sie mich einfach.

Das Projekt

Ziel dieses Programmierprojektes ist es, eine kleine Zeichenrobotersprache zu entwerfen. Wir folgen hier recht genau dem in Christian Wagenknechts und Michael Hielschers Buch Formale Sprachen, abstrakte Automaten und Compiler, allerdings wird unsere Implementierung anders sein. Bei der Zeichensprache handelt es sich um eine Turtle Graphics, eine Schildkrötengrafik. Die "Schildkröte" ist ein imaginärer Cursor, den Sie mit den Befehlen move und rotate steuern können. Zusätzlich können Sie mit pen eine Farbe wählen.

pen blue;
move 100; 
rotate 45;
move 100;
rotate 45;
pen red;
move 100;
rotate 45; 

Unsere Sprache soll auch repeat-Befehle zulassen: mit repeat n [ P ] wird das Programm P wiederholt, und zwar \(n\) mal; dabei startet die Schildkröte die zweite Ausführung von P in der Position und Richtung, die sie am Ende der ersten Ausführung erreicht hat.

width 0.1;
repeat 20 [
    jump 200;
    turn 20;
    repeat 100 [ 
        move 300; 
        turn 170;
    ]
]

erzeugt dann beispielsweise das folgende, deutlich komplexere Bild:

Ziel ist es, eine Web-Anwendung zu schreiben, in der die User links ein Turtle-Programm eingeben können und die dann das Programm in eine Zeichnung übersetzt. Den Code, der gewisse Elm-Objekte dann konkret als Svg-Grafik zeichnet (wie in den Screenshots) werde ich Ihnen zur Verfügung stellen. Wir werden dieses Ziel in mehrere kleine Schritte zerlegen.

1. Lexing. Der Eingabe-String soll in logische Bausteine (Tokens) zerlegt werden, wobei auch schon der Whitespace eliminiert wird. Beispielsweise:

   Turtle.lex "pen green; repeat 10 [move 5; rotate 45;]"
   [Command "pen", Value "green", Semic, Command "repeat", Value "10", Open, Command "move", Value "5", Semic, Command "rotate", Value "45", Semic, Close] : List TurtleToken

   Dies können Sie mit einem Mealy-Automaten ähnlich zum letzten Programmprojekt erledigen.
2. Parsing. Hierfür brauchen wir eine kontextfreie Grammatik, die die obigen Tokens als Terminalsymbole nimmt. "pen" ist also ein Terminalsymbol unserer Grammatik. Eine Regel wäre beispielsweise \begin{align*} {\rm Command} & \rightarrow \texttt{pen}\ \texttt{color} \end{align*} wobei die rechte Seite aus zwei Terminalen besteht. Technisch gesehen hat unsere Sprache eine unendliche Menge von Terminalsymbolen (weil Sie theoretisch zumindest unendlich viele Werte für \(\texttt{color}\) wählen können). Wir müssen also eine Grammatik definieren, zeigen, dass sie LR(0) ist, und dann den DK-Automaten dafür implementieren, analog zu Tgrammar.elm
3. Den Parse-Tree (also Ableitungsbaum) in eine sinnvolle Datenstruktur übersetzen, beispielsweise

   type TurtleCommand
       = Pen String  
       | Rotate Float
       | Move Float
       | Repeat Int (List TurtleCommand)

4. Ein Elm-Programm schreiben, dass eine List TurtleCommand dann konkret zeichnet. Hierfür werde ich Ihnen einen Großteil des Codes zur Verfügung stellen. Alternativ: eine Funktion, die eine List TurtleCommand in einen String umwandelt, der die Zeichnung im svg-Format beschreibt, sodass Sie dann die Zeichnung als svg-Datei abspeichern können.

Wir werden uns nun jeden einzelnen Schritt genauer ansehen.

1. Lexing

Turtle.lex "pen green; repeat 10 [move 5; rotate 45;]"
[Command "pen", Value "green", Semic, Command "repeat", Value "10", Open, Command "move", Value "5", Semic, Command "rotate", Value "45", Semic, Close] : List TurtleToken

2. Parsing.

Hier definieren Sie eine kontextfreie Grammatik, deren Terminalsymbole die Tokens der letzten Aufgabe sind, und die die Struktur der Turtle-Programme (insbesondere die Verschachtelung mit den repeat-Befehlen) beschreibt.

Command -> pen color;

turtleGrammar : ContextFreeGrammar TurtleToken TurtleNonterminal                            
... 
turtleDKautomaton : DKAutomaton TurtleToken TurtleNonterminal TurtleDKstate

delta : State -> Symbol TurtleToken TurtleNonterminal -> State = 
delta state symbol = 
    case (state, symbol) of 
        (bla, Command "move") -> 
            Ihr Code hier
        (bla, Value s) -> 
            Hier lasen Sie offen, ob jetzt Value "red" oder Value "10" oder sonst was steht
        ...

Jetzt sollten Sie eigentlich Ihre Datei TurtleGrammar.elm in meine Datei importieren und sich die Parse-Bäume anschauen:

-- import Tgrammar as Grammar                        
import TurtleGrammar as Grammar                        

3. Vom Parsebaum zum Turtle-Programm

Wir haben nun einen Parsebaum, dessen Knoten mit Nichtterminalen wie beispielsweise ProgramLine oder Program beschriftet ist und dessen Blätter Terminalsymbole wie Command "move" oder Value "100" sind. Wir müssen das nun in eine problemspezifische Datenstruktur übersetzen.

type TurtleCommand
    = Pen String  
    | Rotate Float
    | Move Float
    | Repeat Int (List TurtleCommand)

type alias TurtleProgram : List TurtleCommand

parseTreeToTurtleProgram: ParseTree TurtleToken TurtleNonterminal -> TurtleProgram

parseTreeToTurtleProgram : String -> List TurtleCommand

Hinweis. Das Umwandeln des Parsebaumes in das Turtle-Programm ist unangenehm. Insbesondere, weil Sie im Baum "vorausschauen" müssen, was Ihr Knoten für Kinder hat. Hier ist ein Code-Beispiel von mir, wo ich einen Knoten im Parsebaum, dessen erstes Kind ein "Move"-Command ist, in ein TurtleProgram umwandle:

        Branch Grammar.Command [ Leaf (Lexer.CommandName "pen"), Leaf (Lexer.Parameter color), Leaf Lexer.Semicolon ] ->
            Result.Ok (Pen color)

Beachten Sie, dass der Ausdruck in dieser Pattern-Matching-Zeile sehr verschachtelt ist. Insbesondere wird hier gematcht:

• ein innerer Knoten (also Branch), der mit nicht Nichtterminal Grammar.Command beschriftet ist und
• der drei Kinderknoten hat, die alle Blätter sind Leaf und

Bevor wir das Programm in eine Svg-Grafik übersetzen, wollen wir noch eine Sache erledigen: das Programm glattstreichen. Damit meine ich, dass wir einen TurtleCommand der Form

Repeat 5 list

list ++ list ++ list ++ list ++ list

straightenTurtleProgram : TurtleProgram -> TurtleProgram

4. Das Programm als Svg zeichnen

Svg.line
    [ Svg.Attributes.x1 "100"
    , Svg.Attributes.y1 "0.5"
    , Svg.Attributes.x2 "300"
    , Svg.Attributes.y2 "200"
    , Svg.Attributes.stroke "red"
    , Svg.Attributes.strokeWidth "1.5"
    ]
    []                        

Svg.line : List (Svg.Attribute msg) -> List (Svg msg) -> Svg msg

turtleProgramToSvg : TurtleProgram -> List (Svg smg) 

Nun müssen Sie noch alles zusammenflicken. In der Datei DrawLR0Parser.elm sehen Sie, wie ich Svg-Objekte zeichne. Die entsprechende Code-Zeile ist

ZoomSvg.view model.svgCanvas [] dieListeIhrerSvgObjekte

5. Challenge: von kontextfreier Grammatik zum DK-Automaten

Mittlerweile haben Sie bestimmt festgestellt, dass es sehr mühsam sein kann, den DK-Automaten per Hand auf dem Papier zu konstruieren. In diesem Abschnitt schreiben wir eine Elm-Funktion, die aus einer gegebenen kontextfreien Grammatik automatisch den DK-Automaten baut. Als erstes überlegen wir uns einen Datentyp für die Zustände des DK-Automaten. Ein typischer Zustand wäre ja zum Beispiel \begin{align*} \boxed{ \begin{array}{rl} S \\ S & \rightarrow \text{.}SaSb \\ S & \rightarrow Sa\text{.}Sb \\ T & \rightarrow c\text{.} \end{array} } \end{align*} Wir ignorieren das \(S\) am Anfang mal und tun so, als wäre der Zustand eine Menge von dotted rules: \begin{align*} X & \rightarrow \alpha \text{.} \beta \end{align*} Das ist auch die Standardnotation in der Literatur. Eine Dotted Rule können wir als Datentyp leicht repräsentieren:

type alias DottedRule tt nt =
    { leftSide : nt
    , beforeDot : List (Symbol tt nt)
    , afterDot : List (Symbol tt nt)
    }                        

und somit steht auch klar, was die Zustände unseres DK-Automaten sind:

type alias DKstate tt nt = List (DottedRule tt nt)                            
                        

Wie bauen Sie jetzt daraus einen DK-Automaten? Naja, Sie müssen den gar nicht explizit bauen, d.h. Sie müssen nicht unbedingt alle Zustände berechnen. Sie können einfach die Funktionen delta und whichReduction implementieren. Wie kommen Sie nun von einem DKstate zum Folgezustand, wenn Sie ein Zeichen, beispielsweise \(a\) lesen? Wir gehen einfach alle Dotted Rules im Zustand durch und schauen, ob hinter dem Punkt ein \(a\) kommt; wenn ja, verschieben wir den Punkt hinters \(a\) und werfen die resultierende Regel in den Folgezustand:

In unserem Fall ist die Relation die \(\epsilon\)-Übergänge im nichtdeterministischen Automaten, also \begin{align*} \boxed{X \rightarrow \alpha \text{.} Y \beta} \step{\epsilon} \boxed{Y \rightarrow \text{.} \gamma} \end{align*} Wir müssen für unseren Folgezustand also die \(\epsilon\)-Hülle berechnen.

Schreiben wir nun eine allgemeine Funktion closure, die die Hülle einer Menge unter einer gegebenen Relation berechnet. Als erstes müssen wir uns überlegen, wie wir Mengen darstellen:

• Mengen. Eine Menge stellen wir einfach als Liste dar: List a. Wir müssen nun allerdings aufpassen, dass wir Elemente nicht mehrfach einfügen. Mit List.member a list können Sie überprüfen, ob a in der Liste vorkommt. Dies ist potentiell ineffizient, weil wir lineare Suche verwenden. Für leistungsfähige Anwendungen bräuchten wir eine Datenstruktur (Hashtable, B-Bäume etc.), um Mengen darzustellen. Für dieses Projekt ist die naive Implementierung mit Listen allerdings ausreichend schnell.
• Relationen. Am praktiabelsten ist es, wenn wir eine Relation auf Objekten mit Typ a als Funktion relation: a -> List a darstellen; relation x liefert dann die Liste aller Objekte \(y\) mit \(y \rightarrow z\), in diesem Falle also alle Dotted Rules, die mit einem \(\epsilon\)-Übergang zu erreichen sind.

epsilonFollowers : DottedRule tt nt -> List (DottedRule tt nt)

Wie berechnet man nun eine Hülle im Allgemeinen, wenn man die Relation \(\rightarrow\) als Funktion relation : a -> List a gegeben hat? Hier meine Empfehlung: unterhalten Sie zwei Listen closed und open. Die Idee ist, dass closed diejenigen Elemente \(y\) enthält, bei denen wir sicher sind, dass wir alle Folge-Elemente \(z\) mit \(y \rightarrow z\) bereits "gesehen" haben, dass \(z\) also bereits in closed oder open ist. Jetzt nehmen Sie ein Element \(y\) aus closed und bestimmen per Aufruf der Funktion relation die Menge der Folge-Elemente. Sie fügen alle Folge-Elemente der Liste open hinzu und verschieben \(y\) selbst von open nach closed. Allerdings müssen Sie aufpassen: wenn ein Element bereits in closed ist, sollte es nicht mehr in open eingefügt werden, sonst haben Sie eine Endlosschleife.

closure : (a -> List a) -> List a -> List a 
closure relation set = 
    ... 

Jetzt können Sie eigentlich den DK-Automaten implementieren: der Zustand ist eine Menge (in Elm: eine Liste) von Dotted Rules, und für die Zustandsübergangsfunktion \(\delta\) können Sie closure als Subroutine verwenden. Jetzt brauchen Sie nur noch whichReduction zu implementieren, welches Ihnen eine "abgearbeitete Dotted Rule" \(X \rightarrow \beta \text{.}\) gibt, falls so eine im Zustand zu finden ist.

deltaGeneral : (ContextFreeGrammar tt nt) -> (DKstate tt nt) -> (Symbol tt nt) -> (DKstate tt nt)
whichReductionGeneral : (ContextFreeGrammar tt nt) -> (DKstate tt nt) -> Maybe (Production tt nt)

buildDKautomaton : ContextFreeGrammar tt nt -> DKAutomaton tt nt (DKstate tt nt)