# [racket] Y combinator

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Tue Feb 11 10:09:44 EST 2014 Previous message: [racket] Y combinator Next message: [racket] Y combinator Messages sorted by: [date] [thread] [subject] [author]

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

```

 Posted on the users mailing list. Previous message: [racket] Y combinator Next message: [racket] Y combinator Messages sorted by: [date] [thread] [subject] [author]