diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-07 10:25:32 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-07 10:25:32 +0200 |
commit | 24f64aafe8b05054e307d90564104f1c2d467524 (patch) | |
tree | 0f619bd7779129146f6408cfa3236bbaa0e965b7 | |
parent | a29cce747f3717e32231c9a92b40be12832037b6 (diff) | |
download | incremental-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.tex | 52 |
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 @@ | |||
1 | Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert. | 1 | Im Rahmen dieser Arbeit haben wir die in den vorherigen Abschnitten beschriebenen Verfahren und Konstruktionen in Haskell implementiert. |
2 | 2 | ||
3 | Diese Arbeit und die assoziierte Implementierung sind verfügbar unter \url{https://git.yggdrasil.li/gkleen/pub/incremental-dfsts}. | ||
4 | |||
3 | Es hat sich hierbei die oben beschriebene Konstruktion von $\Lleftarrow$ als Komposition algebraischer Transformationen und generischer, wohlbekannter Algorithmen (Breitensuche auf einem beliebigem Graph) ergeben. | 5 | Es hat sich hierbei die oben beschriebene Konstruktion von $\Lleftarrow$ als Komposition algebraischer Transformationen und generischer, wohlbekannter Algorithmen (Breitensuche auf einem beliebigem Graph) ergeben. |
4 | Unsere vorherigen Versuche, $\Lleftarrow$ in einem imperativeren Stil zu implementieren, blieben erfolglos; | 6 | Unsere vorherigen Versuche, $\Lleftarrow$ in einem imperativeren Stil zu implementieren, blieben erfolglos; |
5 | Größte Schwierigkeiten hat bereitet, die diversen Randbedingungen (Anfangs- und Endzustand, zu produzierende Ausgabe) innerhalb des Algorithmus zur Breitensuche zu wahren. | 7 | Größ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 | |||
11 | Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sektionen dieser Arbeit: | 13 | Die 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 | 16 | Definition 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 | 18 | Definition 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 | 20 | Eine 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 | 22 | Ein 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 | 24 | Datentyp, 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 | 26 | Datentyp, 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} | 28 | Das 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 | 30 | Es 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 | 32 | Konkrete 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}} | 40 | Implementierung 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} | 42 | Unterliegende Datentypen für \texttt{Interact} |
41 | \item[Main] | 43 | \item[Main] |
42 | Aufruf von \texttt{Interact} und Implementierung der angebotenen DFSTs | 44 | Aufruf 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 | ||
54 | Der interaktive Editor kann von der Befehlseingabe gestartet werden wie folgt: | 56 | Der 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} |
59 | Hierbei ist \texttt{<dfst>} einer der in \texttt{Main} implementierten DFSTs: | 61 | Hierbei 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}) | 65 | Wandelt 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} | 67 | Der 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. | 69 | Normalisiert 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 | 70 | JSON 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 | 72 | Akzeptiert 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 | 74 | Identität-DFST |
73 | \item[double] | 75 | \item[double] |
74 | Verdoppelt jedes Zeichen | 76 | Verdoppelt jedes Zeichen |
75 | \end{description} | 77 | \end{description} |
76 | 78 | ||
77 | Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen. | 79 | Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen. |