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