# [racket] Y combinator

 From: Matthew Johnson (mcooganj at gmail.com) Date: Thu Feb 6 10:24:59 EST 2014 Previous message: [racket] 2nd Call for Papers - TFPIE 2014 Next message: [racket] Y combinator Messages sorted by: [date] [thread] [subject] [author]

```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>
```

 Posted on the users mailing list. Previous message: [racket] 2nd Call for Papers - TFPIE 2014 Next message: [racket] Y combinator Messages sorted by: [date] [thread] [subject] [author]