R2 解释器总结 | 子飞的网络日志

看了王垠的博文怎样写一个解释器，除了验证一遍其中的 Racket 代码是对的，我还想用 Rust 实现一遍，于是用了两天时间鼓捣出了 R2 解释器的 Rust 实现。

在这个过程中我逐渐理解到 Lisp 鼓吹者说的种种好处是什么意思了……

Lisp 中列表既是数据形式又是语法形式，所以王垠跳过了写 parser 的步骤，直接解析列表，而我就得现学怎么用 nom，把文本代码转化成 AST（不过 nom 是真的好用），这是我的代码行数相对于王垠的 Racket 版本增加了一个数量级的主要原因。

Racket 是动态类型的，但 Rust 是静态类型的，所以必须声明和安排好各种类型，同时 Rust 没有 GC，还要考虑内存管理——也就是传值和传引用的区别，增加了心智负担。

还有一点不是本质的区别，Racket 自带 IDE 和 REPL，但 Rust 就没有了，想要好用的 REPL 还得导入 rustyline 这样的外部库。这里吐槽一下，rustyline 很难配置，不知道为啥在 crates.io 上下载量那么高。但 rustyline 在 github 上只有 400 多的 star 就很真实了。

当然，凡事不能一概而论，Rust 的静态类型使得很多错误在编译期就被发现，而强类型也使程序员对程序有更大的把握，比如我就清楚的知道最终的计算结果除了数字还有可能是一个闭包，而王垠没怎么提这点；Rust 的内存管理也不是完全手动，主要是 RAII，borrow check 保证了不会像 C++ 那样不知道在哪埋炸弹，心智负担实际上比 C++ 轻多了。

这个 R2 语言并不是纯粹的无类型 lambda 演算，它带有 let 绑定和内置整数类型。王垠的版本里只有对整数的四则运算，并没有让整数结果影响控制流的办法，类似 (if (eq n 0) 1 (f (- n 1))) 这样的表达式是写不出来的，或者根本上说，是没有把内置整数与 Church number 相互转换的办法。所以我增加了一个内置函数 is_zero ，接受一个参数，当传入 0 时求值为 true，当传入其它整数或者非整数时返回 false。这里的 true 和 false 是 Church 定义，分别是 (λx.(λy.x)) 和 (λx.(λy.y))。这样 (if (eq n 0) then-expr else-expr) 就可以写成 (((is_zero n) then-expr) else-expr) ，虽然麻烦了些，但至少能用。

在写测试样例时我试图用 Y Combinator 写出一个递归计算的阶乘函数，结果爆栈了。有问题的代码是这样的：

(let ([yc (lambda (y) (let ([h (lambda (x) (y (lambda (n) ((x x) n))))]) (h h)))])
    (let ([f (lambda (fact) (lambda (n) 
            (((is_zero n) 1) (* n (fact (- n 1))))))])
        ((yc f) 7)))

由于不支持多参，括号是真的多……

其中 yc 就是 Y Combinator，简化写出来就是 (λy.(h h) where h =(λx.(y (λn.((x x) n)))))，为了避免无限求值，把定义中的 (x x) 改写为 (λn.((x x) n))。

经过分析，问题还是在求值上：这里只有表达式而不是 if 语句，而我们的求值策略是为了求出表达式的值必须把所有参数求值，结果 (fact (- n 1)) 总是会被执行，无限递归导致爆栈。

解决办法就是改成返回闭包，然后再执行一次返回的闭包，就能确保只有该分支被实际执行。代码变成这样：

(let ([yc (lambda (y) (let ([h (lambda (x) (y (lambda (n) ((x x) n))))]) (h h)))])
    (let ([f (lambda (fact) (lambda (n) 
    	    (((is_zero n) (lambda (u) 1)) (lambda (u) (* n ((fact (- n 1)) 0))))))])
        (((yc f) 7) 0)))

注意这里用 0 充当了 Unit 值，所有 fact 返回的都是闭包，传入 0 执行后才得到整数值。