How to do this length≤1 more than once?

问题:

I've spent a day reading page 166's length≤1 in the book The Little Schemer; there's the following code:

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
   (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 
           ((mk-length eternity)
            (cdr l))))))))
 l)

where l is (apples) and eternity is as follows:

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

Page 166 (4th ed.) states that:

When we apply mk-length once, we get length≤1

And then

Could we do this more than once?

But I do not know how to do this for getting length≤2?

回答1:

Suppose l is (apples oranges), then it will evaluate like this (note that mk-length is bound to the the (lambda (mk-length) ...) function itself:

(cond ((null? l) 0) 
      (else (add1 ((mk-length eternity) (cdr l)))))
==>
(add1 ((mk-length eternity) '(oranges)))
==>
(add1 ((lambda (l) (cond ((null? l) 0
                          (else (add1 ((eternity eternity) (cdr l))))))))
==>
(add1 (add1 ((eternity eternity) '())))

So here, after two steps, eternity ends up being applied, but what we want is for it to call mk-length. So in the original function, if we replace eternity by mk-length, then the last step I wrote will contain (mk-length mk-length) instead of (eternity eternity), allowing the computation to proceed.