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.