\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Mar08 where
\end{code}
Learning objectives:
\begin{itemize}
\item DSL encodings
\item Expression Problem
\item Finally Tagless
\end{itemize}
Embeddings:
\begin{enumerate}
\item Shallow. (Jan 26 for RegExp). Embed as native functions.
\item Deep. (Feb 4, 8 for RE). Embed as a data-structure.
\item Tagless (today). Embed as an interface – i.e. a typeclass.
\end{enumerate}
Start with a simple expression language. First deep, then shallow, then tagless.
\begin{code}
data Expr = LInt Integer | Expr :+: Expr | Expr :*: Expr
deriving Show
— tiny interpreter for our language. Total, can’t fail.
eval :: Expr -> Integer
eval (LInt i) = i
eval (x :+: y) = eval x + eval y
eval (x :*: y) = eval x * eval y
e0 :: Expr
ex0 :: Integer
e0 = (LInt 5 :+: LInt 3) :*: LInt 8
ex0 = eval e0
\end{code}
And now shallow:
\begin{code}
lint :: Integer -> Integer
ladd :: Integer -> Integer -> Integer
lmul :: Integer -> Integer -> Integer
— the explicit way of defining things:
— lint i = i
— ladd x y = x + y
— lmul x y = x * y
— the implicit way:
lint = id
ladd = (+)
lmul = (*)
ex1 :: Integer
ex1 = lmul (ladd (lint 5) (lint 3)) (lint 8)
\end{code}
And now, as an interface
\begin{code}
class ExprSy e where
int :: Integer -> e
add :: e -> e -> e
mul :: e -> e -> e
\end{code}
Give an implementation:
\begin{code}
newtype R = R {unR :: Integer}
liftR2 :: (Integer -> Integer -> Integer) -> (R -> R -> R)
liftR2 f = \x y -> R $ f (unR x) (unR y)
instance ExprSy R where
— obvious, most direct impl:
— int i = R i
— add (R i) (R j) = R (i + j)
— mul (R i) (R j) = R (i * j)
— the more interesting implementation:
int = R
add = liftR2 (+)
mul = liftR2 (*)
p2 :: ExprSy e => e
p2 = mul (add (int 5) (int 3)) (int 8)
ex2 :: Integer
ex2 = unR p2
\end{code}
But we can easily write ‘other’ interpretations…
Example: size. First deep, then tagless.
\begin{code}
sizeE :: Expr -> Int
sizeE (LInt _) = 1
sizeE (x :+: y) = sizeE x + sizeE y + 1
sizeE (x :*: y) = sizeE x + sizeE y + 1
newtype S = S {unS :: Int}
instance ExprSy S where
int _ = S 1
add (S i) (S j) = S (i + j + 1)
mul (S i) (S j) = S (i + j + 1)
ex2′ :: Int
ex2′ = unS p2
\end{code}
(Recall: in Haskell Ints are small, Integers are arbitrary sized)