软件设计实践大作业

Lv.6 Lambda

终于进入到 Lisp 的核心，重中之重，Lambda 表达式了！

我们之前已经部分实现了 Lambda 过程值的创建，但是还少了一些必要成分。比如，下面的表达式是合法的：

>>> (define y 10)
()
>>> (define (add-y x) (+ x y))
()
>>> (add-y 20)
30 ; 期望结果

过程 add-y 可以使用外层定义的变量 y。不仅如此，Lambda 内部也可以定义变量：

>>> (define (f) (define x 42) x)
()
>>> (f)
42 ; 期望结果
>>> x
Error: variable x not defined.

且这个变量只能在 f 的定义内部使用，外面是用不了的。所以我们说每个 Lambda 都有自己的一套求值环境——回想一下，什么是求值环境？就是变量名到值的绑定关系。在 Lambda 调用时定义的变量，只属于 Lambda 自己的求值环境而非调用前的全局环境。

此外，在 Lambda 中查找变量定义时，如果找不到，就会寻找全局的定义。我们称这种行为叫向上追溯。除了初始的求值环境，每个求值环境都有一个上级环境，如果当前环境找不到变量名，就会寻求上级的帮助。

Mini-Lisp 规定说，调用 Lambda 时使用的环境包含其形参到实参的绑定。而这个环境的上级环境，是 Lambda 被写出时的环境。这允许下面的代码：

>>> (define (compose f g) (lambda (x) (f (g x))))
()
>>> (define (add1 x) (+ x 1))
()
>>> (define add2 (compose add1 add1))
()
>>> (add2 42)
44

注意这里的 (lambda (x) ...) 写在 compose 过程内，所以这个 Lambda 过程被调用时的上级环境就是 compose 的环境。从而，在调用过程 add2 的时候，能够从 compose 环境中找到“局部变量” f 和 g。

详细说是这样的。首先，解释器求值 (compose add1 add1)。求值的时候，会调用 compose 过程，将名字 f 和 g 绑定到“加一”的过程 add 上。随后，过程返回了一个 Lambda，因此这个 Lambda 被定义的环境就是包含 f 和 g 这两对绑定的环境。我们管这个环境叫 A 好了。显然，A 的上级环境就是全局初始环境。

随后，我们把刚刚的那个 Lambda，在全局环境下，绑定到名字 add2 上。最后，我们调用了 add2——这个时候，求值环境就改成了 Lambda 的内部环境：这个内部环境包括名字 x 到值 42 的绑定。而按照规定，它的上级环境就是 A，包含了 f 和 g。在这个环境下，对 (f (g x)) 求值，就得到了 44。

我们的环境不再是一个环境，而且环境与环境之间出现了“上级”的关系。这就要求我们改写关于求值环境的一系列代码。

任务 6.1 重构求值环境

一个环境可能有多个使用者。比如刚刚的 compose 环境，就被其返回值作为上级环境所使用。而全局初始环境，则被所有的外层 Lambda 使用。当这些使用者不再用这些环境后，对应的内存也要释放。为了管理环境所持有的内存，我们只能选择 std::shared_ptr。

在 EvalEnv 中添加成员 std::shared_ptr<EvalEnv> parent，代表该环境的上级环境。parent 为 nullptr 就代表这个环境是唯一一个没有上级的，默认初始环境。

重构求值环境下的变量查找。定义成员函数 EvalEnv::lookupBinding，通过本层级的搜索和向上追溯来找到正确的变量定义。然后，修改 EvalEnv::eval 以应用这个方法。类似地，你也可以把变量定义包装为成员函数 EvalEnv::defineBinding。

重构完成后，你的代码应该仍然能通过所有之前的测试。

任务 6.2 Lambda 的上级环境

由于调用 Lambda 过程时，会将求值环境替换为一个 Lambda 内部环境，而且其上级环境是定义时的环境——所以在 LambdaValue 中，需要保存这个“定义时的环境”。随后，在调用的过程中，创建新环境并把它设为新环境的上级。

修改 LambdaValue 类的定义，添加一个 std::shared_ptr<EvalEnv> 数据成员来保存被定义时的环境。当然，构造函数也要跟着改一下。

最后，我们要修改 lambda 特殊形式（以及 define 特殊形式）中构造 LambdaValue 的代码。但是特殊形式中我们接收到的是一个 EvalEnv& 引用——我们需要把一个引用所绑定到的变量所对应的 std::shared_ptr 拿到手。

