If you are a Haskell convert from Lisp, JavaScript or any other dynamic programming language, you might miss eval function of those languages. eval lets us load code dynamically and execute it on the fly. It is commonly used to provide user-defined plugins and is a very handy tool for software extension.

Dynamic evaluation is not limited to dynamic languages. Even Java supports dynamic class loading through class loaders. It seems Haskell does not support dynamic evaluation as it is a strictly defined language. But GHC allows us to compile and execute Haskell code dynamically through GHC API.

hint library provides a Haskell interpreter built on top of GHC API. It allows to load and execute Haskell expressions and even coerce them into values.

hint provides a bunch of monadic actions based on InterpreterT monad transformer. runInterpreter is used to execute the action.

runInterpreter :: (MonadIO m, MonadMask m) => InterpreterT m a -> m (Either InterpreterError a)

Type check

We can check the type of a Haskell expression using typeOf.

λ> import Language.Haskell.Interpreter
λ> runInterpreter $ typeOf "\"foo\""
Right "[GHC.Types.Char]"
λ> runInterpreter $ typeOf "3.14"
Right "GHC.Real.Fractional t => t"

Import modules

hint does not import prelude implicitly. We need import modules explicitly using setImport. For qualified imports, use setImportQ instead.

λ> runInterpreter $ do { setImports ["Prelude"]; typeOf "head [True, False]" }
Right "Bool"
λ> runInterpreter $ do { setImportsQ [("Prelude", Nothing), ("Data.Map", Just "M") ]; typeOf "M.empty" }
Right "M.Map k a"

Evaluate expressions

eval function lets us evaluate Haskell expressions dynamically.

λ> runInterpreter $ do { setImports ["Prelude"]; eval "head [True, False]" }
Right "True"
λ> runInterpreter $ do { setImports ["Prelude"]; eval "1 + 2 * 3" }
Right "7"

The result type of evaluation is String. To convert the result into the type we want, use interpret with as. Here as provides a witness for its monomorphic type.

λ> runInterpreter $ do { setImports ["Prelude"]; interpret "head [True, False]" (as :: Bool) }
Right True
λ> runInterpreter $ do { setImports ["Prelude"]; interpret "1 + 2 * 3" (as :: Int) }
Right 7

Load modules

It is also possible to load modules dynamically.

Here’s a small module Foo stored in Foo.hs file.

module Foo where

f = head
g = tail

We can load Foo using loadModules function. setTopLevelModules ensures that all bindings of the module are in scope.

import Control.Monad
import Language.Haskell.Interpreter

ex :: Interpreter ()
ex = do
  loadModules ["Foo.hs"]
  setTopLevelModules ["Foo"]
  setImportsQ [("Prelude", Nothing)]

  let expr1 = "f [1, 2, 3]"
  a <- eval expr1
  liftIO $ print a

  let expr2 = "g [1, 2, 3]"
  a <- eval expr2
  liftIO $ print a

main :: IO ()
main = do
  r <- runInterpreter ex
  case r of
    Left err -> print err
    Right () -> return ()

Executing this program prints

"1"
"[2,3]"

because f is head and g is tail.

In the Continuation Passing Style Interpreter, we wrote a continuation-passing style interpreter for a small functional language and implemented the escape expression which is the binder form of Scheme’s call/cc.

Though call/cc is a powerful control operator, it is generally considered as a bad abstraction as a core language feature. So, in this post, we will drop escape expressions and add ML-style exceptions.

Exceptions can be used to effect non-local transfers of control. By using an exception handler we may “catch” a raised exception and continue evaluation. For example,

1 + (raise 2)
handle \x -> x + 3

evaluates to 5 because 2 raised by raise 2 is passed to the exception handler \x -> x + 3.

To support exceptions in our interpreter, eval function is modified to take two continuations: an exception-handler continuation, and a return continuation. This is the so-called double-barrelled continuation-passing style introduced in Comparing Control Constructs by Double-barrelled CPS.

eval :: Env -> Expr -> Cont -> Cont -> Value
eval env term h k = case term of
  Var n -> k $ env !! n
  Lam a -> k $ VClosure (\v k' -> eval (v : env) a h k')
  App a b ->
    eval env a h $ \(VClosure c) ->
    eval env b h $ \v ->
    c v k

  Lit n -> k $ VInt n
  Prim p a b -> eval env a h $ \v1 ->
                eval env b h $ \v2 ->
                k $ evalPrim p v1 v2

