summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGregor Kleen <gkleen@yggdrasil.li>2019-06-07 10:25:32 +0200
committerGregor Kleen <gkleen@yggdrasil.li>2019-06-07 10:25:32 +0200
commit24f64aafe8b05054e307d90564104f1c2d467524 (patch)
tree0f619bd7779129146f6408cfa3236bbaa0e965b7
parenta29cce747f3717e32231c9a92b40be12832037b6 (diff)
downloadincremental-dfsts-24f64aafe8b05054e307d90564104f1c2d467524.tar
incremental-dfsts-24f64aafe8b05054e307d90564104f1c2d467524.tar.gz
incremental-dfsts-24f64aafe8b05054e307d90564104f1c2d467524.tar.bz2
incremental-dfsts-24f64aafe8b05054e307d90564104f1c2d467524.tar.xz
incremental-dfsts-24f64aafe8b05054e307d90564104f1c2d467524.zip
Include repo url
-rw-r--r--implementation.tex52
1 files changed, 27 insertions, 25 deletions
diff --git a/implementation.tex b/implementation.tex
index 26ee2c7..f70f5db 100644
--- a/implementation.tex
+++ b/implementation.tex
@@ -1,5 +1,7 @@
1Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert. 1Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert.
2 2
3Diese Arbeit und die assoziierte Implementierung sind verfügbar unter \url{https://git.yggdrasil.li/gkleen/pub/incremental-dfsts}.
4
3Es hat sich hierbei die oben beschriebene Konstruktion von $\Lleftarrow$ als Komposition algebraischer Transformationen und generischer, wohlbekannter Algorithmen (Breitensuche auf einem beliebigem Graph) ergeben. 5Es hat sich hierbei die oben beschriebene Konstruktion von $\Lleftarrow$ als Komposition algebraischer Transformationen und generischer, wohlbekannter Algorithmen (Breitensuche auf einem beliebigem Graph) ergeben.
4Unsere vorherigen Versuche, $\Lleftarrow$ in einem imperativeren Stil zu implementieren, blieben erfolglos; 6Unsere vorherigen Versuche, $\Lleftarrow$ in einem imperativeren Stil zu implementieren, blieben erfolglos;
5Größte Schwierigkeiten hat bereitet, die diversen Randbedingungen (Anfangs- und Endzustand, zu produzierende Ausgabe) innerhalb des Algorithmus zur Breitensuche zu wahren. 7Größte Schwierigkeiten hat bereitet, die diversen Randbedingungen (Anfangs- und Endzustand, zu produzierende Ausgabe) innerhalb des Algorithmus zur Breitensuche zu wahren.
@@ -11,23 +13,23 @@ Die Implementierung ist aufgeteilt in zwei Stack\footnote{\url{https://haskellst
11Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sektionen dieser Arbeit: 13Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sektionen dieser Arbeit:
12\begin{description} 14\begin{description}
13\item[Control.Edit] 15\item[Control.Edit]
14 Definition von Moduln 16Definition von Moduln
15\item[Control.Lens.Edit] 17\item[Control.Lens.Edit]
16 Definition von zustandsbehafteten Monoidhomomorphismen und edit-lenses sowohl als Typklasse als auch als existentiell quantifizierter Datentyp 18Definition von zustandsbehafteten Monoidhomomorphismen und edit-lenses sowohl als Typklasse als auch als existentiell quantifizierter Datentyp
17\item[Control.Edit.String] 19\item[Control.Edit.String]
18 Eine simple edit-Sprache auf Strings 20Eine simple edit-Sprache auf Strings
19\item[Control.Edit.String.Affected] 21\item[Control.Edit.String.Affected]
20 Ein Algorithmus um die von einem edit aus \textbf{Control.Edit.String} betroffene Stelle in einem String einzuschränken 22Ein Algorithmus um die von einem edit aus \textbf{Control.Edit.String} betroffene Stelle in einem String einzuschränken
21\item[Control.FST] 23\item[Control.FST]
22 Datentyp, schrittweise-, und vollständige Auswertung und die algebraischen Konstruktionen aus $\Lleftarrow$ für finite state transducer 24Datentyp, schrittweise-, und vollständige Auswertung und die algebraischen Konstruktionen aus $\Lleftarrow$ für finite state transducer
23\item[Control.DFST] 25\item[Control.DFST]
24 Datentyp, schrittweise-, und vollständige Auswertung sowie Umwandlung zu einem FST für deterministische finite state transducer 26Datentyp, schrittweise-, und vollständige Auswertung sowie Umwandlung zu einem FST für deterministische finite state transducer
25\item[Control.Lens.Edit.ActionTree] 27\item[Control.Lens.Edit.ActionTree]
26 Das beschriebene Verfahren zur Darstellung eines beliebigen DFST als edit-lens für die edit-Sprache aus \textbf{Control.Edit.String} 28Das beschriebene Verfahren zur Darstellung eines beliebigen DFST als edit-lens für die edit-Sprache aus \textbf{Control.Edit.String}
27 29
28 Es ist hierbei jedoch der konkrete Typ der Wirkung und das Suchschema für $\Lleftarrow$ als Typklasse abstrahiert 30Es ist hierbei jedoch der konkrete Typ der Wirkung und das Suchschema für $\Lleftarrow$ als Typklasse abstrahiert
29\item[Control.DFST.Lens] 31\item[Control.DFST.Lens]
30 Konkrete Anwendung von \textbf{Control.Lens.Edit.ActionTree} auf DFSTs 32Konkrete Anwendung von \textbf{Control.Lens.Edit.ActionTree} auf DFSTs
31\end{description} 33\end{description}
32 34
33\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. 35\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.
@@ -35,43 +37,43 @@ Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sekt
35\texttt{interactive-edit-lens} besteht aus nur drei Modulen: 37\texttt{interactive-edit-lens} besteht aus nur drei Modulen:
36\begin{description} 38\begin{description}
37\item[Interact] 39\item[Interact]
38 Implementierung des interaktiven Editors als TUI\footnote{\url{https://hackage.haskell.org/package/brick-0.47}} 40Implementierung des interaktiven Editors als TUI\footnote{\url{https://hackage.haskell.org/package/brick-0.47}}
39\item[Interact.Types] 41\item[Interact.Types]
40 Unterliegende Datentypen für \texttt{Interact} 42Unterliegende Datentypen für \texttt{Interact}
41\item[Main] 43\item[Main]
42 Aufruf von \texttt{Interact} und Implementierung der angebotenen DFSTs 44Aufruf von \texttt{Interact} und Implementierung der angebotenen DFSTs
43\end{description} 45\end{description}
44 46
45\subsubsection{Verwendung des interaktiven Editors} 47\subsubsection{Verwendung des interaktiven Editors}
46 48
47\begin{figure}[h] 49\begin{figure}[h]
48 \begin{center} 50\begin{center}
49 \includegraphics{screenshot} 51\includegraphics{screenshot}
50 \caption{Der interaktive Editor (im Modus \texttt{json-newl}) nach Import einer kleinen JSON-Datei} 52\caption{Der interaktive Editor (im Modus \texttt{json-newl}) nach Import einer kleinen JSON-Datei}
51 \end{center} 53\end{center}
52\end{figure} 54\end{figure}
53 55
54Der interaktive Editor kann von der Befehlseingabe gestartet werden wie folgt: 56Der interaktive Editor kann von der Befehlseingabe gestartet werden wie folgt:
55\begin{lstlisting}[language=bash] 57\begin{lstlisting}[language=bash]
56 $ stack build 58$ stack build
57 $ stack exec interact <dfst> 59$ stack exec interact <dfst>
58\end{lstlisting} 60\end{lstlisting}
59Hierbei ist \texttt{<dfst>} einer der in \texttt{Main} implementierten DFSTs: 61Hierbei ist \texttt{<dfst>} einer der in \texttt{Main} implementierten DFSTs:
60 62
61\begin{description} 63\begin{description}
62\item[linebreak] 64\item[linebreak]
63 Wandelt Zeilenumbrüche und Leerzeichen ineinander um, sodass alle Zeilen mindestens 80 Zeichen enthalten (Beispiel \ref{eg:linebreak}) 65Wandelt Zeilenumbrüche und Leerzeichen ineinander um, sodass alle Zeilen mindestens 80 Zeichen enthalten (Beispiel \ref{eg:linebreak})
64\item[switch] 66\item[switch]
65 Der einfache DFST aus Abbildung \ref{fig:switchdfst} 67Der einfache DFST aus Abbildung \ref{fig:switchdfst}
66\item[json-newl] 68\item[json-newl]
67 Normalisiert Whitespace in einem JSON\footnote{\url{https://de.wikipedia.org/wiki/JSON}}-String. 69Normalisiert Whitespace in einem JSON\footnote{\url{https://de.wikipedia.org/wiki/JSON}}-String.
68 JSON ist nicht regulär; Es lassen sich Klammern nicht prüfen und Einrückung nicht in Abhängigkeit der Verschachtelung implementieren 70JSON ist nicht regulär; Es lassen sich Klammern nicht prüfen und Einrückung nicht in Abhängigkeit der Verschachtelung implementieren
69\item[alternate] 71\item[alternate]
70 Akzeptiert Strings gerader Länge, jeder zweite Buchstabe wird in den entsprechenden Großbuchstaben umgewandelt und verdoppelt 72Akzeptiert Strings gerader Länge, jeder zweite Buchstabe wird in den entsprechenden Großbuchstaben umgewandelt und verdoppelt
71\item[id] 73\item[id]
72 Identität-DFST 74Identität-DFST
73\item[double] 75\item[double]
74 Verdoppelt jedes Zeichen 76Verdoppelt jedes Zeichen
75\end{description} 77\end{description}
76 78
77Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen. 79Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen.