From f4c419b9ddec15bad267a4463f0720d6e28042d2 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Thu, 30 May 2019 12:18:08 +0200 Subject: Further work --- implementation.tex | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 89 insertions(+) create mode 100644 implementation.tex (limited to 'implementation.tex') 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 } 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). -- cgit v1.2.3