kiyoka.2010_06_30 RSSPLAIN

Related pages: !kiyoka.blog.list !kiyoka.blog.2010_06
55555555455555545555555555555554555555555555555555555545455555555555555555555555555555555555555554555555555555555555555555555555555555555555555555555555555555555555555455555555555555555555555554555554554555
5

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

5

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

5

 

5

先日「kiyoka.2010_05_28[Nendo] 末尾再帰最適化をどう実装するか」で悩んでいた末尾再帰最適化が解決した。

5

結局Chaton上のGaucheのチャットルームで質問したら、shiroさんにcallccのないプラットフォーム上で末尾再帰最適化する方法を教えて頂いた。

5

仕組みは簡単だけど、なぜそれで実現できるのかの説明が難しい。(自分的に)

5

今回はその説明を試みてみる。「継続」などの専門用語を使わずに説明してみたい。

5

 

4

末尾再帰最適化とは

5

Lisp(特にScheme)や関数型言語では再帰呼び出しを多様したプログラミングスタイルが推奨される。

5

理由は、そのほうが手続き的スタイルでコーディングするよりも問題をより自然に表現できるから。(宣言的に書ける)

5

問題は、言語処理系がなんの工夫もしていない場合、再帰呼び出しがスタックを消費するため、いずれスタックオーバーフローを起こすということ。

5

そうならないため、Schemeなどの処理系は末尾再帰最適化を施して、再帰的記述を積極的に使えるようにしている。

5

次の例で、再帰を使ったプログラムの例を挙げる。

5

 

4

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

5

一番シンプルな例では、関数の最後で自分自身を呼び出し無限ループを作る。

5

Schemeなどではごく普通に使われる書き方で、SchemeのサブセットであるNendoもこのスタイルを推奨している。

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

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

5

 

5

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

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

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

5

 

4

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

5

上記のmainループの例では、宣言的に書けるというメリットが感じられなかった。どちらかというと、whileを使ったほうが自然なほどだ。

5

しかし、プログラムによっては、再帰定義で記述するとプログラムを宣言的にすっきり記述できる。

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

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

5

 

5

[実行結果]

5
(my-member?
5
 2
5
 '(1 2 3 4 5))
5
 => #t  ;; リスト中に含まれていた
5

 

5
(my-member?
5
 6
5
 '(1 2 3 4 5))
5
 => #f  ;; リスト中に含まれていなかった
5

 

5

 

4

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

5

 

4

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

5

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

5

Rubyでsimple_loop関数を再帰呼び出しするコードになっているので、当然だ。

5

 

5

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

5
#!/usr/local/bin/ruby
5
#
5
# non tail recursion optimization code.
5
#   => tail_recursion_normal.rb:X: stack level too deep (SystemStackError)
5
#
5
5
def printCounter( count )
5
  m = count % 1000
5
  if 0 == m 
5
    printf( "count = %6d\n", count )
5
  end
5
  count
5
end  
5
5
def main
5
  count = 0
5
  @_simple_loop = lambda {|dummy1|
5
    printCounter( count )
5
    count += 1
5
    if count < 10000
5
      @_simple_loop.call(nil)
5
    end
5
  }
5
  @_simple_loop.call(nil)
5
end
5
5
main
5

 

5

[実行結果]

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

 

4

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

5

遅延呼び出しリクエストパケット(DelayedCallPacketクラス)を使って末尾再帰最適化を実現した。

5

以下のようなコードが生成される。

5

実行しても、生成前のNendoのスクリプトは再帰呼び出しでプログラミングしているにもかかわらず、スタックオーバーフローすることはない。

5

※ 本当のNendoの内部では、可変長引数が扱えるため、下記のコードよりも複雑になっている。

5

 

5

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

5
#!/usr/local/bin/ruby
5
#
5
# tail recursion optimization with trampline and DelayedCallPacket
5
#
5
5
class DelayedCallPacket
5
  def initialize( _proc, _arg1 )
5
    @proc = _proc
5
    @arg1 = _arg1
5
  end
5
5
  def call
5
    @proc.call( @arg1 )
5
  end
5
end
5
5
def trCall( result )
5
  while result.is_a? DelayedCallPacket
5
    result = result.call()
5
  end
5
  result
5
end
5
5
def printCounter( count )
5
  m = count % 10000
5
  if 0 == m 
5
    printf( "count = %6d\n", count )
5
  end
5
  count
5
end  
5
5
5
def main
5
  count = 0
5
  @_simple_loop = lambda {|dummy1|
5
    trCall( printCounter( count ))
5
    count += 1
5
    if count < 100000
5
      DelayedCallPacket.new( @_simple_loop, nil )
5
    end
5
  }
5
  trCall( @_simple_loop.call(nil) ) 
5
end
5
5
main
5

 

5

 

5

[実行結果]

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

 

4

解説

5
末尾再帰呼び出しと判断される箇所には関数呼び出しコードを出力せず、かわりに遅延呼び出しパケットを生成して返すコードを埋め込む。
5

(DelayedCallPacketクラスのインスタンスを返す)

5
それ以外の関数呼び出しについては、いつ遅延呼び出しパケットが戻ってきても良いように、trCall()関数で括る。
5
trCall()関数は、遅延呼び出しパケットが戻って来なくなるまで繰り返し遅延された呼び出しを実行しつづける。(パケット以外の値はスルー)
5

 

5

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

5
main
5
  simple_loop
5
    simple_loop
5
      simple_loop
5
        simple_loop
5
         .
5

 

5

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

5
main
5
  trCall
5
    simple_loop
5
    simple_loop
5
    simple_loop
5
    simple_loop
5
    .
5

 

5

一度trCall()関数に入れば 本来再帰呼び出しとなるところが、trCall()関数内のwhileループ内部からの連続呼び出しに変換される。

5

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

5

 

4

これは継続か?

5

遅延呼び出しパケットは継続を格納したパケットといえなくもない。参考:Scheme:CPSEXT

5

パケットはその時点での未来の実行継続ポイントでもある。

5

Schemeの本物の継続(call/ccで取得できるもの)との大きな違いは、その実行継続ポイントとして関数の入り口しか扱えないという違いがある。

5

(他にもいろいろ違いがあると思う。詳しい人、コメントください)

5

 

4

まとめ

5

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

5

 

4

参考リンク

5

末尾再帰 - WikipediaEXT

5

 

5

...comment disabled...