[CST-2] Opt Comp 97.9.7

[George van den Driessche]

----- Original Message -----
From: "Jamie Shotton" <jdjs2@cam.ac.uk>
To: <cst-2@srcf.ucam.org>
Sent: Monday, May 20, 2002 2:47 PM
Subject: [CST-2] Opt Comp 97.9.7


>
> Looking at the very end of question
> http://www.cl.cam.ac.uk/tripos/y1997p9q7.pdf
> is the answer that expression 'e' cannot have any side effects (which I
> believe is the answer to the penultimate part), or is there something
> subtler going on here?

The difference might be this:

In the first (penultimate) case, expression 'e' is evaluated twice in its
original form, but only once in the optimised form. Clearly, then, e cannot
have side effects if the optimisation is to be allowed.

In the second (last) case, expression 'e' is evaluated twice in both the
original and optimised forms. Furthermore, because of the parameter 'x', 'e'
might use different references in each evaluation - it might be something
like:

'e' = (if x = 1 then ref_1 := ref_2 else ref_3 := ref_4)

If it can be shown that the set of references used by f(1) is disjoint from
those used by f(2), then the side effects of the two evaluations are
guaranteed not to interfere, so the evaluations can proceed concurrently. In
fact, a tighter guarantee can be found, I think - if neither evaluation will
write to a reference which the other reads, then they can still be run
concurrently. This would allow ref_2 and ref_4 to coincide in the above
expression. I imagine that calculating the relevant sets for checking this
property is undecidable... &c &c.

Does that sound reasonable?

George