软件设计实践大作业

Lv.4 内置过程

Mini-Lisp 中共有两种过程。一种是我们解释器自带的过程，比如 + - * / 这些，称作内置过程；一种是用户在代码里定义的，也就是 (define (f x) ...) 定义的 f ，以及 lambda 特殊形式等等。我们这一部分给解释器添加一些简单的内置过程。

任务 4.1 过程类型的值

在 value.h 中定义类 BuiltinProcValue，实现抽象类 Value，以及接口 toString。

class BuiltinProcValue : public Value {
    // [...]

public:
    // 直接返回 #<procedure> 就可以，我们不做更多要求。
    std::string toString() const override;
}

这个类代表内置过程类型的值。那么，它需要什么样的成员数据呢？稍微停顿思考一下——

答案是：函数指针。这个值持有指向某个 C++ 函数的指针后，调用它的时候就可以根据指针指向，来调用其对应的函数。在 C++ 层面，我们目前将内置函数的类型定义为这个样子：

using BuiltinFuncType = ValuePtr(const std::vector<ValuePtr>&);

然后在 BuiltinProcValue 中就可以定义数据成员 BuiltinFuncType* func。不要忘记初始化。

接下来我们看一个例子：如何定义 + 这个内置过程：

ValuePtr add(const std::vector<ValuePtr>& params) {
    auto result = 0.0;
    for (const auto& i : params) {
        if (!i->isNumber()) {
            throw LispError("Cannot add a non-numeric value.");
        }
        result += i->asNumber();
    }
    return std::make_shared<NumericValue>(result);
}

这是 C++ 这边如何做两个值的加法。你可能要实现 isNumber 和 asNumber 这两个辅助方法，或者对刚刚的代码做一些调整。随后，可以通过这个 add 函数创建一个持有 add 的内置过程的 Lisp 值：

// 你需要定义 BuiltinProcValue 的恰当的构造函数
ValuePtr addVal = std::make_shared<BuiltinProcValue>(&add);

如果你把（+，addVal）添加到符号表的话，那么理论上就可以通过 + 去访问这个过程类型了——我们马上来做这件事！

任务 4.2 初始符号表

新建 builtins.h 和 builtins.cpp，把刚刚那个 add 函数的声明和定义分别写进去。随后，我们要修改 EvalEnv——让它的符号表能包含 + 这个过程。

#include "./builtins.h"

EvalEnv::EvalEnv() {
    符号表.添加("+", std::make_shared<BuiltinProcValue>(&add));
}

嗯，这是一件非常没有技术含量的事。随后，修改 EvalEnv::eval 或者 Value::isSelfEvaluating 之类的东西，使得对过程类型求值仍然得到自身。这样改完的运行效果是：

>>> +
#<procedure>
>>> (define add +)
()
>>> add
#<procedure>

这就完事儿了吗？理论上是这样的。但是我们要考虑后续的代码编写。按照 Mini-Lisp 规范，你至少要定义五十多个内置过程，如果一个个在 EvalEnv::EvalEnv 这个构造函数里手动添加，貌似不太美观。你可以尝试让 builtins.h 只暴露一个 std::map 或 std::unordered_map 变量来保存所有的内置过程函数指针，然后 EvalEnv 构造函数循环遍历一趟插到符号表里。

你也可以在这个时候多添加一些内置过程，看看有哪些重复的代码可以提取出来。

任务 4.3 调用内置过程

Mini-Lisp 在调用过程的时候，采用应用序。应用序就是在过程调用前准备好所有的实参。与之相反的叫做正则序，正则序的工作原理类似 C 的宏，将实参表达式逐一替换到过程体内，最后再求值。另一个著名的函数式编程语言，Haskell，就是正则序。

因为是应用序，所以在进行调用之前的必须步骤就是对这个列表的所有元素求值。请修改 EvalEnv::eval 以完成这个操作：

if (expr 是列表且不是特殊形式) {
    ValuePtr              proc = this->eval(列表[0]);
    std::vector<ValuePtr> args = 将列表的剩余元素都求值一遍然后收集起来;
    this->apply(proc, args); // 最后用 EvalEnv::apply 实现调用
}

“将列表的剩余元素都求值一遍然后收集起来”该如何做呢？我把它定义为一个成员函数 evalList。下面我直接给出 evalList 的大致实现——因为它用到了 STL 算法，而相当一部分学生可能并不熟悉——希望你能读懂它并嵌入到你的代码中。

#include <algorithm>
#include <iterator>

std::vector<ValuePtr> EvalEnv::evalList(ValuePtr expr) {
    std::vector<ValuePtr> result;
    std::ranges::transform(expr->toVector(),
                           std::back_inserter(result),
                           [this](ValuePtr v) { return this->eval(v); });
    return result;
}

而“列表的剩余元素”恰恰是 expr 的右半部分。你可以给 PairValue 增加相关的接口。最后，我们用 EvalEnv::apply 方法调用内置过程。

ValuePtr EvalEnv::apply(ValuePtr proc, std::vector<ValuePtr> args) {
    if (typeid(*proc) == typeid(BuiltinProcValue)) {
        // 调用内置过程
    } else {
        throw LispError("Unimplemented");
    }
}

那具体的代码，我想我不用说太多了吧——给 BuiltinProcValue 接入一些方法，以调用其所存放的函数指针，就可以了。

除了 + 以外，我们还要求你在这一阶段实现 print 内置过程——它向标准输出（也就是用 std::cout）传入的值的外部表示，外加一个换行。返回空表。这个过程在下一章节会被频繁用到，所以特此要求。

测试

现在我们可以玩很多东西了！

>>> (+ 1 2)
3
>>> (+)
0
>>> (+ 1 2 3 4 5)
15
>>> (define x (+ 1 2))
()
>>> x
3
>>> (+ x 4)
7
>>> (define add +)
()
>>> (add 1 2 3)
6
>>> (+ 1 (add 2))
3
>>> (print 42) ; print 内置过程——输出的是 42，返回值是 ()
42
()

我们鼓励你在目前阶段尽可能多实现一些内置过程。因为内置过程的数量实在太多了，都放在最后去做也很枯燥。虽然你现在无法完成所有内置过程的实现，不过下面这些简单的是可以现在完成的：

  • 核心库：display exit newline print
  • 类型检查库：atom? boolean? integer? list? number? null? pair? procedure? string? symbol?
  • 对子与列表操作库：car cdr cons length list（还可尝试 append，有难度）
  • 算术运算库：+ - * / abs expt quotient remainder（还可尝试 modulo，有难度）
  • 比较库：= < > <= >= even? odd? zero?

这些内置过程的详细定义请参考语言规范open in new window。

阶段性检查

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

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

重新编译并运行后，观察测试结果。

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

Last Updated:
Contributors: Guyutongxue