Further work

1 files changed, 351 insertions, 0 deletions

diff --git a/presentation.tex b/presentation.tex
new file mode 100644
index 0000000..3eddd70
--- /dev/null
+++ b/presentation.tex
@@ -0,0 +1,351 @@
+\section{Einführung}
+
+\begin{frame}
+  \frametitle{Tl;dr}
+  
+  \begin{itemize}
+    \item Inkrementelle Parser agieren auf \emph{edits} von Ein- und Ausgaben
+    \item Edit-Lenses sind algebraische Struktur für deartige Programme
+    \item DFSTs sind spezielle Parser, schwach genug um immer auch inkrementell zu sein
+    \item Darstellung von DFSTs als edit-lenses als Proof of Concept
+  \end{itemize}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Struktur}
+  \begin{enumerate}
+  \item Begriffe/Definitionen
+    \begin{itemize}
+    \item Parser, Inkrementelle Parser
+    \item Funktionale Linsen, edit-lenses
+    \end{itemize}
+  \item Motivation
+  \item Inhalt der Arbeit
+    \begin{itemize}
+    \item Inkrementelle Parser als edit-lenses für DFSTs
+    \end{itemize}
+  \item Demonstration
+    \begin{itemize}
+    \item Interaktiver Editor unter einer edit-lens
+    \end{itemize}
+  \item Skizze des Verfahrens aus der Arbeit
+    \begin{itemize}
+    \item Komplement-Konstruktion für DFSTs
+    \item $\Rrightarrow$ und $\Lleftarrow$
+    \end{itemize}
+  \item Weiterführendes
+  \end{enumerate}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Inkrementelle Parser}
+
+  \begin{defn}[Parser]
+    Jedes Programm vom Typ $\Sigma^\star \to a$
+    \note[item]{Programme, die Strings analysieren und eine Struktur produzieren}
+  \end{defn}
+
+  \begin{defn}[Inkrementelle Parser]
+    Vermeiden komplette Re-analyse bekannter Eingabe-Texte
+
+    Für unsere Zwecke\footnote{Mit $\delta(x)$ immer einer geeigneten Sprache von edits über $x$}:
+    \[
+      \delta ( \Sigma^\star ) \to \delta ( a )
+    \]
+  \end{defn}
+\end{frame}
+
+\begin{frame}
+  \begin{defn}[Funktionale Linsen]
+    Eine Linse auf ein $a$ \emph{innerhalb} eines größeren $s$:
+    \begin{align*}
+      G & \colon s \to a \\
+      P & \colon (a \to a) \to (s \to s)
+    \end{align*}
+    \note[item]{Zum Verständnis: nimm $s$ als Klasse/Struct und $a$ als Attribut davon}
+    \begin{itemize}
+    \item Bidirektional
+    \item \emph{fokussiert} Teil der großen Struktur $s$
+    \item Projektion und Update-Propagator
+    \item $P$ und $G$ sind \emph{well-behaved}
+    \end{itemize}
+  \end{defn}
+\end{frame}
+
+\begin{frame}
+  \begin{defn}[edit-lenses]
+    \begin{align*}
+      \Rrightarrow & \colon \delta(s) \times C \to \delta(a) \times C \\
+      \Lleftarrow & \colon \delta(a) \times C \to \delta(s) \times C
+    \end{align*}
+    Mit $C$ dem \emph{Komplement}\footnote{\emph{View-Update-Problem} für DBS}, die zusätzlich zu den Edits $\delta(s)$, bzw. $\delta(a)$ notwendige Information um neues $a$ bzw. $s$ zu konstruieren
+    \begin{itemize}
+    \item Bidirektional
+    \item Edit-Propagatoren in beide Richtungen
+    \item Edits haben \emph{Algebraische Struktur}
+    \item $\Rrightarrow$ und $\Lleftarrow$ sind \emph{well-behaved}
+    \end{itemize}
+    \note[item]{$\delta(s)$ ist Speziallfall von $s \to s$}
+  \end{defn}
+\end{frame}
+
+\begin{frame}[fragile]
+
+  \frametitle{Edit-Konversationen}
+  \framesubtitle{Vereinfacht, ohne Komplement}
+
+  \begin{figure}
+    \centering
+    \pinclude{presentation/editconv.tex}
+  \end{figure}
+
+\end{frame}
+
+\begin{frame}
+  \frametitle{FSTs}
+
+  \begin{defn}[Finite state transducer]
+    Endliche Automaten mit Ausgabe-Symbolen an Zustansübergängen annotiert.
+    \note[item]{\emph{Determinismus} analog zu DFAs}
+  \end{defn}
+
+%%   \begin{eg}
+%%     \centering
+%%     \begin{tikzpicture}[->,auto,node distance=2.5cm]
+%%       \node[initial,state] (0) {$A$};
+%%       \node[state,accepting] (1) [right of=0] {$B$};
+%%       \node[state,initial,accepting,initial where=right] (2) [right of=1] {$C$};
+
+%%       \path (0) edge [loop above] node {$(a, x)$} (0)
+%%             (0) edge node {$(a, y)$} (1)
+%%             (1) edge [bend left=20] node [above] {$(a, z)$} (2)
+%%             (1) edge [bend right=20] node [below] {$(b, z)$} (2)
+%%             (2) edge [loop above] node {$(\epsilon, z)$} (2);
+%%     \end{tikzpicture}
+%%     \note[item]{Beispiel ist \emph{nicht} deterministisch}
+%%     \note[item]{Beispiel hat zwei initiale Zustände}
+%%     \note[item]{Beispiel hat zwei akzeptierende Zustände}
+%%     \note[item]{$a^{+}(a \mid b)^{?} \to x^{n}(yz^{+})^{?} \mid z^\star$}
+%%     %% \begin{tikzpicture}[->,auto,node distance=2.5cm]
+%%     %%   \node[initial,state] (0) {$A$};
+%%     %%   \node[state,accepting] (1) [right of=0] {$B$};
+%%     %%   \node[state,accepting] (2) [right of=1] {$C$};
+
+%%     %%   \path (0) edge node {$(a, y)$} (1)
+%%     %%         (1) edge [bend left=20] node [above] {$(a, z)$} (2)
+%%     %%         (1) edge [bend right=20] node [below] {$(b, z)$} (2);
+%%     %% \end{tikzpicture}
+%%   \end{eg}
+%% \end{frame}
+
+%% \begin{frame}
+%%   \frametitle{Beispiel-DFST}
+
+  \begin{figure}
+    \centering
+    \pinclude{presentation/switchdfst.tex}
+  \end{figure}
+\end{frame}
+
+\section{Motivation}
+
+\begin{frame}
+  \frametitle{Motivation}
+  
+  \begin{itemize}
+  \item edit-lenses (und unterliegende edits) haben umfangreiche algebraische Struktur
+  \item Inkrementelle Parser haben praktische Vorteile, wo anwendbar
+  \item Darstellung von inkrementellen Parsern als edit-lenses erlaubt Kompositions-basierte Konstruktion von Parsern
+  \end{itemize}
+
+  \begin{eg}
+    \begin{itemize}
+    \item Interaktive Programmierumgebung kann \emph{sofort} Feedback geben (Semantisches autocomplete, syntax highlighting, ...)
+    \item Grafische Konfigurations-Ansichten für unterliegende Konfigurationsdateien können Formatierung (z.B. Kommentare) erhalten
+    \end{itemize}
+  \end{eg}
+\end{frame}
+
+\section{Inhalt der Arbeit}
+
+\begin{frame}
+  \frametitle{Inhalt}
+  
+  \begin{itemize}
+  \item edits, edit-lenses, und FSTs in Haskell
+  \item Verfahren zum automatischen Ableiten von edit-lenses aus DFSTs
+  \item Interaktiver editor für beliebige edit-lenses zwischen Strings
+  \end{itemize}
+\end{frame}
+
+\section{Demonstration}
+
+\begin{frame}
+  \frametitle{JSON-Normalisierer}
+  \framesubtitle{Demonstration}
+
+  \begin{itemize}
+  \item JSON-Normalisierung ausgedrückt als DFST
+  \item edit-lens aus DFST abgeleitet
+  \item Interaktiver editor akzeptiert edits auf einer Seite und propagiert in Gegenrichtung
+  \end{itemize}
+\end{frame}
+
+\section{Edit-lenses für DFSTs}
+
+\begin{frame}
+  \frametitle{Ansatz}
+
+  Als \emph{Komplement} genug Information um für jedes Intervall im Eingabe-String berechnen zu können:
+  
+  \begin{itemize}
+  \item Gegeben einen Zustand auf der linken Seite des Intervalls, welche Ausgabe wird produziert und welcher Zustand wird auf der rechten Seite erreicht?
+
+    \[ \text{state} \to \text{outChar}^\star \times (\text{state} \cup \{ \bot \}) \]
+
+    \emph{Ausgabe-Wirkung} des FST
+  \item Welche Eingabe wurde im Intervall konsumiert?
+  \end{itemize}
+
+  Gegeben einen edit:
+
+  \begin{enumerate}
+  \item Intervall in Ausgabe/Eingabe bestimmen, die von edit betroffen ist
+  \item Betroffenes Teilstück des Komplements austauschen
+  \item Übertragenen edit Anhand von Differenz der Komplement-Stücke bestimmen
+  \end{enumerate}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Composition-Trees}
+  \framesubtitle{Effiziente Berechnung von Wirkungen beliebiger Eingabe-Intervalle}
+  
+  \begin{columns}[c]
+    \column{.5\textwidth}
+      \begin{center}
+        \scalebox{1}{\pinclude{presentation/switchdfst.tex}}
+      \end{center}
+    \column{.5\textwidth}
+      \begin{center}
+        \scalebox{0.65}{\pinclude{presentation/comptree.tex}}
+      \end{center}
+  \end{columns}
+\end{frame}
+
+\begin{frame}
+  \frametitle{$\Rrightarrow$}
+
+  \begin{align*}
+    \Rrightarrow & \colon \delta ( \text{inChar}^\star ) \times C \to \delta ( \text{outChar}^\star ) \times C \\
+    C & \colon \left ( \text{outChar}^\star \times (\text{state} \cup \{ \bot \}), \text{inChar}^\star \right )
+  \end{align*}
+
+  \begin{enumerate}
+  \item Bestimme Intervall in $\text{inChar}^\star$ betroffen von edit und asoziiertes Stück $c \subseteq C$
+  \item Lese in $C$ betroffenes Intervall in $\text{outChar}^\star$ ab
+  \item Berechne neues Stück $c^\prime$ durch Auswertung des DFST
+  \item Bestimme $\delta (\text{outChar}^\star)$ mit Standard-Diff auf $\text{inChar}^\star$-Komponenten von $c$ und $c^\prime$
+  \item Ersetze $c$ in $C$ mit $c^\prime$
+  \end{enumerate}
+\end{frame}
+
+\begin{frame}
+  \frametitle{$\Rrightarrow$}
+  \framesubtitle{Beispiel}
+
+  \begin{columns}[c]
+    \column{.33\textwidth}
+    \begin{enumerate}
+    \item Intervall im Eingabetext
+    \item Ausgabe-Stück aus Komplement
+    \item Neues Komplement-Stück durch Auswertung
+    \item Komplement-Stück ersetzen
+    \item Ausgabe-Differenz aus Komplement-Stücken
+    \end{enumerate}
+    \column{.33\textwidth}
+      \begin{center}
+        \scalebox{1}{\pinclude{presentation/switchdfst.tex}}
+      \end{center}
+    \column{.33\textwidth}
+      \begin{center}
+        \scalebox{0.6}{\pinclude{presentation/comptree.tex}}
+      \end{center}
+  \end{columns}
+\end{frame}
+
+\begin{frame}
+  \frametitle{$\Lleftarrow$}
+  
+  \begin{align*}
+    \Lleftarrow & \colon \delta ( \text{outChar}^\star ) \times C \to \delta ( \text{inChar}^\star ) \times C \\
+    C & \colon \left ( \text{outChar}^\star \times (\text{state} \cup \{ \bot \}), \text{inChar}^\star \right )
+  \end{align*}
+
+  \begin{enumerate}
+  \item Bestimme Intervall in $\text{outChar}^\star$ betroffen von edit und asoziiertes Stück $c \subseteq C$
+  \item Bestimme neue Ausgabe durch Anwenden von $\delta ( \text{outChar}^\star )$
+  \item Finde, durch Breitensuche, Lauf in DFST mit passender Ausgabe und selben Grenzen wie $c$
+  \item Lese $c^\prime$ aus neuem Lauf ab
+  \item Bestimme $\delta ( \text{inChar}^\star )$ mit Standard-Diff
+  \item Ersetze $c$ in $C$ mit $c^\prime$
+  \end{enumerate}
+\end{frame}
+
+\begin{frame}
+  \frametitle{$\Lleftarrow$}
+  \framesubtitle{Beispiel}
+
+  \begin{columns}[c]
+    \column{.33\textwidth}
+    \begin{enumerate}
+    \item Intervall im Ausgabetext
+    \item Neue Ausgabe für Intervall
+    \item Breitensuche nach neuem Lauf-Stück
+    \item Neues Komplement-Stück
+    \item Komplement-Stück ersetzen
+    \item Eingabe-Differenz aus Komplement-Stücken
+    \end{enumerate}
+    \column{.33\textwidth}
+      \begin{center}
+        \scalebox{1}{\pinclude{presentation/switchdfst.tex}}
+      \end{center}
+    \column{.33\textwidth}
+      \begin{center}
+        \scalebox{0.6}{\pinclude{presentation/comptree.tex}}
+      \end{center}
+  \end{columns}
+\end{frame}
+
+\section{Resultate}
+
+\begin{frame}
+  \frametitle{Ergebnisse}
+  
+  \begin{itemize}
+  \item Verfahren zum automatischen Ableiten von inkrementellen Parsern zu DFSTs
+  \item Inkl. Darstellung als edit-lens
+  \item Interaktive Demonstration von edit-lenses
+  \end{itemize}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Implementierung}
+  \begin{itemize}
+  \item Diverse erfolglose Ansätze zur Implementierung von $\Lleftarrow$
+  \item Erfolgreiche Implementierung dann mit algebraischen FST-Transformationen und als Komposition kleiner Typ-gesteuerter und generischer Teile
+    \note[item]{Demonstriert Erfolg von algebraischer Programmierung: nicht optimale, aber ähnliche, Komplexitätsklasse und dafür leichter verständlich}
+  \item Demonstriert Kodierung von algorithmischen Voraussetzungen in Typen (z.B. Determinismus von FST)
+    \note[item]{Korrekte Kodierung in Typen erlaubt auslassen von wenig interessanten Spezialfällen}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Weiterführendes}
+  \begin{itemize}
+  \item Analoges Verfahren für FSTs auch möglich; $\Lleftarrow$ und $\Rrightarrow$ dann symmetrisch und analog zum DFST-Fall von $\Lleftarrow$
+  \item Edit-Lenses sind nicht kompatibel mit bestehenden Lens-Frameworks (in Haskell), da kodierung der Update-Propagatoren nicht kompatibel mit algebraischer Struktur der Edits
+  \item Linsen bilden große Familie von funktionalen, bidirektionalen Programmen z.B.
+    Imperative accessors für rein-funktionale Datenstrukturen und nützliche Verallgemeinerungen
+  \item Inkrementelle Parser und assoziierte Algorithmen (gewöhnlich basierend auf formalen Grammatiken) sind bekannt seit den 70er-Jahren; neue Darstellungen mit algebraischer Struktur fassen besser die \emph{mostly-incremental}-Struktur der meisten Programmiersprachen
+  \end{itemize}
+\end{frame}