[racket] Y combinator

From: Matthew Johnson (mcooganj at gmail.com)
Date: Tue Feb 11 10:06:03 EST 2014

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) ?

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
>

Posted on the users mailing list.