末尾最適化
本体中の計算の一番最後にある関数呼び出しを末尾呼び出し（tail call）といい，再帰呼び出しがすべて末尾呼び出しであるような再帰関数を末尾再帰的（tail recursive）という
賢いコンパイラは末尾呼び出しを特別扱いし、スタックを消費しないコードを生成する
これは末尾最適化という
言語や処理系によって行われたり行われたなかったりする
Rubyの話
前提
※ YARV の話に限定する
Rubyのコンパイラは末尾最適化を行わない
以下のようなコードは再帰呼び出しを末尾で行っているものの、Stack overflowを引き起こす
rubydef factorial(n, acc = 1)
if n == 0
acc
else
factorial(n - 1, acc * n)
end
end
factorial(10000000) #
Traceback (most recent call last):
16: from (irb):125:in `factorial'
15: from (irb):125:in `factorial'
14: from (irb):125:in `factorial'
13: from (irb):125:in `factorial'
12: from (irb):125:in `factorial'
11: from (irb):125:in `factorial'
10: from (irb):125:in `factorial'
9: from (irb):125:in `factorial'
8: from (irb):125:in `factorial'
7: from (irb):125:in `factorial'
6: from (irb):125:in `factorial'
5: from (irb):125:in `factorial'
4: from (irb):125:in `factorial'
3: from (irb):125:in `factorial'
2: from (irb):125:in `factorial'
1: from (irb):125:in `factorial'
SystemStackError (stack level too deep)
ただし回避策がいくつかある
RubyVM::InstructionSequenceを使う
RubyVM::InstructionSequence を用いて末尾最適化が行われるようなコードを書くことができる
Rubyプロセス起動時のオプションには存在せず、プログラム中で eval しないといけない
rubyRubyVM::InstructionSequence.compile_option = {
tailcall_optimization: true,
trace_instruction: false,
}
RubyVM::InstructionSequence.compile(<<EOS).eval
def factorial(n, acc = 1)
if n == 0
acc
else
factorial(n - 1, acc * n)
end
end
EOS
factorial(10000000) # 合法
Procを使って遅延実行する
スタックの消費を抑える
rubydef trcall(value)
while value.instance_of?(Proc)
value = value.call
end
value
end
def factorial(n, acc = 1)
return acc if n == 0
proc { factorial(n - 1, acc * n) }
end
puts trcall(factorial(10000000))
alias_method
発想はProcの例と似ている
元のメソッドをラップしてスタック消費を抑えている
rubyclass Module
def tco(meth)
called = false
tmp = nil
orig_meth = "orig_#{meth}"
alias_method orig_meth, meth
private orig_meth
define_method(meth) do |*args|
unless called
called = true
args = tmp until result = send(orig_meth, *args)
result
else
tmp = args
false
end
end
end
end
class Factorial
def factorial(n, acc = 1)
if n == 0
acc
else
factorial(n - 1, acc * n)
end
end
tco :factorial
end
s = Factorial.factorial(100)
参考