In the book Real World OCaml, the authors put why OCaml uses let rec for defining recursive functions.
在《真实世界的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.
OCaml区分nonrecursive定义(使用让)和递归定义(使用让rec)很大程度上因为技术原因:类型推断算法需要知道当一组函数定义是相互递归,原因,并不适用于一个纯粹的语言像Haskell,这些必须由程序员显式。
What are the technical reasons that enforces let rec while pure functional languages not?
什么技术原因促使rec而纯函数语言不允许?
6 个解决方案
#1
34
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.
当您定义函数定义的语义(作为语言设计器)时，您可以选择:要么使函数的名称在它自己的主体范围内可见，要么不可见。这两种选择都是完全合法的，例如C-family语言的功能还远远不够，它们的范围内仍然有可见的定义名称(这也扩展到C中的所有定义，使这个int x = x + 1合法)。OCaml语言给了我们更多的自主选择的灵活性。这是真正伟大的。他们决定让它在默认情况下不可见，这是一个很好的下降解，因为我们写的大多数函数都是非递归的。
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:
至于引用，它实际上并不对应函数定义——rec关键字最常用的用法。它主要是关于“为什么函数定义的范围没有扩展到模块的主体”。这是一个完全不同的问题。经过一些研究，我发现了一个非常相似的问题，这个问题有一个答案，可能会让你满意，其中有一个引用:
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.
那么，既然类型检查器需要知道哪些定义集是相互递归的，那么它能做什么呢?一种可能是简单地对范围中的所有定义进行依赖分析，并将它们重新排序到最小可能的组中。Haskell实际上是这样做的，但是在像f#(和OCaml和SML)这样具有不受限制的副作用的语言中，这是一个坏主意，因为它可能也会重新排序副作用。因此，它要求用户显式地标记哪些定义是相互递归的，从而通过扩展来实现泛化。
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构造有两种用法，一种是创建一个自递归函数，比如
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).
第二种情况更难处理。当推断类型时，您需要将所有函数定义分割成由相互依赖的定义组成的集群，以便缩小类型环境。在OCaml中，它更难制作，因为你需要考虑副作用。(或者您可以继续而不将其分解为主组件，但这将导致另一个问题——您的类型系统将更加严格，例如。，将不允许更多有效的程序)。
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.
但是，再回到最初的问题和RWO的引用，我仍然确信添加rec标志没有技术上的原因。考虑一下，SML有相同的问题，但是在默认情况下仍然启用rec。有一个技术原因，让……和…定义一组相互递归函数的语法。在SML中，这种语法不需要我们在OCaml中放置rec标志，因此给了我们更大的灵活性，比如可以用let x = y和y = x表达式交换值。
#2
18
What are the technical reasons that enforces let rec while pure functional languages not?
什么技术原因促使rec而纯函数语言不允许?
Recursiveness is a strange beast. It has a relation to purity, but it's a little more oblique than this. To be clear, you could write "alterna-Haskell" which retains its purity, its laziness but does not have recursively bound lets by default and demands some kind of rec marker just as OCaml does. Some would even prefer this.
递归是一种奇怪的野兽。它和纯度有关系，但它比这个更有倾斜度。需要说明的是，您可以编写“alterna-Haskell”，它保留了它的纯粹性，它的惰性，但默认情况下没有递归绑定的let，并且需要某种rec标记，就像OCaml所做的那样。有些人甚至更喜欢这样。
In essence, there are just many different kinds of "let"s possible. If we compare let and let rec in OCaml we'll see a small difference. In static formal semantics, we might write
本质上，有很多不同的“让我们成为可能”。如果我们在OCaml中比较，我们会看到一个小的区别。在静态形式语义中，我们可以编写。
Γ ⊢ E : A Γ, x : A ⊢ F : B
-----------------------------
Γ ⊢ let x = E in F : B
which says that if we can prove in a variable environment Γ that E has type A and if we can prove in the same variable environment Γ augmented with x : A that F : B then we can prove that in the variable environment Γ let x = E in F has type B.
说,如果我们可以证明在一个变量环境ΓE a型,如果我们可以证明在同一个变量环境Γ增强x:a F:然后我们可以证明,在变量环境Γ让x = E在F B型。
The thing to watch is the Γ argument. This is just a list of ("variable name", "value") pairs like [(x, 3); (y, "hello")] and augmenting the list like Γ, x : A just means consing (x, A) on to it (sorry that the syntax is flipped).
看的是Γ参数。这只是一个(“变量名”、“值”)对的列表，如[(x, 3);(y,“你好”)],增加像Γ列表,x:就是缺点(x),(不好意思,语法是翻转)。
In particular, let's write the same formalism for let rec
特别地，让我们为rec写同样的形式
Γ, x : A ⊢ E : A Γ, x : A ⊢ F : B
-------------------------------------
Γ ⊢ let rec x = E in F : B
In particular, the only difference is that neither of our premises work in the plain Γ environment; both are allowed to assume the existence of the x variable.
特别的,唯一的区别是,无论是我们的纯Γ前提工作环境;两者都可以假设x变量的存在。
In this sense, let and let rec are simply different beasts.
从这个意义上说，让我们让rec只是不同的东西。
So what does it mean to be pure? At the strictest definition, of which Haskell doesn't even participate, we must eliminate all effects including non-termination. The only way to achieve this is to pull away our ability to write unrestricted recursion and replace it only carefully.
那么纯洁意味着什么呢?在最严格的定义中，Haskell甚至不参与其中，我们必须消除所有的影响，包括不终止。要做到这一点，唯一的方法就是去掉写无限制递归的能力，只小心地替换它。
There exist plenty of languages without recursion. Perhaps the most important one is the Simply Typed Lambda Calculus. In it's basic form it is regular lambda calculus but augmented with a typing discipline where types are bit like
有很多语言没有递归。也许最重要的一个是简单类型的微积分。在它的基本形式中，它是常规的lambda演算，但在类型有点类似的情况下，还增加了类型规则
type ty =
| Base
| Arr of ty * ty
It turns out that STLC cannot represent recursion---the Y combinator, and all other fixed-point cousin combinators, cannot be typed. Thusly, STLC is not Turing Complete.
事实证明STLC不能表示递归——Y组合子和所有其他定点表兄弟组合子都不能被输入。Thusly, STLC并不是图灵完成的。
It is however uncompromisingly pure. It achieves that purity with the bluntest of instruments, however, by completely outlawing recursion. What we'd really like is some kind of balanced, careful recursion which doesn't lead to non-termination---we'll still be Turing Incomplete, but not so crippled.
这是一种纯粹的不妥协。然而，它通过完全禁止递归的方法来达到这种纯度。我们真正想要的是某种平衡的、谨慎的递归，它不会导致不终止——我们仍然会图灵不完整，但不会如此残废。
Some languages try this game. There are clever ways of adding typed recursion back along a division between data and codata which ensures that you cannot write non-terminating functions. If you're interested, I suggest learning a bit of Coq.
有些语言尝试这个游戏。有一种巧妙的方法可以将类型化递归沿着数据和codata之间的划分进行添加，从而确保您不能编写非终止函数。如果你有兴趣的话，我建议你学一点Coq。
But OCaml's goal (and Haskell's as well) is not to be delicate here. Both languages are uncompromisingly Turing Complete (and therefore "practical"). So let's discuss some more blunt ways of augmenting the STLC with recursion.
但是OCaml的目标(以及Haskell的目标)并不是在这里显得很微妙。这两种语言都是完美无缺的(因此也是“实用的”)。让我们讨论一些更直接的方法，用递归扩展STLC。
The bluntest of the bunch is to add a single built-in function called fix
最愚蠢的做法是添加一个名为fix的内置函数
val fix : ('a -> 'a) -> 'a
or, in more genuine OCaml-y notation which requires eta-expansion
或者，在更真实的ocml -y表示法中，它要求eta-展开
val fix : (('a -> 'b) -> ('a -> 'b)) -> ('a -> 'b)
Now, remember that we're only considering a primitive STLC with fix added. We can indeed write fix (the latter one at least) in OCaml, but that's cheating at the moment. What does fix buy the STLC as a primitive?
现在，请记住，我们只考虑添加了fix的原始STLC。我们确实可以用OCaml来写fix(至少是后者)，但现在这是作弊。fix购买STLC作为一个原语是什么?
It turns out that the answer is: "everything". STLC + Fix (basically a language called PCF) is impure and Turing Complete. It's also simply tremendously difficult to use.
答案是:“一切”。STLC + Fix(基本上是一种叫做PCF的语言)是不纯的，图灵是完整的。它的使用也非常困难。
So this is the final hurdle to jump: how do we make fix easier to work with? By adding recursive bindings!
因此，这是要跨越的最后一个障碍:我们如何使修复工作变得更容易?通过添加递归绑定!
Already, STLC has a let construction. You can think of it as just syntax sugar:
STLC已经有了一个let结构。你可以把它想象成语法糖:
let x = E in F ----> (fun x -> F) (E)
but once we've added fix we also have the power to introduce let rec bindings
但是一旦我们添加了fix，我们还可以引入rec绑定
let rec x a = E in F ----> (fun x -> F) (fix (fun x a -> E))
At this point it should again be clear: let and let rec are very different beasts. They embody different levels of linguistic power and let rec is a window to allow fundamental impurity through Turing Completeness and its partner-effect non-termination.
在这一点上，应该再次明确:让rec成为完全不同的野兽。它们体现了不同层次的语言力量，让rec成为一个窗口，通过图灵完整性和它的伙伴效应不终止来允许基本的不洁净。
So, at the end of the day, it's a little amusing that Haskell, the purer of the two languages, made the interesting choice of abolishing plain let bindings. That's really the only difference: there is no syntax for representing a non-recursive binding in Haskell.
所以，在这一天结束的时候，有一点有趣的是，哈斯卡尔，这两种语言的纯粹者，做出了一个有趣的选择:废除简单的let绑定。这是唯一的区别:在Haskell中没有表示非递归绑定的语法。
At this point it's essentially just a style decision. The authors of Haskell determined that recursive bindings were so useful that one might as well assume that every binding is recursive (and mutually so, a can of worms ignored in this answer so far).
在这一点上，它本质上只是一个样式决定。Haskell的作者认为，递归绑定非常有用，因此我们不妨假设每个绑定都是递归的(到目前为止，这个答案中忽略了一罐蠕虫)。
On the other hand, OCaml gives you to ability to be totally explicit about the kind of binding you choose, let or let rec!
另一方面，OCaml使您能够完全明确您选择的绑定类型，让或让rec!
#3
13
I think this has nothing to do with being purely functional, it is just a design decision that in Haskell you are not allowed to do
我认为这与纯粹的功能无关，这只是一个设计决定，在Haskell中是不允许你这么做的
let a = 0;;
let a = a + 1;;
whereas you can do it in Caml.
而你可以在Caml里做。
In Haskell this code won't work because let a = a + 1 is interpreted as a recursive definition and will not terminate. In Haskell you don't have to specify that a definition is recursive simply because you can't create a non-recursive one (so the keyword rec is everywhere but is not written).
在Haskell中，这段代码不起作用，因为让a = a + 1被解释为递归定义，不会终止。在Haskell中，您不必指定一个定义是递归的，因为您不能创建一个非递归的定义(因此关键字rec无处不在，但没有写入)。
#4
8
I am not an expert, but I'll make a guess until the truly knowledgable guys show up. In OCaml there can be side effects that happen during the definition of a function:
我不是专家，但我会猜测直到真正有知识的人出现。在OCaml中，在定义一个函数时可能会产生副作用:
let rec f =
let () = Printf.printf "hello\n" in
fun x -> if x <= 0 then 12 else 1 + f (x - 1)
This means that the order of function definitions must be preserved in some sense. Now imagine that two distinct sets of mutually recursive functions are interleaved. It doesn't seem at all easy for the compiler to preserve the order while processing them as two separate mutually recursive sets of definitions.
这意味着函数定义的顺序必须在某种意义上保持不变。现在假设两个不同的相互递归函数集是交错的。编译器在将它们作为两个相互递归的定义集进行处理时，要保持顺序似乎一点都不容易。
The use of `let rec ... and`` means that distinct sets of mutually recursive function definitions can't be interleaved in OCaml as they can in Haskell. Haskell doesn't have side effects (in some sense), so definitions can be freely reordered.
“让rec……”“”意味着不同的相互递归函数定义不能像在Haskell中那样在OCaml中交叉。Haskell没有副作用(在某种意义上)，所以定义可以*地重新排序。
#5
5
It's not a question of purity, it's a question of specifying what environment the typechecker should check an expression in. It actually gives you more power than you would have otherwise. For example (I'm going to write Standard ML here because I know it better than OCaml, but I believe the typechecking process is pretty much the same for the two languages), it lets you distinguish between these cases:
这不是纯度的问题，而是指定类型检查器应该在什么环境中检查表达式的问题。实际上，它给你的能量比你想象的要多。例如(我将在这里写标准ML，因为我知道它比OCaml更好，但我相信两种语言的类型检查过程基本相同)，它可以让你区分这两种情况:
val foo : int = 5
val foo = fn (x) => if x = foo then 0 else 1
Now as of the second redefinition, foo has the type int -> int. On the other hand,
对于第二个重定义，foo的类型是int -> int，另一方面，
val foo : int = 5
val rec foo = fn (x) => if x = foo then 0 else 1
does not typecheck, because the rec means that the typechecker has already decided that foo has been rebound to the type 'a -> int, and when it tries to figure out what that 'a needs to be, there is a unification failure because x = foo forces foo to have a numeric type, which it doesn't.
不typecheck,因为矩形意味着typechecker已经决定foo已经反弹到类型”- > int,当它试图找出“需要,有一个统一的失败者,因为x = foo部队foo数值类型,它不喜欢。
It can certainly "look" more imperative, because the case without rec allows you to do things like this:
它当然可以“看起来”更有必要，因为没有rec的情况允许你做这样的事情:
val foo : int = 5
val foo = foo + 1
val foo = foo + 1
and now foo has the value 7. That's not because it's been mutated, however --- the name foo has been rebound 3 times, and it just so happens that each of those bindings shadowed a previous binding of a variable named foo. It's the same as this:
现在foo的值是7。不过，这并不是因为它发生了突变---名称foo已经反弹了3次，而且碰巧每个绑定都跟踪了一个名为foo的变量的先前绑定。这是一样的:
val foo : int = 5
val foo' = foo + 1
val foo'' = foo' + 1
except that foo and foo' are no longer available in the environment after the identifier foo has been rebound. The following are also legal:
除了foo和foo'在标识符foo被反弹后在环境中不再可用。以下也是合法的:
val foo : int = 5
val foo : real = 5.0
which makes it clearer that what's happening is shadowing of the original definition, rather than a side effect.
这就更清楚地表明，正在发生的事情是原始定义的阴影，而不是副作用。
Whether or not it's stylistically a good idea to rebind identifiers is questionable -- it can get confusing. It can be useful in some situations (e.g. rebinding a function name to a version of itself that prints debugging output).
从风格上来说，重新绑定标识符是否是个好主意值得怀疑——这会让人感到困惑。它在某些情况下是有用的(例如，将函数名重新绑定到打印调试输出的版本)。
#6
0
I'd say that in OCaml they are trying to make REPL and source files work the same way. So, it's perfectly reasonable to redefine some function in REPL; therefore, they have to allow it in the source as well. Now, if you use the (redefined) function in itself, OCaml needs some way of knowing which of the definitions to use: the previous one or the new one.
我想说，在OCaml中，他们试图让REPL和源文件以同样的方式工作。因此，在REPL中重新定义某个函数是完全合理的;因此，他们也必须允许它的来源。现在，如果您使用(重新定义的)函数本身，OCaml需要某种方式知道使用哪个定义:前一个定义还是新的定义。
In Haskell they've just gave up and accepted that REPL works differentyle from source files.
在Haskell中，他们已经放弃并接受了REPL与源文件不同的工作方式。
#1
34
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.
当您定义函数定义的语义(作为语言设计器)时，您可以选择:要么使函数的名称在它自己的主体范围内可见，要么不可见。这两种选择都是完全合法的，例如C-family语言的功能还远远不够，它们的范围内仍然有可见的定义名称(这也扩展到C中的所有定义，使这个int x = x + 1合法)。OCaml语言给了我们更多的自主选择的灵活性。这是真正伟大的。他们决定让它在默认情况下不可见，这是一个很好的下降解，因为我们写的大多数函数都是非递归的。
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:
至于引用，它实际上并不对应函数定义——rec关键字最常用的用法。它主要是关于“为什么函数定义的范围没有扩展到模块的主体”。这是一个完全不同的问题。经过一些研究，我发现了一个非常相似的问题，这个问题有一个答案，可能会让你满意，其中有一个引用:
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.
那么，既然类型检查器需要知道哪些定义集是相互递归的，那么它能做什么呢?一种可能是简单地对范围中的所有定义进行依赖分析，并将它们重新排序到最小可能的组中。Haskell实际上是这样做的，但是在像f#(和OCaml和SML)这样具有不受限制的副作用的语言中，这是一个坏主意，因为它可能也会重新排序副作用。因此，它要求用户显式地标记哪些定义是相互递归的，从而通过扩展来实现泛化。
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构造有两种用法，一种是创建一个自递归函数，比如
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).
第二种情况更难处理。当推断类型时，您需要将所有函数定义分割成由相互依赖的定义组成的集群，以便缩小类型环境。在OCaml中，它更难制作，因为你需要考虑副作用。(或者您可以继续而不将其分解为主组件，但这将导致另一个问题——您的类型系统将更加严格，例如。，将不允许更多有效的程序)。
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.
但是，再回到最初的问题和RWO的引用，我仍然确信添加rec标志没有技术上的原因。考虑一下，SML有相同的问题，但是在默认情况下仍然启用rec。有一个技术原因，让……和…定义一组相互递归函数的语法。在SML中，这种语法不需要我们在OCaml中放置rec标志，因此给了我们更大的灵活性，比如可以用let x = y和y = x表达式交换值。
#2
18
What are the technical reasons that enforces let rec while pure functional languages not?
什么技术原因促使rec而纯函数语言不允许?
Recursiveness is a strange beast. It has a relation to purity, but it's a little more oblique than this. To be clear, you could write "alterna-Haskell" which retains its purity, its laziness but does not have recursively bound lets by default and demands some kind of rec marker just as OCaml does. Some would even prefer this.
递归是一种奇怪的野兽。它和纯度有关系，但它比这个更有倾斜度。需要说明的是，您可以编写“alterna-Haskell”，它保留了它的纯粹性，它的惰性，但默认情况下没有递归绑定的let，并且需要某种rec标记，就像OCaml所做的那样。有些人甚至更喜欢这样。
In essence, there are just many different kinds of "let"s possible. If we compare let and let rec in OCaml we'll see a small difference. In static formal semantics, we might write
本质上，有很多不同的“让我们成为可能”。如果我们在OCaml中比较，我们会看到一个小的区别。在静态形式语义中，我们可以编写。
Γ ⊢ E : A Γ, x : A ⊢ F : B
-----------------------------
Γ ⊢ let x = E in F : B
which says that if we can prove in a variable environment Γ that E has type A and if we can prove in the same variable environment Γ augmented with x : A that F : B then we can prove that in the variable environment Γ let x = E in F has type B.
说,如果我们可以证明在一个变量环境ΓE a型,如果我们可以证明在同一个变量环境Γ增强x:a F:然后我们可以证明,在变量环境Γ让x = E在F B型。
The thing to watch is the Γ argument. This is just a list of ("variable name", "value") pairs like [(x, 3); (y, "hello")] and augmenting the list like Γ, x : A just means consing (x, A) on to it (sorry that the syntax is flipped).
看的是Γ参数。这只是一个(“变量名”、“值”)对的列表，如[(x, 3);(y,“你好”)],增加像Γ列表,x:就是缺点(x),(不好意思,语法是翻转)。
In particular, let's write the same formalism for let rec
特别地，让我们为rec写同样的形式
Γ, x : A ⊢ E : A Γ, x : A ⊢ F : B
-------------------------------------
Γ ⊢ let rec x = E in F : B
In particular, the only difference is that neither of our premises work in the plain Γ environment; both are allowed to assume the existence of the x variable.
特别的,唯一的区别是,无论是我们的纯Γ前提工作环境;两者都可以假设x变量的存在。
In this sense, let and let rec are simply different beasts.
从这个意义上说，让我们让rec只是不同的东西。
So what does it mean to be pure? At the strictest definition, of which Haskell doesn't even participate, we must eliminate all effects including non-termination. The only way to achieve this is to pull away our ability to write unrestricted recursion and replace it only carefully.
那么纯洁意味着什么呢?在最严格的定义中，Haskell甚至不参与其中，我们必须消除所有的影响，包括不终止。要做到这一点，唯一的方法就是去掉写无限制递归的能力，只小心地替换它。
There exist plenty of languages without recursion. Perhaps the most important one is the Simply Typed Lambda Calculus. In it's basic form it is regular lambda calculus but augmented with a typing discipline where types are bit like
有很多语言没有递归。也许最重要的一个是简单类型的微积分。在它的基本形式中，它是常规的lambda演算，但在类型有点类似的情况下，还增加了类型规则
type ty =
| Base
| Arr of ty * ty
It turns out that STLC cannot represent recursion---the Y combinator, and all other fixed-point cousin combinators, cannot be typed. Thusly, STLC is not Turing Complete.
事实证明STLC不能表示递归——Y组合子和所有其他定点表兄弟组合子都不能被输入。Thusly, STLC并不是图灵完成的。
It is however uncompromisingly pure. It achieves that purity with the bluntest of instruments, however, by completely outlawing recursion. What we'd really like is some kind of balanced, careful recursion which doesn't lead to non-termination---we'll still be Turing Incomplete, but not so crippled.
这是一种纯粹的不妥协。然而，它通过完全禁止递归的方法来达到这种纯度。我们真正想要的是某种平衡的、谨慎的递归，它不会导致不终止——我们仍然会图灵不完整，但不会如此残废。
Some languages try this game. There are clever ways of adding typed recursion back along a division between data and codata which ensures that you cannot write non-terminating functions. If you're interested, I suggest learning a bit of Coq.
有些语言尝试这个游戏。有一种巧妙的方法可以将类型化递归沿着数据和codata之间的划分进行添加，从而确保您不能编写非终止函数。如果你有兴趣的话，我建议你学一点Coq。
But OCaml's goal (and Haskell's as well) is not to be delicate here. Both languages are uncompromisingly Turing Complete (and therefore "practical"). So let's discuss some more blunt ways of augmenting the STLC with recursion.
但是OCaml的目标(以及Haskell的目标)并不是在这里显得很微妙。这两种语言都是完美无缺的(因此也是“实用的”)。让我们讨论一些更直接的方法，用递归扩展STLC。
The bluntest of the bunch is to add a single built-in function called fix
最愚蠢的做法是添加一个名为fix的内置函数
val fix : ('a -> 'a) -> 'a
or, in more genuine OCaml-y notation which requires eta-expansion
或者，在更真实的ocml -y表示法中，它要求eta-展开
val fix : (('a -> 'b) -> ('a -> 'b)) -> ('a -> 'b)
Now, remember that we're only considering a primitive STLC with fix added. We can indeed write fix (the latter one at least) in OCaml, but that's cheating at the moment. What does fix buy the STLC as a primitive?
现在，请记住，我们只考虑添加了fix的原始STLC。我们确实可以用OCaml来写fix(至少是后者)，但现在这是作弊。fix购买STLC作为一个原语是什么?
It turns out that the answer is: "everything". STLC + Fix (basically a language called PCF) is impure and Turing Complete. It's also simply tremendously difficult to use.
答案是:“一切”。STLC + Fix(基本上是一种叫做PCF的语言)是不纯的，图灵是完整的。它的使用也非常困难。
So this is the final hurdle to jump: how do we make fix easier to work with? By adding recursive bindings!
因此，这是要跨越的最后一个障碍:我们如何使修复工作变得更容易?通过添加递归绑定!
Already, STLC has a let construction. You can think of it as just syntax sugar:
STLC已经有了一个let结构。你可以把它想象成语法糖:
let x = E in F ----> (fun x -> F) (E)
but once we've added fix we also have the power to introduce let rec bindings
但是一旦我们添加了fix，我们还可以引入rec绑定
let rec x a = E in F ----> (fun x -> F) (fix (fun x a -> E))
At this point it should again be clear: let and let rec are very different beasts. They embody different levels of linguistic power and let rec is a window to allow fundamental impurity through Turing Completeness and its partner-effect non-termination.
在这一点上，应该再次明确:让rec成为完全不同的野兽。它们体现了不同层次的语言力量，让rec成为一个窗口，通过图灵完整性和它的伙伴效应不终止来允许基本的不洁净。
So, at the end of the day, it's a little amusing that Haskell, the purer of the two languages, made the interesting choice of abolishing plain let bindings. That's really the only difference: there is no syntax for representing a non-recursive binding in Haskell.
所以，在这一天结束的时候，有一点有趣的是，哈斯卡尔，这两种语言的纯粹者，做出了一个有趣的选择:废除简单的let绑定。这是唯一的区别:在Haskell中没有表示非递归绑定的语法。
At this point it's essentially just a style decision. The authors of Haskell determined that recursive bindings were so useful that one might as well assume that every binding is recursive (and mutually so, a can of worms ignored in this answer so far).
在这一点上，它本质上只是一个样式决定。Haskell的作者认为，递归绑定非常有用，因此我们不妨假设每个绑定都是递归的(到目前为止，这个答案中忽略了一罐蠕虫)。
On the other hand, OCaml gives you to ability to be totally explicit about the kind of binding you choose, let or let rec!
另一方面，OCaml使您能够完全明确您选择的绑定类型，让或让rec!
#3
13
I think this has nothing to do with being purely functional, it is just a design decision that in Haskell you are not allowed to do
我认为这与纯粹的功能无关，这只是一个设计决定，在Haskell中是不允许你这么做的
let a = 0;;
let a = a + 1;;
whereas you can do it in Caml.
而你可以在Caml里做。
In Haskell this code won't work because let a = a + 1 is interpreted as a recursive definition and will not terminate. In Haskell you don't have to specify that a definition is recursive simply because you can't create a non-recursive one (so the keyword rec is everywhere but is not written).
在Haskell中，这段代码不起作用，因为让a = a + 1被解释为递归定义，不会终止。在Haskell中，您不必指定一个定义是递归的，因为您不能创建一个非递归的定义(因此关键字rec无处不在，但没有写入)。
#4
8
I am not an expert, but I'll make a guess until the truly knowledgable guys show up. In OCaml there can be side effects that happen during the definition of a function:
我不是专家，但我会猜测直到真正有知识的人出现。在OCaml中，在定义一个函数时可能会产生副作用:
let rec f =
let () = Printf.printf "hello\n" in
fun x -> if x <= 0 then 12 else 1 + f (x - 1)
This means that the order of function definitions must be preserved in some sense. Now imagine that two distinct sets of mutually recursive functions are interleaved. It doesn't seem at all easy for the compiler to preserve the order while processing them as two separate mutually recursive sets of definitions.
这意味着函数定义的顺序必须在某种意义上保持不变。现在假设两个不同的相互递归函数集是交错的。编译器在将它们作为两个相互递归的定义集进行处理时，要保持顺序似乎一点都不容易。
The use of `let rec ... and`` means that distinct sets of mutually recursive function definitions can't be interleaved in OCaml as they can in Haskell. Haskell doesn't have side effects (in some sense), so definitions can be freely reordered.
“让rec……”“”意味着不同的相互递归函数定义不能像在Haskell中那样在OCaml中交叉。Haskell没有副作用(在某种意义上)，所以定义可以*地重新排序。
#5
5
It's not a question of purity, it's a question of specifying what environment the typechecker should check an expression in. It actually gives you more power than you would have otherwise. For example (I'm going to write Standard ML here because I know it better than OCaml, but I believe the typechecking process is pretty much the same for the two languages), it lets you distinguish between these cases:
这不是纯度的问题，而是指定类型检查器应该在什么环境中检查表达式的问题。实际上，它给你的能量比你想象的要多。例如(我将在这里写标准ML，因为我知道它比OCaml更好，但我相信两种语言的类型检查过程基本相同)，它可以让你区分这两种情况:
val foo : int = 5
val foo = fn (x) => if x = foo then 0 else 1
Now as of the second redefinition, foo has the type int -> int. On the other hand,
对于第二个重定义，foo的类型是int -> int，另一方面，
val foo : int = 5
val rec foo = fn (x) => if x = foo then 0 else 1
does not typecheck, because the rec means that the typechecker has already decided that foo has been rebound to the type 'a -> int, and when it tries to figure out what that 'a needs to be, there is a unification failure because x = foo forces foo to have a numeric type, which it doesn't.
不typecheck,因为矩形意味着typechecker已经决定foo已经反弹到类型”- > int,当它试图找出“需要,有一个统一的失败者,因为x = foo部队foo数值类型,它不喜欢。
It can certainly "look" more imperative, because the case without rec allows you to do things like this:
它当然可以“看起来”更有必要，因为没有rec的情况允许你做这样的事情:
val foo : int = 5
val foo = foo + 1
val foo = foo + 1
and now foo has the value 7. That's not because it's been mutated, however --- the name foo has been rebound 3 times, and it just so happens that each of those bindings shadowed a previous binding of a variable named foo. It's the same as this:
现在foo的值是7。不过，这并不是因为它发生了突变---名称foo已经反弹了3次，而且碰巧每个绑定都跟踪了一个名为foo的变量的先前绑定。这是一样的:
val foo : int = 5
val foo' = foo + 1
val foo'' = foo' + 1
except that foo and foo' are no longer available in the environment after the identifier foo has been rebound. The following are also legal:
除了foo和foo'在标识符foo被反弹后在环境中不再可用。以下也是合法的:
val foo : int = 5
val foo : real = 5.0
which makes it clearer that what's happening is shadowing of the original definition, rather than a side effect.
这就更清楚地表明，正在发生的事情是原始定义的阴影，而不是副作用。
Whether or not it's stylistically a good idea to rebind identifiers is questionable -- it can get confusing. It can be useful in some situations (e.g. rebinding a function name to a version of itself that prints debugging output).
从风格上来说，重新绑定标识符是否是个好主意值得怀疑——这会让人感到困惑。它在某些情况下是有用的(例如，将函数名重新绑定到打印调试输出的版本)。
#6
0
I'd say that in OCaml they are trying to make REPL and source files work the same way. So, it's perfectly reasonable to redefine some function in REPL; therefore, they have to allow it in the source as well. Now, if you use the (redefined) function in itself, OCaml needs some way of knowing which of the definitions to use: the previous one or the new one.
我想说，在OCaml中，他们试图让REPL和源文件以同样的方式工作。因此，在REPL中重新定义某个函数是完全合理的;因此，他们也必须允许它的来源。现在，如果您使用(重新定义的)函数本身，OCaml需要某种方式知道使用哪个定义:前一个定义还是新的定义。
In Haskell they've just gave up and accepted that REPL works differentyle from source files.
在Haskell中，他们已经放弃并接受了REPL与源文件不同的工作方式。