\input{subfilepreamble}
+\setcounter{chapter}{1}
+
\begin{document}
\input{subfileprefix}
\chapter{First-class data types in shallow \texorpdfstring{embedded domain-specific languages}{\glsxtrlongpl{EDSL}} using metaprogramming}%
\label{chp:first-class_datatypes}%
+%\chaptermark{First-class data types in shallow eDSLs using metaprogramming}
\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.
\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}}
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{\$}}
+Using the \haskellinline{Function} type class can be 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 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.
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}
+\subsection{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.
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.
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.
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.
| i<-[0..total-1]]] (varE f)
\end{lstHaskell}
-\subsubsection{Quasiquotation}
+\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.
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.
-\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.
This information can then be used to generate code according to the structure of data types.
\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}}
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}.
\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)
\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} +]
\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}.
+\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.
\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}.
repositories / phd-thesis.git / blobdiff