diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-04 11:11:57 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-04 11:13:16 +0200 |
commit | 537ac8a2ecb64a141ec8ffc1ab053e84154c4f09 (patch) | |
tree | a50ef75e88f20ea88d7e347484bb79014ff3705a /edit-lens/src/Control/DFST/Lens.lhs | |
parent | f4c419b9ddec15bad267a4463f0720d6e28042d2 (diff) | |
download | incremental-dfsts-537ac8a2ecb64a141ec8ffc1ab053e84154c4f09.tar incremental-dfsts-537ac8a2ecb64a141ec8ffc1ab053e84154c4f09.tar.gz incremental-dfsts-537ac8a2ecb64a141ec8ffc1ab053e84154c4f09.tar.bz2 incremental-dfsts-537ac8a2ecb64a141ec8ffc1ab053e84154c4f09.tar.xz incremental-dfsts-537ac8a2ecb64a141ec8ffc1ab053e84154c4f09.zip |
Cleanup
Diffstat (limited to 'edit-lens/src/Control/DFST/Lens.lhs')
-rw-r--r-- | edit-lens/src/Control/DFST/Lens.lhs | 17 |
1 files changed, 9 insertions, 8 deletions
diff --git a/edit-lens/src/Control/DFST/Lens.lhs b/edit-lens/src/Control/DFST/Lens.lhs index 8222db2..ec81113 100644 --- a/edit-lens/src/Control/DFST/Lens.lhs +++ b/edit-lens/src/Control/DFST/Lens.lhs | |||
@@ -138,12 +138,12 @@ Wir bedienen uns hierbei einer bestehenden Programmbibliothek \cite{composition- | |||
138 | Auf $s$ wechselt der DFST seinen Zustand, auf $p$ produziert er, abhängig vom aktuellen Zustand, genau ein Zeichen. | 138 | Auf $s$ wechselt der DFST seinen Zustand, auf $p$ produziert er, abhängig vom aktuellen Zustand, genau ein Zeichen. |
139 | 139 | ||
140 | Wir stellen die Wirkung des DFST auf den Eingabe-String $spp$ grafisch analog zur Baumstruktur von \texttt{Compositions} dar. | 140 | Wir stellen die Wirkung des DFST auf den Eingabe-String $spp$ grafisch analog zur Baumstruktur von \texttt{Compositions} dar. |
141 | Wir bedienen uns hier der Darstellung von Automaten-Wirkungen als \emph{Schaltboxen} aus \cite{hofmann2011automatentheorie}, angepasst für DFSTs indem wir die Ausgabe des Automaten an den Pfaden innerhalb der Schaltbox annotieren. | 141 | 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. |
142 | 142 | ||
143 | \begin{figure}[H] | 143 | \begin{figure}[H] |
144 | \centering | 144 | \centering |
145 | \pinclude{presentation/comptree.tex} | 145 | \pinclude{presentation/comptree.tex} |
146 | \caption{Die Wirkung der Eingabe $spp$ auf den Automaten aus Abbildung \ref{fig:switchdfst}} | 146 | \caption{Die Wirkung der Eingabe $spp$ auf den einfachen transducer aus Abbildung \ref{fig:switchdfst}} |
147 | \end{figure} | 147 | \end{figure} |
148 | \end{eg} | 148 | \end{eg} |
149 | 149 | ||
@@ -160,7 +160,7 @@ dfstaProduces = fmap fst . runDFSTAction' | |||
160 | \end{code} | 160 | \end{code} |
161 | \end{comment} | 161 | \end{comment} |
162 | 162 | ||
163 | Für $\Rrightarrow$ können wir die alte DFST-Wirkung zunächst anhand des Intervalls indem der input-String von allen gegebenen edits betroffen ist (\texttt{affected}) in einen unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen. | 163 | 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. |
164 | 164 | ||
165 | 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. | 165 | 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. |
166 | 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. | 166 | 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. |
@@ -170,12 +170,12 @@ Für die asymmetrische edit-lens entgegen der DFST-Richtung $\Lleftarrow$ verwen | |||
170 | 170 | ||
171 | 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). | 171 | 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). |
172 | 172 | ||
173 | 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 akzeptierten Zustand führt. | 173 | 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. |
174 | 174 | ||
175 | Wir verwenden dann gewöhnliche Breitensuche über die Zustände und Transitionen des soeben konstruierten FSTs um einen Lauf-Fragment zu bestimmen, dass wir in das betroffene Intervall einsetzen können. | 175 | 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. |
176 | 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 akzeptierten Zustand endet. | 176 | 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. |
177 | 177 | ||
178 | 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. | 178 | 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. |
179 | 179 | ||
180 | \begin{comment} | 180 | \begin{comment} |
181 | \begin{code} | 181 | \begin{code} |
@@ -299,7 +299,8 @@ bfs outgoing predicate | |||
299 | n & \mapsto ( \text{\tt \textbackslash n}, 0 ) \\ | 299 | n & \mapsto ( \text{\tt \textbackslash n}, 0 ) \\ |
300 | & \\ | 300 | & \\ |
301 | \text{act}_\text{L} & \colon Q \to \Delta^\star \times \{ \bot \} \cup Q \\ | 301 | \text{act}_\text{L} & \colon Q \to \Delta^\star \times \{ \bot \} \cup Q \\ |
302 | n & \mapsto (0\, 1\, \ldots\, 80, 80) \\ | ||
303 | \text{other} & \mapsto (\epsilon, \bot) | 302 | \text{other} & \mapsto (\epsilon, \bot) |
304 | \end{align*} | 303 | \end{align*} |
304 | |||
305 | % TODO | ||
305 | \end{eg} | 306 | \end{eg} |