Commonly used intepretations are printing, compiling, simulating, optimising, verifying, proving the program\etc.
There are two main flavours of embedding \glspl{DSL}, deep---also called tagged---embedding and shallow---also called tagless---embedding.
+Most importantly, the two flavours differ on two axes: extensibility of language constructs and extensibility of interpretations.
+\todo{elaborate}
+
\Cref{sec:deep_embedding} shows the basics of deep embedding.
\Cref{sec:shallow_embedding} shows the basics of shallow embedding including tagless embedding.
\Cref{sec:compare_embedding} compares the embedding technique.
-Both flavours have their strengths and weaknesses and both flavours can be improved in order to mitigate (some of the) downsides.
-
-\begin{table}[ht]
- \begin{threeparttable}[b]
- \caption{Comparison of embedding techniques, adapted from \citet[Sec.~3.6]{sun_compositional_2022}}%
- \label{tbl:dsl_comparison}
- \begin{tabular}{lllllll}
- \toprule
- & Shallow & Deep & Hybrid & Poly & Comp. & Classy\\
- \midrule
- Transcoding free & yes & yes & no & yes & yes & yes\\
- Linguistic reuse & yes & no & partly\tnote{1} & yes & yes & no?\\
- Extend constructs & yes & no & partly\tnote{1} & yes & yes & yes\\
- Extend interpretations & no & yes & yes & yes & yes & yes\\
- Transformations & no & yes & yes & maybe\tnote{2} & maybe\tnote{2} & yes\\
- Modular dependencies & no & maybe & maybe & yes & yes & yes\\
- Nested pattern matching & no & yes & yes & no & maybe & maybe\tnote{3}\\
- Type safe & yes & maybe & no & yes & yes & yes\\
- \bottomrule
- \end{tabular}
- \begin{tablenotes}
- \item [1] Only in the shallowly embedded part.
- \item [2] Transformations require some ingenuity and are sometimes awkward to write.
- \item [3] It requires some---safe---form of dynamic typing.
- \end{tablenotes}
- \end{threeparttable}
-\end{table}
-
-In the following sections both techniques are explained.
-As an example, a simple language with integers, booleans and some arithmetic operators is used as a running example.
+In the following sections the basics of both techniques are explained.
+A simple language with integers, booleans and some arithmetic operators is used as a running example.
\section{Deep embedding}\label{sec:deep_embedding}
In a deeply embedded \gls{DSL}, the language terms are represented as data type{(s)} in the host language.
Therefore, interpretations of the terms are functions that operate on these data types.
-Definition~\ref{lst:exdeep} shows an implementation for the example \gls{DSL}.
+\Cref{lst:exdeep} shows an implementation for the example \gls{DSL}.
\begin{lstHaskell}[label={lst:exdeep},caption={A deeply embedded expression \gls{DSL}.}]
data Value = I Int | B Bool
eval :: Expr -> Value
eval (Lit i) = i
eval (Plus l r) = case (eval l, eval r) of
- (Lit (I l), Lit (I r)) -> I (l+r))
+ (Lit (I l), Lit (I r)) -> I (l+r))
(l, r) -> error ("Can't add " ++ show l ++ " to " ++ show r)
eval (Eq l r) = case (eval l, eval r) of
- (Lit (I l), Lit (I r)) -> B (l==r)
- (Lit (B l), Lit (B r)) -> B (l==r)
+ (Lit (I l), Lit (I r)) -> B (l==r)
+ (Lit (B l), Lit (B r)) -> B (l==r)
(l, r) -> error ("Can't compare " ++ show l ++ " to " ++ show r)
\end{lstHaskell}
-\subsection{Deep embedding with \texorpdfstring{\acrshortpl{GADT}}{GADTs}}
+\subsection{\texorpdfstring{\Acrlongpl{GADT}}{Generalised algebraic data types}}
Deep embedding has the advantage that it is easy to build and views are easy to add.
On the downside, the expressions created with this language are not necessarily type-safe.
-In the given language it is possible to create an expression such as \haskellinline{Plus (LitI 4) (LitB True)} that adds a boolean to an integer.
+In the given language it is possible to create an expression such as \haskellinline{LitI 4 `Plus` LitB True} that adds a boolean to an integer.
Extending the \gls{ADT} is easy and convenient but extending the views accordingly is tedious since it has to be done individually for all views.
The first downside of this type of \gls{EDSL} can be overcome by using \glspl{GADT}~\citep{cheney_first-class_2003}.
\Cref{lst:exdeepgadt} shows the same language, but type-safe with a \gls{GADT}.
\glspl{GADT} are not supported in the current version of \gls{CLEAN} and therefore the syntax is hypothetical (See \todo{insert link to appendix}).
-However, it has been shown that \glspl{GADT} can be simulated using bimaps or projection pairs~\citep{cheney_first-class_2003}.
+However, it has been shown that \glspl{GADT} can be simulated using bimaps or projection pairs~\citep[Sec.~2.2]{cheney_lightweight_2002}.
Unfortunately the lack of extendability remains a problem.
If a language construct is added, no compile time guarantee can be given that all views support it.
eval (Eq l r) = eval l == eval r
\end{lstHaskell}
-\section{Shallow embedding}
+\section{Shallow embedding}\label{sec:shallow_embedding}
In a shallowly \gls{EDSL} all language constructs are expressed as functions in the host language.
An evaluator view for the example language then can be implemented as the code shown in \cref{lst:exshallow}.
-Note that much of the internals of the language can be hidden using monads.
+Note that the internals of the language could have been hidden using a reader monad.
\begin{lstHaskell}[label={lst:exshallow}, caption={A minimal shallow \gls{EDSL}.}]
type Env = String -> Int
type DSL a = Env -> a
-Lit :: a -> DSL a
-Lit x = \e->x
+lit :: a -> DSL a
+lit x = \e->x
-Var :: String -> DSL Int
-Var i = \e->retrEnv e i
+var :: String -> DSL Int
+var i = \e->retrEnv e i
-Plus :: DSL Int -> DSL Int -> DSL Int
-Plus x y = \e->x e + y e
+plus :: DSL Int -> DSL Int -> DSL Int
+plus x y = \e->x e + y e
-Eq :: Eq a => DSL a -> DSL a -> DSL Bool
-Eq x y = \e->x e == y e
+eq :: Eq a => DSL a -> DSL a -> DSL Bool
+eq x y = \e->x e == y e
\end{lstHaskell}
One of the advantages of shallowly embedding a language in a host language is its extendability.
It is very easy to add functionality because the compile time checks of the host language guarantee whether or not the functionality is available when used.
-Moreover, the language is type safe as it is directly typed in the host language, i.e.\ \cleaninline{Lit True +. Lit 4} is rejected.
+For example, adding a new construct---such as subtraction---is done as follows:
+
+\begin{lstHaskell}[label={lst:exshallowsubst},caption={Adding subtraction to the shallow \gls{EDSL}.}]
+sub :: DSL Int -> DSL Int -> DSL Int
+sub x y = \e->x e - y e
+\end{lstHaskell}
+
+Moreover, the language is type safe as it is directly typed in the host language, i.e.\ \haskellinline{lit True `plus` lit 4} is rejected.
Another advantage is the intimate link with the host language, allowing for a lot more linguistic reuse such as the support of implicit sharing~\cite{krishnamurthi_linguistic_2001}.
The downside of this method is extending the language with views.
It is nearly impossible to add views to a shallowly embedded language.
-The only way of achieving this is by reimplementing all functions so that they run all backends at the same time.
-This will mean that every component will have to implement all views rendering it slow for multiple views and complex to implement.
+The only way of achieving this is by reimplementing all functions so that they run all backends at the same time or to create a single interpretation that produces a fold function~\citep{gibbons_folding_2014}.
\subsection{Tagless-final embedding}\label{ssec:tagless}
+By lifting the functions representing the \gls{DSL} terms to type classes, interpretations can be added.
+This technique is called tagless-final---or class-based shallow---embedding.
+The interface for the \gls{DSL} looks as follows:
+
+\begin{lstHaskell}[label={lst:extagless},caption={A minimal tagless-final \gls{EDSL}.}]
+class DSL v where
+ lit :: a -> v a
+ var :: String -> v a
+ plus :: v Int -> v Int -> v Int
+ eq :: Eq a => v a -> v a -> v Bool
+\end{lstHaskell}
+
+An interpretation of this view is a data type that implements the type class.
+
+\begin{lstHaskell}[label={lst:extagless},caption={A minimal tagless-final \gls{EDSL}.}]
+data Print a = P {runPrint :: String}
+instance DSL Print where
+ lit a = P (show a)
+ var i = P i
+ plus x y = P ("(" ++ runPrint x ++ "+" ++ runPrint y ++ ")"
+ eq x y = P ("(" ++ runPrint x ++ "==" ++ runPrint y ++ ")"
+\end{lstHaskell}
+Adding a language construct---e.g.\ subtraction---is a easy as adding a type class and providing instances for interpretations.
-\section{Comparison}
-\todo{cite compositional DSLs}
+\begin{lstHaskell}[label={lst:extaglesssubt},caption={Adding subtraction to the shallow \gls{EDSL}.}]
+class Sub v where
+ sub :: v Int -> v Int -> v Int
+
+instance Sub Print where
+ sub x y = P ("(" ++ runPrint x ++ "-" ++ runPrint y ++ ")"
+\end{lstHaskell}
+
+Adding an interpretation means adding a data type and providing instances for the language constructs.
+
+\begin{lstHaskell}[label={lst:extagless},caption={An evaluator interpretation of the minimal tagless-final \gls{EDSL}.}]
+data Eval a = Eval {runEval :: Env -> a}
+
+instance DSL v where
+ lit a = Eval (\_->a)
+ var i = Eval (\e->retrEnv e i)
+ plus x y = Eval (\e->runEval x e + runEval y e)
+ eq x y = Eval (\e->runEval x e == runEval y e)
+
+instance Sub Eval where
+ sub x y = Eval (\e->runEval x e - runEval y e)
+\end{lstHaskell}
+
+\section{Comparison}\label{sec:compare_embedding}
+Both flavours have their strengths and weaknesses and both flavours can be improved in order to mitigate (some of the) downsides.
+
+\begin{table}[ht]
+ \begin{threeparttable}[b]
+ \caption{Comparison of embedding techniques, adapted from \citet[Sec.~3.6]{sun_compositional_2022}}%
+ \label{tbl:dsl_comparison}
+ \begin{tabular}{lllllll}
+ \toprule
+ & Shallow & Deep & Hybrid & Poly & Comp. & Classy\\
+ \midrule
+ Transcoding free & yes & yes & no & yes & yes & yes\\
+ Linguistic reuse & yes & no & partly\tnote{1} & yes & yes & no?\\
+ Extend constructs & yes & no & partly\tnote{1} & yes & yes & yes\\
+ Extend interpretations & no & yes & yes & yes & yes & yes\\
+ Transformations & no & yes & yes & maybe\tnote{2} & maybe\tnote{2} & yes\\
+ Modular dependencies & no & maybe & maybe & yes & yes & yes\\
+ Nested pattern matching & no & yes & yes & no & maybe & maybe\tnote{3}\\
+ Type safe & yes & maybe & no & yes & yes & yes\\
+ \bottomrule
+ \end{tabular}
+ \begin{tablenotes}
+ \item [1] Only in the shallowly embedded part.
+ \item [2] Transformations require some ingenuity and are sometimes awkward to write.
+ \item [3] It requires some---safe---form of dynamic typing.
+ \end{tablenotes}
+ \end{threeparttable}
+\end{table}
\input{subfilepostamble}
\end{document}
repositories / phd-thesis.git / blobdiff