We need more animations for this kind of stuff: http://yinwang0.wordpress.com/2012/04/09/reinvent-y
-- Yin On Thu, Feb 6, 2014 at 7:24 AM, Matthew Johnson <mcoog...@gmail.com> wrote: > 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 > >
____________________ Racket Users list: http://lists.racket-lang.org/users
