ZINC以及partial apply

最早是带着疑惑：ML语言里面的partial apply是如何实现的？比如，scheme语言里面 (define (add x y) (+ x y)) 不允许 (add 3) ，在ML里面可以。

然后发现了这个slide，讲OCaml的实现是如何一步步演进成现在这样子的：

http://pauillac.inria.fr/~xleroy/talks/zam-kazam05.pdf

ML的抽象机模型用的不是scheme中常见的SECD，是一种叫ZINC的东西。这个slide读了好久，主要是越看不懂的越多，现在总算是懂了六七成吧，至少整个过程是从发散到收敛了。有时候就是这样，读一篇文章发现有些点不理解，再去搜相关的东西，又遇到了更多不理解的点，整个发散下去就变成读一个领域了，PL和编译器相关的都是巨坑！

de Bruijn index

先说de Bruijn index表示，跟scheme那边的不同是从de Bruijn index表示开始的。

λx. λy. x	=>	λ λ 1
λx. λy. λz. x z (y z)	=>	λ λ λ 2 0 (1 0)
λz. (λy. y (λx. x)) (λx. z x)	=>	λ (λ 1 (λ 1)) (λ 2 1)

de Bruijn index是lambda演算另一种表示形式，去掉了参数名的概念，直接用出现的位置来表示变量。比如说出现在本层的lambda绑定，就是0。λx. x 等价于 λ 0 ，上面的第一个例子 λx. λy. x 中，x出现在上一层的位置，所以是 λ λ 1 。类似的，如果出现在再上一层的lambda绑定就是2。free variable这里就不讲了，有兴趣自己去查查。

这种表示省掉了alpha变换，并且由于没有了name，环境的表示也就跟scheme不同了(其实也没什么本质的区别，可以看作一种是hash表由key-value查变量，另一种是由数组下标查变量)。

CAM(Categorical Abstract Machine)

CAM的编译很简单，规则就这几个：

C[n] = ACCESS(n)
C[λa] = CLOSURE(C[a]; RETURN)
C[a b] = C[a]; C[b]; APPLY

解释一下就是，变量直接编译成环境访问，由于是Bruijn index表示的，也就是直接变成在环境中的偏移。lambda的编译就生成闭包指令，apply的编译都很直观。

相应的指令：

ACCESS(n)	将环境的第n个对象进栈
CLOSURE(c)	由代码c和当前环境创建闭包，将闭包进栈
APPLY	调这条指令时，当前栈上的内容是参数和闭包，用闭包中的代码和环境替换掉虚拟机的代码和环境
RETURN	调这条指令时，栈上的是一个闭包(APPLY指令保存下来的)，用它替换虚拟机的代码和环境

注意在APPLY的时候，当前上下文(代码&环境)替换为闭包中上下文的同时，是要将当前代码&环境保存并进栈，作为返回地址。除了使用的是Bruinj index表示，CAM跟SECD还是比较像的。

简单lambda演算都是用一个参数的。CAM的问题是做Currying会产生太多的临时闭包(SECD同理)。每多一个参数都产生闭包 fun x y z ... 要变成 λx. λy. λz 会生成三次闭包。

ZAM(ZINC Abstract Machine)

其实避免生成闭包并不困难，稍微改动一下。之前的CAM模型，以及没有做partial apply支持的SECD等，都是由调用者准备好所有的参数，然后调用。如果参数不够或者参数多了，就报错。修改后，不要由调用函数去检查参数。

由被调函数去判断是否有足够的参数，如果有就执行函数体，否则生成partial apply的闭包。

整个在之前的基础上添加了GRAB指令，就是在刚进入函数后执行，检查参数以决定执行函数体还是生成partial apply的闭包。这些变化就是从CAM进化到ZINC。

在此之前Krivine's Machine。Krivine' Machine的编译规则如下：

C[n] = ACCESS(n)
C[λa] = GRAB; C[a]
C[a b] = PUSH(C[b]); C[a]

相应的指令

ACCESS	用环境的第n个对象(闭包)，替换掉当前代码和环境
PUSH	将PUSH指令里的代码跟当前环境形成闭包，闭包进栈
GRAB	将栈上的闭包出栈，进到环境

理解Krivine's Machine重要的两点：

1. 在C[λa]的时候并不构建闭包，这跟CAM/SECD一类其它抽象机器都不同(效果是做currying没有任何额外负担)。
2. delay求值的策略，在C[a b]的时候并不将b求值，而是变成闭包了。

为什么讲到Krivine's Machine呢？因为ZINC其实是一种Krivine's Machine变种。区别是标准的Krivine's Machine是call by name的，而ZINC是严格求值的call by value的变种。

ZINC的编译和指令有点长，这里就不写了，见之前slide里面的第14、15页。

接下来是再从ZINC到Caml Light，就只是一些优化了，包括合并调用栈和返回值栈，优化环境表示，编译期决定更多的东西。

说一下对于环境的表示的优化，用栈来表示环境，而不是堆，只有当真正需要生成闭包时，才会用到堆。

环境是一个支持下列操作的东西：

add(v1, . . . , vn, e)	将v1...vn加入到环境中
accessn(e)	返回环境中的第n个元素
close(c, e)	用环境生成一个闭包

至于环境用栈表示或用堆表示，并不需要关心。于是优化可以做成平时在栈上，只有当需要生成闭包时，把栈上的数据拷到堆上，生成闭包。