The mechanism of anonymous function to call itself in Scheme?

Question

I'm reading The Little Schemer and feel confused about the following code:

((lambda (len)
   (lambda (l)
      (cond
         ((null? l) 0)
         (else 
            (+ 1 (len (cdr l)))))))
   eternity)

(define eternity
    (lambda (x)
         (eternity x)))

The code is to determine the empty list, otherwise it never stops.

Why is the "len" not recursion?

Answer 1

Although it can be dangerous to apply textual substitution to Lisp forms (since there are dangers of multiple evaluation, etc.), in this case it may help to look at this form and see how it fits together:

((lambda (len) 
   (lambda (l)
     ...))
 eternity)

is an application, i.e., a function call. The function getting called takes one argument, called len, and returns another function that takes a single argument l. The function getting called is called with eternity. When the call completes, the result is this function:

(lambda (l)
  (cond
    ((null? l) 0)
    (else (+ 1 (eternity (cdr l))))))

Now, this function takes a list l and if it's empty, returns 0. Otherwise, it computes (cdr l) (the rest of the list), and calls eternity with that value. When that returns, 1 is added to the result, and that's the return value of the whole function. The problem, of course, is that eternity

(define eternity
  (lambda (x)
    (eternity x)))

which could also be written as

(define (eternity x)
  (eternity x))

simply takes an argument x, and then calls eternity with x. That's an infinite loop. In the above, I wrote "When that returns", but in fact, (eternity (cdr l)) never returns. So,

((lambda (len)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (+ 1 (len (cdr l)))))))
 eternity)

is a function call that returns a function (lambda (l) …) that returns 0 if called with an empty list, and goes into an infinite loop with a non-empty list.

From a program analysis side of things, it's worth noting that there are other values for which this won't go into an infinite loop. For instance, if you call it with a string, then (cdr l) will be an error.