What are the benefits of letrec?

Question

While reading "The Seasoned Schemer" I've begun to learn about letrec. I understand what it does (can be duplicated with a Y-Combinator) but the book is using it in lieu of recurring on the already defined function operating on arguments that remain static.

An example of an old function using the defined function recurring on itself (nothing special):

(define (substitute new old l)
  (cond
    ((null? l) '())
    ((eq? (car l) old)
      (cons new (substitute new old (cdr l))))
    (else
      (cons (car l) (substitute new old (cdr l))))))

Now for an example of that same function but using letrec:

(define (substitute new old l)
  (letrec
    ((replace
      (lambda (l)
        (cond
          ((null? l) '())
          ((eq? (car l) old)
           (cons new (replace (cdr l))))
          (else
           (cons (car l) (replace (cdr l))))))))
(replace lat)))

Aside from being slightly longer and more difficult to read I don't know why they are rewriting functions in the book to use letrec. Is there a speed enhancement when recurring over a static variable this way because you don't keep passing it??

Is this standard practice for functions with arguments that remain static but one argument that is reduced (such as recurring down the elements of a list)?

Some input from more experienced Schemers/LISPers would help!

Austin

Answer 1

So you have a few answers that cover the readability issue, which should be fine. But one question that is unclear is whether there are any performance issues. On a shallow look, it seems that the letrec version, like the named-let one (which is really the same) should be faster since there are less arguments to pass around in the loop. However, in practice compilers can do all kinds of optimizations behind your back, like figure out that the loop in the plain version passes the first two arguments unchanged, and turn it into a single-argument loop with the first one. Instead of showing you the numbers on a particular system, here is a PLT module that you can run to time four different versions, and you can easily add more to try out other variations. The short summary is that on my machine, the named-let version is slightly faster, and making it tail-recursive has a larger overall benefit.

#lang scheme

;; original version
(define (substitute1 new old l)
  (cond [(null? l) '()]
        [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))]
        [else (cons (car l) (substitute1 new old (cdr l)))]))

;; letrec version (implicitly through a named-let)
(define (substitute2 new old l)
  (let loop ([l l])
    (cond [(null? l) '()]
          [(eq? (car l) old) (cons new (loop (cdr l)))]
          [else (cons (car l) (loop (cdr l)))])))

;; making the code a little more compact
(define (substitute3 new old l)
  (let loop ([l l])
    (if (null? l)
      '()
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst))
            (loop (cdr l))))))

;; a tail recursive version
(define (substitute4 new old l)
  (let loop ([l l] [r '()])
    (if (null? l)
      (reverse r)
      (loop (cdr l)
            (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r)))))

;; tests and timings

(define (rand-list n)
  (if (zero? n) '() (cons (random 10) (rand-list (sub1 n)))))

(for ([i (in-range 5)])
  (define l   (rand-list 10000000))
  (define new (random 10))
  (define old (random 10))
  (define-syntax-rule (run fun)
    (begin (printf "~a: " 'fun)
           (collect-garbage)
           (time (fun new old l))))
  ;; don't time the first one, since it allocates a new list to use later
  (define new-list (substitute1 new old l))
  (unless (and (equal? (run substitute1) new-list)
               (equal? (run substitute2) new-list)
               (equal? (run substitute3) new-list)
               (equal? (run substitute4) new-list))
    (error "poof"))
  (newline))

Accumbent

As usual, well written and very helpful (thank you for mentioning the timing module). I know I'm getting a lot of your help for free, so, thank you Eli for taking the time that you do to post your answers. Your comment discussions with the other posters is also helpful in the little things that I don't know or haven't chanced upon. Thanks again! – Austin

Answer 2

Regarding you specific example: Personally I find the letrec version easier to read: you define a recursive helper function and you call it in the body of the top-level function. The main difference between the two forms is that in the letrec form you don't have to specify the static arguments over and over again in the recursive calls, which I find to be cleaner.

If the code is compiled, avoiding the passing of the static arguments on each recursive function call will probably also provide a small performance benefit in this case since the caller avoids having to copy the arguments into the new stack frame. If the recursive function call was in the tail position, the compiler might be clever enough to avoid copying the arguments on the stack over and over again.

Similarly if the code is interpreted, having fewer arguments in the recursive calls will be faster.

More generally, one of the main benefits of letrec, which I don't think you mentioned above, is the fact that it allows for mutually recursive function definitions. I'm quite inexperienced with scheme, but as far as I understand, this is one of the main features of the letrec form compared to e.g. define.

Impersonality

To expand on this answer -- it doesn't look immediately more readable if you're hung up on the extra veriage. For that, expressing the loop as a named let will be lighter. But one thing that makes it more readable is that it's clear that the loop happens on just one variable, and that's a benefit (for performance too). – Accumbent

@Eli: Oh, so it does have a performance impact? That's interesting to know. Would a named let be different in this respect? – Afield

This is a good answer, and the comments are good too; the quality of the answers coming from you guys is good, I'm learning a lot. Thank you! – Austin

Answer 3

For one thing, the letrec version allows you to use the function even if its global name is reset to something else, e.g.

(define substitute
  ; stuff involving letrec
  )

(define sub substitute)
(set! substitute #f)

Then sub will still work, whereas it wouldn't with the non-letrec version.

As for performance and readability, the latter is probably a matter of taste, while the former should not differ observably (though I am not really qualified to insist on this being so, and also it's implementation-dependent anyway).

Also, I'd actually use named let personally:

(define (substitute new old lat) ; edit: fixed this line
  (let loop (
             ; whatever iteration variables are needed + initial values
            )
    ; whatever it is that substitute should do at each iteration
    ))

I find it more readable this way. YMMV.

Urticaceous

+1 for named let. Makes more sense in this case and similar. Although letrec lets you define multiple mutually recursive functions. So when you need to do that, you need a letrec. – Margitmargo

The set! point is moot with PLT Scheme -- once you define a function inside your own module, and you never set! the name in this module, no one else can ever change it. The same holds for all Schemes with an R6RS or similar module system -- the "trick" that you're referring too is an old R5RS-ism. – Accumbent

@Eli: True, but since the OP is reading "The Seasoned Schemer", the modern Schemes' approach may not be relevant to his experience. :-) – Afield

Michal: knowing the authors personally, I would be very surprised if it has any such set! tricks... Besides, if/when they're mentioned, they should always come with a big disclaimer saying that this is something that should not be relevant these days. – Accumbent

@Eli: Point taken... Also, bringing attention to the fact that set! is often not available for top level variables nowadays is important, so thanks for the comment. Still, e.g. "The Programming Language Scheme" still includes set! s to top level (see the calc example slightly above Exercise 3.5.1 in the current web text) and I think it would be worthwhile to become accustomed to them (and the associated quirks) just to read that cool book. :-) – Afield