From f4c419b9ddec15bad267a4463f0720d6e28042d2 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Thu, 30 May 2019 12:18:08 +0200 Subject: Further work --- presentation.tex | 351 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 351 insertions(+) create mode 100644 presentation.tex (limited to 'presentation.tex') 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} -- cgit v1.2.3