TAILCALL optimization

ruby

そうそう、なんでdecoratorなんか、、、ってのは実はid:wasabizさんのみて感動したので、それrubyでもって感じで。

戦略

さっきつくったdecoratorでそのまんまやるぞ、と。

書いてみた

def tail_recursive(f, *args)
    saved_args = []
    cont = Object.new
    first_call = true
    proc { |*args|
        if first_call
            first_call = false
            begin
                while true
                    res = f.call(*args)
                    if res.equal?(cont)
                        args = saved_args
                    else
                        return res
                    end
                end
            ensure
                first_call = true
            end
        else
            saved_args = args
            return cont
        end
    }
end

まんまや。

テスト

require 'decorator'
require 'tail_recursive'

def foo(n, acc)
    if n == 0
        acc
    else
        foo(n-1, acc+n)
    end
end

decorator :tail_recursive
def bar(n, acc)
    if n == 0
        acc
    else
        bar(n-1, acc+n)
    end
end

puts "-- foo"
begin
    puts foo(100000, 0)
rescue SystemStackError => err
    puts err
end

puts "-- bar"
begin
    puts bar(100000, 0)
rescue SystemStackError => err
    puts err
end

tkuro@sawshark> ruby -I. sum.rb                                                                             ~/Exp/tailrecursive
-- foo
stack level too deep
-- bar
5000050000

おーーーおっけっぽい
。。。そりゃそうか

ところで、、、

処理系自身では対応してないのかと思って少し調べてみると、どうやらCRubyでもマクロ設定してコンパイルしなおせばよいようです。


vm_opts.h

/* Compile options.
 * You can change these options at runtime by VM::CompileOption.
 * Following definitions are default values.
 */

#define OPT_TRACE_INSTRUCTION        1
#define OPT_TAILCALL_OPTIMIZATION    1  // << ここ
#define OPT_PEEPHOLE_OPTIMIZATION    1
#define OPT_SPECIALISED_INSTRUCTION  1
#define OPT_INLINE_CONST_CACHE       1

で、やってみたのですが(ruby-1.9.2-p136 [ x86_64 ])、やっぱり

[1] tkuro@sawshark> ./miniruby sum.rb
sum.rb:2: stack level too deep (SystemStackError)

あり？？？　

ここだけ切り出して

1: def foo(n, acc)
2:     if n == 0
3:         acc
4:     else
5:         foo(n-1, acc+n)
6:     end
7: end
8:
9: foo(100000, 0)

リバースしてみると、

tkuro@sawshark> ./miniruby -e 'puts RubyVM::InstructionSequence.compile(open("sum.rb").read).disasm'
== disasm: @>==========
0000 trace 1 ( 1)
0002 putspecialobject 1
0004 putspecialobject 2
0006 putobject :foo
0008 putiseq foo
0010 send :"core#define_method", 3, nil, 0,
0016 pop
0017 trace 1 ( 9)
0019 putnil
0020 putobject 100000
0022 putobject 0
0024 send :foo, 2, nil, 40,
0030 leave
foo()の中身
== disasm: >=================
local table (size: 3, argc: 2 [opts: 0, rest: -1, post: 0, block: -1] s1)
[ 3] n [ 2] acc
0000 trace 8 ( 1)
0002 trace 1 ( 2)
0004 getlocal n
0006 putobject 0
:
0025 opt_minus
0027 getlocal acc
0029 getlocal n
0031 opt_plus
0033 send :foo, 2, nil, 8,
0039 trace 16 ( 7)
0041 leave ( 5)

のようにflagがメインからcallと再帰呼び出しでのcallで違ってて、つまりは一回目だけは末尾呼び出ししていて、あとはノーマル呼び出ししている、、という感じみたいです*1。
基本的には send -> leave の並びになっていたら tailflagを立ててるっぽい・・・・はずなのですが、compile.c:new_insn_send()に罠はって見張ってみると、

:
:
insn_send: line_no: 26 flag = 01
insn_send: /home/tkuro/sum.rb line_no: 2 flag = 01
insn_send: /home/tkuro/sum.rb line_no: 5 flag = 01
insn_send: /home/tkuro/sum.rb line_no: 5 flag = 01
insn_send: /home/tkuro/sum.rb line_no: 5 flag = 11 #TAILFLAG!
insn_send: /home/tkuro/sum.rb line_no: 1 flag = 01
insn_send: /home/tkuro/sum.rb line_no: 9 flag = 11 #TAILFLAG!

深追いしてないけど、この当たりなのかな。5行目（再帰呼び）が複数あるようです。TAILFLAG立ってるのと立ってないのが・・・
実はなにか指定が必要なのかな？

結論

あとParrotとかCLRが対応してるって意味でCardinalとかIronRubyとかは対応できるんじゃないかな？　と思うんだけど、僕の手に余りまくりんぐ、と。誰か教えて〜

*1:vm_insnhelper.cに罠張ってみた挙動とも一致します