RubyでつくるRuby ゼロから学びなおすプログラミング言語入門
- 作者: 遠藤侑介
- 出版社/メーカー: ラムダノート
- 発売日: 2017/03/31
- メディア: テキスト
- この商品を含むブログを見る
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
