Compartilhar via

Tail call 最適化を使った再帰関数呼び出し

  • Artigo

F# で気がついたことをメモ代わりに記述していきます。最初に取り上げるのは、再帰呼び出しの最適化(Tail call 最適化)についてです。Manningのアーリーアクセスプログラムで読める Real World Functinal Programmingの10章に詳しく載っています。F#のインタラクティブシェルで以下のようなコードを入力します。

 let test1 = [1..10000]   // 1万までのリスト
let test2 = [1..100000]  // 10万までのリスト
let rec sumList lst =    // 合計を算出する関数
  match lst with
  |[]      -> 0
  |hd::tl  -> hd + (sumList tl)
;;

このコードを実行してみます。

 > sumList test1;;
val it : int = 50005000
> sumList test2;;

Process is terminated due to StackOverflowException.

そうすると「sumList test2」を実行したところでスタックオーバーフローが発生して、インタラクティブシェルが異常終了します。このような問題を解決する場合に利用するのが、Tail Call最適化となります。上記のコードがスタックをどのように使っているかを以下に示します。
TailCall1

図に示したようにスタックを順番に呼び出して行って、逆に戻ることで結果を返しています。この時に作成できるスタックの個数の制限を超えたために、スタックオーバーフローが発生しています。この制限を回避するには、Tail Callの最適化を利用します。
TailCall2
Tail Callの最適化とは、図に示したように順番にスタックを辿って戻っていくのではなく、一気に戻ることです。これを使うメリットは、複数のスタックを使用する必要がなくなることです。F#でTall Call最適化を利用するようにsumList関数を以下のように書きなおします。

 let rec sumList lst total =
  match lst with
  |[]       -> total
  |hd::tl   ->
    let ntotal = hd + total
    sumList tl ntotal

これで呼び出してみた結果が以下です。

 > sumList test1 0;;
val it : int = 50005000
> sumList test2 0;;
val it : int = 705082704

今度は問題なく計算することができました。つまりTail Callの最適化が行われたということです。F#では、計算する引数を渡した場合にTail Call最適化が行われるようです。上記で試した関数をListクラスが提供するsumやfold_left関数で試したのが以下です。

 > List.sum test2;;
System.OverflowException: 算術演算の結果オーバーフローが発生しました。
   場所 .$FSI_0006._main()
stopped due to error
> List.fold_left (fun a b -> a  + b) 0 test2;;
val it : int = 705082704

この結果を見れば、List.sum関数はTail callの最適化が行われていないということが理解できます。
いげ太さんのご指摘通り、List.sumは内部でSeq.sumを呼び出しているだけで、Seq.sumはLanguagePrimitives.GenericZero< (^a) >を使って合計を格納するmutableな変数を定義していています。この変数の型がオーバーフローしただけでした。この意味では、List.sumやfold_leftの例は、適切ではありませんでした。Seq.sumは、再帰関数ですらなくイテレータを使って愚直にMoveNextで和を計算しているだけです。これに対してList.fold_leftは、fold_left f s l と定義しており、ローカル関数としてloop ｓ l を再帰関数として定義しています。そして空のリストのときにsを返すようになっているところが、この結果になっています。

次にF#における名前空間(namespace)とモジュール(module)で気がついた点を記載します。最初にモジュールも名前空間も宣言しないスクリプトをライブラリとしてコンパイルします。こうすると、モジュール名はファイル名(最初の一文字は大文字)となります。作成されたアセンブリを調べるとわかりますが、C#のstatic classの名前がモジュール名になります。
　今度は、スクリプトの先頭に「module 名前」か「module 名前空間.名前」と記載してライブラリとしてコンパイルした場合です。最初の記述は先ほどと同じで、C#のstatic classの名前に相当するものが、moduleで指定した名前になります。後者のパターンは、名前空間は正しく名前空間になり、モジュール名はC#のstatic classの名前に相当します。後者の記述をnamaespaceキーワードを使って記述するには、以下のようになります。

 namespace 名前空間
  module public モジュール名
  実装コード

namespaceキーワードを使用する場合は、moduleにpublicを指定する必要があります。指定しないとprivateになるからです。またnamespaceキーワードは、スクリプトファイルのみに記述できるものとなります。このためインタラクティブシェルでは、記述できませんのでご注意ください。

PS.いげ太さんのご指摘により、list、seq、prim-typeのソースコードを参照して正しい内容に変更しました。

Comments

  • Anonymous
    January 22, 2009
    PingBack from http://windows7news.com.au/2009/01/22/tail-call-%e6%9c%80%e9%81%a9%e5%8c%96%e3%82%92%e4%bd%bf%e3%81%a3%e3%81%9f%e5%86%8d%e5%b8%b0%e9%96%a2%e6%95%b0%e5%91%bc%e3%81%b3%e5%87%ba%e3%81%97/

  • Anonymous
    January 22, 2009
    すいません。釈迦に説法を承知で。 > この結果を見れば、List.sum関数はTail callの最適化が行われていないということが理解できます。 間違いです。上記のエラーは算術演算のオーバーフローであってスタックのオーバーフローではありません。 そもそも List.sum は recursive call として定義されてすらいません。現在の実装において、List.sum は Seq.sum を呼び出すだけになっていて、では Seq.sum はというと、Seq 型（= IEnumerable 型）の値を MoveNext しつつ while でグルグルまわして要素の和を取る、という風になっています。 ではなぜ「List.fold_left (fun a b -> a + b) 0 test2」の結果と違いが出たかというと、Seq.sum が Checked.(+) を使うためです。つまり C# 的にいえば、uncheked か checked かの違いによるものです。 List.fold_left (+) 0 [1..100000]         // 705082704 List.fold_left Checked.(+) 0 [1..100000] // System.OverflowException List.fold_left (+) 0L [1L..100000L]      // 5000050000L List.sum [1..100000]   // System.OverflowException List.sum [1L..100000L] // 5000050000L

  • Anonymous
    January 22, 2009
    いげ太さん、ご指摘ありがとうございます。ライブラリのソースコードを参照して、確認しました。