methods.dsl.tex

   1 An \gls{EDSL} is a language embedded in a host language. \glspl{EDSL} can have
   2 one or more backends or views. Commonly used views are pretty printing,
   3 compiling, simulating, verifying and proving the program.  There are several
   4 techniques available for creating \glspl{EDSL}. They all have their own
   5 advantages and disadvantages in terms of extendability, typedness and view
   6 support. In the following subsections each of the main techniques are briefly
   7 explained.
   8
   9 \section{Deep embedding}
  10 A deep \gls{EDSL} is a language represented as an \gls{ADT}. Views are
  11 functions that transform something to the datatype or the other way around. As
  12 an example, take the simple arithmetic \gls{EDSL} shown in
  13 Listing~\ref{lst:exdeep}.
  14
  15 \begin{lstlisting}[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 Deep embedding has the advantage that it is easy to build and views
  28 are easy to add. To the downside, the expressions created with this language
  29 are not type-safe. In the given language it is possible to create an expression
  30 such as \CI{Plus (LitI 4) (LitB True)} that adds a boolean to an integer.
  31 Evermore so, extending the \gls{ADT} is easy and convenient but extending the
  32 views accordingly is tedious and has to be done individually for all views.
  33
  34 The first downside of this type of \gls{EDSL} can be overcome by using
  35 \glspl{GADT}~\cite{cheney_first-class_2003}. Listing~\ref{lst:exdeepgadt} shows
  36 the same language, but type-safe with a \gls{GADT}. \glspl{GADT} are not
  37 supported in the current version of \gls{Clean} and therefore the syntax is
  38 hypothetical. However, it has been shown that \glspl{GADT} can be simulated
  39 using bimaps or projection pairs~\cite{cheney_lightweight_2002}. Unfortunately
  40 the lack of extendability remains a problem. If a language construct is added,
  41 no compile time guarantee is given that all views support it.
  42
  43 \begin{lstlisting}[label={lst:exdeepgadt},%
  44         caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]
  45 :: DSL a
  46         =     LitI  Int                   -> DSL Int
  47         |     LitB  Bool                  -> DSL Bool
  48         | E.e: Var   String                -> DSL e
  49         |     Plus  (DSL Int) (DSL Int)   -> DSL Int
  50         |     Minus (DSL Int) (DSL Int)   -> DSL Int
  51         |     And   (DSL Bool) (DSL Bool) -> DSL Bool
  52         | E.e: Eq (DSL e) (DSL e)          -> DSL Bool &  == e
  53 \end{lstlisting}
  54
  55 \section{Shallow embedding}
  56 In a shallow \gls{EDSL} all language constructs are expressed as functions in
  57 the host language. An evaluator view for the example language then can be
  58 implemented as the code shown in Listing~\ref{lst:exshallow}. Note that much of
  59 the internals of the language can be hidden using monads.
  60
  61 \begin{lstlisting}[label={lst:exshallow},%
  62         caption={A minimal shallow \gls{EDSL}}]
  63 :: Env   = ...            // Some environment
  64 :: DSL a = DSL (Env -> a)
  65
  66 Lit :: a -> DSL a
  67 Lit x = \e -> x
  68
  69 Var :: String -> DSL Int
  70 Var i = \e -> retrEnv e i
  71
  72 Plus :: (DSL Int) (DSL Int) -> DSL Int
  73 Plus x y = \e -> x e + y e
  74
  75 ...
  76
  77 Eq :: (DSL a) (DSL a) -> DSL Bool | == a
  78 Eq x y = \e -> x e + y e
  79 \end{lstlisting}
  80
  81 The advantage of shallowly embedding a language in a host language is its
  82 extendability. It is very easy to add functionality and compile time checks
  83 of the host language guarantee whether or not the functionality is available
  84 when used. Moreover, the language is type safe as it is directly typed in the
  85 host language.
  86
  87 The downside of this method is extending the language with views. It is nearly
  88 impossible to add views to a shallowly embedded language. The only way of
  89 achieving this is by decorating the datatype for the \gls{EDSL} with all the
  90 information for all the views. This will mean that every component will have to
  91 implement all views rendering it slow for multiple views and complex to
  92 implement.
  93
  94 \section{Class based shallow embedding}
  95 The third type of embedding is called class-based shallow embedding and has the
  96 advantages of both shallow and deep embedding. In class-based shallow embedding
  97 the language constructs are defined as type classes. This language is shown
  98 with the new method in Listing~\ref{lst:exclassshallow}.
  99
 100 This type of embedding inherits the ease of adding views from shallow
 101 embedding. A view is just a different data type implementing one or more of the
 102 type classes as shown in the aforementioned Listing where an evaluator and a
 103 pretty printer are implemented.
 104
 105 Just as with \glspl{GADT}, type safety is guaranteed in deep embedding. Type
 106 constraints are enforced through phantom types. One can add as many phantom
 107 types as necessary. Lastly, extensions can be added easily, just as in
 108 shallow embedding. When an extension is made in an existing class, all views
 109 must be updated accordingly to prevent possible runtime errors. When an
 110 extension is added in a new class, this problem does not arise and views can
 111 choose to implement only parts of the collection of classes.
 112
 113 In contrast to deep embedding, it is very well possible to have multiple views
 114 applied on the same expression. This is also shown in the following listing.
 115
 116 \begin{lstlisting}[label={lst:exclassshallow},%
 117         caption={A minimal class based shallow \gls{EDSL}}]
 118 :: Env   = ...            // Some environment
 119 :: Evaluator a = Evaluator (Env -> a)
 120 :: PrettyPrinter a = PP String
 121
 122 class intArith where
 123         lit   :: t -> v t             | toString t
 124         add   :: (v t) (v t) -> (v t) | + t
 125         minus :: (v t) (v t) -> (v t) | - t
 126
 127 class boolArith where
 128         and :: (v Bool) (v Bool) -> (v Bool)
 129         eq  :: (v t)    (v t)    -> (v Bool) | == t
 130
 131 instance intArith Evaluator where
 132         lit x = \e->x
 133         add x y = ...
 134
 135 instance intArith PrettyPrinter where
 136         lit x = toString x
 137         add x y = x +++ "+" +++ y
 138         ...
 139
 140 ...
 141
 142 Start :: (PP String, Bool)
 143 Start = (print e0, eval e0)
 144 where
 145         e0 :: a Bool | intArith, boolArith a
 146         e0 = eq (lit 42) (lit 21 +. lit 21)
 147
 148         print (PP p) = p
 149         eval (Evaluator e) env = e env
 150 \end{lstlisting}