論壇

其实这大概是朝花夕拾罢. 曾经年少的朝气, 似乎已不可失而复得. 上一次我写编译器的时候, 学习编程不过一年多. 那时我才读了大半的SICP, 两本小人书The Little Schemer和The Seasoned Schemer, 以及一部分的Essentials of Programming Languages. 或许杂七杂八的书也读了些, 不过那大抵还是年少轻狂之时, 一路突飞猛进. 其实上一回的尝试我编译器只写了一半, 到以前的IUB P423/523课程的中间部分, 后面是全写完了, 前面到寄存器分配的时候是怎么也写不下去 (而且再之前的基本块划分我写得也很不满意), 于是就此搁笔. 当然, 那时还有一个谜到现在仍然是一个谜, 即letrec和letrec*的语义. 想来, 那也是很多内容了, 比如闭包变换和优化, 赋值变换, 常量传播 (虽然现在想想可能不保持语义, 但是大部分编译器的做法似乎也和我一样) 之类的.

今天翻出来以前写的编译器重写, 其实几乎没有多少改动, 因为那时我的程序实在是过于干净, 没有必要再改. 我只是修改了一些数据结构的表示. 之前的编译器有一个非常奇怪的地方, 可能除了Lisp程序员之外都干不出这样的事情, 那就是编译器的中间表示仍然几乎是合法的Lisp程序, 可以直接扔进REPL里跑. 我把alpha变换之后的变量表示修改了, 比如以前是temp.13, 那么现在就是(uvar temp 13). 或许有人可能会担心效率问题, 但是这一个变量的表示是由所有变量的出现所共享的, 所以没有问题. (正所谓, S-exp可不是树.) 而且, 我发现从理论上来说那些和集合操作有关的辅助过程也并不需要修改, 因为的确这些变量的出现都共享一处表示.

另外一个变动就是原始过程和非原始过程的应用目前有了新的句法, 这看起来也是更加复杂了, 总之离能够直接扔进REPL里跑越来越远. 不过, 或许可以写一个简单的变换来实现这点.

我还意识到上一次我写编译器的时候犯了一个很大的错误, 根本原因还是在于没有完全遵循句法. (我可以说我是被王垠带偏了吗, 而且我发现他的编译器里面也有非常离谱的一些错误和写法. 突然想到, 我和王垠还吵过一天架, 很有可能改变了历史进程, 笑.) 一个原始过程的应用, 原始过程的名字本身应该视为一个特殊的元素看待, 之前的编译器里我都把它当作变量处理了. 不仅写起来会非常别扭, 而且我还怀疑我引入了一些subtle的bug.

大致上想说的就这么一点, 那么现在看看第一个编译器pass (或者说我喜欢叫做小编译器) parse-scheme的源语言和目标语言的句法.

 值得注意的是, 这里的fixnum是一个61位的有符号整数, 因为拿了3位去做运行时标记 (Scheme是一个动态类型语言).

可以看到, 句法的复杂度下降非常之多. 这些小编译器做的事情, 不过就是分析和变换, 将语言变得越来越简单, 同时保持语义.

看个例子吧, 虽然完全没有体现任何东西, 但是我现在无心编制测试用例.

这数年光景只若南柯一梦. 用了五年时间, 我以几乎垫底的成绩从数学系毕业了 (虽然我承认我几乎没有去上过任何课, 除了期末考试突击考场之外, 我都躺在床上). 想要申请学校, 却不知申请什么好.