爲什麼Ocaml/F＃中的函數默認不遞歸？

Question

爲什麼F＃和Ocaml（以及其他語言）中的函數不是默認遞歸？

換句話說，爲什麼語言設計者決定，這是一個好主意，明確地使你像聲明中鍵入rec：

let rec foo ... = ... 

，並沒有給默認的函數的遞歸功能？爲什麼需要一個明確的rec構造？

Answer 1

原ML的法國和英國後裔作出了不同的選擇，他們的選擇已經延續到現代變體的幾十年。所以這只是傳統，但它確實會影響這些語言的習語。

功能在法語CAML系列語言（包括OCaml）中默認不遞歸。這種選擇使得在這些語言中使用let來取代函數（和變量）定義變得容易，因爲您可以引用新定義體內的先前定義。 F＃從OCaml繼承了這個語法。

例如，計算序列的香農熵當OCaml中代替本功能p：

let shannon fold p = 
    let p x = p x *. log(p x) /. log 2.0 in 
    let p t x = t +. p x in 
    -. fold p 0.0 

注意如何參數p到高階shannon功能被另一個p在第一行所取代的身體，然後在身體的第二行另一個p。

相反，ML語言家族的英國SML分支採取了其他選擇，SML的fun-默認情況下，綁定函數是遞歸的。當大多數函數定義不需要訪問以前的函數名稱綁定時，這會導致代碼更簡單。但是，取代功能會使用不同的名稱（f1,f2等），這會污染範圍，並可能意外調用錯誤的「版本」功能。現在隱式遞歸的fun -bound函數和非遞歸val -bound函數之間存在差異。

Haskell可以通過將定義之間的依賴關係限制爲純粹來推斷它們之間的依賴關係。這使得玩具樣品看起來更簡單，但在其他地方的成本很高。

請注意，由Ganesh和Eddie給出的答案是紅鯡魚。他們解釋了爲什麼功能組不能放在巨大的let rec ... and ...內，因爲它會影響類型變量的泛化。這與012ML在SML中是默認的，而不是在OCaml中沒有任何關係。

Answer 2

一些猜測：

• let不僅用來綁定功能，還包括其他常規值。大多數形式的值不允許遞歸。某些形式的遞歸值是允許的（例如函數，惰性表達式等），所以它需要一個明確的語法來表明這一點。
• 可能更容易優化非遞歸函數
• 當你創建一個遞歸函數需要包含一個指向函數本身（所以函數可以遞歸調用本身），這使得遞歸封閉的入口創建的閉包比非遞歸閉包更復雜。因此，它可能是不錯的能夠創建簡單的非遞歸閉包，當你不需要遞歸
• 它可以讓你在先前定義的名稱相同的功能或價值來定義一個函數;雖然我認爲這是不好的做法
• 額外的安全？確保你在做你想做的事。例如如果你不打算它是遞歸的，但你不小心使用的名稱在函數內部具有相同名稱的功能本身，它很可能會抱怨（除非該名之前已經定義）
• 的let結構是相似到Lisp和Scheme中的let構造;這是非遞歸的。有一個單獨的letrec結構方案遞歸讓我們

Answer 3

有兩個關鍵原因，這是一個好主意：

首先，如果啓用遞歸定義，那麼你不能指的以前的綁定一個同名的值。當你正在做一些擴展現有模塊的工作時，這通常是一個有用的習慣用法。

其次，遞歸值，尤其是相互遞歸值的集合，更難推理，然後定義按順序進行，每個新定義都建立在已經定義的基礎之上。閱讀這樣的代碼以保證除了明確標記爲遞歸的定義之外，新定義只能引用先前的定義。

Answer 4

明確使用rec的一個重要原因是Hindley-Milner類型推理，它是所有靜態類型函數式編程語言（儘管以各種方式進行了改變和擴展）的基礎。

如果您有一個定義let f x = x，您會希望它具有類型'a -> 'a，並適用於不同點上的不同'a類型。但同樣，如果您編寫let g x = (x + 1) + ...，則在g正文的其餘部分中，您會認爲x被視爲int。

Hindley-Milner推斷處理這種區別的方式是通過明確的概括步驟。在處理你的程序的某些時候，類型系統停止並且說「好的，這些定義的類型將在此處被概括，以便當有人使用它們時，它們類型中的任何自由類型變量將是新近實例化的，因此不會干擾此定義的任何其他用途。「

事實證明，做這種泛化的明智之處是在檢查了一組相互遞歸的函數之後。任何更早的，你會泛化太多，導致類型可能實際上碰撞的情況。任何稍後，你會泛化得太少，使定義不能用於多個類型實例。

因此，鑑於類型檢查器需要知道哪些定義是相互遞歸的，它可以做什麼？一種可能性是簡單地對範圍內的所有定義進行依賴性分析，並將它們重新排列成儘可能最小的組。 Haskell實際上做到了這一點，但在像F＃（和OCaml和SML）這樣的語言中，這些語言有不受限制的副作用，這是一個壞主意，因爲它可能會重新排序副作用。因此，它要求用戶明確地標記哪些定義是相互遞歸的，並因此推廣應該發生的地方。

Answer 5

其中很大一部分是它讓程序員更好地控制其本地範圍的複雜性。 let,let*和let rec的頻譜提供了不斷增加的功率和成本水平。 let*和let rec實質上是簡單的let的嵌套版本，所以使用其中任何一個都是更昂貴的。這個評分允許您對程序的優化進行微觀管理，因爲您可以選擇哪種級別的任務來完成手頭的任務。如果你不需要遞歸或者引用上一個綁定的能力，那麼你可以回到簡單的一步以節省一些性能。

它與Scheme中的漸變相等謂詞類似。 （即eq?,eqv?和equal?）

Answer 6

鑑於此：

let f x = ... and g y = ...;; 

比較：

let f a = f (g a) 

有了這個：

let rec f a = f (g a) 

前者重定義f申請之前定義的f施加g到的結果a。後者重新定義f永遠循環申請g到a，這通常不是你想要的ML變種。

這就是說，這是一種語言設計師風格的東西。放手去做。