解密Chez Scheme
与大多人一样，初识并没有把Lisp当回事。为什么？这特么括号怎么在前面？扎眼！不学！不学！
初看黑客与画家，哎哟这什么Lisp有点牛逼。仔细一看，强迫症都犯了，括号在前面！在前面？在前面！为什么在前面！
然后偶然看了七周七语言。有天闲来无事。下一个来看吧！
一直对Java比较排斥。（这是另一个故事了）所以虽然七周七语言是Clojure的故事，所以去下了个SBCL来玩。
为什么是CL？因为一开始是没有把Scheme当回事的。因为它名字没有Lisp啊！我要玩当然要玩最纯正的Lisp啊！你一个不姓Lisp的装什么大头鬼？于是网上搜了下，最快的CL实现是SBCL。
然后偶然间看到Scheme的历史。抱着了解了解的心态去搜了一下可用的实现... 这… 怎么这么多？
当然我一开始也是没有把Chez Scheme当回事的。因为我生活在法国，Chez Scheme这个法语名字也许让英语世界的人觉得牛哔，但与我却是相当老土的… 巴黎满大街的Chez XX，就如国内的老王面馆一样老土。
于是除了Chez Scheme都试过一圈之后，偶然想起，咦王垠貌似说过一个Lisp编译器挺牛逼的是什么来着。翻回去一看，咦？是你？这么快这么牛哔？
当时还想去买一个来玩玩，上网一搜原来已开源。于是brew install了一个。
$ chez 回车
我擦！行家一出手，就知有没有！先不管Chez Scheme有没有传说的那么快，这Repl！这手感！我擦怎么会有这么好用的Repl？
先不说吊打SBCL那个傻屌Repl，我用过的所有Scheme解释器，node，python，ruby… 都没有如此丝滑的体验！
那感觉就像用三星盖乐世S1之后，突然试了试iPhone X。那吊打，是跨越时代式的。
;;;这个Repl是由1000行c实现的，代码在c/expeditor.c
Chez Scheme的Repl有如此顺滑的体验，除了智能的文本编辑和自动缩进，更得益于它的高速增量编译器。
Repl和Petit Chez Scheme的新用户，绝壁会赞不绝口，卧槽，从没见过这么流畅，这么快的解释器…
你会发现这玩意的“解释”速度不仅比所有的Scheme解释器快，还比绝大多数Scheme编译器优化后的代码快。
但是这个东西它其实不是个解释器，它是个编译器。在你以为它在解释的短短过程中，它其实完成了编译，优化，寄存器分配（还是相对缓慢的图着色分配），生成Native Code，将Native Code送入内存并执行…
哦，它是跨过汇编直接生成二进制Native Code的…
所以Chez的编译并执行速度，是吊打绝大多数解释器的解释速度的…这里我说的不只是Scheme。它的编译并执行速度，也是超过大多数Scheme编译器优化后的代码执行速度的…
上一段话有点绕，通俗来说，就是我开优化编译比你直接解释还快，我编译了再执行，比你直接执行编译好的二进制code还快…换句话就是换着角度各种花样吊打就是了
你以为它是个超级快的解释器，结果它是个优化编译器。
你以为它是个王者，结果是个神。
但其实各位用到的Chez Scheme “解释器” 还是“负优化”之后的版本。闭源版本的增量编译器编译速度是现版本的2-2.5倍。
;;; 出处：A. Keep，Nanopass framework of commercial compiler.
这个是啥概念，一秒钟几百万行，王垠说的2秒内编译自身绝不是夸张。闭源版除了具有优良的编译速度和执行速度，还有非同一般的稳定性：不是比其他Scheme实现，而是所有语言。所以有好多大厂，偷偷拿Chez跑模拟流片等芯片设计。这些鬼东西是Chez不流行的原因之一：它们往往和Chez之前公司签订保密协议，让外界根本不知道它们用了Chez Scheme。即使是Chez开源的今天，Chez在思科的跑的项目仍然是绝密。我相信正如黑客与画家所说，这些公司正将Lisp作为自己的绝密武器。
那为什么要“负优化”呢？
在9几年的时候，印第安纳大学计算机系流行着一个想法：传统编译器只采用很少的几个pass，这是因为以往计算机的内存不够大，所以每个pass之间的数据传递必须以文件系统作为媒介。这样越少的pass能占用更少的文件io时间来取得更好的编译效率。但后来计算机内存飞速增大，现在编译器可以用内存在几个pass间互传数据了。
那么？
为什么不多搞几个pass呢？
支持的人（主要存在于印第安纳大学）认为，这样可以简化每个pass。每个pass只做一件事，就如函数式编程拆分大函数以获得低耦合一样：每次修改只用测试改动的一小部分。而不至于像传统编译器一样，一动就要测试整个大pass的所有功能，而且常常引发连锁反应bug。其实这也是传统编译器复杂度巨高的主要原因。采用只有一个功能的小pass，便于修改和增加功能，从工程学角度来说，这是一个进步。
我曾经在朋友圈发过一句话：所有的复杂软件系统，与其说是编程的问题，不如说是大型系统的工程问题。
Nanopass（那时候叫Micropass）正式解决了传统pass难测试，难改动，容易出bug，不好修bug的工程问题，这是一个巨大的进步。
然而学术界并不认可这一点。以至于后来Nanopass向ICFP的投稿被十动然拒：这个玩意可以作为商业编译器？你改成学术研究向我就给你通过。
反对派的主要论点在于，采用Nanopass架构的编译器动辄50多个pass，相较于传统编译器的5个左右pass，会浪费大约十倍以上的语法树遍历时间。换句话说就是，会太慢而根本无法商用。
公说公有理，婆说婆有理。关键是历史上也没有人真用Nanopass架构写过编译器，这个争论谁也无法说服谁。
这个时候Dan Friedman发现，Micropass（Nanopass前身）能不能商用先不说，但是这种每个pass一个功能的简化模型，倒蛮适合用来进行编译器课程的教学。学生每节课写一个简单的pass功能，一学期就能完成一个简易编译器。每个功能互不影响，引起的复杂度能控制在学生能解决的范围。
于是Micropass的编译器课程就成为了印第安纳大学的传统项目。慢慢的在这个课程上发展出Match宏（用来在pass中匹配语法）和Nanopass架构原型。
这就是王垠所说的“Chez Scheme只有少数的几个pass”，这是Chez Scheme闭源版的架构。“Kent Dybvig的编译器课程有很精巧的结构，每个pass只做很微小的一件事” 这是Micropass发展而来的编译器课程。
到了Andy Keep这一代，Micropass架构原型已经经过几代人的迭代，已经非常完善了。Andy一发狠，向Dybvig提出博士阶段研究用Nanopass架构替换原有的Chez Scheme后端。
于是开整。他们发现虽然多了几乎十倍的pass，但是编译时间并没有成正比增长。因为每个pass只做很微小的事情，虽然遍历次数多了，但是每次遍历也要快得多。
具体增加了多少并没有比较详细的数据。因为他们决定既然重写了后端，不如干脆把寄存器分配器也换成更高效的图着色式。
图着色寄存器分配的处理时间虽然要慢一点，但是生成的代码却可以执行的更快一点。两相权衡，还是执行快一点比较重要。
所以最后的比较是原有的少量pass+快速但较为低效的寄存器分配比较Nanopass+缓慢但高效的图着色寄存器分配。
比较的结果是，根据优化的不同，编译时间慢了大约2-2.5倍，但是生成的代码快了大约17-25%。
在座的各位，这17-25%看起来不多，但是这可是原版Chez Scheme秒天秒地的速度上再次提高的。
这多牛逼？就像本来100米世界纪录是8秒，突然一下子干到了6秒。本来到了世界纪录附近大家都是0.几，0点0几秒的破纪录，你一下子干了2秒多…这没法一起玩了呀！（掀桌）
根据论文的说法，虽然是换用了寄存器架构，但这17-25%的效率增加，有不少还是因为Nanopass架构贡献的。
为什么？虽然是同一批人做的，经验学识都一样。但因为我易于迭代，每次迭代bug少，bug也好改，我就可以多迭代两次。那么我这种能不能用的技术，都可以用进去试一下子。
这就是大型系统的工程问题解决了，编程啥的都不是事。
而虽然增加了2倍多的编译时间，但这增加的时间还有部分是图着色寄存器分配耗费的。
结论就是：Nanopass架构还可以！多耗费的时间可以接受，带来的工程复杂度降低和可迭代性增高引起整个工程的质量急剧提升导致速度增加不少！真的还可以！
于是，投稿投稿！ICFP被piapia打脸，接受了Nanopass架构可以开发商业编译器的论文。
需要注意的是，上面的数据是替换架构后的初版比较而来。在几年的迭代后，相信编译时间还要更为降低，速度还要更快了。
© 2019-2020 guenchi. All rights reserved.