Language.CB

Embedding a higher-order domain-specific language (simply-typed lambda-calculus with constants) with a selectable evaluation order: Call-by-value, call-by-name, call-by-need in the same Final Tagless framework

http://okmij.org/ftp/tagless-final/tagless-typed.html#call-by-any

Documentation

data IntT

Our EDSL is typed. EDSL types are built from the following two type constructors:

data a :-> b

class EDSL exp where

We could have used Haskell's type Int and the arrow -> constructor. We would like to emphasize however that EDSL types need not be identical to the host language types. To give the type system to EDSL, we merely need labels -- which is what IntT and :-> are

The (higher-order abstract) syntax of our DSL

Methods

lam :: (exp a -> exp b) -> exp (a :-> b)

app :: exp (a :-> b) -> exp a -> exp b

int :: Int -> exp IntT

add :: exp IntT -> exp IntT -> exp IntT

sub :: exp IntT -> exp IntT -> exp IntT

Instances

MonadIO m => EDSL (S Lazy m)

MonadIO m => EDSL (S Value m)

MonadIO m => EDSL (S Name m)

let_ :: EDSL exp => exp a -> (exp a -> exp b) -> exp b

A convenient abbreviation

t :: EDSL exp => exp IntT

A sample EDSL term

type family Sem m a :: *

Interpretation of EDSL types as host language types The type interpretation function Sem is parameterized by m, which is assumed to be a Monad.

newtype S l m a

Interpretation of EDSL expressions as values of the host language (Haskell) An EDSL expression of the type a is interpreted as a Haskell value of the type S l m a, where m is a Monad (the parameter of the interpretation) and l is the label for the evaluation order (one of Name, Value, or Lazy). (S l m) is not quite a monad -- only up to the Sem interpretation

Constructors

S

Fields

unS :: m (Sem m a)

Instances

MonadIO m => EDSL (S Lazy m)

MonadIO m => EDSL (S Value m)

MonadIO m => EDSL (S Name m)

data Name

Call-by-name

Instances

MonadIO m => EDSL (S Name m)

runName :: S Name m a -> m (Sem m a)

t1 :: EDSL exp => exp IntT

Evaluating:

 t = (lam $ \x -> let_ (x `add` x)
                      $ \y -> y `add` y) `app` int 10

The addition (x add x) is performed twice because y is bound to a computation, and y is evaluated twice

t2 :: EDSL exp => exp IntT

A better example

data Value

The result of subtraction was not needed, and so it was not performed | OTH, (int 5 add int 5) was computed four times

Instances

MonadIO m => EDSL (S Value m)

vn :: S Value m x -> S Name m x

We reuse most of EDSL (S Name) except for lam

nv :: S Name m x -> S Value m x

runValue :: S Value m a -> m (Sem m a)

share :: MonadIO m => m a -> m (m a)

data Lazy

Instances

MonadIO m => EDSL (S Lazy m)

ln :: S Lazy m x -> S Name m x

We reuse most of EDSL (S Name) except for lam

nl :: S Name m x -> S Lazy m x

runLazy :: S Lazy m a -> m (Sem m a)