Lv.7 完善
恭喜你,你已经完成了所有 Mini-Lisp 解释器的关键节点。接下来的内容将是十分枯燥的——你需要补全所有 Mini-Lisp 规范定义的内置过程和特殊形式。
任务 7.1 修改内置过程类型
在实现 eval 和 apply 内置过程(注意与解释器内部实现中的 eval 和 apply 函数区分)时,你需要用到求值环境。而之前我们的内置过程函数指针类型是不提供这个实参的,所以你需要修改相关的定义。
- 你可以直接无脑给所有的过程添加
EvalEnv& env形参,正如同我们在特殊形式中所写的那样; - 你也可以不用函数指针,改用
std::function,然后在创建EvalEnv的时候直接以 Lambda 表达式加捕获的形式塞进去。
任务 7.2 补全 47 个内置过程
请参考标准规范,将所有的内置过程写好。
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
quasiquote 和 unquote
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) 与 你在 Lv.7+ 阶段实现的拓展功能的说明文档(如果有拓展导致不符合文档规约,请一并指出),该提交将作为你的大作业分数的一部分。
- 请按照中作业文档中的指示,将你的 GitHub 用户名、GitHub 仓库名 和生成的 用户令牌 提交到教学网 大作业 / 代码 中。