Rewriting code with continuations

Question

I have some code that evaluates primitive programs. Program is a list of statements (expression, block, return statement). Result of evaluation is last evaluated expression. Also evaluator should properly treat return statement (i.e. stop evaluation after first occurrence of return).

To implement this logic I pass special callback function (NextStep) which make next evaluating step after current statement. I don't call next step when handling return statement:

data Statement = 
      Expr Int
    | Block [Statement]
    | Return Int
    deriving (Show, Eq)

data Value = 
      Undefined
    | Value Int
    deriving (Show, Eq)

type NextStep = Value -> Value

evalStmt :: Statement -> NextStep -> Value
evalStmt (Expr val) next = 
    let res = Value val
    in next res
evalStmt (Block stmts) next = evalBlock stmts next
evalStmt (Return val) next = Value val

evalBlock :: [Statement] -> NextStep -> Value
evalBlock [] next = next Undefined
evalBlock [st] next = evalStmt st next
evalBlock (st:rest) next = evalStmt st $ \ _ -> evalBlock rest next

evalProgram stmts = evalBlock stmts id

prog1 = [Expr 1, Block [Return 3, Expr 2], Expr 4] 
evalProg1 = evalProgram prog1 -- result will be Value 3

The question is how can I rewrite this code with continuation monad? I want to get rid of explicitly passed NextStep callback in evalStmt and evalBlock functions. Is it possible?

Ic

Answer 1

The translation is fairly mechanical.

Keep in mind that in the continuation monad, return feeds the value into the continuation.

evalStmt :: Statement -> Cont Value Value
evalStmt (Expr val) = 
    let res = Value val
    in return res
evalStmt (Block stmts) = evalBlock stmts
evalStmt (Return val) = cont $ \_ -> Value val

evalBlock :: [Statement] -> Cont Value Value
evalBlock [] = return Undefined
evalBlock [st] = evalStmt st
evalBlock (st:rest) = evalStmt st >> evalBlock rest

evalProgram :: [Statement] -> Value
evalProgram stmts = runCont (evalBlock stmts) id

And to simulate early returns, we just ignore the continuation given to Return val and just return the value we have.

Caucus

The monad instance for Cont is defined to chain in precisely that way, so that should simply be equivalent to evalBlock (st:rest) = evalStmt st >> evalBlock rest – Saturninasaturnine