A deep \gls{EDSL} is a language represented as an \gls{ADT}. Views are
functions that transform something to the datatype or the other way around. As
an example, take the simple arithmetic \gls{EDSL} shown in
Listing~\ref{lst:exdeep}.

\begin{lstlisting}[language=Clean,label={lst:exdeep},%
	caption={A minimal deep \gls{EDSL}}]
:: DSL
	= LitI  Int
	| LitB  Bool
	| Var   String
	| Plus  DSL DSL
	| Minus DSL DSL
	| And   DSL DSL
	| Eq    DSL
\end{lstlisting}

Deep embedding has the advantage that it is easy to build and views
are easy to add. To the downside, the expressions created with this language
are not type-safe. In the given language it is possible to create an expression
such as \CI{Plus (LitI 4) (LitB True)} that adds a boolean to an integer.
Evermore so, extending the \gls{ADT} is easy and convenient but extending the
views accordingly is tedious and has to be done individually for all views.

The first downside of this type of \gls{EDSL} can be overcome by using
\glspl{GADT}~\cite{cheney_first-class_2003}. Listing~\ref{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. However, it has been shown that \glspl{GADT} can be simulated
using bimaps or projection pairs~\cite{cheney_lightweight_2002}. Unfortunately
the lack of extendability remains a problem. If a language construct is added,
no compile time guarantee is given that all views support it.

\begin{lstlisting}[language=Clean,label={lst:exdeepgadt},%
	caption={A minimal deep \gls{EDSL} using \glspl{GADT}}]
:: DSL a
	=     LitI  Int                   -> DSL Int
	|     LitB  Bool                  -> DSL Bool
	| E.e: Var   String                -> DSL e
	|     Plus  (DSL Int) (DSL Int)   -> DSL Int
	|     Minus (DSL Int) (DSL Int)   -> DSL Int
	|     And   (DSL Bool) (DSL Bool) -> DSL Bool
	| E.e: Eq (DSL e) (DSL e)          -> DSL Bool &  == e
\end{lstlisting}
