There are several techniques available for creating \glspl{EDSL}. Each of
them have their own advantages and disadvantages such as extendability,
typedness and view support. In the following subsections each of the main
techniques are briefly explained.

\section{Deep embedding}
A deep \gls{EDSL} means that the language is represented as an \gls{ADT}. Views
are functions that transform something to the datatype or the other way around.
As an example we have 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 very simple to build and the views
are easy to make and add. However, there are also a few downsides.  The
expressions created with this language are not type-safe. In the given language
it is possible an expression such as \CI{Plus (LitI 4) (LitB True)} which to
add 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 the 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
artificial. 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 stays 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}

\section{Shallow embedding}
In a shallowly \gls{EDSL} all language constructs are expressed as functions in
the host language. An evaluator view for our example language then looks
something like the code shown in Listing~\ref{lst:exshallow}. Note that much of
the internals of the language can be hidden using monads.

\begin{lstlisting}[language=Clean,label={lst:exshallow},%
	caption={A minimal shallow \gls{EDSL}}]
:: Env   = ...            // Some environment
:: DSL a = DSL (Env -> a)

Lit :: a -> DSL a
Lit x = \e->x

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

...

Eq :: (DSL a) (DSL a) -> DSL Bool | == a
Eq x y = \e->x e + y e
\end{lstlisting}

The advantage of shallowly embedding a language in a host language is the
extendability. It is very easy to add functionality and compile time checks
guarantee that the functionality is available. Moreover, the language is type
safe as it is directly typed in the host language.

The downside of this method is extending the language with views. It is near
impossible to add views to a shallowly embedded language. The only way of
achieving this is by decorating the datatype for the \gls{EDSL} with all the
information for all the views. This will mean that every component will have to
implement all views. This makes it slow for multiple views and complex to
implement.

\section{Class based shallow embedding}
The third type of embedding is called class based shallow embedding and has the
best of both shallow and deep embedding. In class based shallow embedding the
language constructs are defined as type classes. The same language is shown
with the new method in Listing~\ref{lst:exclassshallow}.

This type of embedding inherits the easiness of adding views from shallow
embedding. A view is just a different data type implementing one or more of the
type classes as shown in the aforementioned Listing where an evaluator and a
pretty printer are implemented.

Just as with \glspl{GADT} in deep embedding type safety is guaranteed. Type
constraints are enforced through phantom types. One can add as many phantom
type as is necessary. Lastly, extensions can be added easily, just as in
shallow embedding. When an extension is made in an existing class, all views
must be updated accordingly to prevent possible runtime errors. When an
extension is added in a new class this problem does not arise and views can
choose to implement only parts of the collection of classes.

\begin{lstlisting}[language=Clean,label={lst:exclassshallow},%
	caption={A minimal class based shallow \gls{EDSL}}]
:: Env   = ...            // Some environment
:: Evaluator a = Evaluator (Env -> a)
:: PrettyPrinter a = PP String

class intArith where
	lit   :: t -> v t             | toString t
	add   :: (v t) (v t) -> (v t) | + t
	minus :: (v t) (v t) -> (v t) | - t

class boolArith where
	and :: (v Bool) (v Bool) -> (v Bool)
	eq  :: (v t)    (v t)    -> (v Bool) | == t

instance intArith Evaluator where
	lit x = \e->x
	add x y = ...

instance intArith PrettyPrinter where
	lit x = toString x
	add x y = x +++ "+" +++ y
	...
\end{lstlisting}
