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
____________________ Racket Users list: http://lists.racket-lang.org/users
