add relevant research

[msc-thesis1617.git] / methods.dsl.tex

diff --git a/methods.dsl.tex b/methods.dsl.tex
index c28ed62..0ee9a24 100644 (file)
--- a/methods.dsl.tex
+++ b/methods.dsl.tex
@@ -1,59 +1,59 @@
-\section{\acrlong{EDSL}s}

 There are several techniques available for creating \glspl{EDSL}. Each of
 them have their own advantages and disadvantages such as extendability,
 typedness and view support. In the following subsections each of the main
 techniques are briefly explained.
 
 There are several techniques available for creating \glspl{EDSL}. Each of
 them have their own advantages and disadvantages such as extendability,
 typedness and view support. In the following subsections each of the main
 techniques are briefly explained.
 

-\subsection{Deep embedding}
+\section{Deep embedding}

 A deep \gls{EDSL} means that the language is represented as an \gls{ADT}. Views
 are functions that transform something to the datatype or the other way around.
 As an example we have the simple arithmetic \gls{EDSL} shown in
 A deep \gls{EDSL} means that the language is represented as an \gls{ADT}. Views
 are functions that transform something to the datatype or the other way around.
 As an example we have the simple arithmetic \gls{EDSL} shown in

-Listing~\ref{lst:exdeep}. Deep embedding has the advantage that it is very
-simple to build and the views are easy to make and add. However, there are also
-a few downsides.
+Listing~\ref{lst:exdeep}.

 
 \begin{lstlisting}[language=Clean,label={lst:exdeep},%
        caption={A minimal deep \gls{EDSL}}]
 :: DSL
 
 \begin{lstlisting}[language=Clean,label={lst:exdeep},%
        caption={A minimal deep \gls{EDSL}}]
 :: DSL

-       = LitI Int
-       | LitB Bool
-       | Var String
-       | Plus DSL DSL
+       = LitI  Int
+       | LitB  Bool
+       | Var   String
+       | Plus  DSL DSL

        | Minus DSL DSL
        | Minus DSL DSL

-       | And DSL DSL
-       | Eq DSL
+       | And   DSL DSL
+       | Eq    DSL

 \end{lstlisting}
 \end{lstlisting}

-
-The expressions created with this language are not type-safe. In the given
-language it is possible an expression such as \CI{Plus (LitI 4) (LitB True)}
-which to add a boolean to an integer. Evermore so, extending the \gls{ADT} is
-easy and convenient but extending the views accordingly is tedious and has to
-be done individually for all views.
+Deep embedding has the advantage that it is very simple to build and the views
+are easy to make and add. However, there are also a few downsides.  The
+expressions created with this language are not type-safe. In the given language
+it is possible an expression such as \CI{Plus (LitI 4) (LitB True)} which to
+add a boolean to an integer. Evermore so, extending the \gls{ADT} is easy and
+convenient but extending the views accordingly is tedious and has to be done
+individually for all views.

 
 The first downside of the type of \gls{EDSL} can be overcome by using
 
 The first downside of the type of \gls{EDSL} can be overcome by using

-\glspl{GADT}. Listing~\ref{lst:exdeepgadt} shows the same language, but
-type-safe with a \gls{GADT}\footnote{Note that \glspl{GADT} are not supported
-in \gls{Clean}. They can be simulated using bimaps}\todo{cite}. Unfortunately
-the lack of extendability stays a problem. If a language construct is added no
+\glspl{GADT}\cite{cheney_first-class_2003}. Listing~\ref{lst:exdeepgadt} shows
+the same language, but type-safe with a \gls{GADT}. \glspl{GADT} are not
+supported in the current version of \gls{Clean} and therefore the syntax is
+artificial. However, it has been shown that \glspl{GADT} can be simulated using
+bimaps or projection pairs\cite{cheney_lightweight_2002}. Unfortunately the
+lack of extendability stays a problem. If a language construct is added no

 compile time guarantee is given that all views support it.
 
 \begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
 compile time guarantee is given that all views support it.
 
 \begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%

-       caption={A minimal deep \gls{EDSL}}]
+       caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]

 :: DSL a
 :: DSL a

