庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

Clojure的recur尾递归优化探秘

Posted on 2010-07-11 04:20 dennis 阅读(3707) 评论(0)  编辑  收藏 所属分类: javaClojure

    Clojure由于是基于JVM,同样无法支持完全的尾递归优化(TCO),这主要是Java的安全模型决定的,可以看看这个久远的bug描述。但是Clojure和Scala一样支持同一个函数的直接调用的尾递归优化,也就是同一个函数在函数体的最后调用自身,会优化成循环语句。让我们看看这是怎么实现的。
    Clojure的recur的特殊形式(special form)就是用于支持这个优化,让我们看一个例子,经典的求斐波那契数:
(defn recur-fibo [n]
     (letfn [(fib 
                [current next n]
                (
if (zero? n)
                    current
                    ;recur将递归调用fib函数
                    (recur next (
+ current next) (dec n))))]
    (fib 
0 1 n)))

    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方法(忽略了一些旁枝末节)
 1 // access flags 1
 2   public invoke(Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object; throws java/lang/Exception 
 3    L0
 4     LINENUMBER 2 L0
 5    L1
 6     LINENUMBER 4 L1
 7    L2
 8     LINENUMBER 4 L2
 9     ALOAD 3
10     INVOKESTATIC clojure/lang/Numbers.isZero (Ljava/lang/Object;)Z

11     IFEQ L3
12     ALOAD 1
13     GOTO L4

14    L5
15     POP
16    L3
17     ALOAD 2
18    L6
19     LINENUMBER 6 L6
20     ALOAD 1
21     ALOAD 2
22     INVOKESTATIC clojure/lang/Numbers.add (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number;

23    L7
24     LINENUMBER 6 L7
25     ALOAD 3
26     INVOKESTATIC clojure/lang/Numbers.dec (Ljava/lang/Object;)Ljava/lang/Number;

27     ASTORE 3
28     ASTORE 2
29     ASTORE 1
30     GOTO L0

31    L4
32    L8
33     LOCALVARIABLE this Ljava/lang/Object; L0 L8 0
34     LOCALVARIABLE current Ljava/lang/Object; L0 L8 1
35     LOCALVARIABLE next Ljava/lang/Object; L0 L8 2
36     LOCALVARIABLE n Ljava/lang/Object; L0 L8 3
37     ARETURN
38     MAXSTACK = 0
39     MAXLOCALS = 0

    首先看方法签名,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的实现也可以看出来:

   //覆盖变量
  for (int i = loopLocals.count() - 1; i >= 0; i--) {
                LocalBinding lb 
= (LocalBinding) loopLocals.nth(i);
                Class primc 
= lb.getPrimitiveType();
                
if (primc != null) {
                    gen.visitVarInsn(Type.getType(primc).getOpcode(Opcodes.ISTORE), lb.idx);
                }
                
else {
                    gen.visitVarInsn(OBJECT_TYPE.getOpcode(Opcodes.ISTORE), lb.idx);
                }
            }
   
//执行跳转
   gen.goTo(loopLabel);
 
      recur分析完了,最后有兴趣可以看下recur-fibo的invoke字节码
 1  L0
 2     LINENUMBER 1 L0
 3     ACONST_NULL
 4     ASTORE 2
 5     NEW user$recur_fibo__4346$fib__4348
 6     DUP
 7     INVOKESPECIAL user$recur_fibo__4346$fib__4348.<init> ()V

 8     ASTORE 2
 9     ALOAD 2
10     CHECKCAST user$recur_fibo__4346$fib__4348
11     POP
12    L1
13    L2
14     LINENUMBER 7 L2
15     ALOAD 2
16     CHECKCAST clojure/lang/IFn
17     GETSTATIC user$recur_fibo__4346.const__2 : Ljava/lang/Object;
18     GETSTATIC user$recur_fibo__4346.const__3 : Ljava/lang/Object;
19     ALOAD 1
20     ACONST_NULL
21     ASTORE 1
22     ACONST_NULL
23     ASTORE 2
24     INVOKEINTERFACE clojure/lang/IFn.invoke (Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
25    L3
26     LOCALVARIABLE fib Ljava/lang/Object; L1 L3 2
27    L4
28     LOCALVARIABLE this Ljava/lang/Object; L0 L4 0
29     LOCALVARIABLE n Ljava/lang/Object; L0 L4 1
30     ARETURN

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

     简单来说,recur-fibo生成的对象里只是new了一个fib生成的对象,然后调用它的invoke方法,这也揭示了Clojure的内部函数的实现机制。
      


只有注册用户登录后才能发表评论。


网站导航: