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 --- edit-lens/src/Control/DFST/Lens.lhs | 25 +++++++++++++------------ 1 file changed, 13 insertions(+), 12 deletions(-) (limited to 'edit-lens/src/Control/DFST') 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: -- cgit v1.2.3