1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert.
Diese Arbeit und die assoziierte Implementierung sind verfügbar unter \url{https://git.yggdrasil.li/gkleen/pub/incremental-dfsts}.
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 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 die edit-Sprache aus \textbf{Control.Edit.String}
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 (Beispiel \ref{eg:linebreak})
\item[switch]
Der einfache DFST aus Abbildung \ref{fig:switchdfst}
\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 Eingaben 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 um ca. einen Faktor 200 schneller als das komplett neue Parsen einer Datei (ca. ein Kilobyte JSON).
Eine konkrete Quelle der Performance-Einbußen lies sich nicht bestimmen.
Es wäre möglich einschlägige Profiling-Werkzeuge\footnote{\url{https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/profiling.html}}\textsuperscript{, }\footnote{\url{https://jaspervdj.be/posts/2014-02-25-profiteur-ghc-prof-visualiser.html}} anzusetzen, dies ist jedoch, der eher theoretischen Ausrichtung der Arbeit folgend, nicht geschehen.
Simplere Methoden als Profiling und eingehende Analyse der entstehenden Reports lassen sich, wegen Haskells strikter Behandlung von Seiteneffekten und dem Ziel den unterliegenden Algorithmus Seiteneffekt-frei zu halten, nicht anwenden.
Es wurde aber zumindest in das interaktive Demonstrationsprogramm Funktionalität eingebaut, um, im Seiteneffekt-behafteten Teil, Laufzeitmessungen anzufertigen (\texttt{ctrl + p}).
|
