[racket] Y combinator
Hi scheme experts,
My question is really a plea for someone to fill in the gaps in a
derivation of the Y combinator.
With some effort i've (mostly) understood the explanation of how an
anonymous function might call itself in the following post:
http://www.catonmat.net/blog/derivation-of-ycombinator/
At this point, i understand how
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 ((mk-length mk-length) (cdr list))))))))
generates the naive lambda length function with a re-generator (kernel?) as
a result of (mk-length mk-length) being in the function place in the
recursion.
However once we step toward the derivation of the Y-combinator, i get lost.
There are two changes that just appear (without motivation or
explanation).
Foremost, the below seems to be missing a paren -- and as i'm not sure what
problem it's supposed to solve, i'm not sure where it ought to be placed?
Also, i'm not sure why length has re-appeared, after we replaced them all
with mk-length (with some effort) in a prior step?
((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) *((lambda
(length) (lambda (list) (cond ((null? list) 0) (else (add1 (length (cdr
list)))))))* (lambda (x) ((mk-length mk-length) x)))))
My guess is that `lambda(x) ((mk-length mk-length) x)` is supposed to go in
the length position in `(add1 (length (cdr list)))` -- is this correct?
Finally, as i don't understand the prior step, i'm struggling with the
appearance of (lambda (le) ... in the subsequent step
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
*(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))*
The fact that i cannot see where the paren goes shows that i don't yet
_really_ get it yet -- hopefully with some help i'll make the final steps.
thanks in anticipation.
mj
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140206/f5f8955e/attachment.html>