[racket] Y combinator
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 <mcooganj at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140206/c0d4c026/attachment.html>