末尾再帰最適化、実装完了

2010年06月30日

私がRubyで書いているLisp方言、 [Nendo]について。

先日「2010-05-28Nendo* 末尾再帰最適化をどう実装するか」で悩んでいた末尾再帰最適化が解決した。結局Chaton上のGaucheのチャットルームで質問したら、shiroさんにcallccのないプラットフォーム上で末尾再帰最適化する方法を教えて頂いた。仕組みは簡単だけど、なぜそれで実現できるのかの説明が難しい。(自分的に) 今回はその説明を試みてみる。「継続」などの専門用語を使わずに説明してみたい。

末尾再帰最適化とは

Lisp(特にScheme)や関数型言語では再帰呼び出しを多様したプログラミングスタイルが推奨される。理由は、そのほうが手続き的スタイルでコーディングするよりも問題をより自然に表現できるから。(宣言的に書ける) 問題は、言語処理系がなんの工夫もしていない場合、再帰呼び出しがスタックを消費するため、いずれスタックオーバーフローを起こすということ。そうならないため、Schemeなどの処理系は末尾再帰最適化を施して、再帰的記述を積極的に使えるようにしている。次の例で、再帰を使ったプログラムの例を挙げる。

* mainループ: 自分自身を呼び出す無限ループの例

一番シンプルな例では、関数の最後で自分自身を呼び出し無限ループを作る。 Schemeなどではごく普通に使われる書き方で、Schemeのサブセットである[Nendo]もこのスタイルを推奨している。

(define (main argv)
  ;; イベントキューから新しいイベントを取り出して処理する等
  (main argv)

このようなコーディングは、デーモンプロセスのようにメモリに常駐し半永久的に動き続けるようなプログラムで使われる。

説明のために Rubyで再帰を使わずに記述すると、以下のようになる。

def main
  while true
  # イベントキューから新しいイベントを取り出して処理する等
  end
end

Rubyでは処理系が末尾再帰最適化をサポートしていないため、このように書かないといけない。(実際にRubyは1.9.2になっても末尾再帰最適化はサポートしていない)

* my-member?関数: リスト中に特定の値が含まれているか調べる関数

上記のmainループの例では、宣言的に書けるというメリットが感じられなかった。どちらかというと、whileを使ったほうが自然なほどだ。しかし、プログラムによっては、再帰定義で記述するとプログラムを宣言的にすっきり記述できる。

(define (my-member? val lst)
  (if (null? lst)
      #f
      (if (eq? val (car lst))
          #t
          (my-member? val (cdr lst)))))

この例では、my-member?自身を呼び出して、リストの先頭以外の調査を自分自身に丸投げしている。

実行結果

(my-member?
 2
 '(1 2 3 4 5))

=> #t ;; リスト中に含まれていた

(my-member?
 6
 '(1 2 3 4 5))

=> #f ;; リスト中に含まれていなかった

[Nendo]での末尾再帰最適化の実現方法

* 末尾再帰最適化を施していない場合のイメージ

[Nendo]はNendoのソースコード(S式)をいったんRubyのプログラムに変換する。今回の対策をする前は以下のようなコードを出力していたため、10000回の再帰が完了するまでに、Stackオーバーフローで停止していた。 Rubyでsimple_loop関数を再帰呼び出しするコードになっているので、当然だ。

生成後のRubyソースコードイメージ(説明用に簡略化されている)

#!/usr/local/bin/ruby
#
# non tail recursion optimization code.
#   => tail_recursion_normal.rb:X: stack level too deep (SystemStackError)
#

def printCounter( count )
  m = count % 1000
  if 0 == m 
    printf( "count = %6d\n", count )
  end
  count
end  

def main
  count = 0
  @_simple_loop = lambda {|dummy1|
    printCounter( count )
    count += 1
    if count < 10000
      @_simple_loop.call(nil)
    end
  }
  @_simple_loop.call(nil)
end

main

実行結果

$ ./tail_recursion_normal.rb
count =      0
count =   1000
count =   2000
count =   3000
./tail_recursion_normal.rb:8: stack level too deep (SystemStackError)

* 末尾再帰最適化を施した場合のイメージ

遅延呼び出しリクエストパケット(DelayedCallPacketクラス)を使って末尾再帰最適化を実現した。以下のようなコードが生成される。実行しても、生成前の[Nendo]のスクリプトは再帰呼び出しでプログラミングしているにもかかわらず、スタックオーバーフローすることはない。 ※ 本当のNendoの内部では、可変長引数が扱えるため、下記のコードよりも複雑になっている。

生成後のRubyソースコードイメージ(説明用に簡略化されている)

#!/usr/local/bin/ruby
#
# tail recursion optimization with trampline and DelayedCallPacket
#

class DelayedCallPacket
  def initialize( _proc, _arg1 )
    @proc = _proc
    @arg1 = _arg1
  end

  def call
    @proc.call( @arg1 )
  end
end

def trCall( result )
  while result.is_a? DelayedCallPacket
    result = result.call()
  end
  result
end

def printCounter( count )
  m = count % 10000
  if 0 == m 
    printf( "count = %6d\n", count )
  end
  count
end  


def main
  count = 0
  @_simple_loop = lambda {|dummy1|
    trCall( printCounter( count ))
    count += 1
    if count < 100000
      DelayedCallPacket.new( @_simple_loop, nil )
    end
  }
  trCall( @_simple_loop.call(nil) ) 
end

main

実行結果

$ ./tail_recursion_optimized_with_tramp.rb
count =      0
count =  10000
count =  20000
count =  30000
count =  40000
count =  50000
count =  60000
count =  70000
count =  80000
count =  90000
 .
 .
 .

* 解説

末尾再帰呼び出しと判断される箇所には関数呼び出しコードを出力せず、かわりに遅延呼び出しパケットを生成して返すコードを埋め込む。 (DelayedCallPacketクラスのインスタンスを返す)
それ以外の関数呼び出しについては、いつ遅延呼び出しパケットが戻ってきても良いように、trCall()関数で括る。
trCall()関数は、遅延呼び出しパケットが戻って来なくなるまで繰り返し遅延された呼び出しを実行しつづける。(パケット以外の値はスルー)

末尾再帰最適化をしていない場合の呼び出しツリーはこのようになり、いつか呼び出しスタックが溢れる。

main
  simple_loop
    simple_loop
      simple_loop
        simple_loop
         .

それに比べて、末尾再帰最適化を行った場合には次のようになる。

main
  trCall
    simple_loop
    simple_loop
    simple_loop
    simple_loop
    .

一度trCall()関数に入れば本来再帰呼び出しとなるところが、trCall()関数内のwhileループ内部からの連続呼び出しに変換される。なぜ、これで解決するかというと、遅延された再帰呼び出しを、トランポリン関数trCall()が、スタックを消費しない単純なループに変換して処理しているからだ。

これは継続か？

遅延呼び出しパケットは継続を格納したパケットといえなくもない。参考:Scheme:CPS パケットはその時点での未来の実行継続ポイントでもある。 Schemeの本物の継続(call/ccで取得できるもの)との大きな違いは、その実行継続ポイントとして関数の入り口しか扱えないという違いがある。 (他にもいろいろ違いがあると思う。詳しい人、コメントください)

まとめ

末尾再帰呼び出しの実行を、呼び出し元に遅延させ、呼び出し元でループとして処理すればスタック消費をリダクションできる。(リソース消費の最適化)

参考リンク

末尾再帰 - Wikipedia