summaryrefslogtreecommitdiff
path: root/edit-lens/src/Control/DFST/Lens.lhs
diff options
context:
space:
mode:
authorGregor Kleen <gkleen@yggdrasil.li>2019-06-04 11:11:57 +0200
committerGregor Kleen <gkleen@yggdrasil.li>2019-06-04 11:13:16 +0200
commit537ac8a2ecb64a141ec8ffc1ab053e84154c4f09 (patch)
treea50ef75e88f20ea88d7e347484bb79014ff3705a /edit-lens/src/Control/DFST/Lens.lhs
parentf4c419b9ddec15bad267a4463f0720d6e28042d2 (diff)
downloadincremental-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.lhs17
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
163Fü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. 163Fü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
165Da 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. 165Da 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.
166Die 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. 166Die 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
171Wir 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). 171Wir 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
173Wir 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. 173Wir 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
175Wir 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. 175Wir 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.
176Hierbei 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. 176Hierbei 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
178Die 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. 178Die 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}