F # fonction de construction d'arbre provoque un débordement de pile dans Xamarin studio

Question

Je suis en train de mettre en place des règles dans une structure arborescente, avec portes logiques à savoir et, pas, ou ainsi que les conditions, par exemple la propriété x est égale à la valeur et. J'ai d'abord écrit la fonction récursive la plus évidente, qui a fonctionné. J'ai alors essayé d'écrire une version qui ne provoquerait pas un débordement de pile dans le style de passage continu prenant mon repère de this post about generic tree folding et de this answer on stackoverflow.

Cela fonctionne pour les petits arbres (profondeur d'environ 1000), mais malheureusement, lorsque vous utilisez un grand arbre, cela provoque un stackoverflow lorsque je l'exécute sur mon Mac avec Xamarin Studio. Quelqu'un peut-il me dire si j'ai mal compris comment F # traite le code récursif en queue ou si ce code n'est pas récursif?

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

Le code est récursif à la queue, vous l'avez compris. Mais le problème est avec Mono. Voir, Mono n'est pas aussi bonne mise en œuvre de .NET que la chose officielle. En particulier, il n'effectue pas l'élimination des escargots. Comme, du tout.

Pour le cas d'auto-récurrence le plus simple (et le plus répandu), cela n'a pas beaucoup d'importance, car le compilateur l'attrape plus tôt. Le compilateur F # est assez intelligent pour repérer que la fonction s'appelle elle-même, détermine dans quelles conditions, et le convertit en une bonne boucle while, de sorte que le code compilé ne fasse aucun appel du tout.

Mais lorsque votre appel de queue est à une fonction passée en paramètre, le compilateur ne peut pas le faire, car la fonction réelle appelée n'est pas connue avant l'exécution. En fait, même la récurrence mutuelle de deux fonctions ne peut pas être convertie en boucle de manière fiable.

solutions possibles:

• Passer au .NET de base.
• N'utilisez pas de suites récursives, utilisez l'accumulateur à la place (cela peut ne pas être possible).
• Utilisez la récursion automatique et passez la pile de suites maintenue manuellement.
• Si tout le reste échoue, utilisez une pile mutable.