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}.
  12
  13 \begin{lstlisting}[language=Clean,label={lst:exdeep},%
  14         caption={A minimal deep \gls{EDSL}}]
  15 :: DSL
  16         = LitI  Int
  17         | LitB  Bool
  18         | Var   String
  19         | Plus  DSL DSL
  20         | Minus DSL DSL
  21         | And   DSL DSL
  22         | Eq    DSL
  23 \end{lstlisting}
  24 Deep embedding has the advantage that it is very simple to build and the views
  25 are easy to make and add. However, there are also a few downsides.  The
  26 expressions created with this language are not type-safe. In the given language
  27 it is possible an expression such as \CI{Plus (LitI 4) (LitB True)} which to
  28 add a boolean to an integer. Evermore so, extending the \gls{ADT} is easy and
  29 convenient but extending the views accordingly is tedious and has to be done
  30 individually for all views.
  31
  32 The first downside of the type of \gls{EDSL} can be overcome by using
  33 \glspl{GADT}\cite{cheney_first-class_2003}. Listing~\ref{lst:exdeepgadt} shows
  34 the same language, but type-safe with a \gls{GADT}. \glspl{GADT} are not
  35 supported in the current version of \gls{Clean} and therefore the syntax is
  36 artificial. However, it has been shown that \glspl{GADT} can be simulated using
  37 bimaps or projection pairs\cite{cheney_lightweight_2002}. Unfortunately the
  38 lack of extendability stays a problem. If a language construct is added no
  39 compile time guarantee is given that all views support it.
  40
  41 \begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
  42         caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]
  43 :: DSL a
  44         =     LitI  Int                   -> DSL Int
  45         |     LitB  Bool                  -> DSL Bool
  46         | E.e: Var   String                -> DSL e
  47         |     Plus  (DSL Int) (DSL Int)   -> DSL Int
  48         |     Minus (DSL Int) (DSL Int)   -> DSL Int
  49         |     And   (DSL Bool) (DSL Bool) -> DSL Bool
  50         | E.e: Eq (DSL e) (DSL e)          -> DSL Bool &  == e
  51 \end{lstlisting}
  52
  53 \subsection{Shallow embedding}
  54 In a shallowly \gls{EDSL} all language constructs are expressed as functions in
  55 the host language. An evaluator view for our example language then looks
  56 something like the code shown in Listing~\ref{lst:exshallow}. Note that much of
  57 the internals of the language can be hidden using monads.
  58
  59 \begin{lstlisting}[language=Clean,label={lst:exshallow},%
  60         caption={A minimal shallow \gls{EDSL}}]
  61 :: Env   = ...            // Some environment
  62 :: DSL a = DSL (Env -> a)
  63
  64 Lit :: a -> DSL a
  65 Lit x = \e->x
  66
  67 Var :: String -> DSL Int
  68 Var i = \e->retrEnv e i
  69
  70 Plus :: (DSL Int) (DSL Int) -> DSL Int
  71 Plus x y = \e->x e + y e
  72
  73 ...
  74
  75 Eq :: (DSL a) (DSL a) -> DSL Bool | == a
  76 Eq x y = \e->x e + y e
  77 \end{lstlisting}
  78
  79 The advantage of shallowly embedding a language in a host language is the
  80 extendability. It is very easy to add functionality and compile time checks
  81 guarantee that the functionality is available. Moreover, the language is type
  82 safe as it is directly typed in the host language.
  83
  84 The downside of this method is extending the language with views. It is near
  85 impossible to add views to a shallowly embedded language. The only way of
  86 achieving this is by decorating the datatype for the \gls{EDSL} with all the
  87 information for all the views. This will mean that every component will have to
  88 implement all views. This makes it slow for multiple views and complex to
  89 implement.
  90
  91 \subsection{Class based shallow embedding}
  92 The third type of embedding is called class based shallow embedding and has the
  93 best of both shallow and deep embedding. In class based shallow embedding the
  94 language constructs are defined as type classes. The same language is shown
  95 with the new method in Listing~\ref{lst:exclassshallow}.
  96
  97 This type of embedding inherits the easiness of adding views from shallow
  98 embedding. A view is just a different data type implementing one or more of the
  99 type classes as shown in the aforementioned Listing where an evaluator and a
 100 pretty printer are implemented.
 101
 102 Just as with \glspl{GADT} in deep embedding type safety is guaranteed. Type
 103 constraints are enforced through phantom types. One can add as many phantom
 104 type as is necessary. Lastly, extensions can be added easily, just as in
 105 shallow embedding. When an extension is made in an existing class, all views
 106 must be updated accordingly to prevent possible runtime errors. When an
 107 extension is added in a new class this problem does not arise and views can
 108 choose to implement only parts of the collection of classes.
 109
 110 \begin{lstlisting}[language=Clean,label={lst:exclassshallow},%
 111         caption={A minimal class based shallow \gls{EDSL}}]
 112 :: Env   = ...            // Some environment
 113 :: Evaluator a = Evaluator (Env -> a)
 114 :: PrettyPrinter a = PP String
 115
 116 class intArith where
 117         lit   :: t -> v t             | toString t
 118         add   :: (v t) (v t) -> (v t) | + t
 119         minus :: (v t) (v t) -> (v t) | - t
 120
 121 class boolArith where
 122         and :: (v Bool) (v Bool) -> (v Bool)
 123         eq  :: (v t)    (v t)    -> (v Bool) | == t
 124
 125 instance intArith Evaluator where
 126         lit x = \e->x
 127         add x y = ...
 128
 129 instance intArith PrettyPrinter where
 130         lit x = toString x
 131         add x y = x +++ "+" +++ y
 132         ...
 133 \end{lstlisting}