From 537ac8a2ecb64a141ec8ffc1ab053e84154c4f09 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 4 Jun 2019 11:11:57 +0200 Subject: Cleanup --- intro.tex | 32 +++++++++++++++++--------------- 1 file changed, 17 insertions(+), 15 deletions(-) (limited to 'intro.tex') diff --git a/intro.tex b/intro.tex index 539a0a6..43d909d 100644 --- a/intro.tex +++ b/intro.tex @@ -2,18 +2,19 @@ Unter einem inkrementellen Parser \cite{ghezzi1979incremental} verstehen wir ein Programm, das, nach einem initialen Parsevorgang, gegeben eine Spezifikation einer Änderung der textuellen Eingabe i.A. schneller ein neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre (gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe). -Es ist nun prinzipiell wünschenswert die algebraische Struktur derartiger Klassen von Programmen zu untersuchen, mit dem Ziel neue Parser mit generischen Mitteln aus bereits bekannten konstruieren zu können. +Es ist nun prinzipiell wünschenswert die algebraische Struktur derartiger Klassen von Programmen zu untersuchen, mit dem Ziel neue Parser mit generischen Mitteln aus bereits Bekannten konstruieren zu können. -In dieser Arbeit versuchen wir, anhand von Finite State Transducern als Spezialfall, inkrementelle Parser und die unterliegenden edits mit neuerer algebraischer Struktur, edit-lenses \cite{hofmann2012edit}, zu versehen um Komponierbarkeit zu vereinfachen. +In dieser Arbeit versuchen wir, anhand von finite state transducern als Spezialfall, inkrementelle Parser und die unterliegenden edits mit neuerer algebraischer Struktur, edit-lenses \cite{hofmann2012edit}, zu versehen um Komponierbarkeit zu vereinfachen. Vor allem versuchen wir somit zu demonstrieren, dass sich bekannte Klassen von Programmen, unter Erhalt ihrer vollen Struktur, als edit-lenses auffassen lassen, auch wenn die Darstellung als konventionelle funktionale Linse unzufriedenstellend wäre. \subsubsection{Inhalt} Wir stellen in Abschnitt \ref{edit-lenses} die Definitionen und Konstruktion von edit-lenses aus \cite{hofmann2012edit} vor und diskutieren kurz die Kompatibilität unserer Implementierung und edit-lenses im Allgemeinen mit etablierten frameworks für funktionale Linsen in Haskell. -In Abschnitt \ref{finite-state-transducers} präsentieren wir eine etablierte Version von Finite State Transducern, für die folgenden Teile relevante Konstruktionen darauf, und einige assoziierte Beispiele. -Abschnitt \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} beschreibt eine Methode beliebige deterministische Finite State Transducers als edit-lenses aufzufassen und stellt somit eine non-triviale Anwendung der Methoden und Konzepte aus \cite{hofmann2012edit} dar. -In Abschnitt \ref{ausblick-edit-lenses-fuxfcr-non-determinische-finite-state-transducers} stellen wir kurz einen Ansatz dar unsere Konstruktion aus \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} auch auf non-deterministische Finite State Transducer zu erweitern. -In Abschnitt \ref{implementierung} kommentieren wir den Implementierungs-Prozess der Arbeit und die Schlüsse, die wir aus der Implementierung als solche ziehen konnten. +In Abschnitt \ref{finite-state-transducers} präsentieren wir eine etablierte Version von finite state transducern, für die folgenden Teile relevante Konstruktionen darauf und einige assoziierte Beispiele. +Abschnitt \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} beschreibt eine Methode beliebige deterministische finite state transducers als edit-lenses aufzufassen und stellt somit eine non-triviale Anwendung der Methoden und Konzepte aus \cite{hofmann2012edit} dar. +In Abschnitt \ref{ausblick-edit-lenses-fuxfcr-non-determinische-finite-state-transducers} stellen wir kurz einen Ansatz dar unsere Konstruktion aus \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} auch auf non-deterministische finite state transducer zu erweitern. +In Abschnitt \ref{implementierung} kommentieren wir den Implementierungsprozess der Arbeit und die Schlüsse, die wir aus der Implementierung als solcher ziehen konnten. +Abschnitt \ref{ausblick-anwendbarkeit-der-implementierung-auf-andere-parser} beschreibt kurz wie sich das dargestellte Verfahren auf andere Sorten von Parsern anwenden ließe. \subsection{Historischer Überblick} @@ -41,7 +42,7 @@ Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ei % [ ] ~~universal updates for symmetric lenses~~ \begin{description} % TODO: more - \item[1979] \cite{ghezzi1979incremental} präsentieren, in einer der ersten Arbeiten zu dem Thema, einen Ansatz zum inkrementellen Parsen von deterministischen und Kontext-freien Sprachen basierend auf dem $LR$-Ansatz. + \item[1979] \cite{ghezzi1979incremental} präsentieren, in einer der ersten Arbeiten zu dem Thema, einen Ansatz zum inkrementellen Parsen von deterministischen und kontextfreien Sprachen basierend auf dem $LR$-Ansatz. \item[1992] \cite{hedin1992incremental} präsentieren einen Formalismus zur inkrementellen \emph{semantischen} Analyse (d.h. das Versehen des Syntax-Baums eines Programms mit Attributen wie z.B. Typen) basierend auf (modifizierten) Attribut-Grammatiken. \item[1997] \cite{wagner1997general} stellen einen Algorithmus zur inkrementellen lexikalischen Analyse (tokenizing) der auf den selben Spezifikationen arbeiten kann wie die UNIX-Tools \texttt{lex} und \texttt{flex}. \item[1998] \cite{wagner1998efficient} stellen neue, Laufzeit- und Speicher-optimale, Methoden zur Konstruktion inkrementeller Parser auf Basis beliebiger $LR(k)$-Grammatiken vor. @@ -49,16 +50,16 @@ Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ei \item[2004] \cite{hu2004programmable} spezifizieren eine algebraisch strukturierte Sprache für bidirektionale Baum-Transformationen unter einer programmierbaren Konsistenzrelation mit Blick auf direkte Anwendung im Editieren von bestehenden Baum-Dokumenten \item[2007] \cite{foster2007combinators} präsentieren sowohl eine Sprache bidirektionaler Baum-Transformationen als konventionelle funktionale Linsen im Speziellen, als auch mathematische Resultate für funktionale Linsen und Sammlungen davon im Allgemeinen. Auch enthalten ist eine nützliche Klassifikation und ein historischer Überblick diverser bidirektionalen Programmiertechniken. - \item[2008] Analog zur Sprache bidirektionaler Baum-Transformation aus \cite{foster2007combinators} stellen \cite{bohannon2008boomerang} eine Sprache für semi-Strukturierten Text (als Serie von vertauschbaren Schlüssel-Wert-Assoziationen) vor. - \item[2009] \cite{bernardy2009lazy} implementieren, im Rahmen der Arbeit am Text-Editor Yi, eine Kombinator-basierte Programmbibliothek zum inkrementellen Parsen basierend auf lazy evaluation und aggressivem Caching in Haskell. + \item[2008] Analog zur Sprache bidirektionaler Baum-Transformation aus \cite{foster2007combinators} stellen \cite{bohannon2008boomerang} eine Sprache für semi-strukturierten Text (als Serie von vertauschbaren Schlüssel-Wert-Assoziationen) vor + \item[2009] \cite{bernardy2009lazy} implementieren, im Rahmen der Arbeit am Text-Editor Yi, eine Kombinator-basierte Programmbibliothek zum inkrementellen Parsen basierend auf lazy evaluation und aggressivem Caching in Haskell \item[2011] \cite{hofmann2011symmetric} definieren symmetrische \emph{set-based}-lenses (funktionale Linsen im konventionellen Sinn), d.h. ohne strukturierte edits. Es wird auch die umfangreiche algebraische Struktur symmetrischer Linsen besprochen. Vieles hiervon vererbt sich direkt auf edit-lenses als Spezialfall symmetrischer Linsen. \item[2012] \cite{hofmann2012edit} definieren edit-lenses. In Abgrenzung zu bestehenden Formalismen symmetrischer funktionaler Linsen arbeiten edit-lenses ausschließlich auf algebraisch strukturierten edit-Sprachen, was sie besonders attraktiv macht. - \item[2013] \cite{hofmann2013edit} stellen eine generelle edit-Sprache (zur Verwendung mit und basierend auf edit-lenses) für eine weite Klasse von container-Datentypen (Listen, Bäume, Graphen, ...) vor. - \item[2014] \cite{zaytsev2014parsing} geben einen nützlichen Überblick über die, historisch inkonsistente, Terminologie und Konzepte im Zusammenhang mit Parsing. - \item[2016] \cite{johnson2016unifying} betrachten Zusammenhänge von diversen Klassen funktionaler Linsen (inkl. edit-lenses) und geben dabei einen umfangreichen Überblick über die bestehende Forschung an funktionalen Linsen. + \item[2013] \cite{hofmann2013edit} stellen eine generelle edit-Sprache (zur Verwendung mit und basierend auf edit-lenses) für eine weite Klasse von container-Datentypen (Listen, Bäume, Graphen, ...) vor + \item[2014] \cite{zaytsev2014parsing} geben einen nützlichen Überblick über die, historisch inkonsistente, Terminologie und Konzepte im Zusammenhang mit Parsing + \item[2016] \cite{johnson2016unifying} betrachten Zusammenhänge diverser Klassen funktionaler Linsen (inkl. edit-lenses) und geben dabei einen umfangreichen Überblick über die bestehende Forschung. Ein relevantes Resultat ist hierbei ein Begriff von asymmetrischen edit-lenses kompatibel mit dem symmetrischen Fall. \end{description} @@ -68,14 +69,15 @@ Obwohl wir detailliertere Definitionen der folgenden Konzepte im Laufe der Arbei \begin{description} \item[FST] \emph{Finite-State-Transducer} sind endliche Automaten, die bei jedem Zustandsübergang die Möglichkeit haben ein Zeichen an eine sich akkumulierende Ausgabe anzuhängen - \item[DFST] \emph{Deterministic finite-state-transducer} sind FSTs bei denen für jeden Zustand jedes gelesene Zeichen maximal einen Zustandsübergang zulässt + \item[DFST] \emph{Deterministic Finite-State-Transducer} sind FSTs bei denen für jeden Zustand jedes gelesene Zeichen maximal einen Zustandsübergang zulässt \item[Monoid] \emph{Monoiden} sind algebraisch zwischen Halbgruppen und Gruppen angesiedelt. Wir sagen eine Menge hat Monoidstruktur bzgl. einer zweistelligen Verknüpfung auf jener Menge, wenn sie ein neutrales Element enthält und die Verknüpfung assoziativ ist. \item[Moduln & edits] \emph{Moduln} verknüpfen eine Trägermenge mit einer Menge von \emph{edits} (mit monoidaler Struktur) auf jener Menge. Edits beschreiben jeweils eine partielle Abbildung innerhalb der Trägermenge. - \item[Funktionale Linsen] Eine \emph{Funktionale Linse} von $s$ in $a$ in der üblichen Definition ist ein paar von Abbildungen $\searrow \colon s \to a$ und $\nearrow \colon (a \to a) \to (s \to s)$ mit umfangreicher algebraischer Struktur, die die Komposition komplexer Linsen aus einfacheren ermöglicht. + \item[Funktionale Linsen] Eine \emph{Funktionale Linse} von $s$ in $a$ in der üblichen Definition (\emph{set-based}) ist ein Paar von Abbildungen $\searrow \colon s \to a$ und $\nearrow \colon (a \to a) \to (s \to s)$ mit umfangreicher algebraischer Struktur, die die Komposition komplexer Linsen aus Einfacheren ermöglicht. Wir finden es hilfreich von einer Projektion ($\searrow$) und einem \emph{edit-Propagator} ($\nearrow$) zu sprechen. \item[Van-Laarhoven Linsen] In \cite{laarhoven} wurde eine Darstellung als eine (über einen Funktor parametrisierte) Funktion dargelegt, die unter anderem auch die soeben beschriebenen funktionalen Linsen einbetten kann - \item[edit-lenses] \emph{edit-lenses} verknüpfen zwei Moduln-Trägermengen indem sie edits des einen Modul in die des anderen übersetzen. + \item[edit-lenses] \emph{edit-lenses} verknüpfen zwei Moduln-Trägermengen indem sie edits des einen Modul in die des Anderen übersetzen. Hierbei wird ein, mit den jeweiligen Elementen der Trägermengen konsistenter, unterliegender Zustand, das \emph{Komplement} der edit-lens, gewahrt. + Intuitiv speichert das Komplement genau jene Information, die nicht in beiden Darstellungen vorkommt. \end{description} -- cgit v1.2.3