haskell - 非纯函数式语言 OCaml 出现 'let rec' 的原因是什么？

Question

书中Real World OCaml ，作者阐述了为什么 OCaml 使用 let rec 来定义递归函数。

OCaml distinguishes between nonrecursive definitions (using let) and recursive definitions (using let rec) largely for technical reasons: the type-inference algorithm needs to know when a set of function definitions are mutually recursive, and for reasons that don't apply to a pure language like Haskell, these have to be marked explicitly by the programmer.

强制执行 let rec 而纯函数式语言则不执行的技术原因是什么？

Answer 1

当您定义函数定义的语义时，作为语言设计者，您可以选择:要么使函数的名称在其自身范围内可见，要么不可见。两种选择都是完全合法的，例如 C 系列语言远非功能性的，但仍然具有在其范围内可见的定义名称(这也扩展到 C 中的所有定义，使得 int x = x + 1 合法)。 OCaml 语言决定给我们额外的灵 active ，让我们自己做出选择。这真的很棒。他们决定默认使其不可见，这是一个相当不错的解决方案，因为我们编写的大多数函数都是非递归的。

关于引用，它并不真正对应于函数定义 - rec 最常见的用法关键词。它主要是关于“为什么函数定义的范围没有扩展到模块的主体”。这是一个完全不同的问题。经过一番研究，我发现了一个非常similar question ，有 answer ，这可能会让你满意，引用它:

So, given that the type checker needs to know about which sets ofdefinitions are mutually recursive, what can it do? One possibility isto simply do a dependency analysis on all the definitions in a scope,and reorder them into the smallest possible groups. Haskell actuallydoes this, but in languages like F# (and OCaml and SML) which haveunrestricted side-effects, this is a bad idea because it might reorderthe side-effects too. So instead it asks the user to explicitly markwhich definitions are mutually recursive, and thus by extension wheregeneralization should occur.

即使没有任何重新排序，使用任意非纯表达式，可能会出现在函数定义中(定义的副作用，而不是评估)，也不可能构建依赖关系图。考虑从文件中解码并执行函数。

总而言之，let rec 有两种用法构造，一是创建一个自递归函数，比如

 let rec seq acc = function
    | 0 -> acc
    | n -> seq (acc+1) (n-1)

另一种是定义相互递归函数:

let rec odd n =
  if n = 0 then true
  else if n = 1 then false else even (n - 1)
and even n =
  if n = 0 then false
  else if n = 1 then true else odd (n - 1)

在第一种情况下，没有技术原因坚持使用一个或另一个解决方案。这只是一个品味问题。

第二种情况比较困难。推断类型时，您需要将所有函数定义拆分为由相互依赖的定义组成的簇，以缩小类型环境。在 OCaml 中，它更难实现，因为您需要考虑副作用。 (或者您可以继续而不将其拆分为主要组件，但这将导致另一个问题 - 您的类型系统将受到更多限制，即，将不允许更多有效的程序)。

但是，重新审视最初的问题和 RWO 的引用，我仍然非常确定添加 rec 没有技术原因。旗帜。考虑一下，SML 也有同样的问题，但仍然有 rec默认启用。 有技术原因，let ... and ...用于定义一组相互递归函数的语法。在 SML 中，此语法不需要我们输入 rec OCaml 中的 flag 确实如此，从而为我们提供了更大的灵 active ，例如能够使用 let x = y and y = x 交换到值。表达。