The difference between shallow and deep embedding

Deep and shal­low em­bed­ding are terms as­so­ci­ated with Do­main Spe­cific Lan­guages (DSL). A DSL is a lan­guage geared to­ward a spe­cific do­main. The dot lan­guage is an ex­ample of such a DSL for de­scrib­ing Graphs. Con­cep­tu­ally, a shal­low em­bed­ding cap­tures the se­mantics of the data of the do­main in a data type and provides a fixed in­ter­pret­a­tion of the data, whereas a deep em­bed­ding goes bey­ond this and cap­tures the se­mantics of the op­er­a­tions on the do­main en­abling vari­able in­ter­pret­a­tions.

We will il­lus­trate this dif­fer­ence by em­bed­ding a simple ex­pres­sion lan­guage with sum­ma­tion, mul­ti­plic­a­tion and con­stants in Haskell. Haskell is es­pe­cially well-suited for and of­ten used as a host lan­guage for em­bed­ded DSLs.

We ex­press our lan­guage with the fol­low­ing in­ter­face. A type syn­onym Exp for nor­mal Ints and three sep­ar­ate func­tions rep­res­ent­ing sum­ma­tion, mul­ti­plic­a­tion, and con­stants.

type Exp = Int

plus  :: Exp -> Exp -> Exp
times :: Exp -> Exp -> Exp
const :: Int        -> Exp

We em­bed­ded the data of the do­main in Haskell and provided func­tions for con­struc­tion of the model and we can eas­ily rep­res­ent the cal­cu­la­tion of an ex­pres­sion as $4 + 6 * 8$ with the fol­low­ing lines of Haskell:

val = const 4 `plus` (const 6 `times` const 8)

The ad­vant­age of this em­bed­ding that cal­cu­lat­ing the value of our ex­pres­sion is very fast. Other than the value we can­not de­term­ine any­thing else re­gard­ing our ex­pres­sion. This be­comes more prob­lem­atic when we add vari­ables to our lan­guage.

We change our type to con­tain bind­ing in­form­a­tion and add two func­tions to rep­res­ent the as­sign­ment and us­age of vari­ables.

type Exp = ([String ⊨ Int], Int)

assign :: String -> Int -> Exp
var    :: String        -> Exp

And in our na­iv­ity we can write the ex­pres­sion $x + 6 * 8$ as fol­lows:

val = var "x" `plus` (const 6 `times` const 8)

Ob­vi­ously, eval­u­at­ing this cre­ates havoc! What is the value of x? We should, of course, have in­tro­duced it first:

val = let "x" 4 (var "x" `plus` (const 6 `times` const 8))

Now we have as­signed a value to x and we can safely use it in our ex­pres­sion.

Had we used a deep em­bed­ding we could have pre­ven­ted the cata­clys­mic er­ror by first check­ing whether each vari­able is as­signed be­fore it is used. We cre­ate a deep em­bed­ding of our ex­pres­sion by us­ing a Haskell data type.

data Exp where
  Plus   :: Exp -> Exp    -> Exp -- plus
  Times  :: Exp -> Exp    -> Exp -- times
  Const  :: Int           -> Exp -- const
  Assign :: String -> Int -> Exp -- assign
  Var    :: String        -> Exp -- var

Note that we do not spe­cify how the bind­ings should be stored, only that such a thing ex­ists. We now define a func­tion that checks whether we use a vari­able be­fore it is defined.¹

useBeforeDefine :: Exp -> Bool
useBeforeDefine e = f []
  where
  f :: [String] -> Exp -> Bool
  f (Plus  l r) env      = useBeforeDefine l env || useBeforeDefine r env
  f (Times l r) env      = useBeforeDefine l env || useBeforeDefine r env
  f (Const _)   _        = False
  f (Assign var _ e) env = useBeforeDefine e (var : env)
  f (Var var)        env = not (var `elem` env)

With the func­tion above we can check whether an ex­pres­sion is well-formed. With our deep em­bed­ding we can even define trans­form­a­tions of our ex­pres­sion; e.g. dif­fer­en­ti­ate with re­spect to a vari­able.

diff :: Exp -> String -> Exp
diff (Plus  l r) dx      = diff l dx `Plus` diff r dx
diff (Times l r) dx      = (diff l dx `Times` r) `Plus` (l `Times` diff r dx)
diff (Const _)   _       = Const 0
diff (Assign var x e) dx = Assign var x (diff e dx)
diff (Var var)        dx | var == dx = Const 1
                         | otherwise = Const 0

Deep em­bed­ding al­lows us to util­ise the se­mantics of our model by de­fin­ing mul­tiple in­ter­pret­a­tions of our DSL. The down­side is that just cal­cu­lat­ing the value of our ex­pres­sion has be­come slower due to the ad­ded over­head of the con­struct­ors, whereas the shal­low em­bed­ding can be eval­u­ated by only us­ing Ints.

In short:

• Shal­low em­bed­ding should be used when you only need a single in­ter­pret­a­tion or when you are in a hurry.
• Deep em­bed­ding should be used in all other cases.

More read­ing ma­ter­ial on this sub­ject:

• This present­a­tion by Josef Sven­nings­son.
• Com­bin­ing Deep and Shal­low Em­bed­ding for EDSL (Josef Sven­nings­son and Emil Axels­son, 2012)
• Cer­ti­fy­ing Ma­chine Code Safety: Shal­low versus Deep Em­bed­ding (Mar­tin Wild­moser and To­bias Nip­kow, 2004)
• Deep versus Shal­low em­bed­dings in Coq