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 makeslength
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 oflength
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:
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))
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.
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
1 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.
1length
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