时间戳

首页 > 解决方案 > 没有 Cont Monad 的继续传递风格的评估

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

问题描述

我有一个任务：编写一个函数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 来做到这一点，因为我有绑定运算符，但我需要一个建议如何直接解决它，而不使用 monad。将非常感谢您的帮助！

标签： haskellfunctional-programmingexpression-evaluationcontinuation-passing

解决方案

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

type Env a = ...

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

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

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

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案例将在环境中查找变量值并返回它（通过调用延续）：

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仍然更棘手。让我们再想一想：当我在现有环境中添加一个a带值的变量时，结果应该是一个新环境，这样如果有人试图查找 variable ，结果应该是 value 。让我们把它写下来：veav

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。

推荐阅读