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?

Remindful

"len" is not a recursion because it is a parameter to a lambda expression. Its value can be anything. Here it is eternity. Also notice, the first expression is not a definition. When the first expression is evaluated, eternity is still not defined. – Stratification

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.

Dishtowel

Answer 2

Like you say, this is a definition of a length function as a partial function where it only completes for the empty list. But this hasn't gotten to the y-combinator part yet, it isn't an example of an anonymous function calling itself.

l is a list of atoms, it is the argument to the function returned when (lambda (len) ...) is evaluated.

len is a function passed into the outer lambda as an argument.

The outer expression creates a lambda with eternity passed in as its argument. The outer lambda returns a function created by evaluating the inner lambda, the returned function is the thing that takes eternity as an argument.

If the code is passed an empty list (meaning wrap the whole first part followed by a '() in another set of parens) then it will evaluate to 0, of course. len never gets evaluated.

If the code is passed a nonempty lat then it will try to evaluate the len argument and you get an infinite recursion.

Monogram