\chapter{Background}

\label{sec:background}

\section{The EQL editor}

The work in this thesis stems from two earlier projects. The first is the
development of a graphical editor for a DSL called EQL, developed from
2003-2007 for Hexis B.V. to describe templates for a report generator. Given
such a template and data from some source, it is the report generator's job to
create a PDF file that presents this data in a pleasant way. In this specific
case, the data was assumed to come from a database and so the template files
used SQL to indicate what data they were interested in, creating formatted
tables and referring to fields from database tables. Report generators have
many practical applications. Common ones include managing customer bases,
generating e.g.~invoices, welcoming letters, reminder letters, and so on. Just
as web services dynamically generate documents to be displayed on computers,
report generators dynamically generate pages to be printed out.

Although the DSL for the templates was textual and could easily be written by
hand, the end result would be something formatted and graphical and so a
graphical editor for the templates could offer significant advantages to
template designers. This was the purpose of the EQL editor: the user could
drag and drop various objects into the editor area.

Even though building a text editor or graphical editor is a lot of work, there
are no real inherent difficulties (apart from those originating in the
domain): many useful design patterns are applicable, such as the
\emph{model-view-controller} pattern and the \emph{command} pattern. The EQL
editor, however, was both: it offered both a textual view and a graphical view
and the user was free to switch between the two at will. One of the
requirements was that changes done in the visual view affected the textual
view only locally, leaving the source code unchanged as much as possible and
preserving layout and comments. This proved a very interesting challenge.

The solution we chose to solve this challenge was to have the parser not throw
away any information at all, preserving every single source token, including
whitespace and comments. Changes to the model then always meant changing both
the AST and the list of tokens that make up the source code, keeping them
synchronized. The solution is explained in detail in
\emph{Building a hybrid editor} \cite{vansteenbergen08HybridEditor}.

\section{Grote Trap}

The second related project is \emph{Grote Trap}, a library written by Jeroen
Leeuwestein and Martijn van Steenbergen for the 2007 Generic Programming
course at Utrecht University, taught by Johan Jeuring. Its purpose was to
provide an easy way to define expression languages and get functions for
converting between text selections and structural selections for free. This
was one of the projects that were available; we chose it because it reminded
us of the EQL editor in which similar functionality was available, but
specific to the EQL language. We found extending this to work for arbitrary
languages an interesting challenge.

As an example, consider the following datatype for expressions of
propositional logic:

\begin{code}
data Logic
  =  Var     String
  |  Or   [  Logic]
  |  And  [  Logic]
  |  Impl    Logic Logic
  |  Not     Logic
\end{code}

By defining an expression of type |Language Logic|, a grammar could be
specified and a parser and conversion functions were made available for free.
The language definition looked like this:

\begin{code}
logicLanguage :: Language Logic
logicLanguage = language
  { variable  = Just Var
  , operators =
      [  Unary    Not  Prefix  0  "!"
      ,  Assoc    And          1  "&&"
      ,  Assoc    Or           2  "||"
      ,  Binary   Impl InfixR  3  "->"
      ]
  }
\end{code}

The language definition ties the constructors to lexical constructs, providing
enough information for the generation of a parser. Because the available
constructs were limited to numbers, variables and unary and binary operators,
parsed expressions could be stored in a universal datatype with one
constructor for each type of construct. Not only were the specific operators
stored, the information regarding their positions in the input sentence was
also remembered. This allowed converting between textual and structural
selections of expressions for which a language definition was provided. Grote
Trap is available for download on Hackage.
\footnote{\url{http://hackage.haskell.org/package/GroteTrap}}

Although Grote Trap worked well for small expression languages, any grammar
that required more than just identifiers, numbers, and unary and binary
operators was very hard if not impossible to define. It is from this
deficiency that this thesis project arose: the goal of this work is to make
the selection conversion functions available automatically for any
context-free grammar, however elaborate.