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!