Further work

1 files changed, 89 insertions, 0 deletions

diff --git a/implementation.tex b/implementation.tex
new file mode 100644
index 0000000..f5e5e58
--- /dev/null
+++ b/implementation.tex
@@ -0,0 +1,89 @@
+Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert.
+
+Es hat sich hierbei die oben beschriebene Konstruktion von $\Lleftarrow$ als Komposition algebraischer Transformationen und generischer, wohlbekannter, Algorithmen (Breitensuche auf einem beliebigem Graph) ergeben.
+Unsere vorherigen Versuche $\Lleftarrow$ in einem imperativeren Stil zu implementieren blieben Erfolglos; größte Schwierigkeiten hat bereitet die diversen Randbedingungen (Anfangs- und Endzustand, zu produzierende Ausgabe) innerhalb des Algorithmus zur Breitensuche zu wahren.
+
+\subsubsection{Struktur der Implementierung}
+
+Die Implementierung ist aufgeteilt in zwei Stack\footnote{\url{https://haskellstack.org}}-Pakete: \texttt{edit-lens} und \texttt{interactive-edit-lens}.
+
+Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sektionen dieser Arbeit:
+\begin{description}
+\item[Control.Edit]
+  Definition von Moduln
+\item[Control.Lens.Edit]
+  Definition von zustandsbehafteten Monoidhomomorphismen und, damit, edit-lenses sowohl als Typklasse als auch als existentiell quantifizierter Datentyp
+\item[Control.Edit.String]
+  Eine simple edit-Sprache auf Strings
+\item[Control.Edit.String.Affected]
+  Ein Algorithmus um die von einem edit aus \textbf{Control.Edit.String} betroffene Stelle in einem String einzuschränken
+\item[Control.FST]
+  Datentyp, schrittweise-, und vollständige Auswertung und die algebraischen Konstruktionen aus $\Lleftarrow$ für finite state transducer
+\item[Control.DFST]
+  Datentyp, schrittweise-, und vollständige Auswertung sowie Umwandlung zu einem FST für deterministische finite state transducer
+\item[Control.Lens.Edit.ActionTree]
+  Das beschriebene Verfahren zur Darstellung eines beliebigen DFST als edit-lens für jene edit-Sprache
+
+  Es ist hierbei jedoch der konkrete Typ der Wirkung und das Suchschema für $\Lleftarrow$ als Typklasse abstrahiert
+\item[Control.DFST.Lens]
+  Konkrete Anwendung von \textbf{Control.Lens.Edit.ActionTree} auf DFSTs 
+\end{description}
+
+\texttt{edit-lens} enthält zudem eine rudimentäre suite von Tests, die die Korrektheit der FST- und DFST-Implementierung, sowie den Algorithmus zum Anwenden von String-Edits prüft.
+
+\texttt{interactive-edit-lens} besteht aus nur drei Modulen:
+\begin{description}
+\item[Interact]
+  Implementierung des interaktiven Editors als TUI\footnote{\url{https://hackage.haskell.org/package/brick-0.47}}
+\item[Interact.Types]
+  Unterliegende Datentypen für \texttt{Interact}
+\item[Main]
+  Aufruf von \texttt{Interact} und Implementierung der angebotenen DFSTs
+\end{description}
+
+\subsubsection{Verwendung des interaktiven Editors}
+
+\begin{figure}[h]
+  \begin{center}
+    \includegraphics{screenshot}
+    \caption{Der interaktive Editor (im Modus \texttt{json-newl}) nach import einer kleinen JSON-Datei}
+  \end{center}
+\end{figure}
+
+Der interaktive editor kann von der Befehlseingabe gestartet werden wie folgt:
+\begin{lstlisting}[language=bash]
+  $ stack build
+  $ stack exec interact <dfst
+\end{lstlisting}
+Hierbei ist \texttt{<dfst>} einer der in \texttt{Main} implementierten DFSTs:
+
+\begin{description}
+\item[linebreak]
+  Wandelt Zeilenumbrüche und Leerzeichen ineinander um, sodass alle Zeilen mindestens 80 Zeichen enthalten
+\item[json-newl]
+  Normalisiert Whitespace in einem JSON\footnote{\url{https://de.wikipedia.org/wiki/JSON}}-String.
+  JSON ist nicht regulär; Es lassen sich Klammern nicht prüfen und Einrückung nicht in Abhängigkeit der Verschachtelung implementieren
+\item[alternate]
+  Akzeptiert Strings gerader Länge, jeder zweite Buchstabe wird in den entsprechenden Großbuchstaben umgewandelt und verdoppelt
+\item[id]
+  Identität-DFST
+\item[double]
+  Verdoppelt jedes Zeichen
+\end{description}
+
+Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen.
+
+Der Text auf beiden Seiten kann frei bearbeitet werden.
+Hierbei wechselt \texttt{tab} zwischen den Seiten.
+
+\texttt{ctrl + p} setzt die Propagation aus, bis sie mit \texttt{ctrl + p} wieder eingeschaltet wird.
+Auf der Konsole werden hinterher Zeitmessungen der ersten Propagation nach dem Wiedereinsetzen ausgegeben.
+
+\texttt{ctrl + o} öffnet eine interaktive Dateiauswahl (\texttt{/} veranlasst eine Suche, \texttt{return} bestätigt die Auswahl).
+Nach Auswahl wird der Inhalt der Datei am Cursor eingefügt.
+
+\subsubsection{Performance}
+
+Bei der Implementierung wurde nicht auf Performance geachtet.
+Es ist daher die Laufzeit des interaktiven Editors bereits bei kleinen Eingabe inakzeptabel lang (mehrere Sekunden für ein Kilobyte JSON).
+Es lässt sich allerdings der Speedup beim Propagieren kleiner edits gut beobachten; die Propagation eines ein-Buchstaben-edits nach rechts ist ca. einen Faktor 200 schneller als das komplett neue Parsen einer Datei (ca. ein Kilobyte JSON).