Scheme: 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 lat)
  (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 lat)
  (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!

Answer 1

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.

Answer 2

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.

Answer 3

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))