dsl/first.tex

   1 \documentclass[../thesis.tex]{subfiles}
   2
   3 \input{subfilepreamble}
   4
   5 \setcounter{chapter}{2}
   6
   7 \begin{document}
   8 \input{subfileprefix}
   9 \chapter{First-class data types in shallow embedded domain-specific languages using metaprogramming}%
  10 \label{chp:first-class_datatypes}%
  11 \begin{chapterabstract}
  12         \Gls{FP} languages are excellent for hosting \glspl{EDSL} because of their rich type systems, minimal syntax, and referential transparency.
  13         However, data types defined in the host language are not automatically available in the embedded language.
  14         To do so, all the operations on the data type must be ported to the \gls{EDSL} resulting in a lot of boilerplate.
  15
  16         This chapter shows that by using metaprogramming, all first-order user-defined data types can be automatically made first class in shallow \glspl{EDSL}.
  17         We show this by providing an implementation in \gls{TH} for a typical \gls{DSL} with two different semantics.
  18         Furthermore, we show that by utilising quasiquotation, there is hardly any burden on the syntax.
  19         Finally, the chapter also serves as a gentle introduction to \gls{TH}.
  20 \end{chapterabstract}
  21
  22 \section{Introduction}
  23 \Gls{FP} languages are excellent candidates for hosting \glspl{EDSL} because of their rich type systems, minimal syntax, and referential transparency.
  24 By expressing the language constructs in the host language, the parser, the type checker, and the run time can be inherited from the host language.
  25 Unfortunately, data types defined in the host language are not automatically available in the \gls{EDSL}.
  26
  27 The two main strategies for embedding \glspl{DSL} in \pgls{FP} language are deep embedding (also called initial) and shallow embedding (also called final).
  28 Deep embedding represents the constructs in the language as data types and the semantics as functions over these data types.
  29 This makes extending the language with new semantics effortless: just add another function.
  30 In contrast, adding language constructs requires changing the data type and updating all existing semantics to support this new construct.
  31 Shallow embedding on the other hand models the language constructs as functions with the semantics embedded.
  32 Consequently, adding a construct is easy, i.e.\ it only entails adding another function.
  33 Contrarily, adding semantics requires adapting all language constructs.
  34 Lifting the functions to type classes, i.e.\ parametrising the constructs over the semantics, allows extension of the language both in constructs and in semantics orthogonally. This advanced style of embedding is called tagless-final or class-based shallow embedding \citep{kiselyov_typed_2012}.
  35
  36 While it is often possible to lift values of a user-defined data type to a value in the \gls{DSL}, it is not possible to interact with it using \gls{DSL} constructs, since they are not first-class citizens.
  37
  38 Concretely, it is not possible to
  39 \begin{enumerate*}
  40         \item construct values from expressions using a constructor,
  41         \item deconstruct values into expressions using a deconstructor or pattern matching,
  42         \item test which constructor the value holds.
  43 \end{enumerate*}
  44 The functions for this are simply not available automatically in the embedded language.
  45 For some semantics---such as an interpreter---it is possible to directly lift the functions from the host language to the \gls{DSL}.
  46 In other cases---e.g.\ \emph{compiling} \glspl{DSL} such as a compiler or a printer---this is not possible \citep{elliott_compiling_2003}. %the torget this is not possible. Cannot just be lifted from the host language to the \gls{DSL} so it requires a lot of boilerplate to define and implement them.
  47 Thus, all the operations on the data type have to be defined by hand requiring a lot of plumbing and resulting in a lot of boilerplate code.
  48
  49 To relieve the burden of adding all these functions, metaprogramming\nobreak---\nobreak\hskip0pt and custom quasiquoters---can be used.
  50 Metaprogramming entails that some parts of the program are generated by a program itself, i.e.\ the program is data.
  51 Quasiquotation is a metaprogramming mechanism that allows entering verbatim code for which a---possibly user defined---translation is used to convert the verbatim code to host language \gls{AST} nodes.
  52 Metaprogramming allows functions to be added to the program at compile time based on the structure of user-defined data types.
  53
  54 \subsection{Contributions}
  55 This chapter shows that with the use of metaprogramming, all first-order user-defined data types can automatically be made first class for shallow \glspl{EDSL}.
  56 It does so by providing an implementation in \gls{TH} for a typical \gls{DSL} with two different semantics: an interpreter and a pretty printer.
  57 Furthermore, we show that by utilising quasiquotation, there is hardly any burden on the syntax.
  58 Finally, the chapter also serves as a gentle introduction to \gls{TH} and reflects on the process of using \gls{TH}.
  59
  60 \section{Tagless-final embedding}%
  61 \label{sec:tagless-final}
  62 Tagless-final embedding is an upgrade to standard shallow embedding achieved by lifting all language construct functions to type classes.
  63 As a result, views on the \gls{DSL} are data types implementing these classes.
  64
  65 To illustrate the technique, a simple \gls{DSL}, a language consisting of literals and addition, is outlined.
  66 This language, implemented according to the tagless-final style \citep{carette_finally_2009} in \gls{HASKELL} \citep{peyton_jones_haskell_2003} consists initially only of one type class containing two functions.
  67 The \haskellinline{lit} function lifts values from the host language to the \gls{DSL} domain.
  68 The class constraint \haskellinline{Show} is enforced on the type variable \haskellinline{a} to make sure that the value can be printed.
  69 The infix function \haskellinline{+.} represents the addition of two expressions in the \gls{DSL}.
  70
  71 \begin{lstHaskell}
  72 class Expr v where
  73     lit :: Show a => a -> v a
  74     (+.) :: Num a => v a -> v a -> v a
  75 infixl 6 +.
  76 \end{lstHaskell}
  77
  78 The implementation of a view on the \gls{DSL} is achieved by implementing the type classes with the data type representing the view.
  79 In the case of our example \gls{DSL}, an interpreter accounting for failure may be implemented as an instance for the \haskellinline{Maybe} type.
  80 The standard infix functor application and infix sequential application are used so that potential failure is abstracted away from\footnotemark.
  81 \begin{lrbox}{\LstBox}
  82         \begin{lstHaskell}[frame=]
  83 <$> ::   (a -> b) -> f a -> f b
  84 <*> :: f (a -> b) -> f a -> f b
  85 infixl 4 <$>, <*>\end{lstHaskell}
  86 \end{lrbox}
  87 \footnotetext{\usebox{\LstBox}}
  88
  89 \begin{lstHaskell}
  90 instance Expr Maybe where
  91     lit a = Just a
  92     (+.) l r = (+) <$> l <*> r
  93 \end{lstHaskell}
  94
  95 \subsection{Adding language constructs}
  96 To add an extra language construct we define a new class housing it.
  97 For example, to add division we define a new class as follows:
  98
  99 \begin{lstHaskell}
 100 class Div v where
 101     (/.) :: Integral a => v a -> v a -> v a
 102 infixl 7 /.
 103 \end{lstHaskell}
 104
 105 Division is an operation that is undefined if the right operand is equal to zero.
 106 To capture this behaviour, the \haskellinline{Nothing} constructor from \haskellinline{Maybe} is used to represent errors.
 107 Both sides of the division operator are evaluated.
 108 If the right-hand side is zero, the division is not performed and an error is returned instead:
 109
 110 \begin{lstHaskell}
 111 instance Div Maybe where
 112     (/.) l r = l >>= \x->r >>= \y->
 113         if y == 0 then Nothing else Just (x `div` y)
 114 \end{lstHaskell}
 115
 116 \subsection{Adding semantics}
 117 To add semantics to the \gls{DSL}, the existing classes are implemented with a novel data type representing the view on the \gls{DSL}.
 118 First a data type representing the semantics is defined. In this case, the printer is kept very simple for brevity and just defined as a \haskellinline{newtype} of a string to store the printed representation\footnotemark.
 119 \footnotetext{%
 120         In this case a \haskellinline{newtype} is used instead of regular \haskellinline{data} declarations.
 121         \haskellinline{newtype}s are special data types only consisting a single constructor with one field to which the type is isomorphic.
 122         During compilation the constructor is completely removed resulting in no overhead \citep[\citesection{4.2.3}]{peyton_jones_haskell_2003}.
 123 }
 124 Since the language is typed, the printer data type has to have a type variable, but it is only used during typing---i.e.\ a phantom type \citep{leijen_domain_2000}:
 125
 126 \begin{lstHaskell}
 127 newtype Printer a = P { runPrinter :: String }
 128 \end{lstHaskell}
 129
 130 The class instances for \haskellinline{Expr} and \haskellinline{Div} for the pretty printer are straightforward and as follows:
 131
 132 \begin{lstHaskell}
 133 instance Expr Printer where
 134     lit a = P (show a)
 135     (+.) l r = P ("(" ++ runPrinter l
 136                ++ "+" ++ runPrinter r ++ ")")
 137
 138 instance Div Printer where
 139     (/.) l r = P ("(" ++ runPrinter l
 140                ++ "/" ++ runPrinter r ++ ")")
 141 \end{lstHaskell}
 142
 143 \subsection{Functions}
 144 Adding functions to the language is achieved by adding a multi-parameter class to the \gls{DSL}.
 145 The type of the class function allows for the implementation to only allow first-order functions by supplying the arguments in a tuple.
 146 Furthermore, with the \haskellinline{:-} operator the syntax becomes useable.
 147 Finally, by defining the functions as a \gls{HOAS} type safety is achieved \citep{pfenning_higher-order_1988,chlipala_parametric_2008}.
 148 The complete definition looks as follows:
 149
 150 \begin{lstHaskell}
 151 class Function a v where
 152     fun :: ((a -> v s) -> In (a -> v s) (v u)) -> v u
 153 data In a b = a :- b
 154 infix 1 :-
 155 \end{lstHaskell}
 156
 157 The \haskellinline{Function} type class is now used to define functions with little syntactic overhead\footnote{The \GHCmod{BlockArguments} extension of \gls{GHC} is used to reduce the number of brackets that allows lambda's to be an argument to a function without brackets}.
 158 The following listing shows an expression in the \gls{DSL} utilising two user-defined functions:
 159
 160 \begin{lstHaskell}
 161    fun \increment-> (\x     ->x +. lit 1)
 162 :- fun \divide->    (\(x, y)->x /. y    )
 163 :- increment (divide (lit 38, lit 5))
 164 \end{lstHaskell}
 165
 166 The interpreter only requires one instance of the \haskellinline{Function} class that works for any argument type.
 167 In the implementation, the resulting function \haskellinline{g} is simultaneously provided to the definition \haskellinline{def}.
 168 Because the laziness of \gls{HASKELL}'s lazy let bindings, this results in a fixed point calculation:
 169
 170 \begin{lstHaskell}
 171 instance Function a Maybe where
 172     fun def = let g :- m = def g in m
 173 \end{lstHaskell}
 174
 175 The given \haskellinline{Printer} type is not sufficient to implement the instances for the \haskellinline{Function} class, it must be possible to generate fresh function names.
 176 After extending the \haskellinline{Printer} type to contain some sort of state to generate fresh function names and a \haskellinline{MonadWriter [String]}\footnotemark\ to streamline the output, we define an instance for every arity.
 177 \begin{lrbox}{\LstBox}
 178         \begin{lstHaskell}[frame=]
 179 freshLabel :: Printer String
 180 tell :: MonadWriter w m => w -> m ()\end{lstHaskell}
 181 \end{lrbox}
 182 \footnotetext{\usebox{\LstBox}}
 183 To illustrate this, the instance for unary functions is shown, all other arities are implemented in similar fashion.
 184
 185 \begin{lstHaskell}
 186 instance Function () Printer where ...
 187 instance Function (Printer a) Printer where ...
 188     fun def = freshLabel >>= \f->
 189         let g :- m = def $ \a0->const undefined
 190                 <$> (tell ["f", show f, " ("]
 191                      >> a0 >> tell [")"])
 192         in  tell ["let f", f, " a0 = "]
 193                 >> g (const undefined <$> tell ["a0"])
 194         >>  tell [" in "] >> m
 195 instance Function (Printer a, Printer b) Printer where ...
 196 \end{lstHaskell}
 197
 198 Running the given printer on the example code shown before produces roughly the following output, running the interpreter on this code results in \haskellinline{Just 8}.
 199
 200 \begin{lstHaskell}
 201    let f0 a1 = a1 + 1
 202 in let f2 a3 a4 = a3 / a4
 203 in f0 (f2 38 5)
 204 \end{lstHaskell}
 205
 206 \subsection{Data types}
 207 Lifting values from the host language to the \gls{DSL} is possible using the \haskellinline{lit} function as long as the type of the value has instances for all the class constraints.
 208 Unfortunately, once lifted, it is not possible to do anything with values of the user-defined data type other than passing them around.
 209 It is not possible to construct new values from expressions in the \gls{DSL}, to deconstruct a value into the fields, nor to test of which constructor the value is.
 210 Furthermore, while in our language the only constraint is the automatically derivable \haskellinline{Show}, in real-world languages the class constraints may be very difficult to satisfy for complex types, for example serialisation to a single stack cell in the case of a compiler.
 211
 212 As a consequence, for user-defined data types---such as a pro\-gram\-mer-defined list type\footnotemark---to become first-class citizens in the \gls{DSL}, language constructs for constructors, deconstructors and constructor predicates must be defined.
 213 Field selectors are also useful functions for working with user-defined data types.
 214 They are not considered for the sake of brevity but can be implemented using the deconstructor functions.
 215 \footnotetext{
 216         For example: \haskellinline{data List a = Nil \| Cons \{hd :: a, tl :: List a\}}
 217 }
 218 The constructs for the list type would result in the following class definition:
 219
 220 \begin{lstHaskell}
 221 class ListDSL v where
 222     -- constructors
 223     nil    :: v (List a)
 224     cons   :: v a -> v (List a) -> v (List a)
 225     -- deconstructors
 226     unNil  :: v (List a) -> v b -> v b
 227     unCons :: v (List a) -> (v a -> v (List a) -> v b) -> v b
 228     -- constructor predicates
 229     isNil  :: v (List a) -> v Bool
 230     isCons :: v (List a) -> v Bool
 231 \end{lstHaskell}
 232
 233 Furthermore, instances for the \gls{DSL}'s views need to be created.
 234 For example, to use the interpreter, the following instance must be available.
 235 Note that at first glance, it would feel natural to have \haskellinline{isNil} and \haskellinline{isCons} return \haskellinline{Nothing} since we are in the \haskellinline{Maybe} monad.
 236 However, this would fail the entire expression and the idea is that the constructor test can be done from within the \gls{DSL}.
 237
 238 \begin{lstHaskell}
 239 instance ListDSL Maybe where
 240     nil        = Just Nil
 241     cons hd tl = Cons <$> hd <*> tl
 242     unNil  d f = d >>= \Nil->f
 243     unCons d f = d >>= \(Cons hd tl)->f (Just hd) (Just tl)
 244     isNil  d   = d >>= \case[+\footnotemark+]
 245         Nil -> Just True
 246         _   -> Just False
 247     isCons d   = d >>= \case
 248         Cons _ _ -> Just True
 249         Nil      -> Just False
 250 \end{lstHaskell}
 251 \footnotetext{%
 252         \haskellinline{\\case} is an abbreviation for \haskellinline{\\x->case x of ...} when using GHC's \GHCmod{LambdaCase} extension.
 253 }
 254
 255 Adding these classes and their corresponding instances is tedious and results in boilerplate code.
 256 We therefore resort to metaprogramming, and in particular \gls{TH} \citep{sheard_template_2002} to alleviate this burden.
 257
 258 \section{Template metaprogramming}
 259 Metaprogramming is a special flavour of programming where programs have the ability to treat and manipulate programs or program fragments as data.
 260 There are several techniques to facilitate metaprogramming, moreover it has been around for many years now \citep{lilis_survey_2019}.
 261 Even though it has been around for many years, it is considered complex \citep{sheard_accomplishments_2001}.
 262
 263 \gls{TH} is GHC's de facto metaprogramming system, implemented as a compiler extension together with a library \citep{sheard_template_2002}\citep[\citesection{6.13.1}]{ghc_team_ghc_2021}.
 264 Readers already familiar with \gls{TH} can safely skip this section.
 265
 266 \gls{TH} adds four main concepts to the language, na\-me\-ly \gls{AST} data types, splicing, quasiquotation and reification.
 267 With this machinery, regular \gls{HASKELL} functions can be defined that are called at compile time, inserting generated code into the \gls{AST}.
 268 These functions are monadic functions operating in the \haskellinline{Q} monad.
 269 The \haskellinline{Q} monad facilitates failure, reification and fresh identifier generation for hygienic macros \citep{kohlbecker_hygienic_1986}.
 270 Within the \haskellinline{Q} monad, capturable and non-capturable identifiers can be generated using the \haskellinline{mkName} and \haskellinline{newName} functions respectively.
 271 The \emph{Peter Parker principle}\footnote{With great power comes great responsibility.} holds for the \haskellinline{Q} monad as well because it executes at compile time and is very powerful.
 272 For example, it can subvert module boundaries, thus accessing constructors that were hidden; access the structure of abstract types; and it may cause side effects during compilation because it is possible to call \haskellinline{IO} operations \citep{terei_safe_2012}.
 273 To achieve the goal of embedding data types in a \gls{DSL} we refrain from using these \emph{unsafe} features.
 274
 275 \subsection{Data types}
 276 For all of \gls{HASKELL}'s \gls{AST} elements, data types are provided that are mostly isomorphic to the actual data types used in the compiler.
 277 With these data types, the entire syntax of a \gls{HASKELL} program can be specified.
 278 Often, a data type is suffixed with the context, e.g.\ there is a \haskellinline{VarE} and a \haskellinline{VarP} for a variable in an expression or in a pattern respectively.
 279 To give an impression of these data types, a selection of data types available in \gls{TH} is given below:
 280
 281 \begin{lstHaskell}
 282 data Dec = FunD Name [Clause] | DataD Cxt Name ... | SigD Name Type
 283         | ClassD Cxt Name | ...
 284 data Clause = Clause [Pat] Body [Dec]
 285 data Pat = LitP Lit | VarP Name | TupP [Pat] | WildP | ListP [Pat] | ...
 286 data Body = GuardedB [(Guard, Exp)] | NormalB Exp
 287 data Guard = NormalG Exp | PatG [Stmt]
 288 data Exp = VarE Name | LitE Lit | AppE Exp Exp | TupE [Maybe Exp]
 289         | LamE [Pat] Exp | ...
 290 data Lit = CharL Char | StringL String | IntegerL Integer | ...
 291 \end{lstHaskell}
 292
 293 To ease creating \gls{AST} data types in the \haskellinline{Q} monad, lowercase variants of the constructors are available that lift the constructor to the \haskellinline{Q} monad.
 294 For example, for the \haskellinline{LamE} constructor, the following \haskellinline{lamE} function is available.
 295
 296 \begin{lstHaskell}
 297 lamE :: [Q Pat] -> Q Exp -> Q Exp
 298 lamE ps es = LamE <$> sequence ps <*> es
 299 \end{lstHaskell}
 300
 301 \subsection{Splicing}
 302 Special splicing syntax (\haskellinline{\$(...)}) marks functions for compile-time execution.
 303 Apart from the fact that they always produce a value of an \gls{AST} data type, they are regular functions.
 304 Depending on the context and location of the splice, the result type is either a list of declarations, a type, an expression or a pattern.
 305 The result of this function, when executed successfully, is then spliced into the code and treated as regular code by the compiler.
 306 Consequently, the code that is generated may not be type safe, in which case the compiler provides a type error on the generated code.
 307 The following listing shows an example of a \gls{TH} function generating on-the-fly functions for arbitrary field selection in a tuple.
 308 When called as \haskellinline{\$(tsel 2 4)} it expands at compile time to \haskellinline{\\(_, _, f, _)->f}:
 309
 310 \begin{lstHaskell}
 311 tsel :: Int -> Int -> Q Exp
 312 tsel field total = do
 313     f <- newName "f"
 314     lamE [ tupP [if i == field then varP f else wildP
 315          | i<-[0..total-1]]] (varE f)
 316 \end{lstHaskell}
 317
 318 \subsection{Quasiquotation}
 319 Another key concept of \gls{TH} is Quasiquotation, the dual of splicing \citep{bawden_quasiquotation_1999}.
 320 While it is possible to construct entire programs using the provided data types, it is a little cumbersome.
 321 Using \emph{Oxford brackets} (\verb#[|# \ldots\verb#|]#) or single or double apostrophes, verbatim \gls{HASKELL} code can be entered which is converted automatically to the corresponding \gls{AST} nodes easing the creation of language constructs.
 322 Depending on the context, different quasiquotes are used:
 323 \begin{itemize*}
 324         \item \haskellinline{[\|...\|]} or \haskellinline{[e\|...\|]} for expressions
 325         \item \haskellinline{[d\|...\|]} for declarations
 326         \item \haskellinline{[p\|...\|]} for patterns
 327         \item \haskellinline{[t\|...\|]} for types
 328         \item \haskellinline{'...} for function names
 329         \item \haskellinline{''...} for type names
 330 \end{itemize*}.
 331 It is possible to escape the quasiquotes again by splicing.
 332 Variables defined within quasiquotes are always fresh---as if defined with \haskellinline{newName}---but it is possible to capture identifiers using \haskellinline{mkName}.
 333 For example, \haskellinline{[\|\\x->x\|]} translates to \haskellinline{newName "x" >>= \\x->lamE [varP x] (varE x)} and does not interfere with other \haskellinline{x}s already defined.
 334
 335 \subsection{Reification}
 336 Reification is the act of querying the compiler for information about a certain name.
 337 For example, reifying a type name results in information about the type and the corresponding \gls{AST} nodes of the type's definition.
 338 This information can then be used to generate code according to the structure of data types.
 339 Reification is done using the \haskellinline{reify :: Name -> Q Info} function.
 340 The \haskellinline{Info} type is an \gls{ADT} containing all the---known to the compiler---information about the matching type: constructors, instances, \etc.
 341
 342 \section{Metaprogramming for generating DSL functions}
 343 With the power of metaprogramming, we can generate the boilerplate code for our user-defined data types automatically at compile time.
 344 To generate the code required for the \gls{DSL}, we define the \haskellinline{genDSL} function.
 345 The type belonging to the name passed as an argument to this function is made available for the \gls{DSL} by generating the \haskellinline{typeDSL} class and view instances.
 346 For the \haskellinline{List} type it is called as: \haskellinline{\$(genDSL ''List)}\footnotemark.
 347 \footnotetext{
 348         \haskellinline{''} is used instead of \haskellinline{'} to instruct the compiler to look up the information for \haskellinline{List} as a type and not as a constructor.
 349 }
 350
 351 The \haskellinline{genDSL} function is a regular function---though \gls{TH} requires that it is defined in a separate module---that has type: \haskellinline{Name -> Q [Dec]}, i.e.\ given a name, it produces a list of declarations in the \haskellinline{Q} monad.
 352 The \haskellinline{genDSL} function first reifies the name to retrieve the structural information.
 353 If the name matches a type constructor containing a data type declaration, the structure of the type---the type variables, the type name and information about the constructors\footnotemark---are passed to the \haskellinline{genDSL'} function.
 354 \footnotetext{
 355         Defined as \haskellinline{type VarBangType = (Name, Bang, Type)} by \gls{TH}.
 356 }
 357 The \haskellinline{getConsName} function filters out unsupported data types such as \glspl{GADT} and makes sure that every field has a name.
 358 For regular \glspl{ADT}, the \haskellinline{adtFieldName} function is used to generate a name for the constructor based on the indices of the fields\footnotemark.
 359 \footnotetext{
 360         \haskellinline{adtFieldName :: Name -> Integer -> Name}
 361 }
 362 From this structure of the type, \haskellinline{genDSL'} generates a list of declarations containing a class definition (\cref{sec_fcd:class}), instances for the interpreter (\cref{sec_fcd:interpreter}), and instances of the printer (\cref{sec_fcd:prettyprinter}) respectively.
 363
 364 \begin{lstHaskell}
 365 genDSL :: Name -> Q [Dec]
 366 genDSL name = reify name >>= \case
 367     TyConI (DataD cxt typeName tvs mkind constructors derives)
 368         -> mapM getConsName constructors >>= \d->genDSL' tvs typeName d
 369     t -> fail ("genDSL does not support: " ++ show t)
 370
 371 getConsName :: Con -> Q (Name, [VarBangType])
 372 getConsName (NormalC consName fs) = pure (consName,
 373     [(adtFieldName consName i, b, t) | (i, (b, t))<-[0..] `zip` fs])
 374 getConsName (RecC consName fs) = pure (consName, fs)
 375 getConsName c = fail ("genDSL does not support: " ++ show c)
 376
 377 genDSL' :: [TyVarBndr] -> Name -> [(Name, [VarBangType])] -> Q [Dec]
 378 genDSL' typeVars typeName constructors = sequence
 379     [ mkClass, mkInterpreter, mkPrinter, ... ]
 380   where
 381     (consNames, fields) = unzip constructors
 382     ...
 383 \end{lstHaskell}
 384
 385 \subsection{Class generation}\label{sec_fcd:class}
 386 The function for generating the class definition is defined in the \haskellinline{where} clause of the \haskellinline{genDSL'} function.
 387 Using the \haskellinline{classD} constructor, a single type class is created with a single type variable \haskellinline{v}.
 388 The \haskellinline{classD} function takes five arguments:
 389 \begin{enumerate*}
 390         \item a context, i.e.\ the class constraints, which is empty in this case
 391         \item a name, generated from the type name using the \haskellinline{className} function that simply appends the text \haskellinline{DSL}
 392         \item a list of type variables, in this case the only type variable is the view on the \gls{DSL}, i.e.\ \haskellinline{v}
 393         \item functional dependencies, empty in our case
 394         \item a list of function declarations, i.e.\ the class members, in this case it is a concatenation of the constructors, deconstructors, and constructor predicates
 395 \end{enumerate*}
 396 Depending on the required information, either \haskellinline{zipWith} or \haskellinline{map} is used to apply the generation function to all constructors.
 397
 398 \begin{lstHaskell}
 399 mkClass :: Q Dec
 400 mkClass = classD (cxt []) (className typeName) [PlainTV (mkName "v")] []
 401     (  zipWith mkConstructor   consNames fields
 402     ++ zipWith mkDeconstructor consNames fields
 403     ++ map     mkPredicate     consNames
 404     )
 405 \end{lstHaskell}
 406
 407 In all class members, the view \haskellinline{v} plays a crucial role.
 408 Therefore, a definition for \haskellinline{v} is accessible for all generation functions.
 409 Furthermore, the \haskellinline{res} type represents the \emph{result} type, it is defined as the type including all type variables.
 410 This result type is derived from the type name and the list of type variables.
 411 In case of the \haskellinline{List} type, \haskellinline{res} is defined as \haskellinline{v (List a)} and is available for as well:
 412
 413 \begin{lstHaskell}
 414 v = varT (mkName "v")
 415 res = v `appT` foldl appT (conT typeName)
 416     (map getName typeVars)
 417   where getName (PlainTV name)    = varT name
 418         getName (KindedTV name _) = varT name
 419 \end{lstHaskell}
 420
 421 \subsubsection{Constructors}
 422 The constructor definitions are generated from just the constructor names and the field information.
 423 All class members are defined using the \haskellinline{sigD} constructor that represents a function signature.
 424 The first argument is the name of the constructor function, a lowercase variant of the actual constructor name generated using the \haskellinline{constructorName} function.
 425 The second argument is the type of the function.
 426 A constructor $C_k$ of type $T$ where
 427 $T~tv_0~\ldots~tv_n = \ldots |~ C_k~a_0~\ldots~a_m~| \ldots~$
 428 is defined as a \gls{DSL} function
 429 $c_k \dcolon v~a_0 \shortrightarrow \ldots \shortrightarrow v~a_m \shortrightarrow v~(T~v_0~\ldots~v_n) $.
 430 In the implementation, first the view \haskellinline{v} is applied to all the field types.
 431 Then, the constructor type is constructed by folding over the lifted field types with the result type as the initial value using \haskellinline{mkCFun}.
 432
 433 \begin{lstHaskell}
 434 mkConstructor :: Name -> [VarBangType] -> Q Dec
 435 mkConstructor n fs = sigD (constructorName n) (mkCFun fs res)
 436
 437 mkCFun :: [VarBangType] -> Q Type -> Q Type
 438 mkCFun fs res = foldr (\x y->[t|$x -> $y|])
 439     (map (\(_, _, t)->v `appT` pure t) fs)
 440 \end{lstHaskell}
 441
 442 \subsubsection{Deconstructors}
 443 The deconstructor is generated similarly to the constructor as the function for generating the constructor is the second argument modulo change in the result type.
 444 A deconstructor $C_k$ of type $T$ is defined as a \gls{DSL} function
 445 $\mathit{unC_k} \dcolon v~(T~v_0 \ldots v_n) \shortrightarrow (v~a_0 \shortrightarrow \ldots \shortrightarrow v~a_m \shortrightarrow v~b) \shortrightarrow v~b $.
 446 In the implementation, \haskellinline{mkCFun} is reused to construct the type of the deconstructor as follows:
 447
 448 \begin{lstHaskell}
 449 mkDeconstructor :: Name -> [VarBangType] -> Q Dec
 450 mkDeconstructor n fs = sigD (deconstructorName n)
 451     [t|$res -> $(mkCFun fs [t|$v $b|]) -> $v $b|]
 452   where b = varT (mkName "b")
 453 \end{lstHaskell}
 454
 455 \subsubsection{Constructor predicates}
 456 The last part of the class definition consists of the constructor predicates, a function that checks whether the provided value of type $T$ contains a value with constructor $C_k$.
 457 A constructor predicate for constructor $C_k$ of type $T$ is defined as a \gls{DSL} function $\mathit{isC_k} \dcolon v~(T~v_0~\ldots~v_n) \shortrightarrow v~\mathit{Bool}$.
 458 A constructor predicate---name prefixed by \haskellinline{is}---is generated for all constructors.
 459 They all have the same type:
 460
 461 \begin{lstHaskell}
 462 mkPredicate :: Name -> Q Dec
 463 mkPredicate n = sigD (predicateName n) [t|$res -> $v Bool|]
 464 \end{lstHaskell}
 465
 466 \subsection{Interpreter instance generation}\label{sec_fcd:interpreter}
 467 Generating the interpreter for the \gls{DSL} means generating the class instance for the \haskellinline{Interpreter} data type using the \haskellinline{instanceD} function.
 468 The first argument of the instance is the context, this is left empty.
 469 The second argument of the instance is the type, the \haskellinline{Interpreter} data type applied to the class name.
 470 Finally, the class function instances are generated using the information derived from the structure of the type.
 471 The structure for generating the function instances is very similar to the class definition, only for the function instances of the constructor predicates, the field information is required as well as the constructor names.
 472
 473 \begin{lstHaskell}
 474 mkInterpreter :: Q Dec
 475 mkInterpreter = instanceD (cxt [])
 476         [t|$(conT (className typeName)) Interpreter|]
 477     (  zipWith mkConstructor consNames fields
 478     ++ zipWith mkDeconstructor consNames fields
 479     ++ zipWith mkPredicate consNames fields)
 480   where ...
 481 \end{lstHaskell}
 482
 483 \subsubsection{Constructors}
 484 The interpreter is a view on the \gls{DSL} that immediately executes all operations in the \haskellinline{Maybe} monad.
 485 Therefore, the constructor function can be implemented by lifting the actual constructor to the \haskellinline{Maybe} type using sequential application.
 486 I.e.\ for a constructor $C_k$ this results in the following constructor: \haskellinline{ck a0 ... am = pure Ck <*> a0 <*> ... <*> am}.
 487 To avoid accidental shadowing, fresh names for all the arguments are generated.
 488 The \haskellinline{ifx} function is used as a shorthand for defining infix expressions\footnotemark.
 489 \begin{lrbox}{\LstBox}
 490         \begin{lstHaskell}[frame=]
 491 ifx :: String -> Q Exp -> Q Exp -> Q Exp
 492 ifx op a b = infixE (Just a) (varE (mkName op)) (Just b)\end{lstHaskell}
 493 \end{lrbox}
 494 \footnotetext{\usebox{\LstBox}}
 495
 496 \begin{lstHaskell}
 497 mkConstructor :: Name -> [VarBangType] -> Q Dec
 498 mkConstructor consName fs = do
 499     fresh <- sequence [newName "a" | _<-fs]
 500     fun (constructorName consName) (map varP fresh)
 501         (foldl (ifx "<*>") [|pure $(conE consName)|]
 502         (map varE fresh))
 503 \end{lstHaskell}
 504
 505
 506 \subsubsection{Deconstructors}
 507 In the case of a deconstructor a function with two arguments is created: the object itself (\haskellinline{f}) and the function doing something with the individual fields (\haskellinline{d}).
 508 To avoid accidental shadowing first fresh names for the arguments and fields are generated.
 509 Then, a function is created with the two arguments.
 510 First \haskellinline{d} is evaluated and bound to a host language function that deconstructs the constructor and passes the fields to \haskellinline{f}.
 511 I.e.\ a deconstructor function $C_k$ is defined as: \haskellinline{unCk d f = d >>= \\(Ck a0 .. am)->f (pure a0) ... (pure am))}\footnotemark.
 512 \footnotetext{
 513         The \haskellinline{nameBase :: Name -> String} function from the \gls{TH} library is used to convert a name to a string.
 514 }
 515
 516 \begin{lstHaskell}
 517 mkDeconstructor :: Name -> [VarBangType] -> Q Dec
 518 mkDeconstructor consName fs = do
 519     d <- newName "d"
 520     f <- newName "f"
 521     fresh <- mapM (newName . nameBase . fst3) fs
 522     fun (deconstructorName consName) [varP d, varP f]
 523         [|$(varE d) >>= \($(match f))->$(fapp f fresh)|]
 524   where fapp f = foldl appE (varE f) . map (\f->[|pure $(varE f)|])
 525         match f = pure (ConP consName (map VarP f))
 526 \end{lstHaskell}
 527
 528 \subsubsection{Constructor predicates}
 529 Constructor predicates evaluate the argument and make a case distinction on the result to determine the constructor.
 530 To be able to generate a valid pattern in the case distinction, the total number of fields must be known.
 531 To avoid having to explicitly generate a fresh name for the first argument, a lambda function is used.
 532 In general, the constructor selector for $C_k$ results in the following code \haskellinline{isCk f = f >>= \\case Ck _ ... _ -> pure True; _ -> pure False}.
 533 Generating this code is done with the following function:
 534
 535 \begin{lstHaskell}
 536 mkPredicate :: Name -> [(Var, Bang, Type)] -> Q Dec
 537 mkPredicate n fs = fun (predicateName n) []
 538     [|\x->x >>= \case
 539         $(conP n [wildP | _<-fs]) -> pure True
 540         _                         -> pure False|]
 541 \end{lstHaskell}
 542
 543 \subsection{Pretty printer instance generation}\label{sec_fcd:prettyprinter}
 544 Generating the printer happen analogously to the interpreter, a class instance for the \haskellinline{Printer} data type using the \haskellinline{instanceD} function.
 545
 546 \begin{lstHaskell}
 547 mkPrinter :: Q Dec
 548 mkPrinter = instanceD (cxt []) [t|$(conT (className typeName)) Printer|]
 549     (  zipWith mkConstructor consNames fields
 550     ++ zipWith mkDeconstructor consNames fields
 551     ++ map mkPredicate consNames)
 552 \end{lstHaskell}
 553
 554 To be able to define a printer that is somewhat more powerful, we provide instances for \haskellinline{MonadWriter}; add a state for fresh variables and a context; and define some helper functions the \haskellinline{Printer} datatype.
 555 The \haskellinline{printLit} function is a variant of \haskellinline{MonadWriter}s \haskellinline{tell} that prints a literal string, but it can be of any type (it is a phantom type anyway).
 556 \haskellinline{printCons} prints a constructor name followed by an expression, it inserts parenthesis only when required depending on the state.
 557 \haskellinline{paren} always prints parenthesis around the given printer.
 558 \haskellinline{>->} is a variant of the sequence operator \haskellinline{>>} from the \haskellinline{Monad} class, it prints whitespace in between the arguments.
 559
 560 \begin{lstHaskell}
 561 printLit  :: String -> Printer a
 562 printCons :: String -> Printer a -> Printer a
 563 paren     :: Printer a -> Printer a
 564 (>->)     :: Printer a1 -> Printer a2 -> Printer a3
 565 pl        :: String -> Q Exp
 566 \end{lstHaskell}
 567
 568 \subsubsection{Constructors}
 569 For a constructor $C_k$ the printer is defined as: \haskellinline{ck a0 ... am = printCons "Ck" (printLit "" >-> a0 >-> ... >-> am)}.
 570 To generate the second argument to the \haskellinline{printCons} function, a fold is used with \haskellinline{printLit ""} as the initial element to account for constructors without any fields as well, e.g.\ \haskellinline{Nil} is translated to \haskellinline{nil = printCons "Nil" (printLit "")}.
 571
 572 \begin{lstHaskell}
 573 mkConstructor :: Name -> [VarBangType] -> Q Dec
 574 mkConstructor consName fs = do
 575     fresh <- sequence [newName "f" | _<- fs]
 576     fun (constructorName consName) (map varP fresh)
 577         (pcons `appE` pargs fresh)
 578   where pcons = [|printCons $(lift (nameBase consName))|]
 579         pargs fresh = foldl (ifx ">->") (pl "")
 580             (map varE fresh)
 581 \end{lstHaskell}
 582
 583 \subsubsection{Deconstructors}
 584 Printing the deconstructor for $C_k$ is defined as:
 585 \begin{lstHaskell}
 586 unCk d f
 587     =  printLit "unCk d"
 588     >-> paren (
 589            printLit "\(Ck" >-> printLit "a0 ... am" >> printLit ")->"
 590         >> f (printLit "a0") ... (printLit "am")
 591     )
 592 \end{lstHaskell}
 593
 594 The implementation for this is a little elaborate and it heavily uses the \haskellinline{pl} function, a helper function that translates a string literal \haskellinline{s} to \haskellinline{[\|printLit \$(lift s)\|]}, i.e.\ it lifts the \haskellinline{printLit} function to the \gls{TH} domain.
 595
 596 \begin{lstHaskell}
 597 mkDeconstructor :: Name -> [VarBangType] -> Q Dec
 598 mkDeconstructor consName fs = do
 599     d <- newName "d"
 600     f <- newName "f"
 601     fresh <- sequence [newName "a" | _<-fs]
 602     fun (deconstructorName consName) (map varP [d, f])
 603         [| $(pl (nameBase (deconstructorName consName)))
 604         >-> $(pl (nameBase d))
 605         >-> paren ($(pl ('\\':'(':nameBase consName))
 606                    >-> $lam >> printLit ")->"
 607                    >>  $(hoas f))|]
 608   where
 609     lam = pl $ unwords [nameBase f | (f, _, _)<-fs]
 610     hoas f = foldl appE (varE f)
 611         [pl (nameBase f) | (f, _, _)<-fs]
 612 \end{lstHaskell}
 613
 614 \subsubsection{Constructor predicates}
 615 For the printer, the constructor selector for $C_k$ results in the following code \haskellinline{isCk f = printLit "isCk" >-> f}.
 616
 617 \begin{lstHaskell}
 618 mkPredicate :: Name -> Q Dec
 619 mkPredicate n = fun (predicateName n) []
 620     [|\x-> $(pl $ nameBase $ predicateName n) >-> x|]
 621 \end{lstHaskell}
 622
 623 \section{Pattern matching}
 624 It is possible to construct and deconstruct values from other \gls{DSL} expressions, and to perform tests on the constructor but with a clunky and unwieldy syntax.
 625 They have become first-class citizens in a grotesque way.
 626 For example, given that we have some language constructs to denote failure and conditionals\footnotemark, writing a list summation function in our \gls{DSL} would be done as follows.
 627 For the sake of the argument we take a little shortcut here and assume that the interpretation of the \gls{DSL} supports lazy evaluation by using the host language as a metaprogramming language as well, allowing us to use functions in the host language to construct expressions in the \gls{DSL}.
 628
 629 \begin{lrbox}{\LstBox}
 630         \begin{lstHaskell}[frame=,deletekeywords={if}]
 631 class Support v where
 632     if'    :: v Bool -> v a -> v a -> v a
 633     bottom :: String -> v a\end{lstHaskell}
 634 \end{lrbox}
 635 \footnotetext{\usebox{\LstBox}}
 636
 637 \begin{lstHaskell}[deletekeywords={if}]
 638 program :: (ListDSL v, Support v, ...) => v Int
 639 program
 640     = fun \sum->(\l->if'(isNil l)
 641         (lit 0)
 642         (unCons l (\hd tl->hd +. sum tl)))
 643     :- sum (cons (lit 38) (cons (lit 4) nil))
 644 \end{lstHaskell}
 645
 646 A similar \gls{HASKELL} implementation is much more elegant and less cluttered because of the support for pattern matching.
 647 Pattern matching offers a convenient syntax for doing deconstruction and constructor tests at the same time.
 648
 649 \begin{lstHaskell}
 650 sum :: List Int -> Int
 651 sum Nil = 0
 652 sum (List hd tl) = hd + sum tl
 653
 654 main = sum (Cons 38 (Cons 4 Nil))
 655 \end{lstHaskell}
 656
 657 \subsection{Custom quasiquoters}
 658 The syntax burden of \glspl{EDSL} can be reduced using quasiquotation.
 659 In \gls{TH}, quasiquotation is a convenient way to create \gls{HASKELL} language constructs by entering them verbatim using Oxford brackets.
 660 However, it is also possible to create so-called custom quasiquoters \citep{mainland_why_2007}.
 661 If the programmer writes down a fragment of code between tagged \emph{Oxford brackets}, the compiler executes the associated quasiquoter functions at compile time.
 662 A quasiquoter is a value of the following data type:
 663
 664 \begin{lstHaskell}
 665 data QuasiQuoter = QuasiQuoter
 666     { quoteExp  :: String -> Q Exp
 667     , quotePat  :: String -> Q Pat
 668     , quoteType :: String -> Q Type
 669     , quoteDec  :: String -> Q Dec
 670     }
 671 \end{lstHaskell}
 672
 673 The code between \emph{dsl} brackets (\haskellinline{[dsl\|...\|]}) is preprocessed by the \haskellinline{dsl} quasiquoter.
 674 Because the functions are executed at compile time, errors---thrown using the \haskellinline{MonadFail} instance of the \haskellinline{Q} monad---in these functions result in compile time errors.
 675 The \gls{AST} nodes produced by the quasiquoter are inserted into the location and checked as if they were written by the programmer.
 676
 677 To illustrate writing a custom quasiquoter, we show an implementation of a quasiquoter for binary literals.
 678 The \haskellinline{bin} quasiquoter is only defined for expressions and parses subsequent zeros and ones as a binary number and splices it back in the code as a regular integer.
 679 Thus, \haskellinline{[bin\|101010\|]} results in the literal integer expression \haskellinline{42}.
 680 If an invalid character is used, a compile-time error is shown.
 681 The quasiquoter is defined as follows:
 682
 683 \begin{lstHaskell}
 684 bin :: QuasiQuoter
 685 bin = QuasiQuoter { quoteExp = parseBin }
 686   where
 687     parseBin :: String -> Q Exp
 688     parseBin s = LitE . IntegerL <$> foldM bindigit 0 s
 689
 690     bindigit :: Integer -> Char -> Q Integer
 691     bindigit acc '0' = pure (2 * acc)
 692     bindigit acc '1' = pure (2 * acc + 1)
 693     bindigit acc c = fail ("invalid char: " ++ show c)
 694 \end{lstHaskell}
 695
 696 \subsection{Quasiquotation for pattern matching}
 697 Custom quasiquoters allow the \gls{DSL} user to enter fragments verbatim, bypassing the syntax of the host language.
 698 Pattern matching in general is not suitable for a custom quasiquoter because it does not really fit in one of the four syntactic categories for which custom quasiquoter support is available.
 699 However, a concrete use of pattern matching, interesting enough to be beneficial, but simple enough for a demonstration is the \emph{simple case expression}, a case expression that does not contain nested patterns and is always exhaustive.
 700 They correspond to multi-way conditional expressions and can thus be converted to \gls{DSL} constructs straightforwardly \citep[\citesection{4.4}]{peyton_jones_implementation_1987}.
 701
 702 In contrast to the binary literal quasiquoter example, we do not hand craft the parser.
 703 The parser combinator library \emph{parsec} is used instead to ease the creation of the parser \citep{leijen_parsec_2001}.
 704 First the location of the quasiquoted code is retrieved using the \haskellinline{location} function that operates in the \haskellinline{Q} monad.
 705 This location is inserted in the parsec parser so that errors are localised in the source code.
 706 Then, the \haskellinline{expr} parser is called that returns an \haskellinline{Exp} in the \haskellinline{Q} monad.
 707 The \haskellinline{expr} parser uses parsec's commodity expression parser primitive \haskellinline{buildExpressionParser}.
 708 The resulting parser translates the string directly into \gls{TH}'s \gls{AST} data types in the \haskellinline{Q} monad.
 709 The most interesting parser is the parser for the case expression that is an alternative in the basic expression parser \haskellinline{basic}.
 710 A case expression is parsed when a keyword \haskellinline{case} is followed by an expression that is in turn followed by a non-empty list of matches.
 711 A match is parsed when a pattern (\haskellinline{pat}) is followed by an arrow and an expression.
 712 The results of this parser are fed into the \haskellinline{mkCase} function that transforms the case into an expression using \gls{DSL} primitives such as conditionals, deconstructors and constructor predicates.
 713 The above translates to the following skeleton implementation:
 714
 715 \begin{lstHaskell}
 716 expr :: Parser (Q Exp)
 717 expr = buildExpressionParser [...] basic
 718   where
 719     basic :: Parser (Q Exp)
 720     basic =   ...
 721         <|> mkCase <$ reserved "case" <*> expr
 722                    <* reserved "of"   <*> many1 match
 723         <|> ...
 724
 725     match :: Parser (Q Pat, Q Exp)
 726     match = (,) <$> pat <* reserved "->" <*> expr
 727
 728     pat :: Parser (Q Pat)
 729     pat = conP <$> con <*> many var
 730 \end{lstHaskell}
 731
 732 Case expressions are transformed into constructors, deconstructors and constructor predicates, e.g.\ \haskellinline{case e1 of Cons hd tl -> e2; Nil -> e3;} is converted to:
 733 \begin{lstHaskell}[deletekeywords={if}]
 734 if' (isList e1)
 735     (unCons e1 (\hd tl->e2))
 736     (if' (isNil e1)
 737         (unNil e1 e3)
 738         (bottom "Exhausted case"))
 739 \end{lstHaskell}
 740
 741 The \haskellinline{mkCase} (\cref{mkcase_fcd:mkcase}) function transforms a case expression into constructors, deconstructors and constructor predicates.
 742 \Cref{mkcase_fcd:eval} first evaluates the patterns.
 743 Then the patterns and their expressions are folded using the \haskellinline{mkCase`} function (\cref{mkcase_fcd:pairs}).
 744 While a case exhaustion error is used as the initial value, this is never called since all case expressions are exhaustive.
 745 For every case, code is generated that checks whether the constructor used in the pattern matches the constructor of the value using constructor predicates (\cref{mkcase_fcd:conspred}).
 746 If the constructor matches, the deconstructor (\cref{mkcase_fcd:consdec}) is used to bind all names to the correct identifiers and evaluate the expression.
 747 If the constructor does not match, the continuation (\haskellinline{\$rest}) is used (\cref{mkcase_fcd:consstart}).
 748
 749 \begin{lstHaskell}[numbers=left,deletekeywords={if}]
 750 mkCase :: Q Exp -> [(Q Pat, Q Exp)] -> Q Exp [+\label{mkcase_fcd:mkcase} +]
 751 mkCase name cases = do
 752     pats <- mapM fst cases [+ \label{mkcase_fcd:eval} +]
 753     foldr (uncurry mkCase') [|bottom "Exhausted case"|][+ \label{mkcase_fcd:fold}\label{mkcase_fcd:foldinit} +]
 754         (zip pats (map snd cases)) [+\label{mkcase_fcd:pairs}+]
 755   where
 756     mkCase' :: Pat -> Q Exp -> Q Exp -> Q Exp
 757     mkCase' (ConP cons fs) e rest
 758         = [|if' $pred $then_ $rest|] [+\label{mkcase_fcd:consstart}+]
 759       where
 760         pred  = varE (predicateName cons) `appE` name[+\label{mkcase_fcd:conspred}+]
 761         then_ = [|$(varE (deconstructorName cons))[+\label{mkcase_fcd:consdec}+]
 762                  $name $(lamE [pure f | f<-fs] e)|][+\label{mkcase_fcd:consend}+]
 763 \end{lstHaskell}
 764
 765 Finally, with this quasiquotation mechanism we can define our list summation using a case expression.
 766 As a byproduct, syntactic cruft such as the special symbols for the operators and calls to \haskellinline{lit} can be removed as well resulting in the following summation implementation:
 767
 768 \begin{lstHaskell}
 769 program :: (ListDSL v, DSL v, ...) => v Int
 770 program
 771     = fun \sum->(\l->[dsl|case l of
 772         Cons hd tl -> hd + sum tl
 773         Nil        -> 0|])
 774     :- sum (cons (lit 38) (cons (lit 4) nil))
 775 \end{lstHaskell}
 776
 777 \section{Related work}
 778 Generic or polytypic programming is a promising technique at first glance for automating the generation of function implementations \citep{lammel_scrap_2003}.
 779 However, while it is possible to define a function that works on all first-order types, adding a new function with a new name to the language is not possible.
 780 This does not mean that generic programming is not useable for embedding pattern matches.
 781 In generic programming, types are represented as sums of products and using this representation it is possible to define pattern matching functions.
 782
 783 For example, \citet{rhiger_type-safe_2009} showed a method for expressing statically typed pattern matching using typed higher-order functions.
 784 If not the host language but the \gls{DSL} contains higher order functions, the same technique could be applied to port pattern matching to \glspl{DSL} though using an explicit sums of products representation.
 785 \Citeauthor{atkey_unembedding_2009} describe embedding pattern matching in a \gls{DSL} by giving patterns an explicit representation in the \gls{DSL} by using pairs, sums and injections \citep[\citesection{3.3}]{atkey_unembedding_2009}.
 786
 787 \Citet{mcdonell_embedded_2022} extends on this idea, resulting in a very similar but different solution to ours.
 788 They used the technique that \citeauthor{atkey_unembedding_2009} showed and applied it to deep embedding using the concrete syntax of the host language.
 789 The scaffolding---e.g.\ generating the pairs, sums and injections---for embedding is automated using generics but the required pattern synonyms are generated using \gls{TH}.
 790 The key difference to our approach is that we specialise the implementation for each of the interpretations instead of providing a general implementation of data type handling operations.
 791 Furthermore, our implementation does not require a generic function to trace all constructors, resulting in problems with (mutual) recursion.
 792
 793 \Citet{young_adding_2021} added pattern matching to a deeply embedded \gls{DSL} using a compiler plugin.
 794 This plugin implements an \haskellinline{externalise :: a -> E a} function that allows lifting all machinery required for pattern matching automatically from the host language to the \gls{DSL}.
 795 Under the hood, this function translates the pattern match to constructors, deconstructors, and constructor predicates.
 796 The main difference with this work is that it requires a compiler plugin while our metaprogramming approach works on any compiler supporting a metaprogramming system similar to \gls{TH}.
 797
 798 \subsection{Related work on Template Haskell}
 799 Metaprogramming in general is a very broad research topic and has been around for years already.
 800 We therefore do not claim an exhaustive overview of related work on all aspects of metaprogramming.
 801 However, we have tried to present most research on metaprogramming in \gls{TH}.
 802 \Citet{czarnecki_dsl_2004} provide a more detailed comparison of different metaprogramming techniques.
 803 They compare staged interpreters, metaprogramming and templating by comparing MetaOCaml, \gls{TH} and \gls{CPP} templates.
 804 \gls{TH} has been used to implement related work.
 805 They all differ slightly in functionality from our domain and can be divided into several categories.
 806
 807 \subsubsection{Generating extra code}
 808 Using \gls{TH} or other metaprogramming systems it is possible to add extra code to your program.
 809 The original \gls{TH} paper showed that it is possible to create variadic functions such as \haskellinline{printf} using \gls{TH} that would be almost impossible to define without \citep{sheard_template_2002}.
 810 \Citet{hammond_automatic_2003} used \gls{TH} to generate parallel programming skeletons.
 811 In practice, this means that the programmer selects a skeleton and, at compile time, the code is massaged to suit the pattern and information about the environment is inlined for optimisation.
 812
 813 \Citet{polak_automatic_2006} implemented automatic GUI generation using \gls{TH}.
 814 \Citet{duregard_embedded_2011} wrote a parser generator using \gls{TH} and the custom quasiquoting facilities.
 815 From a specification of the grammar, given in verbatim using a custom quasiquoter, a parser is generated at compile time.
 816 \Citet{shioda_libdsl_2014} used metaprogramming in the D programming language to create a \gls{DSL} toolkit.
 817 They also programmatically generate parsers and an interpretation for either compiling or interpreting the \gls{IR}.
 818 \Citet{blanchette_liquid_2022} use \gls{TH} to simplify the development of Liquid \gls{HASKELL} proofs.
 819 \Citet{folmer_high-level_2022} used \gls{TH} to synthesize C$\lambda$aSH \citep{baaij_digital_2015} \glspl{AST} to be processed.
 820 In similar fashion, \citet{materzok_generating_2022} used \gls{TH} to translate YieldFSM programs to {C$\lambda$aSH}.
 821
 822 \subsubsection{Optimisation}
 823 Besides generating code, it is also possible to analyse existing code and perform optimisations.
 824 Yet, this is dangerous territory because unwantedly, the semantics of the optimised program may be slightly different from the original program.
 825 For example, \citet{lynagh_unrolling_2003} implemented various optimisations in \gls{TH} such as automatic loop unrolling.
 826 The compile-time executed functions analyse the recursive function and unroll the recursion to a fixed depth to trade execution speed for program space.
 827 Also, \citet{odonnell_embedding_2004} embedded Hydra, a hardware description language, in \gls{HASKELL} utilising \gls{TH}.
 828 Using intensional analysis of the \gls{AST}, it detects cycles by labelling nodes automatically so that it can generate \emph{netlists}.
 829 The authors mention that alternatively this could have be done using a monad but this hampers equational reasoning greatly, which is a key property of Hydra.
 830 Finally, \citet{viera_staged_2018} present a way of embedding attribute grammars in \gls{HASKELL} in a staged fashion.
 831 Checking several aspects of the grammar is done at compile time using \gls{TH} while other safety checks are performed at runtime.
 832
 833 \subsubsection{Compiler extension}
 834 Sometimes, expressing certain functionalities in the host languages requires a lot of boilerplate, syntax wrestling, or other pains.
 835 Metaprogramming can relieve some of this stress by performing this translation to core constructs automatically.
 836 For example, implementing generic---or polytypic--- functions in the compiler is a major effort.
 837 \Citet{norell_prototyping_2004} used \gls{TH} to implement the machinery required to implement generic functions at compile time.
 838 \Citet{adams_template_2012} also explores implementing generic programming using \gls{TH} to speed things up considerably compared to regular generic programming.
 839 \Citet{clifton-everest_embedding_2014} use \gls{TH} with a custom quasiquoter to offer skeletons for workflows and embed foreign function interfaces in a \gls{DSL}.
 840 \Citet{eisenberg_promoting_2014} showed that it is possible to programmatically lift some functions from the function domain to the type domain at compile time, i.e.\ type families.
 841 Furthermore, \citet{seefried_optimising_2004} argued that it is difficult to do some optimisations in \glspl{EDSL} and that metaprogramming can be of use there.
 842 They use \gls{TH} to change all types to unboxed types, unroll loops to a certain depth and replace some expressions by equivalent more efficient ones.
 843 \Citet{torrano_strictness_2005} showed that it is possible to use \gls{TH} to perform a strictness analysis and perform let-to-case translation.
 844 Both applications are examples of compiler extensions that can be implemented using \gls{TH}.
 845 Another example of such a compiler extension is shown by \citet{gill_haskell_2009}.
 846 They created a meta level \gls{DSL} to describe rewrite rules on \gls{HASKELL} syntax that are applied on the source code at compile time.
 847
 848 \subsubsection{Quasiquotation}
 849 By means of quasiquotation, the host language syntax that usually seeps through the embedding can be hidden.
 850 The original \gls{TH} quasiquotation paper \citep{mainland_why_2007} shows how this can be done for regular expressions, not only resulting in a nicer syntax but syntax errors are also lifted to compile time instead of run time.
 851 Also, \citet{kariotis_making_2008} used \gls{TH} to automatically construct monad stacks without having to resort to the monad transformers library which requires advanced type system extensions.
 852
 853 \Citet{najd_everything_2016} uses the compile time to be able to do normalisation for a \gls{DSL}, dubbing it \glspl{QDSL}.
 854 They utilise the quasiquotation facilities of \gls{TH} to convert \gls{HASKELL} \gls{DSL} code to constructs in the \gls{DSL}, applying optimisations such as eliminating lambda abstractions and function applications along the way.
 855 \Citet{egi_embedding_2022} extended \gls{HASKELL} to support non-free data type pattern matching---i.e.\ data type with no standard form, e.g.\ sets, graphs---using \gls{TH}.
 856 Using quasiquotation, they make a complicated embedding of non-linear pattern matching available through a simple lens.
 857
 858 \subsubsection{Typed Template Haskell}\label{ssec_fcd:typed_template_haskell}
 859 \Gls{TTH} is a very recent extension/alternative to normal \gls{TH} \citep{pickering_multi-stage_2019,xie_staging_2022}.
 860 Whereas in \gls{TH} you can manipulate arbitrary parts of the syntax tree, add top-level splices of data types, definitions and functions, in \gls{TTH} the programmer can only splice expressions but the \gls{AST} fragments representing the expressions are well-typed by construction instead of untyped.
 861
 862 \Citet{pickering_staged_2020} implemented staged compilation for the \emph{generics-sop} \citep{de_vries_true_2014} generics library to improve the efficiency of the code using \gls{TTH}.
 863 \Citet{willis_staged_2020} used \gls{TTH} to remove the overhead of parsing combinators.
 864
 865 \section{Discussion}
 866 This chapter aims to be twofold, first, it shows how to inherit data types in a \gls{DSL} as first-class citizens by generating the boilerplate at compile time using \gls{TH}.
 867 Secondly, it introduces the reader to \gls{TH} by giving an overview of the literature in which \gls{TH} is used and provides a gentle introduction by explaining the case study.
 868
 869 \Gls{FP} languages are especially suitable for embedding \glspl{DSL} but adding user-defined data types is still an issue.
 870 The tagless-final style of embedding offers great modularity, extensibility and flexibility.
 871 However, user-defined data types are awkward to handle because the built-in operations on them---construction, deconstruction and constructor tests---are not inherited from the host language.
 872 We showed how to create a \gls{TH} function that will splice the required class definitions and view instances.
 873 The code dataset also contains an implementation for defining field selectors and provides an implementation for a compiler (see \cref{chp:research_data_management}).
 874 Furthermore, by writing a custom quasiquoter, pattern matches in natural syntax can be automatically converted to the internal representation of the \gls{DSL}, thus removing the syntax burden of the facilities.
 875 The use of a custom quasiquoter does require the \gls{DSL} programmer to write a parser for their \gls{DSL}, i.e.\ the parser is not inherited from the host language as is often the case in an embedded \gls{DSL}.
 876 However, by making use of modern parser combinator libraries, this overhead is limited and errors are already caught at compilation.
 877
 878 \subsection{Future work}
 879 For future work, it would be interesting to see how generating boilerplate for user-defined data types translates from shallow embedding to deep embedding.
 880 In deep embedding, the language constructs are expressed as data types in the host language.
 881 Adding new constructs, e.g.\ constructors, deconstructors, and constructor tests, for the user-defined data type therefore requires extending the data type.
 882 Techniques such as data types \`a la carte \citep{swierstra_data_2008} and open data types \citep{loh_open_2006} show that it is possible to extend data types orthogonally but whether metaprogramming can still readily be used is something that needs to be researched.
 883 It may also be possible to implemented (parts) of the boilerplate generation using \gls{TTH} (see \cref{ssec_fcd:typed_template_haskell}) to achieve more confidence in the type correctness of the implementation.
 884
 885 Another direction of research is to try to find the limits of this technique regarding richer data type definitions.
 886 It would be interesting to see whether it is possible to apply the technique on data types with existentially quantified type variables or full-fledged generalised \glspl{ADT} \citep{hinze_fun_2003}.
 887 It is not possible to straightforwardly lift the deconstructors to type classes because existentially quantified type variables will escape.
 888 Rank-2 polymorphism offers tools to define the types in such a way that this is not the case anymore.
 889 However, implementing compiling views on the \gls{DSL} is complicated because it would require inventing values of an existentially quantified type variable to satisfy the type system which is difficult.
 890 Finally, having to write a parser for the \gls{DSL} is extra work.
 891 Future research could determine whether it is possible to generate this using \gls{TH} as well.
 892
 893 \input{subfilepostamble}
 894 \end{document}