From 24f64aafe8b05054e307d90564104f1c2d467524 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Fri, 7 Jun 2019 10:25:32 +0200 Subject: Include repo url --- implementation.tex | 52 +++++++++++++++++++++++++++------------------------- 1 file changed, 27 insertions(+), 25 deletions(-) (limited to 'implementation.tex') diff --git a/implementation.tex b/implementation.tex index 26ee2c7..f70f5db 100644 --- a/implementation.tex +++ b/implementation.tex @@ -1,5 +1,7 @@ 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. @@ -11,23 +13,23 @@ Die Implementierung ist aufgeteilt in zwei Stack\footnote{\url{https://haskellst Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sektionen dieser Arbeit: \begin{description} \item[Control.Edit] - Definition von Moduln +Definition von Moduln \item[Control.Lens.Edit] - Definition von zustandsbehafteten Monoidhomomorphismen und edit-lenses sowohl als Typklasse als auch als existentiell quantifizierter Datentyp +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 +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 +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 +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 +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} +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 +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 +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. @@ -35,43 +37,43 @@ Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sekt \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}} +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} +Unterliegende Datentypen für \texttt{Interact} \item[Main] - Aufruf von \texttt{Interact} und Implementierung der angebotenen DFSTs +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} +\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 +$ stack build +$ stack exec interact \end{lstlisting} Hierbei ist \texttt{} 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}) +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} +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 +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 +Akzeptiert Strings gerader Länge, jeder zweite Buchstabe wird in den entsprechenden Großbuchstaben umgewandelt und verdoppelt \item[id] - Identität-DFST +Identität-DFST \item[double] - Verdoppelt jedes Zeichen +Verdoppelt jedes Zeichen \end{description} Alle DFSTs (außer \texttt{json-newl}) akzeptieren nur lateinische Buchstaben, Leerzeichen und das Ausrufezeichen. -- cgit v1.2.3