使用continuations重写代码

Question

我有一些评估原始程序的代码。程序是语句的列表(表达式、块、返回语句)。评估的结果是最后一个被评估的表达式。此外，评估器应该正确地处理"return"语句(即，在第一次出现"return"后停止评估)。

为了实现这个逻辑，我传递了一个特殊的回调函数(NextStep)，它在当前语句之后执行下一个评估步骤。当处理返回语句时，我不调用下一步。

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

问题是如何使用 continuation monad 重写此代码？我想摆脱在 evalStmt 和 evalBlock 函数中明确传递的 NextStep 回调。这可行吗？

- sergeyz

Answer 1

翻译相对机械。

请记住，在 continuation monad 中，return 将值传递给 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

为了模拟早期返回，我们只需忽略传递给Return val的继续执行，直接返回我们拥有的值。

- Daniel Gratzer

---

Cont 的单子实例被定义为精确地以这种方式链接，因此 should 应该等同于 evalBlock (st:rest) = evalStmt st >> evalBlock rest。 - Ørjan Johansen