path: root/presentation.tex

\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}