methods.dsl.tex

   1 \section{\acrlong{EDSL}s}
   2 There are several techniques available for creating \glspl{EDSL}. Each of
   3 them have their own advantages and disadvantages such as extendability,
   4 typedness and view support. In the following subsections each of the main
   5 techniques are briefly explained.
   6
   7 \subsection{Deep embedding}
   8 A deep \gls{EDSL} means that the language is represented as an \gls{ADT}. Views
   9 are functions that transform something to the datatype or the other way around.
  10 As an example we have the simple arithmetic \gls{EDSL} shown in
  11 Listing~\ref{lst:exdeep}. Deep embedding has the advantage that it is very
  12 simple to build and the views are easy to make and add. However, there are also
  13 a few downsides.
  14
  15 \begin{lstlisting}[language=Clean,label={lst:exdeep},%
  16         caption={A minimal deep \gls{EDSL}}]
  17 :: DSL
  18         = LitI Int
  19         | LitB Bool
  20         | Var String
  21         | Plus DSL DSL
  22         | Minus DSL DSL
  23         | And DSL DSL
  24         | Eq DSL
  25 \end{lstlisting}
  26
  27 The expressions created with this language are not type-safe. In the given
  28 language it is possible an expression such as \CI{Plus (LitI 4) (LitB True)}
  29 which to add a boolean to an integer. Evermore so, extending the \gls{ADT} is
  30 easy and convenient but extending the views accordingly is tedious and has to
  31 be done individually for all views.
  32
  33 The first downside of the type of \gls{EDSL} can be overcome by using
  34 \glspl{GADT}. Listing~\ref{lst:exdeepgadt} shows the same language, but
  35 type-safe with a \gls{GADT}\footnote{Note that \glspl{GADT} are not supported
  36 in \gls{Clean}. They can be simulated using bimaps}\todo{cite}. Unfortunately
  37 the lack of extendability stays a problem. If a language construct is added no
  38 compile time guarantee is given that all views support it.
  39
  40 \begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
  41         caption={A minimal deep \gls{EDSL}}]
  42 :: DSL a
  43         = LitI Int                     -> DSL Int
  44         | LitB Bool                    -> DSL Bool
  45         | Var String                   -> DSL Int
  46         | Plus   (DSL Int) (DSL Int)   -> DSL Int
  47         | Minus  (DSL Int) (DSL Int)   -> DSL Int
  48         | And    (DSL Bool) (DSL Bool) -> DSL Bool
  49         | E.e: Eq (DSL e) (DSL e)       -> DSL Bool   &  == e
  50 \end{lstlisting}
  51
  52 \subsection{Shallow embedding}
  53 In a shallowly \gls{EDSL} all language constructs are expressed as functions in
  54 the host language. Our example language then looks something like the code
  55 shown in Listing~\ref{lst:exshallow} if implementing the evaluator. Note that
  56 much of the internals of the language can be hidden away using monads.
  57
  58 \begin{lstlisting}[language=Clean,label={lst:exshallow},%
  59         caption={A minimal shallow \gls{EDSL}}]
  60 :: Env   = ...            // Some environment
  61 :: DSL a = DSL (Env -> a)
  62
  63 Lit :: a -> DSL a
  64 Lit x = \e->x
  65
  66 Var :: String -> DSL Int
  67 Var i = \e->retrEnv e i
  68
  69 Plus :: (DSL Int) (DSL Int) -> DSL Int
  70 Plus x y = \e->x e + y e
  71
  72 ...
  73
  74 Eq :: (DSL a) (DSL a) -> DSL Bool | == a
  75 Eq x y = \e->x e + y e
  76 \end{lstlisting}
  77
  78 The advantage of shallowly embedding a language in a host language is the
  79 extendability. It is very easy to add functionality and compile time checks
  80 guarantee that the functionality is available. Moreover, the language is type
  81 safe as it is directly typed in the host language.
  82
  83 The downside of this method is extending the language with views. It is near
  84 impossible to add views to a shallowly embedded language. The only way of
  85 achieving this is by decorating the datatype for the \gls{EDSL} with all the
  86 information for all the views. This will mean that every component will have to
  87 implement all views. This makes it slow for multiple views and complex to
  88 implement.
  89
  90 \subsection{Class based shallow embedding}
  91
  92 \todo{while iTasks is also a DSL\ldots}
  93 \glspl{mTask} are expressed in a class based shallowly embedded \gls{EDSL}.
  94 There are two main types of \glspl{EDSL}.
  95 \todo{Small shallow embedded dsl intro}
  96 \todo{Small deep embedded dsl}
  97 \todo{Show that class based has the best of both worlds}