末尾呼び出し最適化ごっこ

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

「RubyでつくるRuby」という素晴らしい本があって、toRubyの勉強会で毎月読んでます。そこに出てくるminrubyの話だよ。

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門（紙書籍）www.lambdanote.com

minrubyを改造して末尾呼び出しの最適化ができないか試してみた。

def bar(n)
  foo(n - 1)
end

def foo(n)
  if n > 0
    if n % 1000 == 0
      p n
    end
    bar(n)
  else
    0
  end
end

foo(10000)

カウントダウンを二つの関数をまたぐ再帰呼び出しで実装した例。サブルーチンの末尾（構文木でいう末尾？）がfunc_callだったらそこにマークをつけるようにしたので、ifの分岐先の末尾とかも対象になります。っていうかminrubyにはreturnがないので分岐の先でのfunc_callに対応する必要がありました。

rubyだとこんな感じでスタックが足りません。

$ ruby  loop.rb 
10000
9000
8000
7000
6000
5000
Traceback (most recent call last):
	11913: from loop.rb:27:in `<main>'
	11912: from loop.rb:10:in `foo'
	11911: from loop.rb:2:in `bar'
	11910: from loop.rb:10:in `foo'
	11909: from loop.rb:2:in `bar'
	11908: from loop.rb:10:in `foo'
	11907: from loop.rb:2:in `bar'
	11906: from loop.rb:10:in `foo'
	 ... 11901 levels...
	    4: from loop.rb:10:in `foo'
	    3: from loop.rb:2:in `bar'
	    2: from loop.rb:10:in `foo'
	    1: from loop.rb:2:in `bar'
loop.rb:10:in `foo': stack level too deep (SystemStackError)

改造したminrubyで実行するとこう。

$ ruby interp.rb loop.rb 
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000

なんとか入れ子でも動くようにした。

$ ruby interp.rb interp.rb loop.rb 
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000

追記

末尾にマークつける処理も末尾呼び出し最適化されててかっこよくない？

def mark_tail(tree, genv)
  case tree && tree[0]
  when "func_call"
    mhd = genv[tree[1]]
    if mhd == nil || mhd[0] == "user_defined"
      tree[0] = "tail"
    end
  when "stmts"
    mark_tail(tree[-1], genv) # ここと
  when "if"
    mark_tail(tree[2], genv) # ここは違う
    mark_tail(tree[3], genv) # ここ
  end
end

コードはgistにあるよ

改造したminrubyはこんなの。もっとうまく書けるんだろうなあ。

gist.github.com