f# - solucion - desbordamiento de pila

¿Por qué atravesar un árbol binario grande da como resultado un desbordamiento de la pila incluso cuando se usa el estilo de continuación de paso?

Question

El Capítulo 9 del libro Expert F # 3.0 muestra cómo usar el estilo de continuación de paso para evitar desbordamientos de pila al atravesar árboles binarios. He escrito un código de cruce de árbol que es casi idéntico al código del libro, pero a pesar de todo tengo desbordamientos de pila. Mi código es el siguiente:

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

Cargando esto en el entorno interactivo F # y evaluando la expresión sizeContAcc leftLeaningTree6 hace que la pila se desborde. ¿Por qué es esto?

Answer 1

Lamentablemente, esto puede no ayudarlo a solucionar el problema, pero tal vez proporcione algunos indicadores sobre dónde buscar. Primero, el código y la configuración. Disminuí el tamaño del árbol para que funcione en Windows. El resto es .NET 4.6, 64 bits, win7, en VS2015 Update3.

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

Esto se compila con llamadas de cola, optimiza en modo de lanzamiento:

C: / Archivos de programa (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: / Archivos de programa (x86) / Reference Assemblies / Microsoft / FSharp.NETFramework / v4.0 / 4.4.0.0 / FSharp.Core .dll "-r:" C: / Archivos de programa (x86) / Assemblies de referencia / Microsoft / Framework.NETFramework / v4.6 / mscorlib.dll "-r:" C: / Archivos de programa (x86) / Assemblies de referencia / Microsoft / Framework.NETFramework / v4.6 / System.Core.dll "-r:" C: / Archivos de programa (x86) / Reference Assemblies / Microsoft / Framework.NETFramework / v4.6 / System.dll "-r:" C : / Archivos de programa (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.Asse mblyAttributes.fs "AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C: / Users / UserName / Documents / Visual Studio 2015 / Projects / StackOverflow6 / ConsoleApplication8 / bin / Release / ConsoleApplication8.exe

Entonces con 31 árboles esto funciona:

 ./ConsoleApplication8.exe
450001

Ahora compilemos esto en modo Debug:

C: / Archivos de programa (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: / Archivos de programa (x86) / Reference Assemblies / Microsoft / FSharp.NETFramework / v4.0 / 4.4.0.0 / FSharp.Core.dll "-r:" C: / Archivos de programa (x86) / Assemblies de referencia / Microsoft / Framework.NETFramework / v4.6 / mscorlib.dll "-r:" C : / Archivos de programa (x86) / Conjuntos de referencia / Microsoft / Framework.NETFramework / v4.6 / System.Core.dll "-r:" C: / Archivos de programa (x86) / Assemblies de referencia / Microsoft / Framework.NETFramework / v4 .6 / System.dll "-r:" C: / Archivos de programa (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 / Datos de aplicación/ 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

Y, oops:

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

Entonces cuál es la diferencia?

En la versión Release hay 9 tail calls, si descompilas el IL, y supongo que esto está representado por algún tipo de ciclo 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)

En la versión de depuración, esto faltará:

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

Para un ejemplo más simple de prueba, puede verificar esta pregunta ya que tiene una versión recursiva y recursiva de la cola del algoritmo.

Answer 2

Mi primera suposición fue que estás apilando funciones una encima de la otra en tu argumento de cont, lo entendí como una pila que podría desbordarse (mientras que es un montón como explica Wolfgang en un comentario) pero hice algunas pruebas con un cont argumento y no causó ningún . En cambio, tuve una desaceleración significativa y finalmente llegué a un desbordamiento de memoria.

Una solución a su problema específico sería almacenar explícitamente los árboles que necesitará explorar en una lista (aún estará limitado por el tamaño máximo de una lista):

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 []

Funciona y al instante me da 150001 para leftLeaningTree6.