Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does ocaml need both "let" and "let rec"? [duplicate]

Possible Duplicate:
Why are functions in Ocaml/F# not recursive by default?

OCaml uses let to define a new function, or let rec to define a function that is recursive. Why does it need both of these - couldn't we just use let for everything?

For example, to define a non-recursive successor function and recursive factorial in OCaml (actually, in the OCaml interpreter) I might write

let succ n = n + 1;;  let rec fact n =     if n = 0 then 1 else n * fact (n-1);; 

Whereas in Haskell (GHCI) I can write

let succ n = n + 1  let fact n =     if n == 0 then 1 else n * fact (n-1) 

Why does OCaml distinguish between let and let rec? Is it a performance issue, or something more subtle?

like image 499
Chris Taylor Avatar asked Feb 17 '12 09:02

Chris Taylor


People also ask

What is let REC in OCaml?

OCaml uses let to define a new function, or let rec to define a function that is recursive. Why does it need both of these - couldn't we just use let for everything?

How does let work in OCaml?

The value of a let definition is the value of it's body (i.e. expr2). You can therefore use a let anywhere OCaml is expecting an expression. This is because a let definition is like a syntactially fancy operator that takes three operands (name, expr1 and expr2) and has a lower precedence than the arithmetic operators.

Does OCaml have for loops?

The strange use of recursion in this function is almost certainly for efficiency. OCaml supports for loops, so why didn't the authors use for loops?


1 Answers

Well, having both available instead of only one gives the programmer tighter control on the scope. With let x = e1 in e2, the binding is only present in e2's environment, while with let rec x = e1 in e2 the binding is present in both e1 and e2's environments.

(Edit: I want to emphasize that it is not a performance issue, that makes no difference at all.)

Here are two situations where having this non-recursive binding is useful:

  • shadowing an existing definition with a refinement that use the old binding. Something like: let f x = (let x = sanitize x in ...), where sanitize is a function that ensures the input has some desirable property (eg. it takes the norm of a possibly-non-normalized vector, etc.). This is very useful in some cases.

  • metaprogramming, for example macro writing. Imagine I want to define a macro SQUARE(foo) that desugars into let x = foo in x * x, for any expression foo. I need this binding to avoid code duplication in the output (I don't want SQUARE(factorial n) to compute factorial n twice). This is only hygienic if the let binding is not recursive, otherwise I couldn't write let x = 2 in SQUARE(x) and get a correct result.

So I claim it is very important indeed to have both the recursive and the non-recursive binding available. Now, the default behaviour of the let-binding is a matter of convention. You could say that let x = ... is recursive, and one must use let nonrec x = ... to get the non-recursive binder. Picking one default or the other is a matter of which programming style you want to favor and there are good reasons to make either choice. Haskell suffers¹ from the unavailability of this non-recursive mode, and OCaml has exactly the same defect at the type level : type foo = ... is recursive, and there is no non-recursive option available -- see this blog post.

¹: when Google Code Search was available, I used it to search in Haskell code for the pattern let x' = sanitize x in .... This is the usual workaround when non-recursive binding is not available, but it's less safe because you risk writing x instead of x' by mistake later on -- in some cases you want to have both available, so picking a different name can be voluntary. A good idiom would be to use a longer variable name for the first x, such as unsanitized_x. Anyway, just looking for x' literally (no other variable name) and x1 turned a lot of results. Erlang (and all language that try to make variable shadowing difficult: Coffeescript, etc.) has even worse problems of this kind.

That said, the choice of having Haskell bindings recursive by default (rather than non-recursive) certainly makes sense, as it is consistent with lazy evaluation by default, which makes it really easy to build recursive values -- while strict-by-default languages have more restrictions on which recursive definitions make sense.

like image 80
gasche Avatar answered Sep 22 '22 06:09

gasche