F#建树函数导致Xamarin Studio中的栈溢出

Question

我正在尝试用逻辑门在树结构中建立一些规则，即 and、not、或以及条件，例如属性 x 等于值 y。我先写了最明显的递归函数，它起作用了。然后我尝试编写一个不会导致连续传递样式堆栈溢出的版本，这是我从 this post about generic tree folding and this answer on Whosebug.

得到的提示

它适用于小树（深度大约 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

密码是tail-recursive，你没看错。但问题在于单声道。看，Mono 不像 high-quality 那样是 .NET 的官方实现。特别是，它不进行尾调用消除。完全喜欢。

对于 self-recursion 最简单（也是最普遍）的情况，这无关紧要，因为编译器会更早地捕获它。 F# 编译器足够聪明，可以发现函数正在调用自身，找出在什么条件下，并将其转换为整洁的 while 循环，这样编译后的代码根本不会进行任何调用。

但是当你的尾调用是作为参数传递的函数时，编译器不能这样做，因为实际调用的函数直到运行时才知道。事实上，即使是两个函数的相互递归也不能可靠地转换为循环。

可能的解决方案：

切换到 .NET Core。
不要使用递归延续，而是使用累加器（可能不可能）。
使用self-recursion并传递手动维护的延续堆栈。
如果所有其他方法都失败了，请使用可变堆栈。

F#建树函数导致Xamarin Studio中的栈溢出

F# tree-building function causes stack overflow in Xamarin Studio

stack-overflow

recursion

f#

functional-programming

xamarin