Lv.7 完善

恭喜你,你已经完成了所有 Mini-Lisp 解释器的关键节点。接下来的内容将是十分枯燥的——你需要补全所有 Mini-Lisp 规范定义的内置过程和特殊形式。

任务 7.1 修改内置过程类型

在实现 evalapply 内置过程时,你需要用到求值环境。而之前我们的内置过程函数指针类型是不提供这个实参的,所以你需要修改相关的定义。

  • 你可以直接无脑给所有的过程添加 EvalEnv& env 形参,正如同我们在特殊形式中所写的那样;
  • 你也可以不用函数指针,改用 std::function,然后在创建 EvalEnv 的时候直接以 Lambda 表达式加捕获的形式塞进去。

任务 7.2 补全 47 个内置过程

请参考标准规范open in new window,将所有的内置过程写好。

append map filter reduce 等操作列表的内置过程可能会略微难写,但你可以统统转换到 std::vector,然后用 STL 算法算出来之后再转换回去。

eq?equal? 这两个都是比较相等性的算法,但是 eq? 判断两个对象是否为同一对象,而 equal? 则是值语义的相等。对于符号类型、数类型、布尔类型、空表类型来说,equal?eq? 都是返回值是否相等;而对子类型、字符串类型和过程类型的 eq? 则是表明存储它们的地址(即 std::shared_ptr 本身)是否是相同的。

>>> (define x (cons 1 2))
()
>>> (define y x)
()
>>> (define z (cons 1 2))
()
>>> (eq? x y)
#t
>>> (eq? x z)
#f

数学库的 modulo 定义有些反人类,请仔细甄别含义,小心编写。

任务 7.3 补全特殊形式

Mini-Lisp 规定的特殊形式数量不多,我们还差这些:

cond 多条件判断

形式是

(cond 子句1
      子句2...)

每个 子句 都具有这样的形式:

(条件 表达式...)

求值 cond 特殊形式时,从前到后遍历 子句:如果子句的 条件 求值到 #f,就跳过;否则对 表达式... 逐一求值。返回最后一个。没有 表达式 的话,返回 条件 的求值结果。

如果 条件else 符号的话,那么它必须出现在最后一个子句中。而且这代表条件必然成立,即对后面的 表达式 求值并作为整个特殊形式的结果。

>>> (define n -5)
()
>>> (cond ((< n 0) -1) ((> n 0) 1) (else 0))
-1

begin 顺序执行

传入若干个表达式,然后按顺序对它们求值。和 Lambda 函数体一样一样的,没有技术难度。

let 临时变量

let 具有如下形式:

(let ((形参名1 值1)
      (形参名2 值2)...)
     表达式...)

完全等价于:

((lambda (形参名1 形参名2...)
         表达式...)
 值1 值2...)

你可以将它直接转换为 Lambda 特殊形式;也可以生成一个 LambdaValue 然后再调用;也可以直接给当前的环境添加绑定,执行完再撤掉。总之,只要看上去效果是对的就行。

>>> (let ((x 5) (y 10)) (print x) (print y) (+ x y))
5
10
15

quasiquoteunquote

quasiquote,也就是 `,类似于 quote 不做求值,但是遇到 unquote 或者 , 之后就会对 unquote 里面的东西求值,然后用求值结果替换掉 unquote 特殊形式。

我们不要求实现 quasiquote 被递归时的处理,所以可以实现得比较简单。

>>> `(11 45 ,(* 2 7))
(11 45 14)

任务 7.4 实现文件模式

修改 main.cpp,或者添加更多的源文件,使得你的程序可以读取一份 Mini-Lisp 源码文件并执行它。源码文件路径通过命令行参数传入。程序在解释执行时,不会打印求值结果(这里与 REPL 模式不同!)。只有在 print display displayln newline 时,才会向标准输出写入文本。

如何让 REPL 模式和文件模式尽可能多地复用代码,是一个具有考验性的问题。期待你的解答。

任务 7.5 来试试你的解释器!

编写一段 Mini-Lisp 代码,它将下述列表中的数从小到大排序后输出:

(12 71 2 15 29 82 87 8 18 66 81 25 63 97 40 3 93 58 53 31 47)

将该 Mini-Lisp 代码保存到 lv7-answer.scm 中。随后,用你的解释器解释执行它,看看结果是否正确!

提示:快速排序算法特别适合函数式编程语言实现。

阶段性检查

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

int main() {
    RJSJ_TEST(TestCtx, Lv2, Lv3, Lv4, Lv5, Lv5Extra, Lv6, Lv7, Lv7Lib, Sicp);
}

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

恭喜你完成了我们的大作业要求。在教学网 大作业 / Lv.7 检查 处,提交一个压缩包(学号-姓名.zip),包括该测试结果的截图(lv7-answer.jpg)以及 Mini-lisp 代码(lv7-answer.scm),该提交将作为你的大作业分数的一部分。

Last Updated:
Contributors: 1-rambo