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\}}
}
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
\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:
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 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.
\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.
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.
repositories / phd-thesis.git / blobdiff