継続バイパススタイルを使用していても、大きなバイナリツリーをトラバースするとスタックオーバーフローが発生するのはなぜですか？

Question

本の第9章エキスパートF＃3.0は、バイナリツリーをトラバースするときにスタックオーバーフローを回避するために継続通過スタイルを使用する方法を示しています。私は本のコードとほぼ同じツリートラバーサルコードを書いていますが、それでもスタックオーバーフローが発生します。次のように私のコードは次のとおりです。

type 'a Tree = 
    | Leaf of 'a 
    | Branch of 'a Tree * 'a Tree 

let rec mkLeftLeaningTree n tree = 
    if n = 0 then 
    tree 
    else 
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right") 

let leftLeaningTree1 = Leaf "left" 
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1 
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2 
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3 
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4 
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5 

let sizeContAcc tree = 
    let rec worker acc tree cont = 
    match tree with 
     | Leaf _    -> cont (acc + 1) 
     | Branch (left, right) -> worker acc left (fun acc -> 
           worker acc right cont) 
    worker 0 tree id 

F＃インタラクティブな環境にこれをロードして表現sizeContAcc leftLeaningTree6を評価するには、スタックオーバーフローを作ります。どうしてこれなの？

Answer 1

私が最初に推測したのは、cont引数の中で関数を積み重ねていることです。オーバーフローする可能性があるスタックとして理解しましたが（コメントではWolfgangの説明のとおりヒープですが） cont引数を使用してテストし、スタックオーバーフローを引き起こさなかった。代わりに、私は大幅に減速し、最終的にメモリオーバーフローに達しました。

あなたの特定の問題を解決するには、明示的にあなたが（あなたはまだリストの最大サイズによって制限されます）リストに探求する必要があります木を保存することです

：

let sizeContAcc tree = 
    let rec worker acc tree contList = 
    match tree with 
     | Leaf _ -> 
     match contList with 
     | [] -> acc+1 
     | t::cl -> worker (acc+1) t cl 
     | Branch (left, right) -> worker acc left (right::contList) 
    worker 0 tree [] 

それ直ちにleftLeaningTree6のために私に150001を与えます。

Answer 2

これは実際に問題を解決するのには役立ちませんが、見た目にはいくつかの参考になるかもしれません。まず、コードと設定。私はそれがWindows上で動作するようにツリーサイズ自体を減らしました。残りはVS2015 Update3の.NET 4.6、64-bit、win7です。

type 'a Tree = 
    | Leaf of 'a 
    | Branch of 'a Tree * 'a Tree 

[<EntryPoint>] 
let main argv = 

    ///https://stackoverflow.com/questions/40477122/why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-usi 



    let rec mkLeftLeaningTree n tree = 
     if n = 0 then 
     tree 
     else 
     Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right") 



    let leftLeaningTree1 = Leaf "left" 
    let leftLeaningTree2 = mkLeftLeaningTree 15000 leftLeaningTree1 
    let leftLeaningTree3 = mkLeftLeaningTree 15000 leftLeaningTree2 
    let leftLeaningTree4 = mkLeftLeaningTree 15000 leftLeaningTree3 
    let leftLeaningTree5 = mkLeftLeaningTree 15000 leftLeaningTree4 
    let leftLeaningTree6 = mkLeftLeaningTree 15000 leftLeaningTree5 
    let leftLeaningTree7 = mkLeftLeaningTree 15000 leftLeaningTree6 
    let leftLeaningTree8 = mkLeftLeaningTree 15000 leftLeaningTree7 
    let leftLeaningTree9 = mkLeftLeaningTree 15000 leftLeaningTree8 
    let leftLeaningTree10 = mkLeftLeaningTree 15000 leftLeaningTree9 
    let leftLeaningTree11 = mkLeftLeaningTree 15000 leftLeaningTree10 
    let leftLeaningTree12 = mkLeftLeaningTree 15000 leftLeaningTree11 
    let leftLeaningTree13 = mkLeftLeaningTree 15000 leftLeaningTree12 
    let leftLeaningTree14 = mkLeftLeaningTree 15000 leftLeaningTree13 
    let leftLeaningTree15 = mkLeftLeaningTree 15000 leftLeaningTree14 
    let leftLeaningTree16 = mkLeftLeaningTree 15000 leftLeaningTree15 
    let leftLeaningTree17 = mkLeftLeaningTree 15000 leftLeaningTree16 
    let leftLeaningTree18 = mkLeftLeaningTree 15000 leftLeaningTree17 
    let leftLeaningTree19 = mkLeftLeaningTree 15000 leftLeaningTree18 
    let leftLeaningTree20 = mkLeftLeaningTree 15000 leftLeaningTree19 
    let leftLeaningTree21 = mkLeftLeaningTree 15000 leftLeaningTree20 
    let leftLeaningTree22 = mkLeftLeaningTree 15000 leftLeaningTree21 
    let leftLeaningTree23 = mkLeftLeaningTree 15000 leftLeaningTree22 
    let leftLeaningTree24 = mkLeftLeaningTree 15000 leftLeaningTree23 
    let leftLeaningTree25 = mkLeftLeaningTree 15000 leftLeaningTree24 
    let leftLeaningTree26 = mkLeftLeaningTree 15000 leftLeaningTree25 
    let leftLeaningTree27 = mkLeftLeaningTree 15000 leftLeaningTree26 
    let leftLeaningTree28 = mkLeftLeaningTree 15000 leftLeaningTree27 
    let leftLeaningTree29 = mkLeftLeaningTree 15000 leftLeaningTree28 
    let leftLeaningTree30 = mkLeftLeaningTree 15000 leftLeaningTree29 
    let leftLeaningTree31 = mkLeftLeaningTree 15000 leftLeaningTree30 

    let sizeContAcc tree = 
     let rec worker acc tree cont = 
     match tree with 
      | Leaf _    -> cont (acc + 1) 
      | Branch (left, right) -> worker acc left (fun acc -> 
            worker acc right cont) 
     worker 0 tree id 



    sizeContAcc leftLeaningTree31 |> printfn "%A" 

    printfn "%A" argv 
    0 // return an integer exit code 

これは、末尾再帰でコンパイルされたリリースモードで最適化されています

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Release\ConsoleApplication8.exe --debug:pdbonly --noframework --define:TRACE --doc:bin\Release\ConsoleApplication8.XML --optimize+ --platform:x64 -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Release\ConsoleApplication8.exe

だから、この作品31本の木で：

.\ConsoleApplication8.exe 
450001 

今度は、デバッグモードでこれをコンパイルしてみましょう：

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Debug\ConsoleApplication8.exe -g --debug:full --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication8.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe

さらに、oops：

> .\ConsoleApplication8.exe 
Process is terminated due to StackOverflowException. 

だから違いは何ですか？

リリースバージョンでは、ILを逆コンパイルすると、コールがあります。これは、ある種のwhileループで表されると仮定しています。デバッグバージョンで

IL_0073: ldloc.s 6 
IL_0075: tail. 
IL_0077: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0) 

、これは失われます。それは、アルゴリズムの再帰的と末尾再帰バージョンの両方を持っているとして、あなたはこのQuestionを確認することができますテストするための単純例えば

L_007d: ldloc.s 6 
IL_007f: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0) 
IL_0084: ret 

を。