F＃樹構建函數導致堆棧溢出在Xamarin工作室

我試圖建立在樹結構中的一些規則，用邏輯門即和，不，或，以及條件，例如物業x等於值y。我首先寫了最明顯的遞歸函數，它的工作。然後我試着編寫一個不會導致延續傳遞樣式的堆棧溢出的版本，從this post about generic tree folding和this answer on stackoverflow中提取我的提示。F＃樹構建函數導致堆棧溢出在Xamarin工作室

它適用於小型樹木（深度大約爲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

來源

2017-02-18 NickL

該代碼是尾遞歸的，你說得對。但問題在於Mono。看，Mono不像官方那樣高品質的.NET實現。特別是，它不會去尾呼叫。就像，完全一樣。

對於自遞歸最簡單（也是最普遍）的情況，這並不重要，因爲編譯器會在早期捕獲它。 F＃編譯器足夠聰明，可以發現函數正在調用它自己，找出在什麼條件下，並將其轉換成一個整齊的while循環，以便編譯後的代碼根本不會進行任何調用。

但是，當你的尾部調用是作爲參數傳遞的函數時，編譯器不能這樣做，因爲調用的實際函數直到運行時才知道。事實上，即使是兩個函數的相互遞歸也不能可靠地轉換成循環。

可能的解決方案：

切換到.NET的核心。
不要使用遞歸延續，而應使用累加器（可能不可能）。
使用自遞歸併傳遞手動維護的延續堆棧。
如果一切都失敗，請使用可變堆棧。

來源

2017-02-18 18:41:28

這是令人失望的。花了很長一段時間認爲這是我的執行問題。發現這個[bug報告]（https://bugzilla.xamarin.com/show_bug.cgi?id=12635#c11），看起來像它匹配，最後的評論看起來像它不會很快解決。 – NickL

單聲道正在消失。切換到.NET Core。 –

@FyodorSoikin我不認爲Mono很快就會離開Xamarin。 – svick

F＃樹構建函數導致堆棧溢出在Xamarin工作室

回答

相關問題