软件设计实践大作业

Lv.3 求值环境

语法分析、词法分析都完成了，接下来就是核心中的核心——求值。我们的目标是，把列表 (+ 1 2) 求值得到 3。求值器的实现非常复杂，肯定不是这一部分就能完全讲完的——不然后面的章节就没事情可做了。所以，我们一点一点来，首先还是基本的框架。

任务 3.1 平凡的求值

新建 eval_env.h 和 eval_env.cpp，在其中定义类 EvalEnv。它具有一个方法 eval：

#include "./value.h"
class EvalEnv {
public:
    ValuePtr eval(ValuePtr expr);
};

暂时先只关注 eval，不管其它的东西（比如构造函数具体的样子）。也就是说，给定一个表达式，到底应该如何求值？稍微思考一下，可以得出这样的流程：

  • 如果表达式是一个布尔值、数值、字符串值（以及过程值，这里还没涉及），那么求值结果就是其自身。这种表达式称为自求值表达式。
  • 如果表达式是一个空表，那么这是一个错误——Mini-Lisp 不允许对空表求值。
  • 如果表达式是一个符号，那么去当前的符号表中找这个符号。什么是符号表？就是当前已经定义的变量的列表。
  • 否则，表达式应当是一个列表。那么考察列表的第一个元素：
    • 如果列表的首个元素是类似 define if 这种符号，那么这是一个特殊形式，进行相关的特殊操作；
    • 否则，这是一个过程调用。对首个元素求值得到过程，对剩余元素求值得到实参，然后进行调用。

咱们目前至少前两种情况是能写出来的。

ValuePtr EvalEnv::eval(ValuePtr expr) {
    if (/* expr 是自求值表达式 */) {
        return expr;
    } else if (/* expr 是空表 */) {
        throw LispError("Evaluating nil is prohibited.");
    } else {
        throw LispError("Unimplemented");
    }
}

虽然简短，但是仍然有几个要点。首先是上面的这两行判断具体要如何写的问题。你当然可以像之前说得那样，直接用 typeid 或者 dynamic_cast 判断，但是这样会写得很啰嗦。我们建议你在 Value 基类上定义一些工具函数，比如 Value::isNil 或者 Value::isSelfEvaluating 等等，然后直接在这里调用它们。这样代码看上去也会很整洁。

其次就是这里使用了 LispError 这个异常类，它使我们之前没定义过的。我们的意图是要区分语法分析的错误和求值阶段的错误。使用不同的异常类 SyntaxError LispError 来标识它们，这样在 catch 的时候就可以进行区分，做不同的处理。你需要在 error.h 添加这样一个异常类的定义。

随后，在 main 函数中将这个简单的求值器接在语法分析器的后面：

EvalEnv env;
while (true) {
  // [...]
  auto tokens = Tokenizer::tokenize(line);
  Parser parser(std::move(tokens));
  auto value = parser.parse();
  auto result = env.eval(std::move(value));
  std::cout << result->toString() << std::endl;
}
 





 


程序运行的效果是这样的：

>>> 42
42
>>> #f
#f
>>> ()
Error: Evaluating nil is prohibited.
>>> (+ 1 2)
Error: Unimplemented

Emm……好吧，仍然是一个愚蠢的复读机。慢慢来吧。

任务 3.2 变量定义与查找

在 Mini-Lisp 中，变量通过 define 特殊形式定义。目前这个阶段咱们就做一个特判：

if (expr 是列表 && 列表[0] == "define") {
    auto 变量名 = 列表[1];
    auto 值 = 列表[2];
    将 (变量名, 值) 添加到符号表中;
}

全是伪代码。具体要写成什么样呢？首先我们可以定义一个将 Value 转换成 std::vector 的方法，这样就可以轻松地通过 v[i] 这种方式访问列表特定位置的元素。比如你可以定义方法 Value::toVector；转换失败时抛出异常。

然后我们可以检查 v[0] 是否是符号 define。这一步可以通过定义方法 Value::asSymbol——它可以返回 std::optional<std::string>，如果这个值不是符号就返回 std::nullopt。类似地，这一套方法可以用在获取变量名的逻辑上。

using namespace std::literals; // 使用 s 后缀
std::vector<ValuePtr> v = expr->toVector();
if (v[0]->asSymbol() == "define"s) {
  if (auto name = v[1]->asSymbol()) {
      将 ( 符号name , v[2]的值 ) 添加到符号表中;
      return 空表;
  } else {
      throw LispError("Malformed define.");
  }
}

最后来处理符号表。为什么我们管求值的这个东西叫求值 环境 呢？这个环境其实就代表了符号表。符号表是一个字典数据结构，通过唯一键值区分的键值对的集合。C++ 中有 std::map 和 std::unordered_map，通过不同的内部数据结构来实现。我们这里需要的符号表的键的类型是 std::string，值的类型则是 ValuePtr。给 EvalEnv 添加这样的数据成员，然后实现符号表的添加。

TIP

std::map 要求键类型是可比较大小的，std::unordered_map 要求键类型是可哈希的。由于 std::string 这两个条件都满足，所以你可以任意选择。一般情况下，std::unordered_map 性能会好一点。

有了 define 和符号表之后，就可以实现符号表的查找。如果传入的表达式是一个符号，那么就在符号表里查找对应的值，然后返回。当然，这要求每次求值时都使用同一个符号表，或者说同一个求值环境。

if (auto name = expr->asSymbol()) {
    if (auto value = 符号表.查找(*name)) {
        return value;
    } else {
        throw LispError("Variable " + *name + " not defined.");
    }
}

如是操作后，就只剩下一种表达式没有实现——调用过程。我们还没有定义过任何过程，所以接下来从定义内置过程 + 开始，逐步实现 (+ 1 2) 的求值。

测试

现在你的程序看上去聪明了那么一点点。

>>> "Hello"
"Hello"
>>> (define x 42)
()
>>> x
42
>>> (define y x)
()
>>> y
42
>>> (+ x y)
Error: Unimplemented

阶段性检查

本阶段仍使用“测试框架” rjsj_test。

#include "rjsj_test.hpp"
struct TestCtx {
    EvalEnv env;
    std::string eval(std::string input) {
        auto tokens = Tokenizer::tokenize(input);
        Parser parser(std::move(tokens));
        auto value = parser.parse();
        auto result = env.eval(std::move(value));
        return result->toString();
    }
};
int main() {
    RJSJ_TEST(TestCtx, Lv2, Lv3);
    // [...]
}


 




 
 






如上所述，将“求值环境” env 作为 TestCtx 的成员，随后修改 eval 方法为新的求值过程。调用宏的方法修改为 RJSJ_TEST(TestCtx, Lv2, Lv3)，即测试 Lv2 和 Lv3 两个测试用例集。重新编译并运行后，观察测试结果。

在教学网 大作业 / Lv.3 检查 处，提交上述测试的运行截图（包含运行窗口即可）。在 2024 年 5 月 19 日 23:59:59 前提交的，可能获得分数加成。

Last Updated:
Contributors: Guyutongxue