evalExpr :: Expr -> Value
evalExpr e = eval emptyEnv e (\x -> error "uncaught exception") id

h is the exception-handler continuation and it is simply passed along the application of eval. evalExpr is also modified to handle an uncaught exception.

Once our interpreter is transformed into a double-barrelled continuation-passing style, it is easy to add handle and raise expressions. First, let’s extend Expr with Handle and Raise nodes.

data Expr
  = ...
  | Handle Expr Expr
  | Raise Expr
  ...

Then extend eval function with two additional AST nodes.

eval :: Env -> Expr -> Cont -> Cont -> Value
eval env term h k = case term of
  ...
  Raise a -> eval env a h h
  Handle a b ->
    let h' x = eval (x : env) b h k
    in eval env a h' k

Raise evaluates a with both continuations set to the error-handler continuation h. So the value is passed to the current error-handler.

Handle sets up a new error-handler h' which evaluates b with the environment extended with the raised value x. Note that a is evaluated with the error-handler set to h' so that any exception raised while evaluating a is passed to h'.

Let’s run the example above!

λ> evalExpr $ (Prim Add (Lit 1) (Raise (Lit 2))) `Handle` (Prim Add (Var 0) (Lit 3))
5

Yay, it works again!

If you would like to know why we can’t implement exceptions using call/cc alone, please read Oleg Kiselyov’s article Vast difference between delimited and undelimited continuations.

Lisp programmers learn Lisp by writing various flavors of Lisp interpreters. Two famous Lisp books, Lisp in Small Pieces and Essentials of Programming Languages, teach us how to write Lisp interpreters in Lisp. Both books start with a direct style interpreter which is easy to implement. But they soon rewrite the interpreter in a continuation passing style because advanced control structures such as abort and call/cc can be implemented more easily in this style.

In this post, we will follow the tradition of Lisp and will write a continuation passing style interpreter for a small functional language in Haskell. Then we will see how easily we can add escape expression to the language by extending the interpreter.

Direct-style Interpreter

Our first interpreter is a straightforward implementation of the enriched lambda calculus Expr. It extends the lambda calculus with integer literals and primitive operators.

data Expr
  = Var Int
  | Lam Expr
  | App Expr Expr
  | Lit Int
  | Prim PrimOp Expr Expr
  deriving Show

data PrimOp = Add | Mul
  deriving Show

The central component of our interpreter is a function eval that produces the value of an expression term in an environment env. n in Var n is the De Bruijn index. The Evaluation chapter of Stephen Diehl’s Write You a Haskell explains the details of this direct-style interpreter. There is one difference here. Our version uses a higher-order function to represent lambda expression (VClosure).

data Value
  = VInt Int
  | VClosure (Value -> Value)

instance Show Value where
  show (VInt i) = show i
  show VClosure{} = "<<closure>>"

type Env = [Value]

eval :: Env -> Expr -> Value
eval env term = case term of
  Var n -> env !! n
  Lam a -> VClosure (\v -> eval (v : env) a)
  App a b ->
    let VClosure c = eval env a in
    let v = eval env b in
    c v

  Lit n -> VInt n
  Prim p a b -> (evalPrim p) (eval env a) (eval env b)

evalPrim :: PrimOp -> Value -> Value -> Value
evalPrim Add (VInt a) (VInt b) = VInt (a + b)
evalPrim Mul (VInt a) (VInt b) = VInt (a * b)

emptyEnv :: Env
emptyEnv = []

evalExpr :: Expr -> Value
evalExpr = eval emptyEnv

Continuation-passing-style Interpreter

We can think of a continuation as what to do next in a program. In direct-style, a callee returns a value to the caller. Thus the caller of the function determines what to do next and the continuation is implicitly present in the caller. In continuation-passing-style, the continuation is passed as an argument of a function and the callee determines what to do next by invoking the continuation. A function in continuation-passing-style never returns.

We can transform our interpreter into a continuation-passing-style by adding a continuation argument Cont to eval and VClosure.

type Cont = Value -> Value

data Value
  = ...
  | VClosure (Value -> Cont -> Value)

eval :: Env -> Expr -> Cont -> Value
eval env term k = case term of
  Var n -> k $ env !! n
  Lam a -> k $ VClosure (\v k' -> eval (v : env) a k')
  App a b ->
    eval env a $ \(VClosure c) ->
    eval env b $ \v ->
    c v k

  Lit n -> k $ VInt n
  Prim p a b -> eval env a $ \v1 ->
                eval env b $ \v2 ->
                k $ evalPrim p v1 v2

