[racket] Y combinator

From: Matthew Johnson (mcooganj at gmail.com)
Date: Thu Feb 6 10:24:59 EST 2014

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:


At this point, i understand how

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (list)
       ((null? list) 0)
        (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

However once we step toward the derivation of the Y-combinator, i get lost.
 There are two changes that just appear (without motivation or

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)
        ((null? list) 0)
         (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.

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