[racket] Y combinator

Matthew, you may wish to read the corresponding chapter in the Little Schemer/Lisper. It is a available as a sample chapter from my web page. Or go to a local library and get the book. 

Two hints: 

1. a lambda-bound name is arbitrary. Just because we use 'length' does not mean it has anything to do with the length function. The actual point of this step is to say "let's separate in the length function what is specific to length from what is specific to recursion". That's called abstraction, and in the functional core of Racket, you abstract via lambda. 

2. when you have an expression e and you know it will evaluate to a function if the evaluation terminates but it may not terminate, you can write (lambda (x) (e x)) to make sure that it is a function NOW. That way you can pass this quasi-e to another function and it can make the decision to evaluate it or not. 

If you had written the derivation in #lang lazy as opposed to #lang racket, you would not need this trick. In a lazy language e is passed as an argument without being evaluated to start with.

-- Matthias







On Feb 6, 2014, at 10: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