Little Schemer: length0 and mk-length

问题:

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))))))))

回答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)