\documentclass[../thesis.tex]{subfiles}
-\include{subfilepreamble}
+\input{subfilepreamble}
+
+\setcounter{chapter}{2}
\begin{document}
-\chapter{First-class data types in shallow \texorpdfstring{embedded domain-specific languages}{\glsxtrlongpl{EDSL}} using metaprogramming}%
-\chaptermark{bork}%
+\input{subfileprefix}
+\chapter{First-class data types in shallow embedded domain-specific languages using metaprogramming}%
\label{chp:first-class_datatypes}%
\begin{chapterabstract}
\Gls{FP} languages are excellent for hosting \glspl{EDSL} because of their rich type systems, minimal syntax, and referential transparency.
However, data types defined in the host language are not automatically available in the embedded language.
To do so, all the operations on the data type must be ported to the \gls{EDSL} resulting in a lot of boilerplate.
- This paper shows that by using metaprogramming, all first order user-defined data types can be automatically made first class in shallow \glspl{EDSL}.
+ This paper shows that by using metaprogramming, all first-order user-defined data types can be automatically made first class in shallow \glspl{EDSL}.
We show this by providing an implementation in \gls{TH} for a typical \gls{DSL} with two different semantics.
Furthermore, we show that by utilising quasiquotation, there is hardly any burden on the syntax.
Finally, the paper also serves as a gentle introduction to \gls{TH}.
Shallow embedding on the other hand models the language constructs as functions with the semantics embedded.
Consequently, adding a construct is easy, i.e.\ it only entails adding another function.
Contrarily, adding semantics requires adapting all language constructs.
-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}.
+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}.
-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, they are not first-class citizens.
+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.
Concretely, it is not possible to
\begin{enumerate*}
\end{enumerate*}
The functions for this are simply not available automatically in the embedded language.
For some semantics---such as an interpreter---it is possible to directly lift the functions from the host language to the \gls{DSL}.
-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.
-Thus, all of 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.
+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.
+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.
To relieve the burden of adding all these functions, metaprogramming\nobreak---\nobreak\hskip0pt and custom quasiquoters---can be used.
Metaprogramming entails that some parts of the program are generated by a program itself, i.e.\ the program is data.
-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 AST nodes.
+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.
Metaprogramming allows functions to be added to the program at compile time based on the structure of user-defined data types.
\subsection{Contributions of the paper}
As a result, views on the \gls{DSL} are data types implementing these classes.
To illustrate the technique, a simple \gls{DSL}, a language consisting of literals and addition, is outlined.
-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.
+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.
The \haskellinline{lit} function lifts values from the host language to the \gls{DSL} domain.
The class constraint \haskellinline{Show} is enforced on the type variable \haskellinline{a} to make sure that the value can be printed.
The infix function \haskellinline{+.} represents the addition of two expressions in the \gls{DSL}.
\begin{lstHaskell}[frame=]
<$> :: (a -> b) -> f a -> f b
<*> :: f (a -> b) -> f a -> f b
-infixl 4 <$>, <*>
- \end{lstHaskell}
+infixl 4 <$>, <*>\end{lstHaskell}
\end{lrbox}
\footnotetext{\usebox{\LstBox}}
infixl 7 /.
\end{lstHaskell}
-Division is an operation that undefined if the right operand is equal to zero.
+Division is an operation that is undefined if the right operand is equal to zero.
To capture this behaviour, the \haskellinline{Nothing} constructor from \haskellinline{Maybe} is used to represent errors.
-The right-hand side of the division operator is evaluated first.
+Both sides of the division operator are evaluated.
If the right-hand side is zero, the division is not performed and an error is returned instead:
\begin{lstHaskell}
\footnotetext{%
In this case a \haskellinline{newtype} is used instead of regular \haskellinline{data} declarations.
\haskellinline{newtype}s are special data types only consisting a single constructor with one field to which the type is isomorphic.
- During compilation the constructor is completely removed resulting in no overhead~\citep[\citesection{4.2.3}]{peyton_jones_haskell_2003}.
+ During compilation the constructor is completely removed resulting in no overhead \citep[\citesection{4.2.3}]{peyton_jones_haskell_2003}.
}
-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}:
+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}:
\begin{lstHaskell}
newtype Printer a = P { runPrinter :: String }
instance Expr Printer where
lit a = P (show a)
(+.) l r = P ("(" ++ runPrinter l
- ++ "+" ++ runPrinter r ++ ")")
+ ++ "+" ++ runPrinter r ++ ")")
instance Div Printer where
(/.) l r = P ("(" ++ runPrinter l
- ++ "/" ++ runPrinter r ++ ")")
+ ++ "/" ++ runPrinter r ++ ")")
\end{lstHaskell}
\subsection{Functions}
Adding functions to the language is achieved by adding a multi-parameter class to the \gls{DSL}.
-The type of the class function allows for the implementation to only allow first order function by supplying the arguments in a tuple.
-Furthermore, with the \haskellinline{:-} operator the syntax becomes usable.
-Finally, by defining the functions as a \gls{HOAS} type safety is achieved~\citep{pfenning_higher-order_1988,chlipala_parametric_2008}.
+The type of the class function allows for the implementation to only allow first-order functions by supplying the arguments in a tuple.
+Furthermore, with the \haskellinline{:-} operator the syntax becomes useable.
+Finally, by defining the functions as a \gls{HOAS} type safety is achieved \citep{pfenning_higher-order_1988,chlipala_parametric_2008}.
The complete definition looks as follows:
\begin{lstHaskell}
infix 1 :-
\end{lstHaskell}
-Using the \haskellinline{Function} type class can be used to define functions with little syntactic overhead.\footnote{The \GHCmod{LambdaCase} extension of GHC is used to reduce the number of brackets that allows lambda's to be an argument to a function without brackets or explicit function application using \haskellinline{\$}}
+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}.
The following listing shows an expression in the \gls{DSL} utilising two user-defined functions:
\begin{lstHaskell}
\begin{lrbox}{\LstBox}
\begin{lstHaskell}[frame=]
freshLabel :: Printer String
-tell :: MonadWriter w m => w -> m ()
- \end{lstHaskell}
+tell :: MonadWriter w m => w -> m ()\end{lstHaskell}
\end{lrbox}
\footnotetext{\usebox{\LstBox}}
To illustrate this, the instance for unary functions is shown, all other arities are implemented in similar fashion.
\end{lstHaskell}
\subsection{Data types}
-Lifting values from the host language to the \gls{DSL} is possible using the \haskellinline{lit} function as long as type of the value has instances for all the class constraints.
+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.
Unfortunately, once lifted, it is not possible to do anything with values of the user-defined data type other than passing them around.
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.
-Furthermore, while in the 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.
+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.
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.
Field selectors are also useful functions for working with user-defined data types, they are not considered for the sake of brevity but can be implemented using the deconstructor functions.
cons :: v a -> v (List a) -> v (List a)
-- deconstructors
unNil :: v (List a) -> v b -> v b
- unCons :: v (List a)
- -> (v a -> v (List a) -> v b) -> v b
+ unCons :: v (List a) -> (v a -> v (List a) -> v b) -> v b
-- constructor predicates
isNil :: v (List a) -> v Bool
isCons :: v (List a) -> v Bool
Furthermore, instances for the \gls{DSL}'s views need to be created.
For example, to use the interpreter, the following instance must be available.
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.
-However, the this would fail the entire expression and the idea is that the constructor test can be done from within the \gls{DSL}.
+However, this would fail the entire expression and the idea is that the constructor test can be done from within the \gls{DSL}.
\begin{lstHaskell}
instance ListDSL Maybe where
nil = Just Nil
cons hd tl = Cons <$> hd <*> tl
unNil d f = d >>= \Nil->f
- unCons d f = d
- >>= \(Cons hd tl)->f (Just hd) (Just tl)
+ unCons d f = d >>= \(Cons hd tl)->f (Just hd) (Just tl)
isNil d = d >>= \case[+\footnotemark+]
Nil -> Just True
_ -> Just False
}
Adding these classes and their corresponding instances is tedious and results in boilerplate code.
-We therefore resort to metaprogramming, and in particular \gls{TH}~\citep{sheard_template_2002} to alleviate this burden.
+We therefore resort to metaprogramming, and in particular \gls{TH} \citep{sheard_template_2002} to alleviate this burden.
\section{Template metaprogramming}
Metaprogramming is a special flavour of programming where programs have the ability to treat and manipulate programs or program fragments as data.
-There are several techniques to facilitate metaprogramming, moreover it has been around for many years now~\citep{lilis_survey_2019}.
-Even though it has been around for many years, it is considered complex~\citep{sheard_accomplishments_2001}.
+There are several techniques to facilitate metaprogramming, moreover it has been around for many years now \citep{lilis_survey_2019}.
+Even though it has been around for many years, it is considered complex \citep{sheard_accomplishments_2001}.
-\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}.
+\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}.
Readers already familiar with \gls{TH} can safely skip this section.
-\gls{TH} adds four main concepts to the language, na\-me\-ly AST data types, splicing, quasiquotation and reification.
-With this machinery, regular \gls{HASKELL} functions can be defined that are called at compile time, inserting generated code into the {AST}.
+\gls{TH} adds four main concepts to the language, na\-me\-ly \gls{AST} data types, splicing, quasiquotation and reification.
+With this machinery, regular \gls{HASKELL} functions can be defined that are called at compile time, inserting generated code into the \gls{AST}.
These functions are monadic functions operating in the \haskellinline{Q} monad.
-The \haskellinline{Q} monad facilitates failure, reification and fresh identifier generation for hygienic macros~\citep{kohlbecker_hygienic_1986}.
+The \haskellinline{Q} monad facilitates failure, reification and fresh identifier generation for hygienic macros \citep{kohlbecker_hygienic_1986}.
Within the \haskellinline{Q} monad, capturable and non-capturable identifiers can be generated using the \haskellinline{mkName} and \haskellinline{newName} functions respectively.
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.
-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}.
+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}.
To achieve the goal of embedding data types in a \gls{DSL} we refrain from using these \emph{unsafe} features.
-\subsubsection{Data types}
-Firstly, for all of \gls{HASKELL}'s AST elements, data types are provided that are mostly isomorphic to the actual data types used in the compiler.
+\subsection{Data types}
+Firstly, 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.
With these data types, the entire syntax of a \gls{HASKELL} program can be specified.
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.
To give an impression of these data types, a selection of data types available in \gls{TH} is given below:
\begin{lstHaskell}
-data Dec = FunD Name [Clause] | DataD Cxt Name ...
- | SigD Name Type | ClassD Cxt Name | ...
+data Dec = FunD Name [Clause] | DataD Cxt Name ... | SigD Name Type
+ | ClassD Cxt Name | ...
data Clause = Clause [Pat] Body [Dec]
-data Pat = LitP Lit | VarP Name | TupP [Pat]
- | WildP | ListP [Pat] | ...
+data Pat = LitP Lit | VarP Name | TupP [Pat] | WildP | ListP [Pat] | ...
data Body = GuardedB [(Guard, Exp)] | NormalB Exp
data Guard = NormalG Exp | PatG [Stmt]
-data Exp = VarE Name | LitE Lit | AppE Exp Exp
- | TupE [Maybe Exp] | LamE [Pat] Exp | ...
-data Lit = CharL Char | StringL String
- | IntegerL Integer | ...
+data Exp = VarE Name | LitE Lit | AppE Exp Exp | TupE [Maybe Exp]
+ | LamE [Pat] Exp | ...
+data Lit = CharL Char | StringL String | IntegerL Integer | ...
\end{lstHaskell}
-To ease creating AST data types in the \haskellinline{Q} monad, lowercase variants of the constructors are available that lift the constructor to the \haskellinline{Q} monad as.
+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.
For example, for the \haskellinline{LamE} constructor, the following \haskellinline{lamE} function is available.
\begin{lstHaskell}
lamE ps es = LamE <$> sequence ps <*> es
\end{lstHaskell}
-\subsubsection{Splicing}
+\subsection{Splicing}
Special splicing syntax (\haskellinline{\$(...)}) marks functions for compile-time execution.
-Other than that they always produce a value of an AST data type, they are regular functions.
+Other than that they always produce a value of an \gls{AST} data type, they are regular functions.
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.
The result of this function, when successful, is then spliced into the code and treated as regular code by the compiler.
Consequently, the code that is generated may not be type safe, in which case the compiler provides a type error on the generated code.
| i<-[0..total-1]]] (varE f)
\end{lstHaskell}
-\subsubsection{Quasiquotation}
-Another key concept of \gls{TH} is Quasiquotation, the dual of splicing~\citep{bawden_quasiquotation_1999}.
+\subsection{Quasiquotation}
+Another key concept of \gls{TH} is Quasiquotation, the dual of splicing \citep{bawden_quasiquotation_1999}.
While it is possible to construct entire programs using the provided data types, it is a little cumbersome.
-Using \emph{Oxford brackets} (\verb#[|# \ldots\verb#|]#) or single or double apostrophes, verbatim \gls{HASKELL} code can be entered that is converted automatically to the corresponding AST nodes easing the creation of language constructs.
+Using \emph{Oxford brackets} (\verb#[|# \ldots\verb#|]#) or single or double apostrophes, verbatim \gls{HASKELL} code can be entered that is converted automatically to the corresponding \gls{AST} nodes easing the creation of language constructs.
Depending on the context, different quasiquotes are used:
\begin{itemize*}
\item \haskellinline{[\|...\|]} or \haskellinline{[e\|...\|]} for expressions
\end{itemize*}.
It is possible to escape the quasiquotes again by splicing.
Variables defined within quasiquotes are always fresh---as if defined with \haskellinline{newName}---but it is possible to capture identifiers using \haskellinline{mkName}.
-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.
+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.
-\subsubsection{Reification}
+\subsection{Reification}
Reification is the act of querying the compiler for information about a certain name.
-For example, reifying a type name results in information about the type and the corresponding AST nodes of the type's definition.
+For example, reifying a type name results in information about the type and the corresponding \gls{AST} nodes of the type's definition.
This information can then be used to generate code according to the structure of data types.
Reification is done using the \haskellinline{reify :: Name -> Q Info} function.
The \haskellinline{Info} type is an \gls{ADT} containing all the---known to the compiler---information about the matching type: constructors, instances, \etc.
-\section{Metaprogramming for generating \texorpdfstring{\glsxtrshort{DSL}}{DSL} functions}
+\section{Metaprogramming for generating DSL functions}
With the power of metaprogramming, we can generate the boilerplate code for our user-defined data types automatically at compile time.
To generate the code required for the \gls{DSL}, we define the \haskellinline{genDSL} function.
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.
\begin{lstHaskell}
genDSL :: Name -> Q [Dec]
genDSL name = reify name >>= \case
- TyConI (DataD cxt typeName tvs mkind
- constructors derives)
- -> mapM getConsName constructors
- >>= \d->genDSL' tvs typeName d
+ TyConI (DataD cxt typeName tvs mkind constructors derives)
+ -> mapM getConsName constructors >>= \d->genDSL' tvs typeName d
t -> fail ("genDSL does not support: " ++ show t)
getConsName :: Con -> Q (Name, [VarBangType])
getConsName (NormalC consName fs) = pure (consName,
- [(adtFieldName consName i, b, t)
- | (i, (b, t))<-[0..] `zip` fs])
+ [(adtFieldName consName i, b, t) | (i, (b, t))<-[0..] `zip` fs])
getConsName (RecC consName fs) = pure (consName, fs)
-getConsName c
- = fail ("genDSL does not support: " ++ show c)
+getConsName c = fail ("genDSL does not support: " ++ show c)
-genDSL' :: [TyVarBndr] -> Name -> [(Name, [VarBangType])]
- -> Q [Dec]
+genDSL' :: [TyVarBndr] -> Name -> [(Name, [VarBangType])] -> Q [Dec]
genDSL' typeVars typeName constructors = sequence
[ mkClass, mkInterpreter, mkPrinter, ... ]
where
\begin{lstHaskell}
mkConstructor :: Name -> [VarBangType] -> Q Dec
-mkConstructor n fs
- = sigD (constructorName n) (mkCFun fs res)
+mkConstructor n fs = sigD (constructorName n) (mkCFun fs res)
mkCFun :: [VarBangType] -> Q Type -> Q Type
mkCFun fs res = foldr (\x y->[t|$x -> $y|])
\begin{lstHaskell}
mkPredicate :: Name -> Q Dec
-mkPredicate n = sigD (predicateName n)
- [t|$res -> $v Bool|]
+mkPredicate n = sigD (predicateName n) [t|$res -> $v Bool|]
\end{lstHaskell}
\subsection{Interpreter instance generation}\label{sec_fcd:interpreter}
\begin{lrbox}{\LstBox}
\begin{lstHaskell}[frame=]
ifx :: String -> Q Exp -> Q Exp -> Q Exp
-ifx op a b = infixE (Just a) (varE (mkName op)) (Just b)
- \end{lstHaskell}
+ifx op a b = infixE (Just a) (varE (mkName op)) (Just b)\end{lstHaskell}
\end{lrbox}
\footnotetext{\usebox{\LstBox}}
fresh <- mapM (newName . nameBase . fst3) fs
fun (deconstructorName consName) [varP d, varP f]
[|$(varE d) >>= \($(match f))->$(fapp f fresh)|]
- where fapp f = foldl appE (varE f)
- . map (\f->[|pure $(varE f)|])
+ where fapp f = foldl appE (varE f) . map (\f->[|pure $(varE f)|])
match f = pure (ConP consName (map VarP f))
\end{lstHaskell}
\end{lstHaskell}
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.
-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).
+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).
\haskellinline{printCons} prints a constructor name followed by an expression, it inserts parenthesis only when required depending on the state.
\haskellinline{paren} always prints parenthesis around the given printer.
\haskellinline{>->} is a variant of the sequence operator \haskellinline{>>} from the \haskellinline{Monad} class, it prints whitespace in between the arguments.
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.
They have become first-class citizens in a grotesque way.
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.
-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 contstruct expressions in the \gls{DSL}.
+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}.
\begin{lrbox}{\LstBox}
- \begin{lstHaskell}[frame=]
+ \begin{lstHaskell}[frame=,deletekeywords={if}]
class Support v where
if' :: v Bool -> v a -> v a -> v a
- bottom :: String -> v a
- \end{lstHaskell}
+ bottom :: String -> v a\end{lstHaskell}
\end{lrbox}
\footnotetext{\usebox{\LstBox}}
-\begin{lstHaskell}
+\begin{lstHaskell}[deletekeywords={if}]
program :: (ListDSL v, Support v, ...) => v Int
program
= fun \sum->(\l->if'(isNil l)
\subsection{Custom quasiquoters}
The syntax burden of \glspl{EDSL} can be reduced using quasiquotation.
In \gls{TH}, quasiquotation is a convenient way to create \gls{HASKELL} language constructs by entering them verbatim using Oxford brackets.
-However, it is also possible to create so-called custom quasiquoters~\citep{mainland_why_2007}.
+However, it is also possible to create so-called custom quasiquoters \citep{mainland_why_2007}.
If the programmer writes down a fragment of code between tagged \emph{Oxford brackets}, the compiler executes the associated quasiquoter functions at compile time.
A quasiquoter is a value of the following data type:
The code between \emph{dsl} brackets (\haskellinline{[dsl\|...\|]}) is preprocessed by the \haskellinline{dsl} quasiquoter.
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.
-The AST nodes produced by the quasiquoter are inserted into the location and checked as if they were written by the programmer.
+The \gls{AST} nodes produced by the quasiquoter are inserted into the location and checked as if they were written by the programmer.
To illustrate writing a custom quasiquoter, we show an implementation of a quasiquoter for binary literals.
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.
Custom quasiquoters allow the \gls{DSL} user to enter fragments verbatim, bypassing the syntax of the host language.
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.
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.
-They correspond to a multi-way conditional expressions and can thus be converted to \gls{DSL} constructs straightforwardly~\citep[\citesection{4.4}]{peyton_jones_implementation_1987}.
+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}.
In contrast to the binary literal quasiquoter example, we do not create the parser by hand.
-The parser combinator library \emph{parsec} is used instead to ease the creation of the parser~\citep{leijen_parsec_2001}.
+The parser combinator library \emph{parsec} is used instead to ease the creation of the parser \citep{leijen_parsec_2001}.
First the location of the quasiquoted code is retrieved using the \haskellinline{location} function that operates in the \haskellinline{Q} monad.
This location is inserted in the parsec parser so that errors are localised in the source code.
Then, the \haskellinline{expr} parser is called that returns an \haskellinline{Exp} in the \haskellinline{Q} monad.
The \haskellinline{expr} parser uses parsec's commodity expression parser primitive \haskellinline{buildExpressionParser}.
-The resulting parser translates the string directly into \gls{TH}'s AST data types in the \haskellinline{Q} monad.
+The resulting parser translates the string directly into \gls{TH}'s \gls{AST} data types in the \haskellinline{Q} monad.
The most interesting parser is the parser for the case expression that is an alternative in the basic expression parser \haskellinline{basic}.
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.
A match is parsed when a pattern (\haskellinline{pat}) is followed by an arrow and an expression.
\end{lstHaskell}
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:
-\begin{lstHaskell}
+\begin{lstHaskell}[deletekeywords={if}]
if' (isList e1)
(unCons e1 (\hd tl->e2))
(if' (isNil e1)
If the constructor matches, the deconstructor (\cref{mkcase_fcd:consdec}) is used to bind all names to the correct identifiers and evaluate the expression.
If the constructor does not match, the continuation (\haskellinline{\$rest}) is used (\cref{mkcase_fcd:consstart}).
-\begin{lstHaskell}[numbers=left]
+\begin{lstHaskell}[numbers=left,deletekeywords={if}]
mkCase :: Q Exp -> [(Q Pat, Q Exp)] -> Q Exp [+\label{mkcase_fcd:mkcase} +]
mkCase name cases = do
pats <- mapM fst cases [+ \label{mkcase_fcd:eval} +]
\end{lstHaskell}
\section{Related work}
-Generic or polytypic programming is a promising technique at first glance for automating the generation of function implementations~\citep{lammel_scrap_2003}.
+Generic or polytypic programming is a promising technique at first glance for automating the generation of function implementations \citep{lammel_scrap_2003}.
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.
This does not mean that generic programming is not useable for embedding pattern matches.
In generic programming, types are represented as sums of products and using this representation it is possible to define pattern matching functions.
For example, \citet{rhiger_type-safe_2009} showed a method for expressing statically typed pattern matching using typed higher-order functions.
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.
-\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}.
+\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}.
\Citet{mcdonell_embedded_2022} extends on this idea, resulting in a very similar but different solution to ours.
They used the technique that \citeauthor{atkey_unembedding_2009} showed and applied it to deep embedding using the concrete syntax of the host language.
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}.
-The key difference to our approach is that we specialise the implementation for each of the backends instead of providing a general implementation of data type handling operations.
+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.
Furthermore, our implementation does not require a generic function to trace all constructors, resulting in problems with (mutual) recursion.
\Citet{young_adding_2021} added pattern matching to a deeply \gls{EDSL} using a compiler plugin.
Under the hood, this function translates the pattern match to constructors, deconstructors, and constructor predicates.
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}.
-\subsection{Related work on \texorpdfstring{\glsxtrlong{TH}}{Template Haskell}}
+\subsection{Related work on Template Haskell}
Metaprogramming in general is a very broad research topic and has been around for years already.
We therefore do not claim an exhaustive overview of related work on all aspects of metaprogramming.
-However, we have have tried to present most research on metaprogramming in \gls{TH}.
+However, we have tried to present most research on metaprogramming in \gls{TH}.
\Citet{czarnecki_dsl_2004} provide a more detailed comparison of different metaprogramming techniques.
They compare staged interpreters, metaprogramming and templating by comparing MetaOCaml, \gls{TH} and \gls{CPP} templates.
\gls{TH} has been used to implement related work.
\subsubsection{Generating extra code}
Using \gls{TH} or other metaprogramming systems it is possible to add extra code to your program.
-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}.
+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}.
\Citet{hammond_automatic_2003} used \gls{TH} to generate parallel programming skeletons.
In practise, 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.
\Citet{duregard_embedded_2011} wrote a parser generator using \gls{TH} and the custom quasiquoting facilities.
From a specification of the grammar, given in verbatim using a custom quasiquoter, a parser is generated at compile time.
\Citet{shioda_libdsl_2014} used metaprogramming in the D programming language to create a \gls{DSL} toolkit.
-They also programmatically generate parsers and a backend for either compiling or interpreting the \gls{IR}.
+They also programmatically generate parsers and an interpretation for either compiling or interpreting the \gls{IR}.
\Citet{blanchette_liquid_2022} use \gls{TH} to simplify the development of Liquid \gls{HASKELL} proofs.
-\Citet{folmer_high-level_2022} used \gls{TH} to synthesize C$\lambda$aSH~\citep{baaij_digital_2015} abstract syntax trees to be processed.
+\Citet{folmer_high-level_2022} used \gls{TH} to synthesize C$\lambda$aSH \citep{baaij_digital_2015} \glspl{AST} to be processed.
In similar fashion, \citet{materzok_generating_2022} used \gls{TH} to translate YieldFSM programs to {C$\lambda$aSH}.
\subsubsection{Optimisation}
Besides generating code, it is also possible to analyse existing code and perform optimisations.
-Yet, this is dangerous territory because unwantedly the semantics of the optimised program may be slightly different from the original program.
+Yet, this is dangerous territory because unwantedly, the semantics of the optimised program may be slightly different from the original program.
For example, \citet{lynagh_unrolling_2003} implemented various optimisations in \gls{TH} such as automatic loop unrolling.
The compile-time executed functions analyse the recursive function and unroll the recursion to a fixed depth to trade execution speed for program space.
Also, \citet{odonnell_embedding_2004} embedded Hydra, a hardware description language, in \gls{HASKELL} utilising \gls{TH}.
-Using intensional analysis of the AST, it detects cycles by labelling nodes automatically so that it can generate \emph{netlists}.
+Using intensional analysis of the \gls{AST}, it detects cycles by labelling nodes automatically so that it can generate \emph{netlists}.
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.
Finally, \citet{viera_staged_2018} present a way of embedding attribute grammars in \gls{HASKELL} in a staged fashion.
Checking several aspects of the grammar is done at compile time using \gls{TH} while other safety checks are performed at runtime.
\subsubsection{Quasiquotation}
By means of quasiquotation, the host language syntax that usually seeps through the embedding can be hidden.
-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.
+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.
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.
\Citet{najd_everything_2016} uses the compile time to be able to do normalisation for a \gls{DSL}, dubbing it \glspl{QDSL}.
\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}.
Using quasiquotation, they make a complicated embedding of non-linear pattern matching available through a simple lens.
-\subsubsection{\texorpdfstring{\glsxtrlong{TTH}}{Typed Template Haskell}}\label{ssec_fcd:typed_template_haskell}
-\gls{TTH} is a very recent extension/alternative to normal \gls{TH}~\citep{pickering_multi-stage_2019,xie_staging_2022}.
-Where 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 abstract syntax tree fragments representing the expressions are well-typed by construction instead of untyped.
+\subsubsection{Typed Template Haskell}\label{ssec_fcd:typed_template_haskell}
+\Gls{TTH} is a very recent extension/alternative to normal \gls{TH} \citep{pickering_multi-stage_2019,xie_staging_2022}.
+Where 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.
-\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}.
+\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}.
\Citet{willis_staged_2020} used \gls{TTH} to remove the overhead of parsing combinators.
\section{Discussion}
For future work, it would be interesting to see how generating boilerplate for user-defined data types translates from shallow embedding to deep embedding.
In deep embedding, the language constructs are expressed as data types in the host language.
Adding new constructs, e.g.\ constructors, deconstructors, and constructor tests, for the user-defined data type therefore requires extending the data type.
-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.
+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.
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.
Another venue of research is to try to find the limits of this technique regarding richer data type definitions.
-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}.
+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}.
It is not possible to straightforwardly lift the deconstructors to type classes because existentially quantified type variables will escape.
Rank-2 polymorphism offers tools to define the types in such a way that this is not the case anymore.
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.
repositories / phd-thesis.git / blobdiff