Example where letrec/letrec* is better than let with internal defines or named let ?

Question

The two examples Kent Dybvig gives in The Scheme Programming Language for letrec and letrec* are:

(letrec ([sum (lambda (x)
             (if (zero? x)
                 0
                 (+ x (sum (- x 1)))))])
   (sum 5))

and

(letrec* ([sum (lambda (x)
            (if (zero? x)
                    0
                (+ x (sum (- x 1)))))]
         [f (lambda () (cons n n-sum))]
         [n 15]
         [n-sum (sum n)])
  (f))

The first can also be written as a named let:

(let sum ([x 5]) 
  ((lambda (x)
                 (if (zero? x)
                     0
                     (+ x (sum (- x 1))))) x))

and the second can be written as a let with internal defines:

(let ()
  (define sum  (lambda (x)
               (if (zero? x)
               0 
                   (+ x (sum (- x 1))))))
  (define f (lambda () (cons n n-sum)))
  (define n 15)
  (define n-sum (sum n))
  (f))

The letrec/letrec* forms don't seem any more concise or clearer than the named let or let with internal defines forms.

Can someone show me an example where letrec/letrec* does improve the code or is necessary instead of named let or let with internal defines.

score 7 · Accepted Answer · answered Dec 29 '11 at 02:01

Yes, the first example can be rewritten using a named let, but note that there is no need for the lambda form in there:

(let sum ([x 5])
  (if (zero? x)
    0
    (+ x (sum (- x 1)))))

This kind of transformation is a bit misleading -- it is fine to do in case you're defining a single "looping function" (in the broad not-only-tail-recursive sense) and immediately use it on a known input. But usually, when you see examples such as the one you gave, the intention is to show the definition and use of a local function, so it's possible to do this transformation only because it's a for-demonstration toy example.

Secondly, note that a named let is usually not a primitive form -- the implementation strategy that practically all Scheme implementations use is to have that form expand into a letrec. It is therefore still a good idea to understand letrec if you want to understand named-lets. (And this is a fundamental feature: being able to do self-reference via a recursive scope.)

Finally, the example that you gave with internal definitions is similar to named-lets: it is a syntactic sugar that expands into a letrec (which can be either a proper letrec or a letrec* with R5RS, and required to be a letrec* in R6RS). So in order to understand how it works, you need to understand letrec. Note also that some implementation that use strict letrec would also barf at your second example, and complain that sum is undefined. It is this syntactic sugaring that is behind the main argument for the letrec* semantics that was adopted in R6RS: many people like using internal definitions, but then there is a problem that toplevel definitions allow using previous definitions but internal definitions are less convenient in an unexpected way. With letrec*, internal definitions work like toplevel ones. (More precisely, they work like toplevel barring re-definitions, which means that they're actually like module-toplevel definitions.)

(Note also that (a) both Racket and Chez extend internal bodies to allow definitions and expressions to be mixed which means that the expansion is as straightforward.)

Are you ever fast Eli :-) And thank you for your amazingly clear explanations. — Harry Spier, Dec 29 '11 at 02:04
One more question Eli. You said that named let is not a primitive form but is usually implemented as a letrec. Is letrec usually a primitive form or is it us usually implemented as a let with set!'s? Similarly is let a primitive form or is it usually implemented as a lambda. Thanks. — Harry Spier, Dec 30 '11 at 00:43
@HarrySpier: `letrec` is usually primitive, though it often does something similar to a `let` and `set!`s. (It's something that almost never matters, but can be exposed using continuations.) As for `let` I think that there's much less agreement, with some implementations using `lambda` as the expansion and some treating it as primitive. — Eli Barzilay, Dec 30 '11 at 07:52

score 2 · Answer 2 · answered Dec 30 '11 at 21:52

I second Eli's answer; named let and internal define are defined in terms of letrec.

I will add some empirical, numerical anecdata to this, though. I work at a company that uses Scheme. We have 981 Scheme code files, that sum up to a grand total of 206,878 lines (counting comments, blank lines, the whole thing). This was written by a team that ranged between 8-16 people over some 8 years.

So, how many uses of letrec are in that codebase? 16. This is compared to about an estimated 7,000 uses of let and let* (estimated because I'm not gonna bother to refine the regexp I used). It also looks like all of the letrec uses were written by the same guy.

So, I'm not going to be surprised that you won't find much practical use for letrec.

This may just be a testament to the well-designed libraries you're using. All your invocations of `letrec` are really taking place under the guise of `map` and so on. — dubiousjim, Nov 04 '12 at 12:55

score 2 · Answer 3 · edited May 23 '17 at 10:27

From some of Kent's students, I have learned the following: letrec is implemented in terms of let using macro expansion. It expands the letrec into a let that uses set! inside. So your first example would expand to this:

(let
  ([sum (void)])
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (sum 5))

Your second, similarly (note that the nested lets are a result of the let* - also, this may not be a completely correct expansion, but is my best guess):

(let
  ([sum (void)] 
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (let
    [f (void)] 
    (set! f (lambda () (cons n n-sum)))
    (let 
      [n (void)]
      (set! n 15)
      (let
        [n-sum (void)])
        (set! n-sum (sum n))
        (f))

I am not 600% sure how the named let expands, but Eli suggests that it would be implemented in terms of letrec itself (which makes sense and should be pretty obvious). So your named let moves from a named let into a letrec into an unnamed let. And your rewrite of the second looks almost exactly like the expansion of it anyway.

If you are interpreting it and looking for good performance, I would lean toward the letrec because it is one shorter macro-expand step. Also, let gets turned into a lambda so you're using defines in your second example instead of set!s (which may be heavier).

Of course, if you're compiling, it will probably all fall out in the compiler anyway so just use whichever you think looks nicer (I'm partial to letrec because let loops remind me of imperative programming but ymmv). That said, it should be up to you, stylistically (since they are more or less equivalent).

That said, let me provide you an example that you may find worthwhile:

(letrec
 ([even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))]
  [odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))])
  (even? 88))

Using your internal define style will yield:

(let ()
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

So here the letrec code is actually shorter. And, honestly, if you're doing to do something like the latter, why not settle for begin?

(begin
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

I suspect that begin is more of a built-in and, as such, will not get macro-expanded (like let will). Finally, a similar issue has been raised on the Lisp stack overflow a bit ago with more or less the same point.

Example where letrec/letrec* is better than let with internal defines or named let ?

3 Answers3