evalExpr :: Expr -> Value
evalExpr e = eval emptyEnv e id

In Var, Lit and Lam cases, eval simply applies the value to the continuation. In App case, eval evaluates the function first and then subsequently evaluates the argument. The evaluation order is enforced as only one value can be passed to the continuation. c v applies the argument to the function and its result is passed to the original continuation k. Prim case similarly enforces the left-to-right evaluation order.

evalExpr passes id as the initial continuation which merely returns the value back.

Escape Expression

Because all the control paths are explicit in continuation-passing-style, we can easily add control operators to our interpreter. Let’s extend our interpreter with escape expressions that was first introduced in Definitional interpreters for higher-order programming languages.

escape x in r

is an escape expression, whose escape variable is x and whose body is r. If x is applied to a in r, the body is aborted and a is returned. Otherwise, the evaluation of r proceeds normally.

escape x in (1 + 3) * (4 + x 10)

evaluates to 10 because x is applied to 10 inside the escape expression.

The implementation of the escape expression is one-liner. eval of Escape a adds a closure to the environment and then evaluates the expression. This closure is a reified continuation which ignores the current continuation and passes the argument as a value to the saved continuation of the escape expression.

data Expr
  = ...
  | Escape Expr
  ...

eval :: Env -> Expr -> Cont -> Value
eval env term k = case term of
  ...
  Escape a -> eval (VClosure (\v _ -> k v) : env) a k

λ> evalExpr $ Escape (Prim Mul (Prim Add (Lit 1) (Lit 3)) (Prim Add (Lit 4) (App (Var 0) (Lit 10))))
10

Yay, it works!

Call-by-value is the most commonly used evaluation strategy in which all arguments to a function are reduced to normal form before they are bound inside lambda. Languages such as Java, C++, Scala and F# all use this evaluation model. A notable exception is Haskell, which uses call-by-need evaluation in which expressions are represented as thunks which are passed into a function unevaluated and only evaluated when needed.

This difference in evaluation model poses some challenges in writing a call-by-value interpreter in Haskell. In this post, I am going to explain how we can implement a call-by-value interpreter using various methods.

Let’s start the discussion by writing a lambda calculus interpreter.

data Expr
  = Var Int
  | Lam Expr
  | App Expr Expr
  | Lit Int
  | Prim PrimOp Expr Expr
  | Bot
  deriving Show

data Value
  = VInt Int
  | VClosure Expr Env

instance Show Value where
  show (VInt i) = show i
  show VClosure{} = "<<closure>>"

data PrimOp = Add | Mul
  deriving Show

type Env = [Value]

