What are the merits of letrec as a programming language feature

Question

I've looked at everything I can find about letrec, and I still don't understand what it brings to a language as a feature. It seems like everything expressible with letrec could just as easily be written as a recursive function. But are there any reasons to expose letrec as a feature of a programming language, if the language already supports recursive functions? Why do several languages expose both?

I get that letrec might be used to implement other features including recursive functions, but that's not relevant to why it should itself be a feature. I've also read that some people find it more readable than recursive functions in some lisps, but again this is not relevant, because the designer of the language can make an effort to make recursive functions readable enough to not need another feature. Finally, I've been told that letrec makes it possible to express some kinds of recursive values more succinctly, but I have yet to find a motivating example.

Answer 1

NB: Although this is not a Scheme specific problem I'm using Scheme to demonstrate the differences. Hope you can read a little lisp code

A letrec is just a special let where the bindings themselves are defined before the expressions that represent their values are evaluated. Imagine this:

(define (fib n)
  (let ((fib (lambda (n a b) 
               (if (zero? n) 
                   a 
                   (fib (- n 1) b (+ a b))))))
    (fib n))

This code fails since while fib does exist in the body of the let it does exist in the closure it defines since the binding didn't exist when the lambda was evaluated. To fix this letrec comes to the rescue:

(define (fib n)
  (letrec ((fib (lambda (n a b) 
                  (if (zero? n) 
                      a 
                      (fib (- n 1) b (+ a b))))))
    (fib n))

That letrec is just syntax that does something like this:

(define (fib n)
  (let ((fib 'undefined))
    (let ((tmp (lambda (n a b) 
                 (if (zero? n) 
                     a 
                     (fib (- n 1) b (+ a b))))))
      (set! fib tmp))
    (fib n)))

So here you clearly see fib exists when the lambda gets evaluated and the binding is later set to the closure itself. The binding is the same, only it's pointer has changed. It's circular reference 101..

So what happens when you make a global function? Clearly if it is to recurse it needs to exist before the lambda is evaluated or the environment has to be mutated. It needs to fix the same problem here too.

In a functional language implementation where mutation is not ok you can solve this problem with a Y (or Z) combinator.

If you are interested in how languages are implemented I suggest you start at Matt Mights articles.

Answer 2

TL;DR: define is letrec. This is what enables us to write recursive defintions in the first place.

Consider

let fact = fun (n => (n==0 -> 1 ; n * fact (n-1)))

To what entity does the name fact inside the body of this definiton refer? With let foo = val, val is defined in terms of already known entities, so it can't refer to foo which is not defined yet. In terms of scope this can be said (and usually is) that the RHS of the let equation is defined in the outer scope.

The only way for the inner fact to actually point at the one being defined, is to use letrec, where the entity being defined is allowed to refer to the scope in which it is being defined. So while causing evaluation of an entity while its definition is in progress is an error, storing a reference to its (future, at this point in time) value is fine -- in the case of using letrec that is.

The define you refer to, is just letrec under another name. In Scheme as well.

Without the ability of an entity being defined to refer to itself, i.e. in languages with non-recursive let, to have recursion one has to resort to the use of arcane devices such as the y-combinator. Which is cumbersome and usually inefficient. Another way is the definitions like

let fact = (fun (f => f f)) (fun (r => n => (n==0 -> 1 ; n * r r (n-1))))

So letrec brings to the table the efficiency of implementation, and convenience for a programmer.

The quesion then becomes, why expose the non-recursive let? Haskell indeed does not. Scheme has both letrec and let. One reason might be for completeness. Another might be a simpler implementation for let, with less self-referential run-time structures in memory making it easier on the garbage collector.

You ask for a motivational example. Consider defining Fibonacci numbers as a self-referential lazy list:

letrec fibs = {0} + {1} + add fibs (tail fibs) 

With non-recursive let another copy of the list fibs will be defined, to be used as the input to the element-wise addition function add. Which will cause the definition of another copy of fibs for this one to be defined in its terms. And so on; accessing the nth Fibonacci number will cause a chain of n-1 lists to be created and maintained at run-time! Not a pretty picture.

And that's assuming the same fibs was used for tail fibs as well. If not, all bets are off.

What is needed is that fibs uses itself, refers to itself, so only one copy of the list is maintained.