116

Why is it that functions in F# and OCaml (and possibly other languages) are not by default recursive?

In other words, why did the language designers decide it was a good idea to explicitly make you type rec in a declaration like:

let rec foo ... = ...

and not give the function recursive capability by default? Why the need for an explicit rec construct?

1

6 Answers 6

94

The French and British descendants of the original ML made different choices and their choices have been inherited through the decades to the modern variants. So this is just legacy but it does affect idioms in these languages.

Functions are not recursive by default in the French CAML family of languages (including OCaml). This choice makes it easy to supercede function (and variable) definitions using let in those languages because you can refer to the previous definition inside the body of a new definition. F# inherited this syntax from OCaml.

For example, superceding the function p when computing the Shannon entropy of a sequence in 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

Note how the argument p to the higher-order shannon function is superceded by another p in the first line of the body and then another p in the second line of the body.

Conversely, the British SML branch of the ML family of languages took the other choice and SML's fun-bound functions are recursive by default. When most function definitions do not need access to previous bindings of their function name, this results in simpler code. However, superceded functions are made to use different names (f1, f2 etc.) which pollutes the scope and makes it possible to accidentally invoke the wrong "version" of a function. And there is now a discrepancy between implicitly-recursive fun-bound functions and non-recursive val-bound functions.

Haskell makes it possible to infer the dependencies between definitions by restricting them to be pure. This makes toy samples look simpler but comes at a grave cost elsewhere.

Note that the answers given by Ganesh and Eddie are red herrings. They explained why groups of functions cannot be placed inside a giant let rec ... and ... because it affects when type variables get generalized. This has nothing to do with rec being default in SML but not OCaml.

5
  • 3
    I don't think they are red herrings: if it wasn't for the restrictions on inference, it's likely that entire programs or modules would be automatically treated as mutually recursive like most other languages do. That would make the specific design decision of whether or not "rec" should be required moot. Dec 13, 2009 at 10:57
  • "...automatically treated as mutually recursive like most other languages do". BASIC, C, C++, Clojure, Erlang, F#, Factor, Forth, Fortran, Groovy, OCaml, Pascal, Smalltalk and Standard ML don't.
    – J D
    Mar 9, 2011 at 9:52
  • 3
    C/C++ only require prototypes for forward definitions, which isn't really about marking recursion explicitly. Java, C# and Perl certainly do have implicit recursion. We could get into an endless debate about the meaning of "most" and the importance of each language, so let's just settle for "very many" other languages. Apr 13, 2011 at 19:43
  • 3
    "C/C++ only require prototypes for forward definitions, which isn't really about marking recursion explicitly". Only in the special case of self-recursion. In the general case of mutual recursion, forward declarations are mandatory in both C and C++.
    – J D
    Feb 17, 2012 at 12:22
  • 3
    Actually forward declarations are not required in C++ in class scopes, i.e. static methods are fine to call each other without any declarations. Nov 25, 2019 at 0:54
55

One crucial reason for the explicit use of rec is to do with Hindley-Milner type inference, which underlies all staticly typed functional programming languages (albeit changed and extended in various ways).

If you have a definition let f x = x, you'd expect it to have type 'a -> 'a and to be applicable on different 'a types at different points. But equally, if you write let g x = (x + 1) + ..., you'd expect x to be treated as an int in the rest of the body of g.

The way that Hindley-Milner inference deals with this distinction is through an explicit generalisation step. At certain points when processing your program, the type system stops and says "ok, the types of these definitions will be generalised at this point, so that when someone uses them, any free type variables in their type will be freshly instantiated, and thus won't interfere with any other uses of this definition."

It turns out that the sensible place to do this generalisation is after checking a mutually recursive set of functions. Any earlier, and you'll generalise too much, leading to situations where types could actually collide. Any later, and you'll generalise too little, making definitions that can't be used with multiple type instantiations.

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 generalisation should occur.

8
  • 3
    Err, no. Your first paragraph is wrong (you're talking about the explicit use of "and" and not "rec") and, consequently, the rest is irrelevant.
    – J D
    Dec 11, 2009 at 22:57
  • 5
    I was never pleased with this requirement. Thanks for the explanation. Another reason why Haskell is superior in design. Mar 19, 2010 at 4:30
  • 9
    NO!!!! HOW COULD THIS HAPPEN?! This answer is plain wrong! Please read Harrop's answer below or check out The Definition of Standard ML (Milner, Tofte, Harper, MacQueen -- 1997)[p.24] Mar 12, 2011 at 13:37
  • 9
    As I said in my answer, the type inference issue is one of the reasons for the need for rec, as opposed to being the only reason. Jon's answer is also a very valid answer (apart from the usual snide comment about Haskell); I don't think the two are in opposition. Apr 13, 2011 at 19:46
  • 17
    "the type inference issue is one of the reasons for the need for rec". The fact that OCaml requires rec but SML does not is an obvious counter example. If type inference were the issue for the reasons you describe, OCaml and SML could not have chosen different solutions as they did. The reason is, of course, that you are talking about and in order to make Haskell relevant.
    – J D
    Feb 17, 2012 at 12:27
11

There are two key reasons this is a good idea:

First, if you enable recursive definitions then you can't refer to a previous binding of a value of the same name. This is often a useful idiom when you are doing something like extending an existing module.

Second, recursive values, and especially sets of mutually recursive values, are much harder to reason about then are definitions that proceed in order, each new definition building on top of what has been already defined. It is nice when reading such code to have the guarantee that, except for definitions explicitly marked as recursive, new definitions can only refer to previous definitions.

5

Some guesses:

  • let is not only used to bind functions, but also other regular values. Most forms of values are not allowed to be recursive. Certain forms of recursive values are allowed (e.g. functions, lazy expressions, etc.), so it needs an explicit syntax to indicate this.
  • It might be easier to optimize non-recursive functions
  • The closure created when you create a recursive function needs to include an entry that points to the function itself (so the function can recursively call itself), which makes recursive closures more complicated than non-recursive closures. So it might be nice to be able to create simpler non-recursive closures when you don't need recursion
  • It allows you to define a function in terms of a previously-defined function or value of the same name; although I think this is bad practice
  • Extra safety? Makes sure that you are doing what you intended. e.g. If you don't intend it to be recursive but you accidentally used a name inside the function with the same name as the function itself, it will most likely complain (unless the name has been defined before)
  • The let construct is similar to the let construct in Lisp and Scheme; which are non-recursive. There is a separate letrec construct in Scheme for recursive let's
1
  • "Most forms of values are not allowed to be recursive. Certain forms of recursive values are allowed (e.g. functions, lazy expressions, etc.), so it needs an explicit syntax to indicate this". That is true for F# but I'm not sure how true it is for OCaml where you can do let rec xs = 0::ys and ys = 1::xs.
    – J D
    Apr 20, 2020 at 16:10
4

Given this:

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

Compare:

let f a = f (g a)

With this:

let rec f a = f (g a)

The former redefines f to apply the previously defined f to the result of applying g to a. The latter redefines f to loop forever applying g to a, which is usually not what you want in ML variants.

That said, it's a language designer style thing. Just go with it.

1

A big part of it is that it gives the programmer more control over the complexity of their local scopes. The spectrum of let, let* and let rec offer an increasing level of both power and cost. let* and let rec are in essence nested versions of the simple let, so using either one is more expensive. This grading allows you to micromanage the optimization of your program as you can choose which level of let you need for the task at hand. If you don't need recursion or the ability to refer to previous bindings, then you can fall back on a simple let to save a bit of performance.

It's similar to the graded equality predicates in Scheme. (i.e. eq?, eqv? and equal?)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.