[CST-2] Opt Comp 97.9.7

[Jamie Shotton]

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

Matt's provided this solution which I think is tighter and correct:

>> I think the answer to the previous part is not that 'e' can 
>> have no side effects but that it cannot have both a 'R' and a 
>> 'W' side effect.  Any other set of effects is OK.

I think this is correct, though one possible consideration is whether
you consider the creation of references as important side effects - if e
allocates a new reference and then writes it to some storage location
then you have the original expression e+e creating two new locations
(though one is instantly discarded), but the 'optimisation' only creates
one location...

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

I think you're right in that this is undecidable.  So while what you say
is correct, it's not of much use to this question I think.  Again Matt's
provided a nice solution:
 
>> However, for the second part, the criterion is slightly 
>> stricter.  The effects must not contain a 'W' effect at all.  
>> This is to avoid the problem that would be encountered if 'e' 
>> was 'a:=x' (where 'a' was a reference to an integer or 
>> equivalent) in which it would be non-deterministic what 'a' 
>> was set to at the end of the processing.

I *think* this is what the question's aimed towards...

J