haskell - 没有 Cont Monad 的继续传递风格的评估

Question

我有一个任务:写一个函数evalCPS它评估由下面的 ADT 形式化的表达式，使用继续传递样式但没有 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 来做到这一点，因为我在其中有绑定(bind)运算符，但我需要一个建议如何直接解决它，而不使用 monad。将非常感谢您的帮助!

Answer 1

您需要为自己获取某种存储空间来存储通过 Let 定义的变量的值。 .在一般解释器/编译器术语中，这种存储通常称为“环境”。让我们这样定义:

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

:+: case 不需要查看环境，所以它应该只是将它通过隧道传递到递归 evalCPS调用:

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

:/: 也是如此案子。
Var case 将在环境中查找变量值并返回它(通过调用延续):

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

很简单。
Let case 必须通过将新变量添加到旧变量来构造一个新环境，然后在这个新环境的上下文中计算表达式:

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

还是很简单的。

现在，我们如何实现环境本身？ lookupVar的尸体应该怎么做？ , insertVar , 和 emptyEnv看起来像？

从概念上讲，环境可以看作是一个函数:你给它一个变量标识符，它给你它的 Int。值(value)。根据这种理解，最简单的环境实现可能会失败:

type Env a = a -> Int

由此，定义 lookupVar 是微不足道的。 :

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

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

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

insertVar仍然更棘手。让我们再想一想:当我添加一个变量 a有值 v到现有环境 e ，结果应该是一个新的环境，这样如果有人试图查找变量 a ，结果应该是值 v .让我们把它写下来:

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

否则呢？好吧，如果有人试图查找除 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作为练习。