-       = LitI Int                     -> DSL Int
-       | LitB Bool                    -> DSL Bool
-       | Var String                   -> DSL Int
-       | Plus   (DSL Int) (DSL Int)   -> DSL Int
-       | Minus  (DSL Int) (DSL Int)   -> DSL Int
-       | And    (DSL Bool) (DSL Bool) -> DSL Bool
-       | E.e: Eq (DSL e) (DSL e)       -> DSL Bool   &  == e
+       =     LitI  Int                   -> DSL Int
+       |     LitB  Bool                  -> DSL Bool
+       | E.e: Var   String                -> DSL e
+       |     Plus  (DSL Int) (DSL Int)   -> DSL Int
+       |     Minus (DSL Int) (DSL Int)   -> DSL Int
+       |     And   (DSL Bool) (DSL Bool) -> DSL Bool
+       | E.e: Eq (DSL e) (DSL e)          -> DSL Bool &  == e

 \end{lstlisting}
 
 \end{lstlisting}
 

-\subsection{Shallow embedding}
+\section{Shallow embedding}

 In a shallowly \gls{EDSL} all language constructs are expressed as functions in
 In a shallowly \gls{EDSL} all language constructs are expressed as functions in

-the host language. Our example language then looks something like the code
-shown in Listing~\ref{lst:exshallow} if implementing the evaluator. Note that
-much of the internals of the language can be hidden away using monads.
+the host language. An evaluator view for our example language then looks
+something like the code shown in Listing~\ref{lst:exshallow}. Note that much of
+the internals of the language can be hidden using monads.

 
 \begin{lstlisting}[language=Clean,label={lst:exshallow},%
        caption={A minimal shallow \gls{EDSL}}]
 
 \begin{lstlisting}[language=Clean,label={lst:exshallow},%
        caption={A minimal shallow \gls{EDSL}}]


@@ -87,10 +87,46 @@ information for all the views. This will mean that every component will have to
 implement all views. This makes it slow for multiple views and complex to
 implement.
 
 implement all views. This makes it slow for multiple views and complex to
 implement.
 

-\subsection{Class based shallow embedding}
-\todo{while iTasks is also a DSL\ldots}
-\glspl{mTask} are expressed in a class based shallowly embedded \gls{EDSL}.
-There are two main types of \glspl{EDSL}.
-\todo{Small shallow embedded dsl intro}
-\todo{Small deep embedded dsl}
-\todo{Show that class based has the best of both worlds}
+\section{Class based shallow embedding}
+The third type of embedding is called class based shallow embedding and has the
+best of both shallow and deep embedding. In class based shallow embedding the
+language constructs are defined as type classes. The same language is shown
+with the new method in Listing~\ref{lst:exclassshallow}.
+
+This type of embedding inherits the easiness of adding views from shallow
+embedding. A view is just a different data type implementing one or more of the
+type classes as shown in the aforementioned Listing where an evaluator and a
+pretty printer are implemented.
+
+Just as with \glspl{GADT} in deep embedding type safety is guaranteed. Type
+constraints are enforced through phantom types. One can add as many phantom
+type as is necessary. Lastly, extensions can be added easily, just as in
+shallow embedding. When an extension is made in an existing class, all views
+must be updated accordingly to prevent possible runtime errors. When an
+extension is added in a new class this problem does not arise and views can
+choose to implement only parts of the collection of classes.
+
+\begin{lstlisting}[language=Clean,label={lst:exclassshallow},%
+       caption={A minimal class based shallow \gls{EDSL}}]
+:: Env   = ...            // Some environment
+:: Evaluator a = Evaluator (Env -> a)
+:: PrettyPrinter a = PP String
+
+class intArith where
+       lit   :: t -> v t             | toString t
+       add   :: (v t) (v t) -> (v t) | + t
+       minus :: (v t) (v t) -> (v t) | - t
+
+class boolArith where
+       and :: (v Bool) (v Bool) -> (v Bool)
+       eq  :: (v t)    (v t)    -> (v Bool) | == t
+
+instance intArith Evaluator where
+       lit x = \e->x
+       add x y = ...
+
+instance intArith PrettyPrinter where
+       lit x = toString x
+       add x y = x +++ "+" +++ y
+       ...
+\end{lstlisting}