2

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?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
abelard2008
  • 1,984
  • 1
  • 20
  • 35
  • I think [this answer](https://stackoverflow.com/a/48323411/849891) of mine answers this question, for `length≤2` specifically (i.e. only 2, not more). – Will Ness Jan 20 '18 at 11:29

1 Answers1

3

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.

hzap
  • 1,103
  • 7
  • 9