在没有 Cont Monad 的情况下使用 Continuation Passing Style 进行评估

Question

我有一个任务：编写一个函数 evalCPS 来评估由下面的 ADT 形式化的表达式，使用 Continuation Passing Style 但没有 Cont Monad 或类似的东西。

data Expr a = Expr a :+: Expr a
            | Expr a :/: Expr a
            | Num Int
            | Var a
            | Let a Int (Expr a)

我为前三个构造函数做了，这并不难：

evalCPS :: Expr a -> (Int -> r) -> r

evalCPS (Num n) k = k n

evalCPS (e1 :+: e2) k =
   evalCPS e1 $ \n1 ->
   evalCPS e2 $ \n2 ->
   k (n1 + n2)

evalCPS (e1 :/: e2) k =
  evalCPS e2 $ \n2 ->
  if n2 == 0 then error "division by zero" else evalCPS e1 $ \n1 ->
  k (n1 `div` n2)

但现在我只能使用 Var 和 Let 构造函数。我想我有点理解如何使用 monad 来做到这一点，因为我在其中有绑定运算符，但我需要一个建议如何直接解决它，而不是使用 monads。将非常感谢您的帮助！

Answer 1

您需要为自己设置某种存储空间来存储通过 Let 定义的变量的值。在一般的interpreter/compiler术语中，这种存储通常被称为"environment"。让我们这样定义它：

type Env a = ...

每当遇到Let，就需要在存储中添加一个变量。每当遇到 Var 时，都需要在存储中查找变量。此外，整个计算应该从一个空存储开始。这意味着对存储应该有三个操作：

emptyEnv :: Env a
lookupVar :: a -> Env a -> Int
insertVar :: (a, Int) -> Env a -> Env a

现在，您的 evalCPS 函数需要将 Env 作为参数（否则它将如何查找变量？）。这将是应该在其上下文中评估表达式的环境：

evalCPS :: Env a -> Expr a -> (Int -> r) -> r

:+: 案例不需要查看环境，因此它应该直接将其传递给递归 evalCPS 调用：

evalCPS env (e1 :+: e2) k =
   evalCPS env e1 $ \n1 ->
   evalCPS env e2 $ \n2 ->
   k (n1 + n2)

:/: 案例也类似。

Var 案例将查找环境中的变量值，并且只是 return 它（通过调用延续）：

evalCPS env (Var a) k =
   k $ lookupVar a env

很简单。

Let案例必须通过将新变量添加到旧变量来构造一个新环境，然后在这个新环境的上下文中计算表达式：

evalCPS env (Let a value e) k =
    let newEnv = insertVar (a, value) env
    in evalCPS newEnv e k

还是够简单的。

现在，我们如何实施环境本身？ lookupVar、insertVar、emptyEnv的身体应该是什么样的？

从概念上讲，环境可以看作只是一个函数：你给它一个变量标识符，它会返回它的 Int 值。从这个理解来看，最简单的环境实现可能会失败：

type Env a = a -> Int

由此，定义 lookupVar:

是微不足道的

lookupVar :: a -> Env a -> Int
lookupVar a env = env a

emptyEnv 有点棘手。让我们想一想：当程序试图引用一个尚未定义的变量时会发生什么？这个问题有很多种可能的答案，但我会按照你的指导处理这个错误情况，就像你处理除零一样：只需调用 error:

emptyEnv :: Env a
emptyEnv _ = error "Undefined variable"

insertVar 更棘手。让我们再想一想：当我将一个值为 v 的变量 a 添加到现有环境 e 时，结果应该是一个新环境，这样如果有人试图查找变量 a，结果应该是值v。让我们记下来：

insertVar :: Eq a => (a, Int) -> Env a -> Env a
insertVar (a, v) oldEnv = 
    \x -> if x == a then v else ???

否则呢？好吧，如果有人试图查找 other 而不是 a 的任何变量，结果应该与 oldEnv 给出的结果相同。让我们也写下来：

insertVar :: Eq a => (a, Int) -> Env a -> Env a
insertVar (a, v) oldEnv = 
    \x -> if x == a then v else oldEnv x

很简单。请注意，因为我使用的是比较运算符 ==，所以我必须向类型签名添加一个 Eq a 约束。由于 evalCPS 试图在某个时候调用 insertVar，约束也会渗入 evalCPS：

evalCPS :: Eq a => Env a -> Expr a -> (Int -> r) -> r

这是合理的：如果我们希望能够在我们的变量存储中查找变量，必须有一些方法来判断哪个变量是哪个。

当然，Env 的这种实现有一个关键缺点：它在每次查找时都有效地执行线性搜索，从而导致在变量很多时性能不佳。虽然这对于玩具练习来说没问题，但对于任何严肃的编译器或解释器来说都行不通。

如果需要更好的性能，请随意尝试其他存储变量 -> 值映射的方法。例如，您可能希望将存储实现为 Map（提供对数查找时间）：

type Env a = Map a Int

我将 emptyEnv、lookupVar 和 insertVar 的实现留作练习。

在没有 Cont Monad 的情况下使用 Continuation Passing Style 进行评估

Evaluation with Continuation Passing Style without the Cont Monad

haskell

functional-programming

expression-evaluation

continuation-passing