edsl.deep.tex

   1 A deep \gls{EDSL} is a language represented as an \gls{ADT}. Views are
   2 functions that transform something to the datatype or the other way around. As
   3 an example, take the simple arithmetic \gls{EDSL} shown in
   4 Listing~\ref{lst:exdeep}.
   5
   6 \begin{lstlisting}[language=Clean,label={lst:exdeep},%
   7         caption={A minimal deep \gls{EDSL}}]
   8 :: DSL
   9         = LitI  Int
  10         | LitB  Bool
  11         | Var   String
  12         | Plus  DSL DSL
  13         | Minus DSL DSL
  14         | And   DSL DSL
  15         | Eq    DSL
  16 \end{lstlisting}
  17
  18 Deep embedding has the advantage that it is easy to build and views
  19 are easy to add. To the downside, the expressions created with this language
  20 are not type-safe. In the given language it is possible to create an expression
  21 such as \CI{Plus (LitI 4) (LitB True)} that adds a boolean to an integer.
  22 Evermore so, extending the \gls{ADT} is easy and convenient but extending the
  23 views accordingly is tedious and has to be done individually for all views.
  24
  25 The first downside of this type of \gls{EDSL} can be overcome by using
  26 \glspl{GADT}~\cite{cheney_first-class_2003}. Listing~\ref{lst:exdeepgadt} shows
  27 the same language, but type-safe with a \gls{GADT}. \glspl{GADT} are not
  28 supported in the current version of \gls{Clean} and therefore the syntax is
  29 hypothetical. However, it has been shown that \glspl{GADT} can be simulated
  30 using bimaps or projection pairs~\cite{cheney_lightweight_2002}. Unfortunately
  31 the lack of extendability remains a problem. If a language construct is added,
  32 no compile time guarantee is given that all views support it.
  33
  34 \begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
  35         caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]
  36 :: DSL a
  37         =     LitI  Int                   -> DSL Int
  38         |     LitB  Bool                  -> DSL Bool
  39         | E.e: Var   String                -> DSL e
  40         |     Plus  (DSL Int) (DSL Int)   -> DSL Int
  41         |     Minus (DSL Int) (DSL Int)   -> DSL Int
  42         |     And   (DSL Bool) (DSL Bool) -> DSL Bool
  43         | E.e: Eq (DSL e) (DSL e)          -> DSL Bool &  == e
  44 \end{lstlisting}