[racket] Y combinator

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

> So in terms of my example:
> 
> We have the general form: ( (lambda (x) e) V) ~ e with all [free] x
> replaced by V
> 
> And for V <-- 2  ::  ( (lambda (x) (* x y) 2) ~ (* 2 y) ?
> 
> But for V <-- z^2 :: error and NOT ~ (* (* z z) y) ?

Not error. It just doesn't reduce. But usually this doesn't happen, z will have been replaced with a value. 



> 
> Thanks
> 
> On 11/02/2014, at 3:59 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
> 
>> 
>> 
>> Ouch, I forgot to explain V. NO, you canNOT replace x with arbitrary expressions. You may use ONLY VALUES (V for Value). In this context a value is one of: #t/#f, number, or a lambda expression. -- Matthias
>> 
>> 
>> 
>> 
>> 
>> On Feb 11, 2014, at 9:50 AM, Matthew Johnson <mcooganj at gmail.com> wrote:
>> 
>>> The general form: ( (lambda (x) e) V) ~ e with all [free] x replaced by V
>>> 
>>> In concrete terms means:  ( (lambda (x) (* x y) 2) ~ (* 2 y) ?
>>> 
>>> I figure best to be sure now.
>>> 
>>> Thanks and best regards
>>> 
>>> matt johnson
>>> 
>>> 
>>> On 11/02/2014, at 3:35 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>>> 
>>>> 
>>>> 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
>>