eval :: Env -> Expr -> Value
eval env term = case term of
  Var n -> env !! n
  Lam a -> VClosure a env
  App a b ->
    let VClosure c env' = eval env a in
    let v = eval env b in
    eval (v : env') c

  Lit n -> VInt n
  Prim p a b -> (evalPrim p) (eval env a) (eval env b)
  Bot -> error "Evaluation would not terminate"

evalPrim :: PrimOp -> Value -> Value -> Value
evalPrim Add (VInt a) (VInt b) = VInt (a + b)
evalPrim Mul (VInt a) (VInt b) = VInt (a * b)

emptyEnv :: Env
emptyEnv = []

-- (\x y -> x) 10 bot
test :: Value
test = eval emptyEnv $ App (App (Lam (Lam (Var 1))) (Lit 10)) Bot

Can you guess the evaluation order implemented by this interpreter? Because test is equivalent to (\x y -> x) 10 undefined, it would be undefined in a call-by-value language.

Let’s evaluate test on GHCi.

λ> test
10

The evaluation order implemented by our interpreter is call-by-need because the defining language, Haskell, uses the call-by-need evaluation order and our interpreter depends on this. Transforming our interpreter into a call-by-value interpreter is not trivial because we need to find and fix every place where lazy evaluation is used in our interpreter.

In his seminar paper Definitional interpreters for higher-order programming languages, John C. Reynolds showed how to remove this order dependence by CPS transformation. But in Haskell, we can use monads to enforce the evaluation order. This is not a coincidence because there is a close relationship between computational monads and generalized CPS.

UPDATE: There is a technical mistake in the original article. The Identity monad does not make any difference here. I should have used either a strict variant of Identity monad or the Cont monad to force strict evaluation.

Here’s a monadic version of our interpreter.

import Control.Monad.Identity

data Expr
  = Var Int
  | Lam Expr
  | App Expr Expr
  | Lit Int
  | Prim PrimOp Expr Expr
  | Bot
  deriving Show

data Value
  = VInt Int
  | VClosure Expr Env

instance Show Value where
  show (VInt i) = show i
  show VClosure{} = "<<closure>>"

data PrimOp = Add | Mul
  deriving Show

type Env = [Value]

eval :: (Monad m) => Env -> Expr -> m Value
eval env term = case term of
  Var n -> return $ env !! n
  Lam a -> return $ VClosure a env
  App a b -> do
    VClosure c env' <- eval env a
    v <- eval env b
    eval (v : env') c

  Lit n -> return $ VInt n
  Prim p a b -> evalPrim p <$> eval env a <*> eval env b
  Bot -> error "Evaluation would not terminate"

evalPrim :: PrimOp -> Value -> Value -> Value
evalPrim Add (VInt a) (VInt b) = VInt (a + b)
evalPrim Mul (VInt a) (VInt b) = VInt (a * b)

emptyEnv :: Env
emptyEnv = []

-- (\x y -> x) 10 bot
test :: Value
test = runIdentity $ eval emptyEnv $ App (App (Lam (Lam (Var 1))) (Lit 10)) Bot

Let’s evaluate test again.

λ> test
10

Oops. What went wrong? The problem is that our interpreter does not enforce the evaluation of the argument in App a b case of eval. v <- eval env b just binds a thunk to v and it won’t be evaluated until it is actually needed. To fix the problem, we need to force the evaluation of the argument using bang patterns.

UPDATE: This bang pattern is not necessary if we used a strict monad.

{-# LANGUAGE BangPatterns #-}

...

eval :: (Monad m) => Env -> Expr -> m Value
eval env term = case term of
  Var n -> return $ env !! n
  Lam a -> return $ VClosure a env
  App a b -> do
    VClosure c env' <- eval env a
    !v <- eval env b
    eval (v : env') c

  Lit n -> return $ VInt n
  Prim p a b -> evalPrim p <$> eval env a <*> eval env b
  Bot -> error "Evaluation would not terminate"

...

Finally, we can see that evaluating test throws an error.

λ> test
*** Exception: Evaluation would not terminate

The moral of this story is that it is really hard to correctly implement a call-by-value interpreter in Haskell. There is high chance of making a mistake. For example, let’s add a division operator to our interpreter.

data PrimOp = Add | Mul | Div
  deriving Show

evalPrim :: PrimOp -> Value -> Value -> Value
evalPrim Add (VInt a) (VInt b) = VInt (a + b)
evalPrim Mul (VInt a) (VInt b) = VInt (a * b)
evalPrim Div (VInt a) (VInt b) = VInt (a `div` b)

-- (\x y -> x) 10 (20 / 0)
test :: Value
test = runIdentity $ eval emptyEnv $ App (App (Lam (Lam (Var 1))) (Lit 10)) (Prim Div (Lit 20) (Lit 0))

Evaluating test must throw an divide-by-zero error because its second argument is 20 / 0. But GHCi shows that we reverted back to cal-by-need.

λ> test
10

This happens because the data constructor VInt is not strict. 20 / 0 is evaluated to VInt undefined instead of undefined. To make it call-by-value again, we need to add another bang pattern to VInt data constructor as follows:

data Value
  = VInt !Int
  | VClosure Expr Env

Fortunately, we can avoid this tricky business and make our first interpreter call-by-value by just adding Strict language extension introduced in GHC 8. Strict pragma allows us to switch the default evaluation strategy to call-by-value on a per module basis. This saves us huge efforts because writing a call-by-value interpreter in a call-by-value language is an easy task!

{-# LANGUAGE Strict #-}

fold is a Swiss Army knife in functional programming. It is expressive enough to write an interpreter for a simple functional programming language.

Let’s start with a simple arithmetic language.

> data Expr = Const Int
>           | Add Expr Expr
>           | Mul Expr Expr

Writing an interpreter for this language is trivial.

> interp :: Expr -> Int
> interp (Const x) = x
> interp (Add e1 e2) = interp e1 + interp e2
> interp (Mul e1 e2) = interp e1 * interp e2

Writing a pretty printer is also easy.

> pretty :: Expr -> String
> pretty (Const x) = show x
> pretty (Add e1 e2) = "(" ++ pretty e1 ++ " + " ++ pretty e2 ++ ")"
> pretty (Mul e1 e2) = "(" ++ pretty e1 ++ " * " ++ pretty e2 ++ ")"

Sensitive readers might have noticed the duplication of code in interp and pretty. Yes, recursion on the structure of Expr is repeated.

We can extract recursion as foldExpr and algorithms as ExprA. foldExpr does recursion on the structure of Expr regardless of the algorithm being used.

> data ExprA a = ExprA
>   { val :: Int -> a
>   , add :: a -> a -> a
>   , mul :: a -> a -> a
>   }
> 
> foldExpr :: ExprA a -> Expr -> a
> foldExpr alg (Const i)   = val alg i
> foldExpr alg (Add e1 e2) = add alg (foldExpr alg e1) (foldExpr alg e2)
> foldExpr alg (Mul e1 e2) = mul alg (foldExpr alg e1) (foldExpr alg e2)

Now it is possible to define the interpreter just by giving val, add and mul functions.

> interpA :: ExprA Int
> interpA = ExprA
>   { val = id
>   , add = (+)
>   , mul = (*)
>   }

The same goes for pretty printer.

> prettyA :: ExprA String
> prettyA = ExprA
>   { val = show
>   , add = \a b -> "(" ++ a ++ " + " ++ b ++ ")"
>   , mul = \a b -> "(" ++ a ++ " * " ++ b ++ ")"
>   }

Here is our interp' function defined in terms of foldExpr and interpA.

> interp' :: Expr -> Int
> interp' = foldExpr interpA

We successfully isolated algorithms from recursion, but we are still not satisfied. ExprA is mostly duplication of Expr and defining foldExpr is boilerplate.

We can fix this by introducing F-algebras and catamorphisms. Interested readers might want to take a look at Bartosz Milewski’s Understanding F-Algebras article.

Writing an interpreter for a functional language is a good exercise in Haskell. There are several tutorials on this topic.

• Write Yourself a Scheme in 48 Hours
• Write You a Haskell

Implementation techniques used in these tutorials are similar even though their source languages are distinct. They all compile the source language into a small core language based on lambda calculus, and evaluate the program with a context (or an environment).

In this post, I am not going to revisit this common technique. Instead, I will show you how to compile a program to a finite, fixed set of combinators (SKI), and then evaluate these combinators as normal Haskell function. This technique was introduced in Matthew Naylor’s Evaluating Haskell in Haskell.

The source code is available here.

Poly

We are going to borrow the parser and type checker from Stephen Diehls’s Poly, a simple ML dialect with definitions, let polymorphism and a fixpoint operator.

An example of Poly:

let rec factorial n = if (n == 0) then 1 else (n * (factorial (n-1)));

The core language of Poly is a variant of lambda calculus. Let, If, Fix and Op are added as additional constructs.

type Name = String

data Expr
  = Var Name
  | App Expr Expr
  | Lam Name Expr
  | Let Name Expr Expr
  | Lit Lit
  | If Expr Expr Expr
  | Fix Expr
  | Op Binop Expr Expr
  deriving (Show, Eq, Ord)

data Lit
  = LInt Integer
  | LBool Bool
  deriving (Show, Eq, Ord)

data Binop = Add | Sub | Mul | Eql
  deriving (Eq, Ord, Show)

Desugar

Our first task is to desugar Let, If, Fix and Op to simplify the later stage of compilation.

desugar :: Expr -> Expr
desugar (App fun arg) = App (desugar fun) (desugar arg)
desugar (Lam x body) = Lam x (desugar body)
desugar (Let x e body) = App (Lam x (desugar body)) (desugar e)
desugar (If cond tr fl) = foldl App (Var "$IF") args
   where args = map desugar [cond, tr, fl]
desugar (Fix e) = App (Var "$FIX") (desugar e)
desugar (Op op a b) = foldl App (Var n) args
  where
    args = map desugar [a, b]
    n = case op of
      Add -> "$ADD"
      Sub -> "$SUB"
      Mul -> "$MUL"
      Eql -> "$EQL"
desugar e = e

desugar function converts let x = e in body into (\x -> body) e. If, Fix are Op are desugared into function applications. $IF, $FIX, $ADD, $SUB, $MUL, $EQL will be provided as primitive functions. (Note that $IF can be a function because we piggy back on the lazy evaluation of the host language, Haskell.)

Compilation to SKI combinators

The next step is to compile expressions into a fixed, finite combinators. The key idea is to replace Lam and Ap constructors with Haskell’s built-in lambda and application constructs. The original interpreter of Poly is slow because it emulates beta reduction on top of Haskell, but our implementation avoids this overhead by utilizing the host system’s support for beta-reduction.

For example,

Lam "f" (Lam "a" (Lam "b" (App (App (Var "f") (Var "b") (Var "a")))

is compiled to

CLam (\f -> CLam (\a -> CLam (\b -> ap (ap f b) a)))

Here’s the definition of CExpr. You can see that CLam contains a Haskell function CExpr -> CExpr. No variable in the lambda abstraction is necessary.

data CExpr
  = CVar Name
  | CApp CExpr CExpr
  | CLam (CExpr -> CExpr)
  | CBool Bool
  | CInt Integer

compile transforms a lambda calculus expression into an expression involving only S, K, I and constants. The SK compilation algorithm is well described in Simon Peyton Jones’s The Implementation of Functional Programming Languages.

compile :: Expr -> CExpr
compile (Var n) = CVar n
compile (App fun arg) = CApp (compile fun) (compile arg)
compile (Lam x body) = abstract x (compile body)
compile (Lit (LInt k)) = CInt k
compile (Lit (LBool k)) = CBool k

abstract :: Name -> CExpr -> CExpr
abstract x (CApp fun arg) = combS (abstract x fun) (abstract x arg)
abstract x (CVar n) | x == n = combI
abstract _ k = combK k

combS :: CExpr -> CExpr -> CExpr
combS f = CApp (CApp (CVar "$S") f)

combK :: CExpr -> CExpr
combK = CApp (CVar "$K")

combI :: CExpr
combI = CVar "$I"

For example, (\x -> + x x) 5 is transformed as follows:

S --> S (\x -> + x) (\x -> x) 5
S --> S (S (\x -> +) (\x -> x)) (\x -> x) 5
I --> S (S (\x -> +) I) (\x -> x) 5
I --> S (S (\x -> +) I) I 5
K --> S (S (K +) I) I 5

Primitives

Here’s the definition of our primitive functions:

infixl 0 !
(!) :: CExpr -> CExpr -> CExpr
(CLam f) ! x = f x

primitives :: [(String, CExpr)]
primitives =
  [ ("$I", CLam $ \x -> x)
  , ("$K", CLam $ \x -> CLam $ \_ -> x)
  , ("$S", CLam $ \f -> CLam $ \g -> CLam $ \x -> f!x!(g!x))
  , ("$IF", CLam $ \(CBool cond) -> CLam $ \tr -> CLam $ \fl -> if cond then tr else fl)
  , ("$FIX", CLam $ \(CLam f) -> fix f)
  , ("$ADD", arith (+))
  , ("$SUB", arith (-))
  , ("$MUL", arith (*))
  , ("$EQL", logical (==))
  ]

arith :: (Integer -> Integer -> Integer) -> CExpr
arith op = CLam $ \(CInt a) -> CLam $ \(CInt b) -> CInt (op a b)

logical :: (Integer -> Integer -> Bool) -> CExpr
logical op = CLam $ \(CInt a) -> CLam $ \(CInt b) -> if op a b then true else false

true, false :: CExpr
true = CBool True
false = CBool False

Link

The final step is link our compiled program with other functions and primitives in the environment. link traverses the structure of CExpr and replaces CVar node with the actual function definition.

type TermEnv = Map.Map String CExpr

emptyTmenv :: TermEnv
emptyTmenv = Map.fromList primitives

link :: TermEnv -> CExpr -> CExpr
link bs (CApp fun arg) = link bs fun ! link bs arg
link bs (CVar n) = fromJust (Map.lookup n bs)
link _ e = e

Eval

Finally, eval is just a composition of desugar, compile and link env.

eval :: TermEnv -> Expr -> CExpr
eval env = link env . compile . desugar

runEval :: TermEnv -> String -> Expr -> (CExpr, TermEnv)
runEval env nm ex =
  let res = eval env ex in
  (res, Map.insert nm res env)

Optimization

The basic compilation algorithm shown above tends to produce large combinator expressions. New combinators such as B, C, S', B' and C' can optimize both execution speed and program size.