X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=methods.dsl.tex;h=1a153b1b5b9ef9aa76a61bc66776396d6f36b055;hb=7694dfaa240c6dd9af2f1ac8880f0fb1d7f38324;hp=262f228685e5f230600b81fe690d05990ecea0fe;hpb=130cec648788a4660c91ffed6c1c2fb682413055;p=msc-thesis1617.git

diff --git a/methods.dsl.tex b/methods.dsl.tex
index 262f228..1a153b1 100644
--- a/methods.dsl.tex
+++ b/methods.dsl.tex
@@ -1,97 +1,135 @@
-\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.
-
-\subsection{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
-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.
-
-\begin{lstlisting}[language=Clean,label={lst:exdeep},%
+An \gls{EDSL} is a language embedded in a host language. \glspl{EDSL} can have
+one or more backends or views. Commonly used views are pretty printing,
+compiling, simulating, verifying and proving the program.  There are several
+techniques available for creating \glspl{EDSL}. Each of them have their own
+advantages and disadvantages in terms of extendability, typedness and view
+support. In the following subsections each of the main techniques are briefly
+explained.
+
+\section{Deep embedding}
+A deep \gls{EDSL} is a language 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}.
+
+\begin{lstlisting}[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
-	| And DSL DSL
-	| Eq DSL
+	| And   DSL DSL
+	| Eq    DSL
 \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.
-
-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
-compile time guarantee is given that all views support it.
-
-\begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
-	caption={A minimal deep \gls{EDSL}}]
+Deep embedding has the advantage that it is very simple to build and the views
+are easy to add. To the downside, the expressions created with this language
+are not type-safe. In the given language it is possible to create an expression
+such as \CI{Plus (LitI 4) (LitB True)} that adds a 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 this type of \gls{EDSL} can be overcome by using
+\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
+hypothetical. 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 remains a problem. If a language construct is added,
+no compile time guarantee is given that all views support it.
+
+\begin{lstlisting}[label={lst:exdeepgadt},%
+	caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]
 :: 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}
 
-\subsection{Shallow embedding}
+\section{Shallow embedding}
 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},%
+\begin{lstlisting}[label={lst:exshallow},%
 	caption={A minimal shallow \gls{EDSL}}]
 :: Env   = ...            // Some environment
 :: DSL a = DSL (Env -> a)
 
 Lit :: a -> DSL a
-Lit x = \e->x
+Lit x = \e -> x
 
 Var :: String -> DSL Int
-Var i = \e->retrEnv e i
+Var i = \e -> retrEnv e i
 
 Plus :: (DSL Int) (DSL Int) -> DSL Int
-Plus x y = \e->x e + y e
+Plus x y = \e -> x e + y e
 
 ...
 
 Eq :: (DSL a) (DSL a) -> DSL Bool | == a
-Eq x y = \e->x e + y e
+Eq x y = \e -> x e + y e
 \end{lstlisting}
 
-The advantage of shallowly embedding a language in a host language is the
+The advantage of shallowly embedding a language in a host language is its
 extendability. It is very easy to add functionality and compile time checks
-guarantee that the functionality is available. Moreover, the language is type
-safe as it is directly typed in the host language.
+of the host language guarantee whether the functionality is available when used.
+Moreover, the language is type safe as it is directly typed in the host
+language.
 
-The downside of this method is extending the language with views. It is near
+The downside of this method is extending the language with views. It is nearly
 impossible to add views to a shallowly embedded language. The only way of
 achieving this is by decorating the datatype for the \gls{EDSL} with all the
 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 all views rendering 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
+advantages 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 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}[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}