[plt-scheme] Procedure equality

On Apr 30, 2009, at 4:24 PM, Alex Shinn wrote:

> Abdulaziz Ghuloum <aghuloum at gmail.com> writes:
>
>> It can go both ways.
>>
>> For example, the expression
>>
>>   (let ([foo (lambda () 42)])
>>     (eq? foo foo))
>>
>> might be transformed after copy propagation to
>>
>>   (eq? (lambda () 42) (lambda () 42))
>>
>> and this expression may evaluate to #f.
>>
>> The same nonguarantee applies to numbers (afaik).  For example
>>
>>   (let ([x 1.0]) (eq? x x))
>>
>> may return #f.
>
> Isn't the trick here to order the optimization passes so
> that the (eq? x x) => #t rewrite always occurs before the
> copy propagation pass? ;)

No actually.  That's insufficient.  Consider:

(let ([foo 1.0])
   (let ([bar foo])
     (eq? foo bar)))

So, you try to do your (eq? x x) => #t rewrites first.  Nothing
there, so, you move on.

Now you can copy propagate variables only, and you end up with

(let ([foo 1.0])
   (eq? foo foo))

but you already missed that optimization.  And if you succeed
that pass (or perform simultaneously with it) a pass that does
copy propagation of constants, you end up with

(eq? 1.0 1.0)

So, doing (eq? x x) => #t rewrites first does not cut it.  You
need to do more work (like what Matthew described) in order to
guarantee that you can both copy-propagate and at the same time
maintain that `(let ([x <expr>]) (eq? x x))' always holds.

Also, most effective optimizers do not work as a set of little
micro optimization passes.  See Chapter 4 of Oscar Waddell's
dissertation for why that's so.

Aziz,,,