From a29cce747f3717e32231c9a92b40be12832037b6 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Fri, 7 Jun 2019 09:08:42 +0200 Subject: Finish for submission --- abstract.tex | 13 + conclusion.tex | 9 +- cover.tex | 15 + edit-lens/src/Control/DFST.lhs | 4 +- edit-lens/src/Control/DFST/Lens.lhs | 25 +- edit-lens/src/Control/Edit.lhs | 8 +- edit-lens/src/Control/Edit/String.lhs | 4 +- edit-lens/src/Control/Edit/String/Affected.lhs | 2 +- edit-lens/src/Control/FST.lhs | 33 +- edit-lens/src/Control/FST/Lens.tex | 4 +- edit-lens/src/Control/Lens/Edit.lhs | 12 +- implementation.tex | 19 +- intro.tex | 47 +-- org.tex | 14 +- sigillum.pdf | Bin 0 -> 69369 bytes sigillum.pdf_tex | 58 +++ sigillum.svg | 19 + template.tex | 488 +++++++++++++++++++++++++ thesis.args | 2 +- thesis.deps | 8 +- thesis.meta.yml.gup | 43 ++- thesis.tex | 6 +- title.tex | 28 ++ 23 files changed, 753 insertions(+), 108 deletions(-) create mode 100644 abstract.tex create mode 100644 cover.tex create mode 100644 sigillum.pdf create mode 100644 sigillum.pdf_tex create mode 100644 sigillum.svg create mode 100644 template.tex create mode 100644 title.tex diff --git a/abstract.tex b/abstract.tex new file mode 100644 index 0000000..9b8949a --- /dev/null +++ b/abstract.tex @@ -0,0 +1,13 @@ +\section*{Zusammenfassung} + +Parser, die bekannte Texte nach einer kleinen Änderung neu analysieren können, ohne die ganze Eingabe erneut zu betrachten, nennt man inkrementell. + +Inkrementelle Parser sind seit den 1970er-Jahren bekannt und inzwischen umfangreich erforscht. + +Edit-lenses sind eine vergleichsweise neue algebraische Darstellung von Programmen, die algebraisch strukturierte Änderungen zwischen Strukturen übersetzen. + +Wir demonstrieren, dass sich Inkrementelle Parser in der Sprache von edit-lenses fassen lassen, anhand einer besonders einfachen Klasse von Parsern, den deterministic finite state transducers. + +Hierzu speichern wir im unterliegenden Zustand der assoziierten edit-lens die Ausgabe-Wirkung des DFST als balancierten Binärbaum um Teile davon effizient austauschen zu können. + +Im Rahmen dessen stellen wir eine Implementierung von edit-lenses im Allgemeinen und unserem Verfahren in möglichst idiomatischem Haskell vor. diff --git a/conclusion.tex b/conclusion.tex index c604841..b0b8ae7 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -1,4 +1,9 @@ +Wir haben Definitionen von edit-lenses, finite-state-automata und manchen nützlichen algebraischen Operationen (Wort-DFST, Produkt von FSTs) darauf, sowohl menschenlesbar als auch in lauffähigem und idiomatischen Haskell gegeben. +Wir haben zudem ein Verfahren dargelegt, um aus einem gegebenen DFST einen inkrementellen Parser abzuleiten und diesen direkt als edit-lens konstruiert, um später Wiederverwendbarkeit zu gewährleisten. +Die gewünschte Laufzeitcharakteristik erreichen wir indem wir als Komplement einen balancierten Binärbaum von Transducer-Wirkungen speichern und, soweit möglich, nur Teilbäume davon betrachten müssen, um einen edit zu propagieren. +Zudem beschreiben wir ein interaktives Demonstrationsprogramm für das dargelegte Verfahren, das wir zusammen mit der Haskell-Implementierung ausliefern und geben einen groben Überblick über die bestehende Forschung in diesem Gebiet. + Unsere konkrete Implementierung hat, wie in Abschnitt \ref{performance} besprochen, Performance-Charakteristik, die sie für den tatsächlichen Einsatz untauglich macht. -Aufgrund der Struktur unserer Implementierung lässt sich jedoch eine der unterliegenden Ideen, das Komplement der edit-lens als Binärbaum von Wirkungen darzustellen und durch effizientes Austauschen von Baumfragmenten die gewünschte Laufzeit-Charakteristik zu erreichen, in Zukunft recht einfach auf andere Parser anwenden. +Aufgrund der Struktur unserer Implementierung (siehe Abschnitt \ref{ausblick-anwendbarkeit-der-implementierung-auf-andere-parser}) lässt sich jedoch eine der unterliegenden Ideen, das Komplement der edit-lens als Binärbaum von Wirkungen darzustellen und durch effizientes Austauschen von Baumfragmenten die gewünschte Laufzeit-Charakteristik zu erreichen, in Zukunft recht einfach auf andere Parser anwenden. -Zusammenfassend haben wir eine neue und non-triviale Anwendung von edit-lenses vorgestellt. +Zusammenfassend haben wir eine neue und nicht-triviale Anwendung von edit-lenses vorgestellt. diff --git a/cover.tex b/cover.tex new file mode 100644 index 0000000..3055f48 --- /dev/null +++ b/cover.tex @@ -0,0 +1,15 @@ +{\sffamily + \centering + {\scshape\LARGE Ludwig-Maximilians-Universität München\par} + \vspace{1cm} + \def\svgwidth{0.33 \textwidth} + \input{sigillum.pdf_tex}\par\vspace{1cm} + \vspace{1cm} + %{\huge \uppercase{Bachelorarbeit}\par} + %\vspace{0.5cm} + {\fontsize{1cm}{1.5cm}\selectfont Inkrementelle Parser als edit-lenses anhand von DFSTs \par} + \vfill + {\LARGE Gregor \textsc{Kleen}\par} +% Bottom of the page + {\LARGE \the\year\par} +} diff --git a/edit-lens/src/Control/DFST.lhs b/edit-lens/src/Control/DFST.lhs index eb838ae..48feaf9 100644 --- a/edit-lens/src/Control/DFST.lhs +++ b/edit-lens/src/Control/DFST.lhs @@ -41,7 +41,7 @@ import Text.Dot \begin{defn}[deterministic finite state transducer] Wir nennen einen FST \emph{deterministic}, wenn jedes Paar aus Ausgabezustand und Eingabesymbol maximal eine Transition zulässt, $\epsilon$-Transitionen keine Schleifen bilden und die Menge von initialen Zuständen einelementig ist. - Zusätzlich ändern wir die Darstellung indem wir $\epsilon$-Transitionen kontrahieren. + Zusätzlich ändern wir die Darstellung, indem wir $\epsilon$-Transitionen kontrahieren. Wir erweitern hierfür die Ausgabe pro Transition von einem einzelnen Zeichen zu einem Wort beliebiger Länge und fügen, bei jeder Kontraktion einer $\epsilon$-Transition $A \rightarrow B$, die Ausgabe der Transition vorne an die Ausgabe aller Transitionen $B \rightarrow \ast$ von $B$ an. \end{defn} @@ -92,7 +92,7 @@ toFST DFST{..} = flip execState initialFST $ forM_ (Map.toList stTransition) han \end{comment} Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST. -Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs um den Determinismus bereits im Typsystem zu kodieren. +Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs, um den Determinismus bereits im Typsystem zu kodieren. \begin{code} runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output) diff --git a/edit-lens/src/Control/DFST/Lens.lhs b/edit-lens/src/Control/DFST/Lens.lhs index 56f37a0..04dade5 100644 --- a/edit-lens/src/Control/DFST/Lens.lhs +++ b/edit-lens/src/Control/DFST/Lens.lhs @@ -68,7 +68,7 @@ import Data.Universe (Finite(..)) \begin{defn}[Ausgabe-Wirkung von DFSTs] Wir definieren zunächst die \emph{Ausgabe-Wirkung}\footnote{Wir schreiben im Folgenden auch nur \emph{Wirkung}} eines DFST auf einen festen String als eine Abbildung \texttt{state -> (Seq output, Maybe state)}, die den aktuellen Zustand vor dem Parsen des Strings auf den Zustand danach und die (womöglich leere) Ausgabe schickt. Wir annotieren Wirkungen zudem mit dem konsumierten String. -Diese Wirkungen bilden einen Monoiden analog zu Endomorphismen, wobei die Resultat-Strings concateniert werden. +Diese Wirkungen bilden einen Monoiden analog zu Endomorphismen, wobei die Resultat-Strings konkateniert werden. \begin{code} data DFSTAction state input output = DFSTAction @@ -132,13 +132,13 @@ Wir bedienen uns hierbei einer bestehenden Programmbibliothek \cite{composition- \begin{figure}[H] \centering \pinclude{presentation/switchdfst.tex} - \caption{\label{fig:switchdfst} Ein einfacher DFST, der zwischen zwei Zustanden wechselt und Ausgabe abhängig vom aktuellen Zustand erzeugt} + \caption{\label{fig:switchdfst} Ein einfacher DFST, der zwischen zwei Zuständen wechselt und Ausgabe abhängig vom aktuellen Zustand erzeugt} \end{figure} Auf $s$ wechselt der DFST seinen Zustand, auf $p$ produziert er, abhängig vom aktuellen Zustand, genau ein Zeichen. Wir stellen die Wirkung des DFST auf den Eingabe-String $spp$ grafisch analog zur Baumstruktur von \texttt{Compositions} dar. - Wir bedienen uns hier der Darstellung von Automaten-Wirkungen als \emph{Schaltboxen} aus \cite{hofmann2011automatentheorie}, angepasst für DFSTs indem wir die Ausgabe des transducers an den Pfaden innerhalb der Schaltbox annotieren. + Wir bedienen uns hier der Darstellung von Automaten-Wirkungen als \emph{Schaltboxen} aus \cite{hofmann2011automatentheorie}, angepasst für DFSTs, indem wir die Ausgabe des transducers an den Pfaden innerhalb der Schaltbox annotieren. \begin{figure}[H] \centering @@ -160,22 +160,23 @@ dfstaProduces = fmap fst . runDFSTAction' \end{code} \end{comment} -Für $\Rrightarrow$ können wir die alte DFST-Wirkung zunächst anhand des Intervalls in dem der input-String von allen gegebenen edits betroffen ist (\texttt{affected}) in einen unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen. +Für $\Rrightarrow$ können wir die alte DFST-Wirkung zunächst, anhand des Intervalls, in dem der input-String von allen gegebenen edits betroffen ist (\texttt{affected}), in einen unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen. -Da wir wissen welche Stelle im input-String vom ersten gegebenen edit betroffen ist können wir, anhand der Wirkung des Teilstücks bis zu jener Stelle, den betroffenen Suffix wiederum teilen. +Da wir wissen welche Stelle im input-String vom ersten gegebenen edit betroffen ist, können wir, anhand der Wirkung des Teilstücks bis zu jener Stelle, den betroffenen Suffix wiederum teilen. Die Wirkung ab der betroffenen Stelle im input-String können wir als Komposition der Wirkung der durch den edit betroffenen Stelle und derer aller Zeichen danach bestimmen. -Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes im output-String und des aus der gerade berechneten Wirkung zu bestimmen, wir bedienen uns hierzu dem Unix Standard-Diff-Algorithmus zwischen der ursprünglichen Ausgabe und dem Ergebnis der Iteration des Verfahrens auf alle gegebenen edits. +Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes im output-String und des aus der gerade berechneten Wirkung zu bestimmen. +Wir bedienen uns hierzu dem Unix Standard-Diff-Algorithmus zwischen der ursprünglichen Ausgabe und dem Ergebnis der Iteration des Verfahrens auf alle gegebenen edits. Für die asymmetrische edit-lens entgegen der DFST-Richtung $\Lleftarrow$ verwenden wir Breitensuche über die Zustände des DFST innerhalb des von allen gegeben edits betroffenen Intervalls: -Wir unterteilen zunächst das Komplement an den Grenzen des betroffenen Intervalls im output-String in drei Teile (durch Akkumulation der Elemente des Komplements bis die gewünschte Länge erreicht ist). +Wir unterteilen zunächst das Komplement an den Grenzen des betroffenen Intervalls im output-String in drei Teile durch Akkumulation der Elemente des Komplements bis die gewünschte Länge erreicht ist. Wir transformieren dann den DFST in einen FST, dessen Ausgabe wir mit \texttt{restrictOutput} auf das gewünschte Fragment einschränken, setzen als initialen Zustand des FST den Zustand am linken Rand des von den edits betroffenen Intervalls und akzeptieren jene Zustände, von denen aus das Komplement-Fragment ab dem rechten Rand des betroffenen Intervalls zu einem im ursprünglichen DFST akzeptierenden Zustand führt. -Wir verwenden dann gewöhnliche Breitensuche über die Zustände und Transitionen des soeben konstruierten FSTs um einen Lauffragment zu bestimmen, dass wir in das betroffene Intervall einsetzen können. -Hierbei sind sämtliche Randbedingungen (korrekte Ausgabe, Übereinstimmung an den Intervallgrenzen) bereits in den FST kodiert sodass wir nur noch prüfen müssen, dass der gefunde Lauf in einem akzeptierenden Zustand endet. +Wir verwenden dann gewöhnliche Breitensuche über die Zustände und Transitionen des soeben konstruierten FSTs, um einen Lauffragment zu bestimmen, das wir in das betroffene Intervall einsetzen können. +Hierbei sind sämtliche Randbedingungen (korrekte Ausgabe, Übereinstimmung an den Intervallgrenzen) bereits in den FST kodiert, sodass wir nur noch prüfen müssen, dass der gefundene Lauf in einem akzeptierenden Zustand endet. -Die input-edits können nun wiederum, unter Beachtung der Verschiebung der Indices um die Länge der Eingabe vor der linken Intervallgrenze, mit dem Unix Standard-Diff-Algorithmus berechnet werden. +Die input-edits können nun wiederum, unter Beachtung der Verschiebung der Indizes um die Länge der Eingabe vor der linken Intervallgrenze, mit dem Unix Standard-Diff-Algorithmus berechnet werden. \begin{comment} \begin{code} @@ -323,7 +324,7 @@ bfs outgoing predicate Wie auch im ursprünglichen DFST sind alle Zustände akzeptierend. Wir müssen nun bestimmen welche Zustände, unter $\text{act}_\text{R}$, zu einem akzeptierenden Zustand führen. - Da alle Zustände akzeptieren ist hier jeder Zustand geeignet. + Da alle Zustände akzeptieren, ist hier jeder Zustand geeignet. Wir müssen nun (vermöge Breitensuche) den kürzesten Pfad im Produkt-FST zwischen $Q_\text{L}$ und einem der Zustände finden, der unter $\text{act}_\text{R}$ zu einem akzeptierenden Zustand im ursprünglichen transducer führt. Der leere Pfad ist geeignet. @@ -339,7 +340,7 @@ bfs outgoing predicate \text{\tt \textbackslash n} \cdot e = \epsilon \end{equation*} Man beachte das $\text{\tt \textbackslash n}$ und $\epsilon$ hierbei die \emph{Eingaben} von $\text{act}_{e^\prime}$ bzw. $\text{act}_0$ sind. - Nach Behandlung der Indices ergibt sich $e = \rho_{80}$. + Nach Behandlung der Indizes ergibt sich $e = \rho_{80}$. Als neues Komplement erhalten wir: diff --git a/edit-lens/src/Control/Edit.lhs b/edit-lens/src/Control/Edit.lhs index 80c143a..98fa8c4 100644 --- a/edit-lens/src/Control/Edit.lhs +++ b/edit-lens/src/Control/Edit.lhs @@ -6,10 +6,10 @@ module Control.Edit \end{code} \end{comment} -Um das intuitive Verhalten von Änderungen auf Texten\footnote{Im folgenden \emph{edits}} und ihre interne algebraische Struktur zu fassen formalisieren wir sie als \emph{Moduln}: +Um das intuitive Verhalten von Änderungen auf Texten\footnote{Im folgenden \emph{edits}} und ihre interne algebraische Struktur zu fassen, formalisieren wir sie als \emph{Moduln}: \begin{defn}[Moduln] -Ein \emph{Modul} $M$ ist eine partielle Monoidwirkung zusammen mit einem schwach-initialen Element\footnote{Gemeint ist hier die übliche Definition von \emph{schwach-initial} aus der Kategorientheorie—ein Modul $M$ bildet eine Kategorie mit Objekten aus $\Dom M$ und Morphismen von $x$ nach $y$ den Monoidelementen $\partial x \in \partial M$ sodass $x \cdot \partial x = y$} (bzgl. der Monoidwirkung) auf dem Träger, d.h. $M = (\Dom M, \partial M, \init_M)$ ist ein Tupel aus einer Trägermenge $\Dom M$, einem Monoid $\partial M$ zusammen mit mit einer partiellen Funktion $\cdot \colon \Dom M \times \partial M \to \Dom$, die \emph{kompatibel} ist mit der Monoid-Struktur: +Ein \emph{Modul} $M$ ist eine partielle Monoidwirkung zusammen mit einem schwach-initialen Element\footnote{Gemeint ist hier die übliche Definition von \emph{schwach-initial} aus der Kategorientheorie—ein Modul $M$ bildet eine Kategorie mit Objekten aus $\Dom M$ und Morphismen von $x$ nach $y$ den Monoidelementen $\partial x \in \partial M$ sodass $x \cdot \partial x = y$} (bzgl. der Monoidwirkung) auf dem Träger. D.h. $M = (\Dom M, \partial M, \init_M)$ ist ein Tupel aus einer Trägermenge $\Dom M$, einem Monoid $\partial M$ zusammen mit einer partiellen Funktion $\cdot \colon \Dom M \times \partial M \to \Dom M$, die \emph{kompatibel} ist mit der Monoid-Struktur: \begin{itemize} \item $\forall m \in \Dom M \colon m \cdot 1_{\partial M} = m$ @@ -22,7 +22,7 @@ $$\forall m \in \Dom M \ \exists \partial m \in \partial M \colon m = \init_M \c Wir führen außerdem eine Abbildung $(\init_M \cdot)^{-1} \colon \Dom M \to \partial m$ ein, die ein $m$ auf ein arbiträr gewähltes $\partial m$ abbildet für das $\init_M \cdot \partial m = m$ gilt. -In Haskell charakterisieren wir Moduln über ihren Monoid, d.h. die Wahl des Monoiden \texttt{m} legt den Träger \texttt{Domain m}, die Wirkung \texttt{apply}, das initiale Element \texttt{init} und $(\init_M \cdot)^{-1}$ eindeutig fest\footnote{Betrachten wir mehrere Moduln über dem selben Träger (oder mit verschiedenen Wirkungen) führen wir neue, isomorphe Typen ein (\texttt{newtype}-Wrapper)}. +In Haskell charakterisieren wir Moduln über ihren Monoid, d.h. die Wahl des Monoiden \texttt{m} legt den Träger \texttt{Domain m}, die Wirkung \texttt{apply}, das initiale Element \texttt{init} und $(\init_M \cdot)^{-1}$ eindeutig fest\footnote{Betrachten wir mehrere Moduln über dem selben Träger (oder mit verschiedenen Wirkungen), führen wir neue, isomorphe Typen ein (\texttt{newtype}-Wrapper)}. Eine Repräsentierung als Typklasse bietet sich an: \begin{code} @@ -50,7 +50,7 @@ apply' md e = flip apply e =<< md \end{code} \end{defn} -Wir weichen von der originalen Definition von Moduln aus \cite{hofmann2012edit} darin ab, dass wir für das ausgezeichnete Element $\init_X$ des Trägers explizit (und konstruktiv\footnote{$(\init_M \cdot)^{-1}$}) fordern, dass es ein schwach-initiales Element bzgl. der Monoidwirkung sei. +Wir weichen von der originalen Definition von Moduln aus \cite{hofmann2012edit} ab, indem wir für das ausgezeichnete Element $\init_X$ des Trägers explizit (und konstruktiv\footnote{$(\init_M \cdot)^{-1}$}) fordern, dass es ein schwach-initiales Element bzgl. der Monoidwirkung sei. \begin{comment} \begin{defn}[Modulhomomorphismen] diff --git a/edit-lens/src/Control/Edit/String.lhs b/edit-lens/src/Control/Edit/String.lhs index c1411cf..f0ca588 100644 --- a/edit-lens/src/Control/Edit/String.lhs +++ b/edit-lens/src/Control/Edit/String.lhs @@ -24,7 +24,7 @@ import Data.Monoid \end{comment} \begin{defn}[Atomare edits of strings] -Wir betrachten, zur Einfachheit, ein minimiales Set von Edits auf Strings\footnote{Wie in der Konstruktion zum Longest Common Subsequence Problem}, bestehend nur aus Einfügung eines einzelnen Zeichens $\sigma$ an einer bestimmten Position $\iota_n(\sigma)$ und löschen des Zeichens an einer einzelnen Position $\rho_n$: +Wir betrachten zur Einfachheit ein minimiales Set von Edits auf Strings\footnote{Wie in der Konstruktion zum Longest Common Subsequence Problem} bestehend nur aus Einfügung eines einzelnen Zeichens $\sigma$ an einer bestimmten Position $\iota_n(\sigma)$ und löschen des Zeichens an einer einzelnen Position $\rho_n$: \begin{code} data StringEdit pos char = Insert { _sePos :: pos, _seInsertion :: char } @@ -38,7 +38,7 @@ data StringEdit pos char = Insert { _sePos :: pos, _seInsertion :: char } makeLenses ''StringEdit \end{code} -Atomare edits werden, als Liste, zu edits komponiert. +Atomare edits werden als Liste zu edits komponiert. Wir führen einen speziellen edit ein, der nicht-Anwendbarkeit der edits repräsentiert: \begin{code} data StringEdits pos char = StringEdits (Seq (StringEdit pos char)) diff --git a/edit-lens/src/Control/Edit/String/Affected.lhs b/edit-lens/src/Control/Edit/String/Affected.lhs index 851267b..15f73af 100644 --- a/edit-lens/src/Control/Edit/String/Affected.lhs +++ b/edit-lens/src/Control/Edit/String/Affected.lhs @@ -29,7 +29,7 @@ import Data.Maybe (fromMaybe, maybeToList, listToMaybe, catMaybes, isNothing, is \end{comment} Um eine obere Schranke an das von einer Serie von edits betroffene Intervall zu bestimmen ordnen wir zunächst jeder von mindestens einem atomaren edit betroffenen Position $n$ im Eingabe-Wort einen $\text{offset}_n = \text{\# deletions} - \text{\# inserts}$ zu. -Das gesuchte Intervall ist nun $(\text{minK}, \text{maxK})$, mit $\text{minK}$ der Position im Eingabe-Wort mit niedrigstem $\text{offset}$ und $\text{maxK}$ die Position im Eingabe-Wort mit höchstem $\text{offset}$, $\text{maxK}^\prime$, modifiziert um das Maximum aus $\{ 0 \} \cup \{ \text{maxK}_n \colon n \in \{ 0 \ldots \text{maxK}^\prime \} \}$ wobei $\text{maxK}_n = -1 \cdot (n + \text{offset}_n)$ an Position $n$ ist. +Das gesuchte Intervall ist nun $(\text{minK}, \text{maxK})$, mit $\text{minK}$ der Position im Eingabe-Wort mit niedrigstem $\text{offset}$ und $\text{maxK}$ die Position im Eingabe-Wort mit höchstem $\text{offset}$ $\text{maxK}^\prime$ modifiziert um das Maximum aus $\{ 0 \} \cup \{ \text{maxK}_n \colon n \in \{ 0 \ldots \text{maxK}^\prime \} \}$ wobei $\text{maxK}_n = -1 \cdot (n + \text{offset}_n)$ an Position $n$ ist. \begin{code} affected :: forall char. StringEdits Natural char -> Maybe (Interval Natural) diff --git a/edit-lens/src/Control/FST.lhs b/edit-lens/src/Control/FST.lhs index 9cc7524..165f247 100644 --- a/edit-lens/src/Control/FST.lhs +++ b/edit-lens/src/Control/FST.lhs @@ -47,12 +47,12 @@ import Text.Dot \end{comment} \begin{defn}[Finite State Transducers] -Unter einem \emph{finite state transducer} verstehen wir ein 6-Tupel $(\Sigma, \Delta, Q, I, F, E)$ mit $\Sigma$ dem endlichen Eingabe-Alphabet, $\Delta$ dem endlichen Ausgabe-Alphabet, $Q$ einer endlichen Menge an Zuständen, $I \subset Q$ der Menge von initialen Zuständen, $F \subset Q$ der Menge von akzeptierenden Endzuständen, und $E \subset Q \times (\Sigma \cup \{ \epsilon \}) \times (\Delta \cup \{ \epsilon \}) \times Q$ der Transitionsrelation. +Unter einem \emph{finite state transducer} verstehen wir ein 6-Tupel $(\Sigma, \Delta, Q, I, F, E)$ mit $\Sigma$ dem endlichen Eingabe-Alphabet, $\Delta$ dem endlichen Ausgabe-Alphabet, $Q$ einer endlichen Menge an Zuständen, $I \subset Q$ der Menge von initialen Zuständen, $F \subset Q$ der Menge von akzeptierenden Endzuständen und $E \subset Q \times (\Sigma \cup \{ \epsilon \}) \times (\Delta \cup \{ \epsilon \}) \times Q$ der Transitionsrelation. -Semantisch ist ein finite state transducer ein endlicher Automat erweitert um die Fähigkeit bei Zustandsübergängen ein Symbol aus seinem Ausgabe-Alphabet an ein Ausgabe-Wort anzuhängen. +Semantisch ist ein finite state transducer ein endlicher Automat, erweitert um die Fähigkeit bei Zustandsübergängen ein Symbol aus seinem Ausgabe-Alphabet an ein Ausgabe-Wort anzuhängen (Siehe Definition \ref{defn:fst-eval}). In Haskell lockern wir die Anforderung, dass die Ein- und Ausgabe-Alphabete endlich sein müssen und annotieren sie nur im Typsystem. -Zudem speichern wir die Transitionsrelation als multimap um effiziente lookups von Zustand-Eingabe-Paaren zu ermöglichen. +Zudem speichern wir die Transitionsrelation als multimap, um effiziente lookups von Zustand-Eingabe-Paaren zu ermöglichen. \begin{code} data FST state input output = FST @@ -64,7 +64,7 @@ data FST state input output = FST \end{defn} \begin{eg} \label{eg:linebreak} - Als wiederkehrendes Beispiel betrachten wir einen Transducer $L_{80} = (\Sigma, \Delta, Q, I, F, E)$, der für ein beliebiges Alphabet $\Sigma \supseteq \{ \text{\tt ' '}, \text{\tt \textbackslash n} \}$ durch Umwandlung zwischen Leerzeichen und Zeilenumbrüchen sicherstellt, dass jede Zeile des Ausgabetextes möglichst wenige aber mindestens 80 Zeichen enthält, und nur an Wortgrenzen umbricht: + Als wiederkehrendes Beispiel betrachten wir einen Transducer $L_{80} = (\Sigma, \Delta, Q, I, F, E)$, der für ein beliebiges Alphabet $\Sigma \supseteq \{ \text{\tt ' '}, \text{\tt \textbackslash n} \}$ durch Umwandlung zwischen Leerzeichen und Zeilenumbrüchen sicherstellt, dass jede Zeile des Ausgabetextes möglichst wenige, aber mindestens 80 Zeichen enthält und nur an Wortgrenzen umbricht: \begin{align*} \Delta & = \Sigma \\ @@ -103,7 +103,7 @@ data FST state input output = FST \draw[-] (rest)--(i.north); \draw[-] (rest)--(si.west); \end{tikzpicture} - \caption{\label{fig:linebreak} Ein Transducer der, durch Übersetzung zwischen Leerzeichen und Zeilenumbrüchen, sicher stellt, dass jede Zeile eines Texts mindestens 80 Zeichen hat} + \caption{\label{fig:linebreak} Ein Transducer der durch Übersetzung zwischen Leerzeichen und Zeilenumbrüchen sicher stellt, dass jede Zeile eines Texts mindestens 80 Zeichen hat} \end{figure} \end{eg} @@ -131,8 +131,8 @@ instance (Show state, Show input, Show output, Ord state, Ord input, Ord output) \end{code} \end{comment} -\begin{defn}[Auswertung von FSTs] -Wir definieren die \emph{Auswertung} von finite state transducers induktiv indem wir zunächst angeben wie ein einzelner Auswertungs-Schritt erfolgt. +\begin{defn}[Auswertung von FSTs] \label{defn:fst-eval} +Wir definieren die \emph{Auswertung} von finite state transducers induktiv, indem wir zunächst angeben, wie ein einzelner Auswertungs-Schritt erfolgt. Hierzu kommentieren wir die Haskell-Implementierung eines Auswertungs-Schritts. Notwendigerweise ist die Auswertung eines FSTs nicht deterministisch, wir produzieren daher eine Liste von möglichen Resultaten in keiner besonderen Reihenfolge. @@ -145,7 +145,7 @@ step :: forall input output state. (Ord input, Ord output, Ord state) -> [(Maybe input, state, Maybe output)] -- ^ Tuples of unconsumed input, next state, and produced output step FST{..} Nothing inS = (\s -> (inS, s, Nothing)) <$> Set.toList stInitial \end{code} -Ist kein vorheriger Schritt erfolgt so wählen wir einen initialen Zustand, konsumieren keine Eingabe, und produzieren keine Ausgabe. +Ist kein vorheriger Schritt erfolgt, so wählen wir einen initialen Zustand, konsumieren keine Eingabe und produzieren keine Ausgabe. \begin{code} step FST{..} (Just c) inS = let @@ -154,7 +154,7 @@ step FST{..} (Just c) inS = let in Set.toList $ Set.map (\(n, mOut) -> (Nothing, n, mOut)) consuming `Set.union` Set.map (\(n, mOut) -> (inS, n, mOut)) unconsuming \end{code} Ansonsten wählen wir einen Eintrag aus der Transitionstabelle für den aktuellen Zustand, der entweder keine oder die gegebene Eingabe konsumiert. -Im Ergebnis geben wir den nächsten Zustand, die Ausgabe aus der Transitionstabelle, und ob die Eingabe konsumiert wurde an. +Im Ergebnis geben wir den nächsten Zustand, die Ausgabe aus der Transitionstabelle und ob die Eingabe konsumiert wurde, an. \begin{code} runFST' :: forall input output state. (Ord input, Ord output, Ord state) @@ -199,9 +199,8 @@ akzeptierenden Endzustände liegt. \end{comment} \end{defn} -Es ist gelegentlich nützlich nur die möglichen Ausgaben eines FST auf gegebener -Eingabe zu bestimmen, wir führen eine Hilfsfunktion auf Basis von -{\ttfamily runFST'} ein: +Es ist gelegentlich nützlich nur die möglichen Ausgaben eines FST auf gegebener Eingabe zu bestimmen. +Wir führen eine Hilfsfunktion auf Basis von {\ttfamily runFST'} ein: \begin{code} runFST :: forall input output state. (Ord input, Ord output, Ord state) => FST state input output -> Seq input -> [Seq output] @@ -216,14 +215,14 @@ runFST = fmap (map $ catMaybes . fmap (view _2) . view _2) . runFST' \end{comment} Wir können das Produkt zweier FSTs definieren. -Intuitiv wollen wir beide FSTs gleichzeitig ausführen und dabei sicherstellen, dass Ein- und Ausgabe der FSTs übereinstimmen\footnote{Da wir $\epsilon$-Transitionen in FSTs erlauben müssen wir uns festlegen wann eine $\epsilon$-Transition übereinstimmt mit einer anderen Transition. Wir definieren, dass $\epsilon$ als Eingabe ausschließlich mit $\epsilon$ übereinstimmt.}. +Intuitiv wollen wir beide FSTs gleichzeitig ausführen und dabei sicherstellen, dass Ein- und Ausgabe der FSTs übereinstimmen\footnote{Da wir $\epsilon$-Transitionen in FSTs erlauben, müssen wir uns festlegen, wann eine $\epsilon$-Transition übereinstimmt mit einer anderen Transition. Wir definieren, dass $\epsilon$ als Eingabe ausschließlich mit $\epsilon$ übereinstimmt.}. Hierfür berechnen wir das Graphen-Produkt der FSTs: \begin{defn}[FST-Produkt] Gegeben zwei finite state transducer $T = (\Sigma, \Delta, Q, I, F, E)$ und $T^\prime = (\Sigma^\prime, \Delta^\prime, Q^\prime, I^\prime, F^\prime, E^\prime)$ nennen wir $T^\times = (\Sigma^\times, \Delta^\times, Q^\times, I^\times, F^\times, E^\times)$ das Produkt $T^\times = T \times T^\prime$ von $T$ und $T^\prime$. - $T^\times$ bestimmt sich als das Graphenprodukt der beiden, die FSTs unterliegenden, Graphen wobei wir die Zustandsübergänge als Kanten mit Gewichten aus dem Boolschen Semiring auffassen: + $T^\times$ wird bestimmt als das Graphenprodukt der beiden die FSTs unterliegenden Graphen wobei wir die Zustandsübergänge als Kanten mit Gewichten aus dem Boolschen Semiring auffassen: \begin{align*} \Sigma^\times & = \Sigma \cap \Sigma^\prime \\ @@ -271,7 +270,7 @@ productFST fst1 fst2 = FST Es ist später erforderlich einen FST derart einzuschränken, dass er eine gegebene Ausgabe produziert. Hierzu nehmen wir das FST-Produkt mit einem FST, der, ungeachtet der Eingabe, immer die gewünschte Ausgabe produziert. -Da die Ausgaben der beiden FSTs übereinstimmen müssen produziert das Produkt mit einem derartigen FST (solange dessen Ausgabe in keinem Sinne von der Eingabe abhängt) die gewünschte Ausgabe. +Da die Ausgaben der beiden FSTs übereinstimmen müssen, produziert das Produkt mit einem derartigen FST (solange dessen Ausgabe in keinem Sinne von der Eingabe abhängt) die gewünschte Ausgabe. Zur Konstruktion eines derartigen \emph{Wort-FST}s nehmen wir Indizes im Ausgabe-Wort (natürliche Zahlen) als Zustände. Übergänge sind immer entweder der Form $n \rightarrow \text{succ}(n)$, konsumieren keine Eingabe ($\epsilon$) und produzieren als Ausgabe das Zeichen am Index $n$ im Ausgabe-Wort, oder der Form $n \overset{(\sigma, \epsilon)}{\rightarrow} n$, für jedes Eingabesymbol $\sigma$ (um die Unabhängigkeit von der Eingabe sicherzustellen). @@ -335,7 +334,7 @@ wordFST inps outs = FST \end{figure} \end{eg} -Da \texttt{wordFST} zur Konstruktion eine komprehensive Menge aller Eingabesymbole benötigt verwenden wir im folgenden eine optimierte Variante des Produkts mit einem Wort-FST. +Da \texttt{wordFST} zur Konstruktion eine komprehensive Menge aller Eingabesymbole benötigt, verwenden wir im Folgenden eine optimierte Variante des Produkts mit einem Wort-FST. \begin{code} restrictOutput :: forall state input output. (Ord state, Ord input, Ord output) => Seq output -> FST state input output -> FST (Natural, state) input output @@ -381,7 +380,7 @@ restrictOutput :: forall state input output. (Ord state, Ord input, Ord output) \begin{rem} Es ist bemerkenswert, dass in Beispiel \ref{eg:l80timesw100} die zirkuläre Struktur von $L_{80}$ durch das Produkt mit einem Wort verloren geht. - I.\@A.\@ ist das Produkt eines beliebigen FST mit einem Wort-FST zwar nicht azyklisch, erbt jedoch die lineare Struktur des Wort-FST in dem Sinne, dass Fortschritt in Richtung der akzeptierenden Zustände nur möglich ist indem der $(i, \sigma, w_i, i + 1)$-Klasse von Transitionen des Wort-FSTs gefolgt wird. + I.\@A.\@ ist das Produkt eines beliebigen FST mit einem Wort-FST zwar nicht azyklisch, erbt jedoch die lineare Struktur des Wort-FST in dem Sinne, dass Fortschritt in Richtung der akzeptierenden Zustände nur möglich ist, indem der $(i, \sigma, w_i, i + 1)$-Klasse von Transitionen des Wort-FSTs gefolgt wird. \end{rem} \begin{comment} diff --git a/edit-lens/src/Control/FST/Lens.tex b/edit-lens/src/Control/FST/Lens.tex index 31af317..7e9e9e3 100644 --- a/edit-lens/src/Control/FST/Lens.tex +++ b/edit-lens/src/Control/FST/Lens.tex @@ -1,4 +1,4 @@ -Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nondeterminische finite state transducers anwenden lässt. +Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nicht determinische finite state transducers anwenden lässt. Eine natürlich Erweiterung von \texttt{DFSTAction} wäre: \begin{lstlisting}[language=Haskell] @@ -9,7 +9,7 @@ data FSTAction state input output = FSTAction \end{lstlisting} wobei die Liste aller möglichen output-Strings in der rechten Seite von \texttt{runFSTAction} in aller Regel unendlich ist. -$\Rrightarrow$ würde sich notwendigerweise arbiträr auf einen der möglichen output-Strings festlegen aber ansonsten wohl identisch zum DFST-Fall implementieren lassen. +$\Rrightarrow$ würde sich notwendigerweise arbiträr auf einen der möglichen output-Strings festlegen, aber ansonsten wohl identisch zum DFST-Fall implementieren lassen. $\Lleftarrow$ basiert fundamental darauf im Komplement anhand der erzeugten output-Strings zu suchen (um das betroffene Intervall im output-String auf das Komplement zu übertragen). Um sicher zu stellen, dass jene Suche immer terminiert, müsste die Aufzählung der i.A. unendlich vielen zulässigen output-Strings in \texttt{FSTAction} geschickt gewählt sein. diff --git a/edit-lens/src/Control/Lens/Edit.lhs b/edit-lens/src/Control/Lens/Edit.lhs index 5cf8662..84216bd 100644 --- a/edit-lens/src/Control/Lens/Edit.lhs +++ b/edit-lens/src/Control/Lens/Edit.lhs @@ -12,7 +12,7 @@ import Control.Edit \end{comment} \begin{defn}[Zustandsbehaftete Monoidhomomorphismen] -Gegeben eine Menge $C$ von \emph{Komplementen} und zwei Monoiden $M$ und $N$ nennen wir eine partielle Funktion $\psi \colon C \times M \to C \times N$ einen \emph{zustandsbehafteten Monoidhomomorphismus} wenn sie den folgenden Ansprüchen genügt: +Gegeben eine Menge $C$ von \emph{Komplementen} und zwei Monoiden $M$ und $N$ nennen wir eine partielle Funktion $\psi \colon C \times M \to C \times N$ einen \emph{zustandsbehafteten Monoidhomomorphismus}, wenn sie den folgenden Ansprüchen genügt: \begin{itemize} \item $\forall c \in C \colon \psi(1_M, c) = (1_N, c)$ @@ -28,7 +28,7 @@ type StateMonoidHom s m n = (s, m) -> (s, n) \end{defn} \begin{defn}[edit-lenses] -Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$ und $N$ aus zwei zustandsbehafteten Monoidhomomorphismen $\Rrightarrow \colon C \times \partial M \to C \times \partial N$ und $\Lleftarrow \colon C \times \partial N \to C \times \partial M$, mit kompatiblem Komplement $C$, einem ausgezeichneten Element $\ground_C \in C$ und einer \emph{Konsistenzrelation} $K \subset \Dom M \times C \times \Dom N$ sodass gilt: +Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$ und $N$ aus zwei zustandsbehafteten Monoidhomomorphismen $\Rrightarrow \colon C \times \partial M \to C \times \partial N$ und $\Lleftarrow \colon C \times \partial N \to C \times \partial M$, mit kompatiblem Komplement $C$, einem ausgezeichneten Element $\ground_C \in C$ und einer \emph{Konsistenzrelation} $K \subset \Dom M \times C \times \Dom N$, sodass gilt: \begin{itemize} \item $(\init_M, \ground_C, \init_N) \in K$ @@ -43,7 +43,7 @@ Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$ Wir schreiben auch nur \emph{edit-lens} für den symmetrischen Fall\footnote{Für den asymmetrischen Fall siehe \cite{johnson2016unifying}}. -In Haskell erwähnen wir die Konsistenzrelation nicht in der Erwartung, dass $\Rrightarrow$ und $\Lleftarrow$ nur auf konsistente Zustände angewandt werden (und somit auch entweder einen konsistenten Zustand erzeugen oder nicht definiert sind): +In Haskell erwähnen wir die Konsistenzrelation nicht, in der Erwartung, dass $\Rrightarrow$ und $\Lleftarrow$ nur auf konsistente Zustände angewandt werden (und somit auch entweder einen konsistenten Zustand erzeugen oder nicht definiert sind): \begin{code} data EditLens c m n where @@ -67,12 +67,12 @@ instance (Module m, Module n) => HasEditLens (EditLens c m n) m n where \end{code} \end{defn} -\subsection{Kompatibilität mit bestehenden lens frameworks} +\subsection{Kompatibilität mit bestehenden lens Frameworks} Das einschlägige bestehende lens framework \cite{lens} konstruiert seine Linsen à la \citeauthor{laarhoven} wie folgt: \begin{defn}[lenses à la Laarhoven] -Für Typen $n$ und $m$ ist eine \emph{lens} $\ell$ von $n$ in $m$ eine Abbildung\footnote{Gdw. die betrachtete Linse einen Isomorphismus kodiert wird auch über den verwendeten Profunktor anstatt $\to$ quantifiziert} folgender Struktur: +Für Typen $n$ und $m$ ist eine \emph{lens} $\ell$ von $n$ in $m$ eine Abbildung\footnote{Gdw. die betrachtete Linse einen Isomorphismus kodiert, wird auch über den verwendeten Profunktor anstatt $\to$ quantifiziert} folgender Struktur: $$ \forall f \, \text{Funktor} \colon \left ( \ell \colon \left ( m \to f(m) \right ) \to \left ( n \to f(n) \right ) \right )$$ @@ -80,7 +80,7 @@ Durch geschickte Wahl des Funktors\footnote{\texttt{Const m} bzw. \texttt{Identi \end{defn} Es liegt nun nahe $\nearrow \colon (m \to m) \to (n \to n)$ mit $\Rrightarrow \colon \partial m \to \partial n$ zu identifizieren. -Und in der Tat, eine Funktion $\text{map} \colon (o \to o) \to \partial o$ für $o \in \{ m, n \}$ würde van Laarhoven-lenses in edit-lenses einbetten. +In der Tat, eine Funktion $\text{map} \colon (o \to o) \to \partial o$ für $o \in \{ m, n \}$ würde van Laarhoven-lenses in edit-lenses einbetten. Die charakteristische Eigenschaft der Betrachtung als edit-lens, nämlich die algebraische Struktur von $\partial o$, würde hierbei jedoch notwendigerweise verloren gehen. Wegen diesem Argument haben wir entschieden keine Komponierbarkeit (durch $\text{id} \colon a \to a$ und $\circ \colon (b \to c) \to (a \to b) \to (a \to c)$, wie in \cite{lens}) von edit-lenses mit van Laarhoven-lenses anzustreben. diff --git a/implementation.tex b/implementation.tex index 3a68e04..26ee2c7 100644 --- a/implementation.tex +++ b/implementation.tex @@ -1,7 +1,8 @@ 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. +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} @@ -12,7 +13,7 @@ Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sekt \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 + 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] @@ -46,11 +47,11 @@ Die Module innerhalb von \texttt{edit-lens} entsprechen im wesentlichen den Sekt \begin{figure}[h] \begin{center} \includegraphics{screenshot} - \caption{Der interaktive Editor (im Modus \texttt{json-newl}) nach import einer kleinen JSON-Datei} + \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: +Der interaktive Editor kann von der Befehlseingabe gestartet werden wie folgt: \begin{lstlisting}[language=bash] $ stack build $ stack exec interact @@ -88,4 +89,10 @@ Nach Auswahl wird der Inhalt der Datei am Cursor eingefügt. 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 ca. einen Faktor 200 schneller als das komplett neue Parsen einer Datei (ca. 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}). diff --git a/intro.tex b/intro.tex index 43d909d..56d1ef3 100644 --- a/intro.tex +++ b/intro.tex @@ -1,18 +1,18 @@ -\subsubsection{Motivation} +\subsection{Motivation} -Unter einem inkrementellen Parser \cite{ghezzi1979incremental} verstehen wir ein Programm, das, nach einem initialen Parsevorgang, gegeben eine Spezifikation einer Änderung der textuellen Eingabe i.A. schneller ein neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre (gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe). +Unter einem inkrementellen Parser \cite{ghezzi1979incremental} verstehen wir ein Programm, das, nach einem initialen Parsevorgang, gegeben eine Spezifikation einer Änderung der textuellen Eingabe i.A. schneller, gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe, ein neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre. -Es ist nun prinzipiell wünschenswert die algebraische Struktur derartiger Klassen von Programmen zu untersuchen, mit dem Ziel neue Parser mit generischen Mitteln aus bereits Bekannten konstruieren zu können. +Es ist nun prinzipiell wünschenswert die algebraische Struktur derartiger Klassen von Programmen zu untersuchen mit dem Ziel, neue Parser mit generischen Mitteln aus bereits Bekannten konstruieren zu können. In dieser Arbeit versuchen wir, anhand von finite state transducern als Spezialfall, inkrementelle Parser und die unterliegenden edits mit neuerer algebraischer Struktur, edit-lenses \cite{hofmann2012edit}, zu versehen um Komponierbarkeit zu vereinfachen. -Vor allem versuchen wir somit zu demonstrieren, dass sich bekannte Klassen von Programmen, unter Erhalt ihrer vollen Struktur, als edit-lenses auffassen lassen, auch wenn die Darstellung als konventionelle funktionale Linse unzufriedenstellend wäre. +Vor Allem versuchen wir somit zu demonstrieren, dass sich bekannte Klassen von Programmen unter Erhalt ihrer vollen Struktur als edit-lenses auffassen lassen, auch dann, wenn die Darstellung als konventionelle funktionale Linse unzufriedenstellend wäre. -\subsubsection{Inhalt} +\subsection{Inhalt} -Wir stellen in Abschnitt \ref{edit-lenses} die Definitionen und Konstruktion von edit-lenses aus \cite{hofmann2012edit} vor und diskutieren kurz die Kompatibilität unserer Implementierung und edit-lenses im Allgemeinen mit etablierten frameworks für funktionale Linsen in Haskell. +Wir stellen in Abschnitt \ref{edit-lenses} die Definitionen und Konstruktion von edit-lenses aus \cite{hofmann2012edit} vor und diskutieren kurz die Kompatibilität unserer Implementierung und edit-lenses im Allgemeinen mit etablierten Frameworks für funktionale Linsen in Haskell. In Abschnitt \ref{finite-state-transducers} präsentieren wir eine etablierte Version von finite state transducern, für die folgenden Teile relevante Konstruktionen darauf und einige assoziierte Beispiele. -Abschnitt \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} beschreibt eine Methode beliebige deterministische finite state transducers als edit-lenses aufzufassen und stellt somit eine non-triviale Anwendung der Methoden und Konzepte aus \cite{hofmann2012edit} dar. -In Abschnitt \ref{ausblick-edit-lenses-fuxfcr-non-determinische-finite-state-transducers} stellen wir kurz einen Ansatz dar unsere Konstruktion aus \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} auch auf non-deterministische finite state transducer zu erweitern. +Abschnitt \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} beschreibt eine Methode, beliebige deterministische finite state transducers als edit-lenses aufzufassen und stellt somit eine nicht triviale Anwendung der Methoden und Konzepte aus \cite{hofmann2012edit} dar. +In Abschnitt \ref{ausblick-edit-lenses-fuxfcr-non-determinische-finite-state-transducers} stellen wir kurz einen Ansatz vor, unsere Konstruktion aus \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} auch auf nicht-deterministische finite state transducers zu erweitern. In Abschnitt \ref{implementierung} kommentieren wir den Implementierungsprozess der Arbeit und die Schlüsse, die wir aus der Implementierung als solcher ziehen konnten. Abschnitt \ref{ausblick-anwendbarkeit-der-implementierung-auf-andere-parser} beschreibt kurz wie sich das dargestellte Verfahren auf andere Sorten von Parsern anwenden ließe. @@ -43,22 +43,22 @@ Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ei \begin{description} % TODO: more \item[1979] \cite{ghezzi1979incremental} präsentieren, in einer der ersten Arbeiten zu dem Thema, einen Ansatz zum inkrementellen Parsen von deterministischen und kontextfreien Sprachen basierend auf dem $LR$-Ansatz. - \item[1992] \cite{hedin1992incremental} präsentieren einen Formalismus zur inkrementellen \emph{semantischen} Analyse (d.h. das Versehen des Syntax-Baums eines Programms mit Attributen wie z.B. Typen) basierend auf (modifizierten) Attribut-Grammatiken. + \item[1992] \cite{hedin1992incremental} präsentieren einen Formalismus zur inkrementellen \emph{semantischen} Analyse\footnote{Das Versehen des Syntax-Baums eines Programms mit Attributen wie z.B. Typen} basierend auf (modifizierten) Attribut-Grammatiken. \item[1997] \cite{wagner1997general} stellen einen Algorithmus zur inkrementellen lexikalischen Analyse (tokenizing) der auf den selben Spezifikationen arbeiten kann wie die UNIX-Tools \texttt{lex} und \texttt{flex}. - \item[1998] \cite{wagner1998efficient} stellen neue, Laufzeit- und Speicher-optimale, Methoden zur Konstruktion inkrementeller Parser auf Basis beliebiger $LR(k)$-Grammatiken vor. - \item[2001] \cite{swierstra2001combinator} demonstriert den Nutzen Kombinator-basierter Parser-Konstruktion in der Praxis - \item[2004] \cite{hu2004programmable} spezifizieren eine algebraisch strukturierte Sprache für bidirektionale Baum-Transformationen unter einer programmierbaren Konsistenzrelation mit Blick auf direkte Anwendung im Editieren von bestehenden Baum-Dokumenten - \item[2007] \cite{foster2007combinators} präsentieren sowohl eine Sprache bidirektionaler Baum-Transformationen als konventionelle funktionale Linsen im Speziellen, als auch mathematische Resultate für funktionale Linsen und Sammlungen davon im Allgemeinen. - Auch enthalten ist eine nützliche Klassifikation und ein historischer Überblick diverser bidirektionalen Programmiertechniken. - \item[2008] Analog zur Sprache bidirektionaler Baum-Transformation aus \cite{foster2007combinators} stellen \cite{bohannon2008boomerang} eine Sprache für semi-strukturierten Text (als Serie von vertauschbaren Schlüssel-Wert-Assoziationen) vor - \item[2009] \cite{bernardy2009lazy} implementieren, im Rahmen der Arbeit am Text-Editor Yi, eine Kombinator-basierte Programmbibliothek zum inkrementellen Parsen basierend auf lazy evaluation und aggressivem Caching in Haskell + \item[1998] \cite{wagner1998efficient} stellen neue Laufzeit- und Speicher-optimale Methoden zur Konstruktion inkrementeller Parser auf Basis beliebiger $LR(k)$-Grammatiken vor. + \item[2001] \cite{swierstra2001combinator} demonstriert den Nutzen Kombinator-basierter Parser-Konstruktion in der Praxis. + \item[2004] \cite{hu2004programmable} spezifizieren eine algebraisch strukturierte Sprache für bidirektionale Baum-Transformationen unter einer programmierbaren Konsistenzrelation mit Blick auf direkte Anwendung im Editieren von bestehenden Baum-Dokumenten. + \item[2007] \cite{foster2007combinators} präsentieren sowohl eine Sprache bidirektionaler Baum-Transformationen als konventionelle funktionale Linsen im Speziellen, als auch mathematische Resultate für funktionale Linsen und Sammlungen dieser im Allgemeinen. + Auch enthalten ist eine nützliche Klassifikation und ein historischer Überblick diverser bidirektionaler Programmiertechniken. + \item[2008] Analog zur Sprache bidirektionaler Baum-Transformation aus \cite{foster2007combinators}, stellen \cite{bohannon2008boomerang} eine Sprache für semi-strukturierten Text als Serie von vertauschbaren Schlüssel-Wert-Assoziationen vor. + \item[2009] \cite{bernardy2009lazy} implementieren, im Rahmen der Arbeit am Text-Editor Yi, eine Kombinator-basierte Programmbibliothek zum inkrementellen Parsen basierend auf lazy evaluation und aggressivem Caching in Haskell. \item[2011] \cite{hofmann2011symmetric} definieren symmetrische \emph{set-based}-lenses (funktionale Linsen im konventionellen Sinn), d.h. ohne strukturierte edits. Es wird auch die umfangreiche algebraische Struktur symmetrischer Linsen besprochen. - Vieles hiervon vererbt sich direkt auf edit-lenses als Spezialfall symmetrischer Linsen. + Vieles hiervon lassen sich direkt auf edit-lenses als Spezialfall symmetrischer Linsen vererben. \item[2012] \cite{hofmann2012edit} definieren edit-lenses. In Abgrenzung zu bestehenden Formalismen symmetrischer funktionaler Linsen arbeiten edit-lenses ausschließlich auf algebraisch strukturierten edit-Sprachen, was sie besonders attraktiv macht. \item[2013] \cite{hofmann2013edit} stellen eine generelle edit-Sprache (zur Verwendung mit und basierend auf edit-lenses) für eine weite Klasse von container-Datentypen (Listen, Bäume, Graphen, ...) vor - \item[2014] \cite{zaytsev2014parsing} geben einen nützlichen Überblick über die, historisch inkonsistente, Terminologie und Konzepte im Zusammenhang mit Parsing + \item[2014] \cite{zaytsev2014parsing} geben einen nützlichen Überblick über die historisch inkonsistente Terminologie und Konzepte im Zusammenhang mit Parsing. \item[2016] \cite{johnson2016unifying} betrachten Zusammenhänge diverser Klassen funktionaler Linsen (inkl. edit-lenses) und geben dabei einen umfangreichen Überblick über die bestehende Forschung. Ein relevantes Resultat ist hierbei ein Begriff von asymmetrischen edit-lenses kompatibel mit dem symmetrischen Fall. \end{description} @@ -68,16 +68,19 @@ Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ei Obwohl wir detailliertere Definitionen der folgenden Konzepte im Laufe der Arbeit geben, ist es dennoch nützlich vorab die Bedeutung der verwendeten Begriffe kurz anzuschneiden: \begin{description} - \item[FST] \emph{Finite-State-Transducer} sind endliche Automaten, die bei jedem Zustandsübergang die Möglichkeit haben ein Zeichen an eine sich akkumulierende Ausgabe anzuhängen - \item[DFST] \emph{Deterministic Finite-State-Transducer} sind FSTs bei denen für jeden Zustand jedes gelesene Zeichen maximal einen Zustandsübergang zulässt + \item[FST] \emph{Finite-State-Transducer} sind endliche Automaten, die bei jedem Zustandsübergang die Möglichkeit haben ein Zeichen an eine sich akkumulierende Ausgabe anzuhängen. + \item[DFST] \emph{Deterministic Finite-State-Transducer} sind FSTs bei denen für jeden Zustand jedes gelesene Zeichen maximal einen Zustandsübergang zulässt. \item[Monoid] \emph{Monoiden} sind algebraisch zwischen Halbgruppen und Gruppen angesiedelt. Wir sagen eine Menge hat Monoidstruktur bzgl. einer zweistelligen Verknüpfung auf jener Menge, wenn sie ein neutrales Element enthält und die Verknüpfung assoziativ ist. \item[Moduln & edits] \emph{Moduln} verknüpfen eine Trägermenge mit einer Menge von \emph{edits} (mit monoidaler Struktur) auf jener Menge. Edits beschreiben jeweils eine partielle Abbildung innerhalb der Trägermenge. \item[Funktionale Linsen] Eine \emph{Funktionale Linse} von $s$ in $a$ in der üblichen Definition (\emph{set-based}) ist ein Paar von Abbildungen $\searrow \colon s \to a$ und $\nearrow \colon (a \to a) \to (s \to s)$ mit umfangreicher algebraischer Struktur, die die Komposition komplexer Linsen aus Einfacheren ermöglicht. Wir finden es hilfreich von einer Projektion ($\searrow$) und einem \emph{edit-Propagator} ($\nearrow$) zu sprechen. - \item[Van-Laarhoven Linsen] In \cite{laarhoven} wurde eine Darstellung als eine (über einen Funktor parametrisierte) Funktion dargelegt, die unter anderem auch die soeben beschriebenen funktionalen Linsen einbetten kann - \item[edit-lenses] \emph{edit-lenses} verknüpfen zwei Moduln-Trägermengen indem sie edits des einen Modul in die des Anderen übersetzen. + \item[Van-Laarhoven Linsen] In \cite{laarhoven} wurde eine Darstellung als eine über einen Funktor parametrisierte Funktion dargelegt, die unter anderem auch die soeben beschriebenen funktionalen Linsen einbetten kann. + \item[edit-lenses] \emph{edit-lenses} verknüpfen zwei Moduln-Trägermengen indem sie edits des einen Moduls in die des Anderen übersetzen. Hierbei wird ein, mit den jeweiligen Elementen der Trägermengen konsistenter, unterliegender Zustand, das \emph{Komplement} der edit-lens, gewahrt. Intuitiv speichert das Komplement genau jene Information, die nicht in beiden Darstellungen vorkommt. + \item[Parser] \emph{Parser} sind Programme, die einen Text (als Liste von Symbolen $\Sigma^\star$ aus einem Alphabet $\Sigma$) Seiteneffekt-frei verarbeiten $\Sigma^\star \to a$. + \item[Inkrementelle Parser] \emph{Inkrementelle Parser} sind Programme, die sowohl in der Lage sind als Parser zu agieren $\Sigma^\star \to a$, als auch, nach einem vorhergehenden konventionellen Parsevorgang, eine Änderung am Eingabetext in eine Änderung am Ergebnis zu übersetzen $\partial \left ( \Sigma^\star \right ) \to \partial a$. + Hierbei muss die Laufzeitcharakteristik i.A. besser sein als die Änderung auf die alte Eingabe anzuwenden und schlichtweg neu zu Parsen. \end{description} diff --git a/org.tex b/org.tex index d0c6ed4..38f26d4 100644 --- a/org.tex +++ b/org.tex @@ -1,16 +1,10 @@ -\pagebreak - -Diese Arbeit ist entstanden unter Betreuung durch Stephan Barth. - -Verantwortliche Hochschullehrer sind \textdagger Prof. Martin Hoffmann PhD und Dr. Steffen Jost. - -\vfill +\section*{Erklärung der Eigenständigkeit} \noindent Ich erkläre hiermit, dass ich die vorliegende Arbeit -selbstständig angefertigt, alle Zitate als solche kenntlich gemacht +selbstständig angefertigt, alle Zitate als solche kenntlich gemacht, sowie alle benutzten Quellen und Hilfsmittel angegeben habe. -\bigskip +\vspace{1cm} \makebox[.5\linewidth][r]{}{\xleaders\hbox to .2em{\d{}}\hfill\d{}}\smallskip \\ \hspace*{.5\linewidth}Gregor Kleen \\ @@ -19,5 +13,3 @@ sowie alle benutzten Quellen und Hilfsmittel angegeben habe. %% \bigskip\noindent München, \today %% \vspace{4ex}\noindent\makebox[7cm]{\dotfill} - -\pagebreak diff --git a/sigillum.pdf b/sigillum.pdf new file mode 100644 index 0000000..5db4e00 Binary files /dev/null and b/sigillum.pdf differ diff --git a/sigillum.pdf_tex b/sigillum.pdf_tex new file mode 100644 index 0000000..fb8a15d --- /dev/null +++ b/sigillum.pdf_tex @@ -0,0 +1,58 @@ +%% Creator: Inkscape inkscape 0.92.4, www.inkscape.org +%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010 +%% Accompanies image file 'sigillum.pdf' (pdf, eps, ps) +%% +%% To include the image in your LaTeX document, write +%% \input{.pdf_tex} +%% instead of +%% \includegraphics{.pdf} +%% To scale the image, write +%% \def\svgwidth{} +%% \input{.pdf_tex} +%% instead of +%% \includegraphics[width=]{.pdf} +%% +%% Images with a different path to the parent latex file can +%% be accessed with the `import' package (which may need to be +%% installed) using +%% \usepackage{import} +%% in the preamble, and then including the image with +%% \import{}{.pdf_tex} +%% Alternatively, one can specify +%% \graphicspath{{/}} +%% +%% For more information, please see info/svg-inkscape on CTAN: +%% http://tug.ctan.org/tex-archive/info/svg-inkscape +%% +\begingroup% + \makeatletter% + \providecommand\color[2][]{% + \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}% + \renewcommand\color[2][]{}% + }% + \providecommand\transparent[1]{% + \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}% + \renewcommand\transparent[1]{}% + }% + \providecommand\rotatebox[2]{#2}% + \newcommand*\fsize{\dimexpr\f@size pt\relax}% + \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}% + \ifx\svgwidth\undefined% + \setlength{\unitlength}{425.1663821bp}% + \ifx\svgscale\undefined% + \relax% + \else% + \setlength{\unitlength}{\unitlength * \real{\svgscale}}% + \fi% + \else% + \setlength{\unitlength}{\svgwidth}% + \fi% + \global\let\svgwidth\undefined% + \global\let\svgscale\undefined% + \makeatother% + \begin{picture}(1,1.01676314)% + \lineheight{1}% + \setlength\tabcolsep{0pt}% + \put(0,0){\includegraphics[width=\unitlength,page=1]{sigillum.pdf}}% + \end{picture}% +\endgroup% diff --git a/sigillum.svg b/sigillum.svg new file mode 100644 index 0000000..7853823 --- /dev/null +++ b/sigillum.svg @@ -0,0 +1,19 @@ + + + + + + + image/svg+xml + + + + + + + + + + + + diff --git a/template.tex b/template.tex new file mode 100644 index 0000000..44a7322 --- /dev/null +++ b/template.tex @@ -0,0 +1,488 @@ +% Options for packages loaded elsewhere +\PassOptionsToPackage{unicode$for(hyperrefoptions)$,$hyperrefoptions$$endfor$}{hyperref} +\PassOptionsToPackage{hyphens}{url} +$if(colorlinks)$ +\PassOptionsToPackage{dvipsnames,svgnames*,x11names*}{xcolor} +$endif$ +$if(dir)$ +$if(latex-dir-rtl)$ +\PassOptionsToPackage{RTLdocument}{bidi} +$endif$ +$endif$ +% +\documentclass[ +$if(fontsize)$ + $fontsize$, +$endif$ +$if(lang)$ + $babel-lang$, +$endif$ +$if(papersize)$ + $papersize$paper, +$endif$ +$if(beamer)$ + ignorenonframetext, +$if(handout)$ + handout, +$endif$ +$if(aspectratio)$ + aspectratio=$aspectratio$, +$endif$ +$endif$ +$for(classoption)$ + $classoption$$sep$, +$endfor$ +]{$documentclass$} +$if(beamer)$ +$if(background-image)$ +\usebackgroundtemplate{% + \includegraphics[width=\paperwidth]{$background-image$}% +} +$endif$ +\usepackage{pgfpages} +\setbeamertemplate{caption}[numbered] +\setbeamertemplate{caption label separator}{: } +\setbeamercolor{caption name}{fg=normal text.fg} +\beamertemplatenavigationsymbols$if(navigation)$$navigation$$else$empty$endif$ +$for(beameroption)$ +\setbeameroption{$beameroption$} +$endfor$ +% Prevent slide breaks in the middle of a paragraph +\widowpenalties 1 10000 +\raggedbottom +$if(section-titles)$ +\setbeamertemplate{part page}{ + \centering + \begin{beamercolorbox}[sep=16pt,center]{part title} + \usebeamerfont{part title}\insertpart\par + \end{beamercolorbox} +} +\setbeamertemplate{section page}{ + \centering + \begin{beamercolorbox}[sep=12pt,center]{part title} + \usebeamerfont{section title}\insertsection\par + \end{beamercolorbox} +} +\setbeamertemplate{subsection page}{ + \centering + \begin{beamercolorbox}[sep=8pt,center]{part title} + \usebeamerfont{subsection title}\insertsubsection\par + \end{beamercolorbox} +} +\AtBeginPart{ + \frame{\partpage} +} +\AtBeginSection{ + \ifbibliography + \else + \frame{\sectionpage} + \fi +} +\AtBeginSubsection{ + \frame{\subsectionpage} +} +$endif$ +$endif$ +$if(beamerarticle)$ +\usepackage{beamerarticle} % needs to be loaded first +$endif$ +$if(fontfamily)$ +\usepackage[$for(fontfamilyoptions)$$fontfamilyoptions$$sep$,$endfor$]{$fontfamily$} +$else$ +\usepackage{lmodern} +$endif$ +$if(linestretch)$ +\usepackage{setspace} +$endif$ +\usepackage{amssymb,amsmath} +\usepackage{ifxetex,ifluatex} +\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex + \usepackage[$if(fontenc)$$fontenc$$else$T1$endif$]{fontenc} + \usepackage[utf8]{inputenc} + \usepackage{textcomp} % provide euro and other symbols +\else % if luatex or xetex +$if(mathspec)$ + \ifxetex + \usepackage{mathspec} + \else + \usepackage{unicode-math} + \fi +$else$ + \usepackage{unicode-math} +$endif$ + \defaultfontfeatures{Scale=MatchLowercase} + \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1} +$if(mainfont)$ + \setmainfont[$for(mainfontoptions)$$mainfontoptions$$sep$,$endfor$]{$mainfont$} +$endif$ +$if(sansfont)$ + \setsansfont[$for(sansfontoptions)$$sansfontoptions$$sep$,$endfor$]{$sansfont$} +$endif$ +$if(monofont)$ + \setmonofont[$for(monofontoptions)$$monofontoptions$$sep$,$endfor$]{$monofont$} +$endif$ +$for(fontfamilies)$ + \newfontfamily{$fontfamilies.name$}[$for(fontfamilies.options)$$fontfamilies.options$$sep$,$endfor$]{$fontfamilies.font$} +$endfor$ +$if(mathfont)$ +$if(mathspec)$ + \ifxetex + \setmathfont(Digits,Latin,Greek)[$for(mathfontoptions)$$mathfontoptions$$sep$,$endfor$]{$mathfont$} + \else + \setmathfont[$for(mathfontoptions)$$mathfontoptions$$sep$,$endfor$]{$mathfont$} + \fi +$else$ + \setmathfont[$for(mathfontoptions)$$mathfontoptions$$sep$,$endfor$]{$mathfont$} +$endif$ +$endif$ +$if(CJKmainfont)$ + \ifxetex + \usepackage{xeCJK} + \setCJKmainfont[$for(CJKoptions)$$CJKoptions$$sep$,$endfor$]{$CJKmainfont$} + \fi +$endif$ +$if(luatexjapresetoptions)$ + \ifluatex + \usepackage[$for(luatexjapresetoptions)$$luatexjapresetoptions$$sep$,$endfor$]{luatexja-preset} + \fi +$endif$ +$if(CJKmainfont)$ + \ifluatex + \usepackage[$for(luatexjafontspecoptions)$$luatexjafontspecoptions$$sep$,$endfor$]{luatexja-fontspec} + \setmainjfont[$for(CJKoptions)$$CJKoptions$$sep$,$endfor$]{$CJKmainfont$} + \fi +$endif$ +\fi +$if(beamer)$ +$if(theme)$ +\usetheme[$for(themeoptions)$$themeoptions$$sep$,$endfor$]{$theme$} +$endif$ +$if(colortheme)$ +\usecolortheme{$colortheme$} +$endif$ +$if(fonttheme)$ +\usefonttheme{$fonttheme$} +$endif$ +$if(mainfont)$ +\usefonttheme{serif} % use mainfont rather than sansfont for slide text +$endif$ +$if(innertheme)$ +\useinnertheme{$innertheme$} +$endif$ +$if(outertheme)$ +\useoutertheme{$outertheme$} +$endif$ +$endif$ +% Use upquote if available, for straight quotes in verbatim environments +\IfFileExists{upquote.sty}{\usepackage{upquote}}{} +\IfFileExists{microtype.sty}{% use microtype if available + \usepackage[$for(microtypeoptions)$$microtypeoptions$$sep$,$endfor$]{microtype} + \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts +}{} +$if(indent)$ +$else$ +\makeatletter +\@ifundefined{KOMAClassName}{% if non-KOMA class + \IfFileExists{parskip.sty}{% + \usepackage{parskip} + }{% else + \setlength{\parindent}{0pt} + \setlength{\parskip}{6pt plus 2pt minus 1pt}} +}{% if KOMA class + \KOMAoptions{parskip=half}} +\makeatother +$endif$ +$if(verbatim-in-note)$ +\usepackage{fancyvrb} +$endif$ +\usepackage{xcolor} +\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available +\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}} +\hypersetup{ +$if(title-meta)$ + pdftitle={$title-meta$}, +$endif$ +$if(author-meta)$ + pdfauthor={$author-meta$}, +$endif$ +$if(subject)$ + pdfsubject={$subject$}, +$endif$ +$if(keywords)$ + pdfkeywords={$for(keywords)$$keywords$$sep$, $endfor$}, +$endif$ +$if(colorlinks)$ + colorlinks=true, + linkcolor=$if(linkcolor)$$linkcolor$$else$Maroon$endif$, + filecolor=$if(filecolor)$$filecolor$$else$Maroon$endif$, + citecolor=$if(citecolor)$$citecolor$$else$Blue$endif$, + urlcolor=$if(urlcolor)$$urlcolor$$else$Blue$endif$, +$else$ + hidelinks, +$endif$ + pdfcreator={LaTeX via pandoc}} +\urlstyle{same} % disable monospaced font for URLs +$if(verbatim-in-note)$ +\VerbatimFootnotes % allow verbatim text in footnotes +$endif$ +$if(geometry)$ +\usepackage[$for(geometry)$$geometry$$sep$,$endfor$]{geometry} +$endif$ +$if(beamer)$ +\newif\ifbibliography +$endif$ +$if(listings)$ +\usepackage{listings} +\newcommand{\passthrough}[1]{#1} +\lstset{defaultdialect=[5.3]Lua} +\lstset{defaultdialect=[x86masm]Assembler} +$endif$ +$if(lhs)$ +\lstnewenvironment{code}{\lstset{language=Haskell,basicstyle=\small\ttfamily}}{} +$endif$ +$if(highlighting-macros)$ +$highlighting-macros$ +$endif$ +$if(tables)$ +\usepackage{longtable,booktabs} +$if(beamer)$ +\usepackage{caption} +% Make caption package work with longtable +\makeatletter +\def\fnum@table{\tablename~\thetable} +\makeatother +$else$ +% Correct order of tables after \paragraph or \subparagraph +\usepackage{etoolbox} +\makeatletter +\patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{} +\makeatother +% Allow footnotes in longtable head/foot +\IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}} +\makesavenoteenv{longtable} +$endif$ +$endif$ +$if(graphics)$ +\usepackage{graphicx,grffile} +\makeatletter +\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi} +\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi} +\makeatother +% Scale images if necessary, so that they will not overflow the page +% margins by default, and it is still possible to overwrite the defaults +% using explicit options in \includegraphics[width, height, ...]{} +\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio} +% Set default figure placement to htbp +\makeatletter +\def\fps@figure{htbp} +\makeatother +$endif$ +$if(links-as-notes)$ +% Make links footnotes instead of hotlinks: +\DeclareRobustCommand{\href}[2]{#2\footnote{\url{#1}}} +$endif$ +$if(strikeout)$ +\usepackage[normalem]{ulem} +% Avoid problems with \sout in headers with hyperref +\pdfstringdefDisableCommands{\renewcommand{\sout}{}} +$endif$ +\setlength{\emergencystretch}{3em} % prevent overfull lines +\providecommand{\tightlist}{% + \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} +$if(numbersections)$ +\setcounter{secnumdepth}{$if(secnumdepth)$$secnumdepth$$else$5$endif$} +$else$ +\setcounter{secnumdepth}{-\maxdimen} % remove section numbering +$endif$ +$if(beamer)$ +$else$ +$if(block-headings)$ +% Make \paragraph and \subparagraph free-standing +\ifx\paragraph\undefined\else + \let\oldparagraph\paragraph + \renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}} +\fi +\ifx\subparagraph\undefined\else + \let\oldsubparagraph\subparagraph + \renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}} +\fi +$endif$ +$endif$ +$if(pagestyle)$ +\pagestyle{$pagestyle$} +$endif$ +$for(header-includes)$ +$header-includes$ +$endfor$ +$if(lang)$ +\ifxetex + % Load polyglossia as late as possible: uses bidi with RTL langages (e.g. Hebrew, Arabic) + \usepackage{polyglossia} + \setmainlanguage[$polyglossia-lang.options$]{$polyglossia-lang.name$} +$for(polyglossia-otherlangs)$ + \setotherlanguage[$polyglossia-otherlangs.options$]{$polyglossia-otherlangs.name$} +$endfor$ +\else + \usepackage[shorthands=off,$for(babel-otherlangs)$$babel-otherlangs$,$endfor$main=$babel-lang$]{babel} +$if(babel-newcommands)$ + $babel-newcommands$ +$endif$ +\fi +$endif$ +$if(dir)$ +\ifxetex + % Load bidi as late as possible as it modifies e.g. graphicx + \usepackage{bidi} +\fi +\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex + \TeXXeTstate=1 + \newcommand{\RL}[1]{\beginR #1\endR} + \newcommand{\LR}[1]{\beginL #1\endL} + \newenvironment{RTL}{\beginR}{\endR} + \newenvironment{LTR}{\beginL}{\endL} +\fi +$endif$ +$if(natbib)$ +\usepackage[$natbiboptions$]{natbib} +\bibliographystyle{$if(biblio-style)$$biblio-style$$else$plainnat$endif$} +$endif$ +$if(biblatex)$ +\usepackage[$if(biblio-style)$style=$biblio-style$,$endif$$for(biblatexoptions)$$biblatexoptions$$sep$,$endfor$]{biblatex} +$for(bibliography)$ +\addbibresource{$bibliography$} +$endfor$ +$endif$ + +$if(title)$ +\title{$title$$if(thanks)$\thanks{$thanks$}$endif$} +$endif$ +$if(subtitle)$ +$if(beamer)$ +$else$ +\usepackage{etoolbox} +\makeatletter +\providecommand{\subtitle}[1]{% add subtitle to \maketitle + \apptocmd{\@title}{\par {\large #1 \par}}{}{} +} +\makeatother +$endif$ +\subtitle{$subtitle$} +$endif$ +$if(author)$ +\author{$for(author)$$author$$sep$ \and $endfor$} +$endif$ +\date{$date$} +$if(beamer)$ +$if(institute)$ +\institute{$for(institute)$$institute$$sep$ \and $endfor$} +$endif$ +$if(titlegraphic)$ +\titlegraphic{\includegraphics{$titlegraphic$}} +$endif$ +$if(logo)$ +\logo{\includegraphics{$logo$}} +$endif$ +$endif$ + +\begin{document} +$if(has-frontmatter)$ +\frontmatter +$endif$ +$if(title)$ +$if(beamer)$ +\frame{\titlepage} +$else$ +\maketitle +$endif$ +$if(abstract)$ +\begin{abstract} +$abstract$ +\end{abstract} +$endif$ +$endif$ + +$for(include-before)$ +$include-before$ + +$endfor$ +$if(toc)$ +$if(toc-title)$ +\renewcommand*\contentsname{$toc-title$} +$endif$ +$if(beamer)$ +\begin{frame} +$if(toc-title)$ + \frametitle{$toc-title$} +$endif$ + \tableofcontents[hideallsubsections] +\end{frame} +$else$ +{ +$if(colorlinks)$ +\hypersetup{linkcolor=$if(toccolor)$$toccolor$$else$$endif$} +$endif$ +\setcounter{tocdepth}{$toc-depth$} +\tableofcontents +} +$endif$ +$endif$ +$if(lot)$ +\listoftables +$endif$ +$if(lof)$ +\listoffigures +$endif$ +$if(linestretch)$ +\setstretch{$linestretch$} +$endif$ +$if(has-frontmatter)$ +\mainmatter +$endif$ +$body$ + +$if(has-frontmatter)$ +\backmatter +$endif$ +$if(natbib)$ +$if(bibliography)$ +$if(biblio-title)$ +$if(has-chapters)$ +\renewcommand\bibname{$biblio-title$} +$else$ +\renewcommand\refname{$biblio-title$} +$endif$ +$endif$ +$if(beamer)$ +\begin{frame}[allowframebreaks]{$biblio-title$} + \bibliographytrue +$endif$ + \bibliography{$for(bibliography)$$bibliography$$sep$,$endfor$} +$if(beamer)$ +\end{frame} +$endif$ + +$endif$ +$endif$ +$if(biblatex)$ +$if(beamer)$ +\begin{frame}[allowframebreaks]{$biblio-title$} + \bibliographytrue + \printbibliography[heading=none] +\end{frame} +$else$ +\printbibliography[ +$if(biblio-title)$ + title=$biblio-title$, +$endif$ +$if(biblio-heading)$ + heading=$biblio-heading$, +$endif$ +] +$endif$ + +$endif$ +$for(include-after)$ +$include-after$ + +$endfor$ +\end{document} diff --git a/thesis.args b/thesis.args index bf836dc..3416ee6 100644 --- a/thesis.args +++ b/thesis.args @@ -1 +1 @@ ---table-of-contents \ No newline at end of file +--template=template.tex \ No newline at end of file diff --git a/thesis.deps b/thesis.deps index b1cfe6a..4460750 100644 --- a/thesis.deps +++ b/thesis.deps @@ -1,3 +1,9 @@ presentation/switchdfst.tex presentation/comptree.tex -screenshot.png \ No newline at end of file +screenshot.png +sigillum.pdf_tex +sigillum.pdf +cover.tex +title.tex +abstract.tex +org.tex \ No newline at end of file diff --git a/thesis.meta.yml.gup b/thesis.meta.yml.gup index b13ea3a..8f4a69c 100644 --- a/thesis.meta.yml.gup +++ b/thesis.meta.yml.gup @@ -4,24 +4,37 @@ gup -u literature.bibtex cat >$1 <<'EOF' --- -title: Inkrementelle Parser als edit-lenses anhand von DFSTs -abstract: |- - Parser, die bekannte Texte nach einer kleinen Änderung neu analysieren können, ohne die ganze Eingabe erneut zu betrachten, nennt man inkrementell. - - Inkrementelle Parser sind seit den 1970er-Jahren bekannt und inzwischen umfangreich erforscht. - - Edit-lenses sind eine vergleichsweise neue algebraische Darstellung von Programmen, die algebraisch strukturierte Änderungen zwischen Strukturen übersetzen. - - Wir demonstrieren, dass sich Inkrementelle Parser in der Sprache von edit-lenses fassen lassen, anhand einer besonders einfachen Klasse von Parsern, den deterministic finite state transducers. - - Hierzu speichern wir im unterliegenden Zustand der assoziierten edit-lens die Ausgabe-Wirkung des DFST als balancierten Binärbaum um Teile davon effizient austauschen zu können. - - Im Rahmen dessen stellen wir eine Implementierung von edit-lenses im Allgemeinen und unserem Verfahren in möglichst idiomatischem Haskell vor. +include-before: + - |- + \pagenumbering{gobble} + \pagestyle{empty} + - \input{./cover.tex} + - \input{./title.tex} + - \cleardoublepage + - |- + \pagenumbering{roman} + \pagestyle{plain} + - \input{./abstract.tex} + - \cleardoublepage + - |- + \setcounter{tocdepth}{3} + \tableofcontents +include-after: + - \cleardoublepage + - |- + \pagenumbering{gobble} + \pagestyle{empty} + - \input{./org.tex} lang: de-de link-citations: true bibliography: literature.bibtex -author: Gregor Kleen -date: \formatdate{30}{05}{2019} numbersections: true +biblatexoptions: + - style=alphabetic + - citestyle=alphabetic +has-frontmatter: true +biblio-heading: bibintoc +classoption: + - twoside ... EOF diff --git a/thesis.tex b/thesis.tex index e24e544..7172abc 100644 --- a/thesis.tex +++ b/thesis.tex @@ -1,5 +1,3 @@ -\input{./org.tex} - \section{Einführung} \input{./intro.tex} @@ -22,7 +20,7 @@ Dabei werden wir die Definitionen aus \cite{hofmann2012edit} sowohl in natürlic \input{./edit-lens/src/Control/DFST/Lens.lhs.tex} \input{./edit-lens/src/Control/Edit/String/Affected.lhs.tex} -\subsection{Ausblick: Edit-lenses für non-determinische finite state transducers} +\subsection{Ausblick: Edit-lenses für nicht-determinische finite state transducers} \input{./edit-lens/src/Control/FST/Lens.tex} @@ -36,6 +34,6 @@ Dabei werden wir die Definitionen aus \cite{hofmann2012edit} sowohl in natürlic \input{./edit-lens/src/Control/Lens/Edit/ActionTree.lhs.tex} -\section{Fazit} +\section{Zusammenfassung} \input{conclusion.tex} diff --git a/title.tex b/title.tex new file mode 100644 index 0000000..9353f5d --- /dev/null +++ b/title.tex @@ -0,0 +1,28 @@ +\begin{titlepage} + \centering + {\scshape\LARGE Ludwig-Maximilians-Universität München\par} + Institut für Informatik\par + Lehr- und Forschungseinheit für Theoretische Informatik\par + %\vspace{1cm} + %\def\svgwidth{0.33 \textwidth} + %\input{sigillum.pdf_tex}\par\vspace{1cm} + \vspace{0.75cm} + {\scshape\Large Bachelorarbeit\par} + %\vspace{1cm} + \vfill + {\huge Inkrementelle Parser als edit-lenses anhand von DFSTs \par} + \vspace{1.5cm} + {\LARGE Gregor \textsc{Kleen}\par} + \vfill + Betreuer\par + Stephan \textsc{Barth}\par + \vspace{1cm} + Verantwortliche Hochschullehrer\par + \textdagger Prof.~Martin \textsc{Hofmann}, PhD \par + Dr.~Steffen \textsc{Jost} + + \vfill + +% Bottom of the page + {\LARGE \today\par} +\end{titlepage} -- cgit v1.2.3