Clojure的recur尾递归优化探秘

    Clojure由于是基于JVM，同样无法支持完全的尾递归优化（TCO)，这主要是Java的安全模型决定的，可以看看这个 久远的bug描述。但是Clojure和Scala一样支持同一个函数的直接调用的尾递归优化，也就是同一个函数在函数体的最后调用自身，会优化成循环语句。让我们看看这是怎么实现的。
    Clojure的recur的特殊形式（special form）就是用于支持这个优化，让我们看一个例子，经典的求斐波那契数：

    recur-fibo这个函数的内部定义了一个fib函数，fib函数的实现就是斐波那契数的定义，fib函数的三个参数分别是当前的斐波那契数(current)、下一个斐波那契数(next)、计数器(n)，当计数器为0的时候返回当前的斐波那契数字，否则就将当前的斐波那契数设置为下一个，下一个斐波那契数字等于两者之和，计数递减并递归调用fib函数。注意，你这里不能直接调用(fib next ( +  current next) (dec n))，否则仍将栈溢出。这跟Scala不同，Clojure是用recur关键字而非原函数名作TOC优化。

    Clojure是利用asm 3.0作字节码生成，观察下recur-fibo生成的字节码会发现它其实生成了两个类，类似user$recur_fibo__4346$fib__4348和user$recur_fibo__4346，user是namespace,前一个是recur-fibo中的fib函数的实现，后一个则是recur-fibo自身，这两个类都继承自 clojure.lang.AFunction类，值得一提的是前一个类是后一个类的内部类，这跟函数定义相吻合。所有的用户定义的函数都将继承 clojure.lang.AFunction。
   
    在这两个类中都有一个invoke方法，用于实际的方法执行，让我们看看内部类fib的invoke方法（忽略了一些旁枝末节）

    首先看方法签名，invoke接收三个参数，都是Object类型，对应fib函数里的current、next和n。
    关键指令都已经加亮，9——11行，加载n这个参数，利用Number.isZero判断n是否为0，如果为0，将1弹入堆，否则弹入0。IFEQ比较栈顶是否为0，为0（也就是n不为0)就跳转到L3，否则继续执行(n为0，加载参数1，也就是current，然后跳转到L4，最后通过ARETURN返回值current作结果。
   
    指令20——22行，加载current和next，执行相加操作，生成下一个斐波那契数。
    指令25-——26行，加载n并递减。
    指令27——29行，将本次计算的结果存储到local变量区，覆盖了原有的值。
    指令30行，跳转到L0，重新开始执行fib函数，此时local变量区的参数值已经是上一次执行的结果。
   
    有的朋友可能要问，为什么加载current是用aload 1，而不是aload 0，处在0位置上的是什么？0位置上存储的就是著名的this指针，invoke是实例方法，第一个参数一定是this。

   从上面的分析可以看到，recur干的事情就两件：覆盖原有的local变量，以及跳转到函数开头执行循环操作，这就是所谓的软尾递归优化。这从RecurExp的实现也可以看出来：

 
      recur分析完了，最后有兴趣可以看下recur-fibo的invoke字节码

     5——7行,实例化一个内部的fib函数。
     24行，调用fib对象的invoke方法，传入3个初始参数。

     简单来说，recur-fibo生成的对象里只是new了一个fib生成的对象，然后调用它的invoke方法，这也揭示了Clojure的内部函数的实现机制。
   文章转自庄周梦蝶  ，原文发布时间 2010-07-11