Non-mutually Recursive `let ... and` Expressions

I’ve read that mutually recursive functions can be expensive to use (I think in terms of type checking??). Is there any difference between using let ... and for multiple non-mutually recursive let expressions vs multiple let expressions? The only purpose this serves is I like the look of it better.

For example,

let x = [1; 2; 3] in
let y = [] in
x @ y

vs

let x = [1, 2, 3] 
and y = [] in
x @ y

The main difference is that in

let x = [1; 2; 3] in
let y = [] in
x @ y

the variable x could be used in the definition of y, e.g., you can write let y = [x], while in the latter example, y is defined in parallel with x.

The latter style (with and) lets you state explicitly that the computation of y doesn’t depend on x, which is always good. Concerning the compiler, it can potentially type parallel bindings faster, but type-checking is so fast in OCaml so you wan’t notice any difference unless you have thousands of nested lets (e.g., when your code is generated).

Concerning the mutually recursive case, it is again not because the type-checking is expensive. OCaml can easily cope with more mutually recursive functions than a mere human can write. We can imagine, that mutually recursive functions can prevent some compiler optimizations, like inlining, but this is natural. Of course, using rec in cases when it is not needed is a bad idea, as you can accidentally make non-recursive call recursive and in general increase confusion for someone who will read your code. That’s why there is a special warning for a non-recursive definition that is marked as recursive.

The only complexity of mutually recursive definitions is that the typing scope is extended to all bindings that compise the definition. So when you change something in one definition, the error may pop up miles away in a completely different definition. In other words, the larger the scope the harder it is to reason, at least for a human. It is not a problem for the compiler though.

Actually (cough), there is another difference: generalization is done outside of the let-group.

What it means concretely is that this is not accepted:

let rec f x = x 
and g () = f 2 
and h () = f "plop"
# Error: This expression has type string but an expression was expected of type
         int

Because f is used with integers and strings, but it isn’t polymorphic yet. It will only be made polymorphic when we exit the let-group. It can appear in real code when you write a generic functions that walks over an AST, but must be used in several specialized contexts. The solution is to either avoid using let rec when unnecessary or to annotate the type:

let rec f : 'a . 'a -> 'a = fun x -> x 
and g () = f 2 
and h () = f "plop"
3 Likes

That is what I mean by the scope of a recursive let definition. Here we have a type variable quantified in the prenex position of the recursive let definition. Not on the scope of f, or g, or h, as although they look like let definitions by themselves, they are not, there is only one (recursive definition let rec f = .. and g = ... and h = ... and all variables are quantified over this definition.

Thank you both for the great responses! I’ll definitely only use let...and when necessary :grin:

no, you should use let ... and when possible and let rec ... and when necessary :slight_smile:

Note that let name1 = f1 () and name2 = f2 () in ... makes debugging gratuitously harder since the evaluation order of f1 () and f2 () is unspecified.

3 Likes

That’s a good point, yep. And yet another reason not to write code that has side-effects :slight_smile:

Just to be clear, the whole point is to track what happens in the program by inserting printfs. Printing material in the order expected by the programmer is a highly desirable property.