Little Schemer: length0 and mk-length

Question

The little schemer gives the following on page 165 as still the function length₀. But how does this work? It looks like the length lambda is being passed to the mk-length lambda, which evaluates the length lambda with the length lambda itself passed as an argument. So then, when (length (cdr l)) at the bottom is evaluated length is just the length lambda itself. But the length lambda takes two parameters curried: length and l. So how can (length (cdr l)) make sense then?

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

Baca

correct; it doesn't. it returns the (lambda (l) ...) to add1 and thus causes an error; and that's why it's length_0: it only works for empty lists. And the name length is wrong too, it should really be called mk-length -- as it is, in the right half of that frame. – Rowdyism

Answer 1

The Little Schemer is building up a function that will work for lists of greater and greater lengths. Part of the point of length_≤0 is that it only works for lists whose length is less than or equal to zero (and since there are no lists of negative length, this means lists of length zero). The code that you've shown intentionally only works for lists of length zero. In fact, this is even pointed out in the text on page 165:

A: What if we could create another application of mk-length to eternity at this point?
B: That would only postpone the problem to one, and besides, how could we do that?
A: Well, since nobody cares what function we pass to mk-length we could pass it mk-length initially.
B: That's the right idea. And then we invoke mk-length on eternity and the result of this on the cdr so that we get one more piece of the tower.
A: Then this is still length₀

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

B: Yes, we could even use mk-length instead of length:

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

A: Why would we want to do that?
B: All names are equal, but some names more equal than others.
A: True: as long as we use the names consistently, we are just fine.
B: And mk-length is a far more equal name than length. If we use a name like mk-length, it is a constant reminder that the first argument to mk-length is mk-length.

On page 166, the authors show a version that works for lists of length 0 or 1 (i.e., ≤1). Finally, on page 167, they get to a version that works on lists of any length. How that works is described in more detail in another question:

• Y combinator discussion in "The Little Schemer"

You might also find the following questions of interest:

• how to do this length<=1 more than once? (about page 166's length_≤1)
• The mechanism of anonymous function to call itself of Scheme? (touches on the eternity function used on page 166's length_≤1)

Bidget

From the previous examples before that I would have thought that works for length 0 only would mean it goes into recursion forever on eternity for any nonempty list. Failing by hitting eternity as opposed to failing for dynamic typing reasons. But I do find it odd to consider "works" if it fails for dynamic typing reasons for nonempty lists. – Baca

@Baca Yes, "works" is sort of an odd term here. It's important to keep in mind the code isn't a continual refinement and refactoring of already working code; the book presents a Socratic dialogue where the final code is gradually teased out after a series of attempts. – Bidget