为什么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变种。

这就是说，这是一种语言设计师风格的东西。放手去做。