[racket] Y combinator

From: Yin Wang (yinwang0 at gmail.com)
Date: Thu Feb 6 15:39:08 EST 2014

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>

Posted on the users mailing list.