[racket] Y combinator

On Feb 11, 2014, at 12:48 AM, Matthew Johnson <mcooganj at gmail.com> wrote:

> I am still a little unclear.  Is this a logical result, or a result of the evaluator's rules?  Or are they the same thing? 


They are the same thing. To calculate with the Racket that you see in the book/derivation, use this rule: 

  ( (lambda (x) e) V ) ~ e with all [free] occurrences of x replaced by V

[This is the rule you learn in pre-algebra,  with the 'free' needed here because 
variables can occur at more places than in pre-algebra.] Using this rule, plus 
simple car/cdr/cons/+1 rules, you can confirm every step in the derivation. As it 
turns out, the compiler implements this rule totally faithfully BUT instead of 
copying actual code it "copies" references to code by moving things from registers
to registers. Because the two are equivalent, a programmer can use the above
rule to think about code and the compiler writer (one among 10,000s of language
users) is the only one who has to keep references, registers, and replication 
in mind (kind of). 

-- Matthias