dsl/dsl_techniques.tex

   1 \documentclass[../thesis.tex]{subfiles}
   2
   3 \begin{document}
   4 \ifSubfilesClassLoaded{
   5         \pagenumbering{arabic}
   6 }{}
   7
   8 \chapter{\texorpdfstring{\Acrshort{DSL}}{DSL} embedding techniques}%
   9 \label{chp:dsl_embedding_techniques}%
  10 An \gls{EDSL} is a language embedded in a host language created for a specific domain\todo{citation needed?}.
  11 Properties such as referential transparency, minimal syntax and \glspl{ADT} make \gls{FP} languages excellent candidates for hosting \glspl{EDSL}.
  12 Terms in an \glspl{EDSL} can have multiple interpretations---also called backends or views---i.e.\ preferably, a term in the \gls{DSL} is just an interface.
  13 Commonly used intepretations are printing, compiling, simulating, optimising, verifying, proving the program\etc.
  14 There are two main flavours of embedding \glspl{DSL}, deep---also called tagged---embedding and shallow---also called tagless---embedding.
  15
  16 \Cref{sec:deep_embedding} shows the basics of deep embedding.
  17 \Cref{sec:shallow_embedding} shows the basics of shallow embedding including tagless embedding.
  18 \Cref{sec:compare_embedding} compares the embedding technique.
  19
  20 Both flavours have their strengths and weaknesses and both flavours can be improved in order to mitigate (some of the) downsides.
  21
  22 \begin{table}[ht]
  23         \begin{threeparttable}[b]
  24                 \caption{Comparison of embedding techniques, adapted from \citet[Sec.~3.6]{sun_compositional_2022}}%
  25                 \label{tbl:dsl_comparison}
  26                 \begin{tabular}{lllllll}
  27                         \toprule
  28                                                                         & Shallow & Deep  & Hybrid          & Poly           & Comp. & Classy\\
  29                         \midrule
  30                         Transcoding free        & yes     & yes   & no              & yes            & yes            & yes\\
  31                         Linguistic reuse        & yes     & no    & partly\tnote{1} & yes            & yes            & no?\\
  32                         Extend constructs       & yes     & no    & partly\tnote{1} & yes            & yes            & yes\\
  33                         Extend interpretations  & no      & yes   & yes             & yes            & yes            & yes\\
  34                         Transformations         & no      & yes   & yes             & maybe\tnote{2} & maybe\tnote{2} & yes\\
  35                         Modular dependencies    & no      & maybe & maybe           & yes            & yes            & yes\\
  36                         Nested pattern matching & no      & yes   & yes             & no             & maybe          & maybe\tnote{3}\\
  37                         Type safe               & yes     & maybe & no              & yes            & yes            & yes\\
  38                         \bottomrule
  39                 \end{tabular}
  40                 \begin{tablenotes}
  41                         \item [1] Only in the shallowly embedded part.
  42                         \item [2] Transformations require some ingenuity and are sometimes awkward to write.
  43                         \item [3] It requires some---safe---form of dynamic typing.
  44                 \end{tablenotes}
  45         \end{threeparttable}
  46 \end{table}
  47
  48 In the following sections both techniques are explained.
  49 As an example, a simple language with integers, booleans and some arithmetic operators is used as a running example.
  50
  51 \section{Deep embedding}\label{sec:deep_embedding}
  52 In a deeply embedded \gls{DSL}, the language terms are represented as data type{(s)} in the host language.
  53 Therefore, interpretations of the terms are functions that operate on these data types.
  54 Definition~\ref{lst:exdeep} shows an implementation for the example \gls{DSL}.
  55
  56 \begin{lstHaskell}[label={lst:exdeep},caption={A deeply embedded expression \gls{DSL}.}]
  57 data Value = I Int | B Bool
  58 data Expr
  59         = Lit  Value
  60         | Plus Expr Expr
  61         | Eq   Expr Expr
  62   deriving Show
  63 \end{lstHaskell}
  64
  65 Implementing a printer for the language is straightforward, we just define a function that transforms the term to a string.
  66
  67 \begin{lstHaskell}[caption={A printer for the deeply embedded expression \gls{DSL}.}]
  68 print :: Expr -> String
  69 print (Lit i)    = show i
  70 print (Plus l r) = "(" ++ print l ++ "+" ++ print r ++ ")"
  71 print (Eq l r)   = "(" ++ print l ++ "==" ++ print r ++ ")"
  72 \end{lstHaskell}
  73
  74 Adding a construct---for example subtraction---reveals the Achilles' heel of deep embedding, namely that we need to revisit the original data type \emph{and} all the existing views.
  75 I.e.\ we need to add \haskellinline{| Sub Expr Expr} to the \haskellinline{Expr} data type.
  76 Furthermore, we need to add \haskellinline{print (Sub l r) = ...} to the \haskellinline{print} view in order to not end up with a partial function.
  77 This limitation can be overcome by lifting the views to classes (See \cref{chp:classy_deep_embedding}).
  78
  79 Implementing an evaluator for the language is possible without touching any original code, we just add a function operating on the \haskellinline{Expr} data type.
  80 To store variables, it has an extra environment argument.
  81 Here another downside of basic deep embedding arises immediately, the expressions are not typed, and therefore there has to be some type checking in the evaluation code.
  82 Luckily this problem can be overcome by switching from regular \glspl{ADT} to \glspl{GADT}, resulting in the following data type and evaluator.
  83
  84 \begin{lstHaskell}[caption={An evaluator for the deeply embedded expression \gls{DSL}.}]
  85 eval :: Expr -> Value
  86 eval (Lit i)    = i
  87 eval (Plus l r) = case (eval l, eval r) of
  88     (Lit (I l), Lit (I r)) -> I (l+r))
  89         (l, r)       -> error ("Can't add " ++ show l ++ " to " ++ show r)
  90 eval (Eq l r) = case (eval l, eval r) of
  91     (Lit (I l), Lit (I r)) -> B (l==r)
  92     (Lit (B l), Lit (B r)) -> B (l==r)
  93         (l, r)       -> error ("Can't compare " ++ show l ++ " to " ++ show r)
  94 \end{lstHaskell}
  95
  96 \subsection{Deep embedding with \texorpdfstring{\acrshortpl{GADT}}{GADTs}}
  97 Deep embedding has the advantage that it is easy to build and views are easy to add.
  98 On the downside, the expressions created with this language are not necessarily type-safe.
  99 In the given language it is possible to create an expression such as \haskellinline{Plus (LitI 4) (LitB True)} that adds a boolean to an integer.
 100 Extending the \gls{ADT} is easy and convenient but extending the views accordingly is tedious since it has to be done individually for all views.
 101
 102 The first downside of this type of \gls{EDSL} can be overcome by using \glspl{GADT}~\citep{cheney_first-class_2003}.
 103 \Cref{lst:exdeepgadt} shows the same language, but type-safe with a \gls{GADT}.
 104 \glspl{GADT} are not supported in the current version of \gls{CLEAN} and therefore the syntax is hypothetical (See \todo{insert link to appendix}).
 105 However, it has been shown that \glspl{GADT} can be simulated using bimaps or projection pairs~\citep{cheney_first-class_2003}.
 106 Unfortunately the lack of extendability remains a problem.
 107 If a language construct is added, no compile time guarantee can be given that all views support it.
 108
 109 \begin{lstHaskell}[label={lst:exdeepgadt},caption={A deeply embedded expression \gls{DSL} using \glspl{GADT}.}]
 110 data Expr a where
 111     Lit  :: Show a => a -> Expr a
 112     Plus :: Num a  => Expr a -> Expr a -> Expr a
 113     Eq   :: Eq a   => Expr a -> Expr a -> Expr Bool
 114
 115 eval :: Expr a -> a
 116 eval (Lit i)    = i
 117 eval (Plus l r) = eval l + eval r
 118 eval (Eq l r)   = eval l == eval r
 119 \end{lstHaskell}
 120
 121 \section{Shallow embedding}
 122 In a shallowly \gls{EDSL} all language constructs are expressed as functions in the host language.
 123 An evaluator view for the example language then can be implemented as the code shown in \cref{lst:exshallow}.
 124 Note that much of the internals of the language can be hidden using monads.
 125
 126 \begin{lstHaskell}[label={lst:exshallow}, caption={A minimal shallow \gls{EDSL}.}]
 127 type Env   = String -> Int
 128 type DSL a = Env -> a
 129
 130 Lit :: a -> DSL a
 131 Lit x = \e->x
 132
 133 Var :: String -> DSL Int
 134 Var i = \e->retrEnv e i
 135
 136 Plus :: DSL Int -> DSL Int -> DSL Int
 137 Plus x y = \e->x e + y e
 138
 139 Eq :: Eq a => DSL a -> DSL a -> DSL Bool
 140 Eq x y = \e->x e == y e
 141 \end{lstHaskell}
 142
 143 One of the advantages of shallowly embedding a language in a host language is its extendability.
 144 It is very easy to add functionality because the compile time checks of the host language guarantee whether or not the functionality is available when used.
 145 Moreover, the language is type safe as it is directly typed in the host language, i.e.\ \cleaninline{Lit True +. Lit 4} is rejected.
 146 Another advantage is the intimate link with the host language, allowing for a lot more linguistic reuse such as the support of implicit sharing~\cite{krishnamurthi_linguistic_2001}.
 147
 148 The downside of this method is extending the language with views.
 149 It is nearly impossible to add views to a shallowly embedded language.
 150 The only way of achieving this is by reimplementing all functions so that they run all backends at the same time.
 151 This will mean that every component will have to implement all views rendering it slow for multiple views and complex to implement.
 152
 153 \subsection{Tagless-final embedding}\label{ssec:tagless}
 154
 155
 156 \section{Comparison}
 157 \todo{cite compositional DSLs}
 158
 159 \input{subfilepostamble}
 160 \end{document}