Archive for 2015年3月

不用 Lisp 学 Lisp

2015/03/22

发布上一篇 blog 一周后我离开北京来到了美国,当时没想到这一篇会隔了这么久才动笔。写 blog 一直是在 wordpress.com 上 draft 和发布,然后再复制到 techsingular.net 上。所以之前还在想搬来后写作条件也许会大大改善(因为 wordpress.com 众所周知的原因)。没想到一拖就是一年多。期间还两次忘记给 techsingular.net 的域名和主机续费。多亏杜超和 @mozetianxing 提醒。感谢大家一直关注。

大概两个月前开始有再写 blog 的想法。但中断这么久后一时不知道说点儿什么。或者说想写的还不少,不知从什么开始。这次终于动笔源自在 Twitter 上和张克炎 (@keyanzhang) 关于《 Lisp in Small Pieces 》的讨论。

另外说起「写作条件大大改善」,wordpress.com 的 editor 确实改进了不少。techsingular.net 的主机商也给免费升级了空间。Wordpress 升级到了 4.1.1。一年多真是很长的时间。

学编程语言理论的一个有意思的途径是读关于 Lisp 的书。但我并不想花精力摆弄任何一个 Lisp 的实现,更不要说先得从许多选择中挑一个。所以几年前就尝试在完全不安装 Lisp 环境的前提下读《 Structure and Interpretation of Programming Language 》。更确切地说,我的计划是在整个过程中用 Lua 逐步构建环境。现在看来这个计划很成功。SICP 中的 Scheme 代码都能简单对应为 Lua 代码。最后的小成果是用 Lua 写的 Scheme evaluator

当时的版本非常简单,不仅没有 macro,也没有著名的 first-class continuation (call/cc) 。我当然希望加上更复杂的 feature,离开北京前就开始看《 Lisp in Small Pieces 》(LiSP) 和《 The Little Scheme 》。不过这两个计划很快被搁置了。部分原因是大搬迁的影响。还有部分原因是兴趣转到了理解 Lua VM 本身的实现。因为 Lua 和 Scheme 如此类似,它的 VM 实现又非常简洁,特别是和 C 的交互部分做得比任何语言都好,所以对 Lisp 的兴趣很大程度上转化成对 Lua VM 的研究。几个月前恢复阅读 LiSP 后才意识到还有很大一部分原因是这本书的行文常常误导读者,没有不断改错的毅力实在读不下去。

在网上搜索对《 Lisp in Small Pieces 》的评价得到的几乎都是溢美之词。一本面向小众读者的专业书在 Amazon 上得到 12 个五星评价,不能不说这本书相当出色,覆盖了极广的知识、例子代码很详尽。但是它的问题也很严重,而网上一面倒的正面评价让我花了很长时间才确信阅读时遇到的很多困难并非自己的原因。简单的说,这本书犯了很多论文和教科书经常犯的错误 —— 证明推导时经常来个「显而易见」。它倒是很少在字面上出现「显而易见」,而是犯更隐蔽的等价错误:举例和结论之间经常有很多缺环  (gap)。

比如第 3.6.2 节 Tail Recursion 后半部分讲如何在 begin sequence 结束时省掉 continuation。这本来没什么问题。问题在于此节前半部分大幅以 fact (阶乘)函数举例。这个例子在多个层次上都有问题。首先是前文里有两个 fact 函数的例子:普通递归风格和 CPS 风格的。这无疑增加了读者误解的几率。

第二层问题是,普通风格的 fact 函数根本不是 tail-recursion。CPS 风格的虽然是 tail-recursion(而且也确实是文中用到的例子),但与其相关的 continuation 有两种:一是 CPS 风格代码每个函数的参数 k,二是 CPS 风格的代码和任何代码一样也有自己的 continuation。一般提到 CPS 时通常讨论第一种 continuation。第二种 continuation 几乎不会提及 —— 因为 CPS 风格代码都是 tail-call,可以说本身根本没有 continuation。《 Lisp in Small Pieces 》却反其道行之。用 CPS 风格代码举例,讨论的却不是参数 k,而是 (fact n k) 函数本身代码的 continuation。读到这里的时候,我先是花了好久都搞不懂要说什么。搞懂了之后又不明白作者为什么非要举这个例子。尽管这节后半部分的结论没问题,evaluator 代码的 tail-call 优化很简洁,但用来开篇的例子糟糕到不行。

接下来是一个同样糟糕的例子,引起了和 @keyanzhang 的讨论。在第 3.7 节 Partial Continuation 里有一个例子。

第一眼看上去,我很怀疑这段代码是否能按照文中所示返回 3 和 4。但我没有标准的 Lisp 环境,只有自己实现的还没有 REPL 的 evaluator。运行上面的代码的结果是死循环。所以我把问题发到了 Twitter 上。@keyanzhang 回复说他的运行结果如下,看起来和 LiSP 类似:

这就比较尴尬了…… 当初决定用 Lua 学 Lisp 时最大的顾虑是出了问题只能硬想,没有真正的 Lisp 环境用来参考。现在果然遇到了。不过话说回来,如果只用标准的 Scheme 环境,也许这个问题实验一下就过去了。现在有了真正的 Scheme 运行结果和我的 evaluator 的差异,问题可能出在两个地方:我的 evaluator 实现不对,或者又是一个《 Lisp in Small Pieces 》的行文问题。有过 fact 函数的例子,我比较怀疑是后者。第一,在第 3.1.5 节曾经有用 call/cc 模拟 goto 的例子,用那个例子来对比,这里的 (foo 3) 明显像 infinite loop。第二,和书上简单的代码片段不同,@keyanzhang 的例子是在 REPL 中。

经过痛苦的思考,终于发现正是 REPL 的原因。REPL 在每次收到 Enter 之后都用新的 bottom continuation 调用一次 evaluator,而不是调用一次 evaluator 运行所有代码。所以 REPL 中 (foo 3) 不是前面代码的 continuation,也就打破了 infinite loop。本来一直懒得给自己的 evluator 写一个 REPL,想通了这次困扰好几天的问题,立刻就写了一个。这回的结果终于和书上一致了。其实,无论是 @keyanzhang 的例子还是我最后的 REPL 结果都和原文并不一致,也不可能一致。

通过这两三年断断续续、磕磕绊绊的经历,说明熟悉编程的人完全可以只用 Lua 来学 Lisp。为什么要这么大费周章呢?下载一个 Racket、使用 Emacs 或者其它 Lisp 环境很难吗?因为我更喜欢 no-drill 的方式 —— 尽量用接近工作的环境来学习,不喜欢摆弄最终在产品中用不到的玩具。我们很少有人能在工作中用到 Lisp,大多数人学 Lisp 是希望借鉴思想。另一方面,Lua 已经在借鉴 Scheme 方面实践的很好,由于其 embedable/extendable 的特点又很容易在各种真正的生产环境中采用。所以希望研究 Lisp 所体现的编程思想,也可以尝试不安装任何 Lisp 环境。