可以直接这样写吗？

ValuePtr lambdaForm(/* [...] */, EvalEnv& env) {
    // [...]
    auto envPtr = std::make_shared<EvalEnv>(env);
    return std::make_shared<LambdaValue>(/* [...] */, envPtr);
}


 


我这样问了说明肯定不行。std::make_shared 会创建一个新的控制块（引用计数块），因此会和原来控制 env 的引用计数块向冲突。那怎么获取原先控制 env 的那个 std::shared_ptr 的复制呢？当然，你可以直接将传入特殊形式的 EvalEnv& 改成 std::shared_ptr<EvalEnv>，这肯定就没问题了。但是这样不仅麻烦，没必要，性能也会降低。其实，标准库已经考虑到了这种情形，并给出了解决方案——std::enable_shared_from_this。

std::enable_shared_from_this 是一种 CRTP 手法。CRTP——中文叫诡异模板递归模式（Curiously Recurring Template Pattern）——总之就是一种比较诡异的写法。我们暂且不考虑那么多（如果感兴趣的话就在网上搜索搜索吧~），你需要做的改动是这样的：

修改 EvalEnv 的类声明，使其继承自 std::enable_shared_from_this<EvalEnv>：

class EvalEnv : public std::enable_shared_from_this<EvalEnv> {
  // [...]
};

随后，你的 EvalEnv 就拥有了一个名为 shared_from_this 的成员函数，返回值类型恰恰就是你想要的 std::shared_ptr<EvalEnv>。用就完事儿了。

return std::make_shared<LambdaValue>(/* [...] */, env.shared_from_this());

WARNING

如果 env.shared_from_this() 中的 env 不是被 std::shared_ptr 所管理的话，会抛出一个运行时异常！所以请仔细检查所有使用 EvalEnv 的地方是否正确定义。——一个常见的做法是将构造函数定义为私有的，然后只提供几个静态方法作为“创建工厂”，比如 static std::shared_ptr<EvalEnv> createGlobal()。

任务 6.3 调用 Lambda

现在开始修改 EvalEnv::apply，把之前没实现的部分补充完整。如果 proc 是 LambdaValue，那么就进行 Lambda 过程的调用。你可以给 LambdaValue 实现这么个接口：

ValuePtr LambdaValue::apply(const std::vector<ValuePtr>& args);

其中 args 是准备好的实参，然后直接在 EvalEnv::apply 中调用即可。那这个东西要怎么实现呢？

之前讨论过。首先是创建一个新的 Lambda 内部求值环境。这个应当包含 LambdaValue::params 数据成员到 args 的一一绑定。然后，将它的上级环境设置为之前保存的 parent。最后，在这个求值环境下对 body 数据成员的表达式逐一求值，返回最后一个即可。

至于怎么实现“新建求值环境”，方法就很多了。比如，你可以给 EvalEnv 再开一个接口：

std::shared_ptr<EvalEnv> EvalEnv::createChild(const std::vector<std::string>& params, const std::vector<ValuePtr>& args);

返回一个新的环境，将添加绑定和设置上级一口气完成。当然也有别的做法，取决于你自己想怎么写了。当然，咱们还是要工程化一点的；直接将数据成员设为公开的并不是一个好的做法。

测试

完成下面的测试，需要你实现内置过程 * 和 >。

>>> (define (square x) (* x x))
()
>>> (square 21)
441
>>> (define (sum-of-squares x y) (+ (square x) (square y)))
()
>>> (sum-of-squares 3 4)
25
>>> (define (add-partial x) (lambda (y) (+ x y)))
()
>>> (define add42 (add-partial 42))
()
>>> add42
#<procedure>
>>> (add42 36)
78
>>> (define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
()
>>> (a-plus-abs-b 3 -2)
5
>>> (define (print-twice x) (print x) (print x))
()
>>> (print-twice "Hello")
"Hello"
"Hello"
()

阶段性检查

本阶段仍使用“测试框架” rjsj_test。以下述方式调用 RJSJ_TEST 宏：

int main() {
    RJSJ_TEST(TestCtx, Lv2, Lv3, Lv4, Lv5, Lv6);
    // [...]
}

出于 EvalEnv 的重构，你可能需要修改 TestCtx 里的 env 的声明和初始化方式。重新编译并运行后，观察测试结果。

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

Last Updated:
Contributors: Guyutongxue