Little Schemer: why wrap (mk-length mk-length) into a function?

Question

In The Little Schemer book, in Chapter 9, while building a length function for arbitrary long input, the following is suggested (on pages 170-171), that in the following code snippet (from page 168 itself):

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

the part (mk-length mk-length), will never return and will be infinitely applying itself to itself:

Because we just keep applying mk-length to itself again and again and again...

and

But now that we have extracted (mk-length mk-length) from the function that makes length it does not return a function anymore.

Now, to cure this the book suggest:

Turn the application of mk-length to itself in our last correct version of length into a function.

Like, so:

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

What I get puzzled by is:

1. If (mk-length mk-length)

   does not return a function

   how we can apply the result of (mk-length mk-length) to something, as if it is a function?

   (lambda (x)
     ((mk-length mk-length) x))
   

2. How wrapping (mk-length mk-length) into a function solves the 'never returning' (i.e. infinite recursion) problem? My understanding is, that in:

   (lambda (x)
     ((mk-length mk-length) x))
   

x will just be passed to infinitely recursive function, which never returns.

Bubble

It is the fixed-point combinator. – Hus

It's not infinite recursion. Each step uses (cdr l) as the argument, and it stops when that becomes null. – Anthropography

Why do you think (mk-length mk-length) doesn't return a function? The value of mk-length is the second lambda-expression, and it returns (lambda (l) ...), which is a function. – Anthropography

cf. Y combinator discussion in “The Little Schemer” which discusses the same piece of code. Your question is already answered there. – Swallowtail

@DanD. still not a combinator though at that point, just getting ever so closer to it. it becomes combinator when the (lambda (l) ...) gets abstracted away. – Swallowtail

There is a great post by Mike Vanier with the detailed explanation on topic. – Bubble

Answer 1

You probably copied the wrong code snippet, the one before that which you actually talk about. The first code you've shown is totally fine. What loops is, rather, this one:

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (mk-length mk-length))))                   ; (3)

This is already answered here: the application (1) triggers the application (2) which triggers the application (3) right away, which is equivalent to (1)! Thus, the looping.

Wrapping it in a lambda (aka eta-expansion) delays the application (3) until the call to the constructed length is made in (4), and that's fully OK (you copied this with some typos as well):

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)                                   ; (5)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (lambda (x)                                ; (3)
         (mk-length mk-length) x))))

(3) is a lambda expression now, not an application. Evaluating this lambda expression produces an anonymous function. This lambda function will perform the application (mk-length mk-length) later, when length is called.

(a longer explanation:) (3) just returns the lambda function right away which gets bound to length, and (lambda (l) ...) is happily returned such that when that (lambda (l) ...) will be applied to some list, possibly causing this length¹ to be called in (4), only then the application (mk-length mk-length) inside the lambda (3) will actually be performed — giving us the new (lambda (l) ...) anonymous function eventually, which will get applied to the (cdr l) there.

¹length is (lambda (x) ((mk-length mk-length) x)) which means that (length (cdr l)) is the same as ((mk-length mk-length) (cdr l)) (with mk-length bound to the whole lambda-expression (5)), and eventually, ((lambda (l) ...) (cdr l)).

nina

Swallowtail

Thanks for detailed explanation and pointing out my typos and 'mis-copings' (I believe I've corrected them, now). – Bubble

Answer 2

This call

(mk-length mk-length)

will call mk-length only once.

If mk-length happens to call it-self, then the body of mk-length will be evaluated again — but mk-length doesn't always call itself.

As to why — notice that no function in your expression has been named using define. All function expressions use lambda which introduce an anonymous function.

The example shows that even though only anonymous functions are used, it is possible to write recursive functions. Instead of naming the function directly (using define), the function is passed as argument to another function — and that function has names for its arguments.

Emlin