F＃のツリー構築機能は、Xamarin Studioでスタックオーバーフローが発生

Question

Iは、例えば、ない、論理ゲート、すなわちとで、ツリー構造でいくつかのルールを構築するためにまたはなどの条件をしようとしていますプロパティxは、値yと等しい。私は最初に最も明白な再帰関数を書いた。私はその後、継続待ちのスタイルでスタックオーバーフローが発生しないようなバージョンを、this post about generic tree foldingとthis answer on stackoverflowからキューに入れて書きました。

これは小さな木（深度約1000）で動作しますが、残念ながら大きな木を使用するとXamarin StudioでMac上で実行するとスタックオーバーフローが発生します。 F＃がテール再帰コードを扱う仕組みや、このコードがテール再帰でないかどうか誤解しているかどうかは誰にでも分かりますか？

The full sample is here。

let FoldTree andF orF notF leafV t data = 
    let rec Loop t cont = 
     match t with 
     | AndGate (left, right)-> 
      Loop left (fun lacc -> 
      Loop right (fun racc -> 
      cont (andF lacc racc))) 
     | OrGate (left, right)-> 
      Loop left (fun lacc -> 
      Loop right (fun racc -> 
      cont (orF lacc racc))) 
     | NotGate exp -> 
      Loop exp (fun acc -> cont (notF acc)) 
     | EqualsExpression(property,value) -> cont (leafV (property,value)) 
    Loop t id 

let evaluateContinuationPassingStyle tree data = 
    FoldTree (&&) (||) (not) (fun (prop,value) -> data |> Map.find prop |> ((=) value)) tree data 

Answer 1

コードはテール再帰的です。正しいと思います。しかし、問題はMonoにあります。 Monoは.NETの高品質な実装ではありません。特に、テールコールの消去は行いません。同じように、

自己再帰の最も単純な（そして最も一般的な）ケースでは、これはあまり重要ではありません。これは、コンパイラが先にそれをキャッチするためです。 F＃コンパイラは、関数が自分自身を呼び出していて、どのような条件の下で計算してループを正確に変換して、コンパイルされたコードがまったく呼び出しを行わないようにすることができます。

しかし、あなたのテールコールがパラメータとして渡された関数への呼び出しである場合、コンパイラはそれを実行できません。なぜなら、呼び出される実際の関数は実行時までわからないからです。事実、2つの関数の相互再帰も、ループに確実に変換することはできません。

考えられる解決策：.NETのコアへ

• スイッチ。
• 再帰的な継続を使用しないで、代わりにアキュムレータを使用してください（可能でない可能性があります）。
• 自己再帰を使用し、手動で維持された連続のスタックを渡します。
• その他すべてが失敗した場合は、可変スタックを使用してください。