\input{subfilepreamble}
-\setcounter{chapter}{1}
+\setcounter{chapter}{2}
\begin{document}
\input{subfileprefix}
-\chapter{First-class data types in shallow \texorpdfstring{embedded domain-specific languages}{\glsxtrlongpl{EDSL}} using metaprogramming}%
+\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 chapter 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}.
+ Finally, the chapter also serves as a gentle introduction to \gls{TH}.
\end{chapterabstract}
\section{Introduction}
\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 \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}
-This paper shows that with the use of metaprogramming, all first-order user-defined data types can automatically be made first class for shallow \glspl{EDSL}.
+\subsection{Contributions}
+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}.
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.
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} and reflects on the process of using \gls{TH}.
+Finally, the chapter also serves as a gentle introduction to \gls{TH} and reflects on the process of using \gls{TH}.
-\section{Tagless-final embedding}
+\section{Tagless-final embedding}%
+\label{sec:tagless-final}
Tagless-final embedding is an upgrade to standard shallow embedding achieved by lifting all language construct functions to type classes.
As a result, views on the \gls{DSL} are data types implementing these classes.
\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}.
}
-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 }
\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 functions by supplying the arguments in a tuple.
-Furthermore, with the \haskellinline{:-} operator the syntax becomes usable.
+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:
infix 1 :-
\end{lstHaskell}
-The \haskellinline{Function} type class is now used to define functions with little syntactic overhead\footnote{The \GHCmod{BlockArguments} extension of GHC is used to reduce the number of brackets that allows lambda's to be an argument to a function without brackets}.
+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}
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.
+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.
\footnotetext{
For example: \haskellinline{data List a = Nil \| Cons \{hd :: a, tl :: List a\}}
}
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
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.
\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.
+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:
\subsection{Splicing}
Special splicing syntax (\haskellinline{\$(...)}) marks functions for compile-time execution.
-Other than that they always produce a value of an \gls{AST} data type, they are regular functions.
+Apart from the fact 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.
+The result of this function, when executed successfully, 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.
The following listing shows an example of a \gls{TH} function generating on-the-fly functions for arbitrary field selection in a tuple.
When called as \haskellinline{\$(tsel 2 4)} it expands at compile time to \haskellinline{\\(_, _, f, _)->f}:
\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 \gls{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 which 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
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.
\end{lstHaskell}
\subsubsection{Constructor predicates}
-The last part of the class definition are the constructor predicates, a function that checks whether the provided value of type $T$ contains a value with constructor $C_k$.
+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$.
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}$.
A constructor predicate---name prefixed by \haskellinline{is}---is generated for all constructors.
They all have the same type:
\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.
)
\end{lstHaskell}
-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.
+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.
\begin{lstHaskell}
mkDeconstructor :: Name -> [VarBangType] -> Q Dec
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.
+In contrast to the binary literal quasiquoter example, we do not hand craft the parser.
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.
\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.
+\Citet{young_adding_2021} added pattern matching to a deeply embedded \gls{DSL} using a compiler plugin.
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}.
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.
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}.
\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.
+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.
\Citet{polak_automatic_2006} implemented automatic GUI generation using \gls{TH}.
\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} \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}.
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}.
-They utilise the quasiquation 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.
+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.
\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}
+\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.
+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.
\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}
-This paper 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}.
+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}.
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.
\Gls{FP} languages are especially suitable for embedding \glspl{DSL} but adding user-defined data types is still an issue.
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.
+Another direction 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 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.
-
Finally, having to write a parser for the \gls{DSL} is extra work.
Future research could determine whether it is possible to generate this using \gls{TH} as well.
repositories / phd-thesis.git / blobdiff