不明功能语言OCaml的'let rec'的原因是什么？ [英] What's the reason of 'let rec' for impure functional language OCaml?

问题描述

在真实世界OCaml 一书中，作者提出了为什么OCaml使用 let rec 来定义递归函数。
$ b

OCaml很大程度上出于技术原因区分非递归定义（使用let）和递归定义（使用let rec）：类型推断算法需要要知道什么时候一组函数定义是相互递归的，并且由于不适用于像Haskell这样的纯语言的原因，这些必须由程序员明确地标记。

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

int x = x + 1 合法）。 OCaml语言决定给我们额外的灵活性，让我们自己做出选择。这真的很棒。他们决定默认情况下将它隐藏起来，这是一个相当不错的解决方案，因为我们编写的大部分函数都是非递归的。

与引用有关的内容，它并不真正对应于函数定义 - rec 关键字。它主要是关于为什么函数定义的范围不扩展到模块的主体。这是一个完全不同的问题。
经过一番研究，我发现了一个非常的类似的问题，它有一个答案，可能会满足你，从它引用：

因此，鉴于类型检查器需要知道
定义的哪些集合是相互递归的，它可以做什么？一种可能性是
简单地对范围内的所有定义进行依赖分析，
并将它们重新排列到最小的可能组中。 Haskell实际上是
这样做的，但是在像F＃（和OCaml和SML）这样的语言中，它们有
无限制的副作用，这是一个坏主意，因为它可能会重新订购
，效果也是。因此，它会要求用户明确标记
，这些定义是相互递归的，并因此延伸到应该发生
概括的地方。

即使没有任何重新排序，使用任意的非纯表达式，可能出现在函数定义中（定义的副作用，而不是评估），建立依赖关系图是不可能的。考虑从文件解码和执行功能。总之，我们有两种使用方式： let rec 构造，一种是创建一个自递归函数，就像

 让rec seq acc =函数
 | 0  - > acc 
 | n  - > seq（acc + 1）（n-1）
  

另一个是定义相互递归函数： p>



 让rec奇数n = 
如果n = 0，则返回true 
 else if n = 1 then false else （n  -  1）
，甚至n = 
，如果n = 0，那么假
否则如果n = 1，则返回true否则奇（n  -  1）
  

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



第二种情况更难。在推断类型时，您需要将所有函数定义拆分为由相互依赖的定义组成的群集，以缩小打字环境。在OCaml中很难做到，因为你需要考虑到副作用。 （或者你可以继续而不将它分解成主要组件，但是这会导致另一个问题 - 你的类型系统会受到更多限制，也就是说，将不允许更多有效的程序）。

<但是，重新回顾一下原来的问题和RWO的报价，我仍然非常确定添加 rec 标志没有技术上的原因。考虑一下，SML具有相同的问题，但仍默认启用 rec 。 是技术原因，用于定义一组相互递归函数的 let ...和... 语法。在SML中，这个语法并不要求我们在OCaml中放置 rec 标志，从而为我们提供了更多的灵活性，就像使用<$ c $交换值c>让x = y和y = x 表达式。

In the book Real World OCaml, the authors put why OCaml uses let rec for defining recursive functions.

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.

What are the technical reasons that enforces let rec while pure functional languages not?

解决方案

When you define a semantics of function definition, as a language designer, you have choices: either to make the name of the function visible in the scope of its own body, or not. Both choices are perfectly legal, for example C-family languages being far from functional, still do have names of definitions visible in their scope (this also extends to all definitions in C, making this int x = x + 1 legal). OCaml language decides to give us extra flexibility of making the choice by ourselves. And that's really great. They decided to make it invisible by default, a fairly descent solution, since most of the functions that we write are non recursive.

What concerning the cite, it doesn't really correspond to the function definitions – the most common use of the rec keyword. It is mostly about "Why the scope of function definition doesn't extend to the body of the module". This is a completely different question. After some research I've found a very similar question, that has an answer, that might satisfy you, a cite from it:

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

Even without any reordering, with arbitrary non-pure expressions, that can occur in the function definition (a side effect of definition, not evaluation) it is impossible to build the dependency graph. Consider demarshaling and executing function from file.

To summarize, we have two usages of let rec construct, one is to create a self recursive function, like

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

Another is to define mutually recursive functions:

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)

At the first case, there is no technical reasons to stick to one or to another solution. This is just a matter of taste.

The second case is harder. When inferring type you need to split all function definitions into clusters consisting of mutually depending definitions, in order to narrow typing environment. In OCaml it is harder to make, since you need to take into account side-effects. (Or you can continue without splitting it into principal components, but this will lead to another issue – your type system will be more restrictive, i.e., will disallow more valid programs).

But, revisiting the original question and the quote from RWO, I'm still pretty sure that there is no technical reasons for adding the rec flag. Consider, SML that has the same problems, but still has rec enabled by default. There is a technical reason, for let ... and ... syntax for defining a set of mutual recursive functions. In SML this syntax doesn't require us to put the rec flag, in OCaml does, thus giving us more flexibility, like the ability to swap to values with let x = y and y = x expression.

这篇关于不明功能语言OCaml的'let rec'的原因是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！