110

为什么默认情况下 F# 和 OCaml（可能还有其他语言）中的函数不是递归的？

换句话说，为什么语言设计者认为明确地让你输入rec如下声明是个好主意：

let rec foo ... = ...

并且默认不赋予函数递归能力？为什么需要显式rec构造？

4

6 回答 6

90

最初的 ML 的法国和英国后裔做出了不同的选择，他们的选择几十年来一直被继承到现代变体中。所以这只是遗留问题，但它确实会影响这些语言的习语。

在法语 CAML 系列语言（包括 OCaml）中，函数默认不是递归的。这种选择使取代let在这些语言中使用的函数（和变量）定义变得容易，因为您可以在新定义的主体内引用先前的定义。F# 从 OCaml 继承了这种语法。

例如，p在 OCaml 中计算序列的香农熵时取代函数：

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-bound 函数默认情况下是递归的。当大多数函数定义不需要访问其函数名称的先前绑定时，这会导致代码更简单。但是，被取代的函数使用不同的名称（f1等f2），这会污染范围并可能意外调用错误的函数“版本”。现在隐式递归fun绑定函数和非递归val绑定函数之间存在差异。

Haskell 可以通过将定义限制为纯定义来推断定义之间的依赖关系。这使玩具样品看起来更简单，但在其他地方却付出了沉重的代价。

请注意，Ganesh 和 Eddie 给出的答案是红鲱鱼。他们解释了为什么不能将函数组放在一个巨大的内部，let rec ... and ...因为它会影响类型变量何时被泛化。这与 SML 中的默认值无关，但与recOCaml 中的默认值无关。

于 2009-12-11T23:37:50.493 回答
54

显式使用的一个关键原因rec是与 Hindley-Milner 类型推断有关，它是所有静态类型函数式编程语言的基础（尽管以各种方式进行了更改和扩展）。

如果你有一个定义let f x = x，你会期望它有类型'a -> 'a并且适用于'a不同点的不同类型。但同样，如果你写let g x = (x + 1) + ...，你会期望x在.intg

Hindley-Milner 推理处理这种区别的方式是通过明确的概括步骤。在处理程序的某些时刻，类型系统停止并说“好的，此时这些定义的类型将被泛化，因此当有人使用它们时，其类型中的任何自由类型变量都将被重新实例化，因此不会干扰该定义的任何其他用途。”

事实证明，进行这种概括的明智之处是在检查一组相互递归的函数之后。任何更早的，你都会概括太多，导致类型实际上可能发生冲突的情况。稍后，您将泛化得太少，从而使定义不能用于多种类型的实例化。

那么，鉴于类型检查器需要知道哪些定义集是相互递归的，它可以做什么呢？一种可能性是简单地对范围内的所有定义进行依赖性分析，并将它们重新排序为尽可能小的组。Haskell 实际上是这样做的，但是在像 F#（以及 OCaml 和 SML）这样具有不受限制的副作用的语言中，这是一个坏主意，因为它也可能对副作用进行重新排序。因此，它要求用户明确标记哪些定义是相互递归的，从而扩展应该在哪里进行泛化。

于 2009-05-24T21:37:57.227 回答
11

这是一个好主意有两个关键原因：

首先，如果您启用递归定义，那么您不能引用以前绑定的同名值。当你在做一些像扩展现有模块这样的事情时，这通常是一个有用的习惯用法。

其次，递归值，尤其是相互递归值的集合，更难推理，因为定义是按顺序进行的，每个新定义都建立在已经定义的之上。阅读这样的代码时最好能保证，除了明确标记为递归的定义外，新定义只能引用以前的定义。

于 2009-05-23T02:05:55.170 回答
5

一些猜测：

  • let不仅用于绑定函数，还用于绑定其他常规值。大多数形式的值不允许递归。某些形式的递归值是允许的（例如函数、惰性表达式等），因此需要明确的语法来表明这一点。
  • 优化非递归函数可能更容易
  • 创建递归函数时创建的闭包需要包含一个指向函数本身的条目（以便函数可以递归调用自身），这使得递归闭包比非递归闭包更复杂。因此，当您不需要递归时，能够创建更简单的非递归闭包可能会很好
  • 它允许您根据先前定义的函数或同名值来定义函数；虽然我认为这是不好的做法
  • 额外的安全？确保你正在做你想做的事。例如，如果您不打算将其递归，但您不小心在函数内部使用了与函数本身同名的名称，它很可能会抱怨（除非之前已定义该名称）
  • 该let构造类似于letLisp 和 Scheme 中的构造；这是非递归的。Scheme中有一个单独的letrec构造用于递归让我们
于 2009-05-23T01:29:35.337 回答
4

鉴于这种：

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

比较：

let f a = f (g a)

有了这个：

let rec f a = f (g a)

前者重新定义f以将先前定义的应用到应用到f的结果中。后者重新定义为循环永远应用于，这通常不是您在 ML 变体中想要的。gafga

也就是说，这是语言设计师风格的事情。放手去做。

于 2010-12-22T05:30:16.877 回答
1

其中很大一部分是它使程序员可以更好地控制其本地范围的复杂性。的频谱let，let*并let rec提供越来越高的功率和成本水平。let*并且let rec本质上是 simple 的嵌套版本let，因此使用任何一个都更昂贵。此分级允许您对程序的优化进行微观管理，因为您可以选择手头任务所需的级别。如果您不需要递归或引用先前绑定的能力，那么您可以依靠一个简单的 let 来节省一些性能。

它类似于 Scheme 中的分级相等谓词。（即eq?和）eqv?equal?

于 2009-05-24T22:36:23.147 回答