1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
\subsubsection{Motivation}
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.
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.
\subsection{Historischer Überblick}
Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ein vergleichsweise modernes Konzept und stützen sich in weiten Teilen auf vorhergehende Arbeit:
% [x] a programmable editor
% [x] bidirectional tree transformations
% [x] boomerang
% [x] combinator parser
% [ ] ~~delta lenses & optifibrations~~
% [x] edit languages for information trees
% [x] edit lenses
% [x] efficient and flexible incremental parsing
% [x] general incremental lexical analysis
% [ ] ~~incrementel analysis of real programming languages~~
% [x] incremental parsing
% [x] incremental semantic analysis
% [x] lazy functional incremental parsing
% [ ] ~~lenses and bidirectional programs~~
% [ ] ~~parallel inceremntal compilation~~
% [x] parsing in a broad sense
% [ ] polish parsers
% [x] symmetric lenses
% [x] unifying lenses
% [ ] ~~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[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.
\item[2001] \cite{swierstra2001combinator} demonstriert den Nutzen Kombinator-basierter Parser-Konstruktion in der Praxis
\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[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.
Ein relevantes Resultat ist hierbei ein Begriff von asymmetrischen edit-lenses kompatibel mit dem symmetrischen Fall.
\end{description}
\subsection{Begriffsverzeichnis}
Obwohl wir detailliertere Definitionen der folgenden Konzepte im Laufe der Arbeit geben, ist es dennoch nützlich vorab die Bedeutung der verwendeten Begriffe kurz anzuschneiden:
\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[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.
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.
Hierbei wird ein, mit den jeweiligen Elementen der Trägermengen konsistenter, unterliegender Zustand, das \emph{Komplement} der edit-lens, gewahrt.
\end{description}
|
