[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 3:33 PM
Subject: [CST-2] Opt Comp 97.9.7


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

Just for completeness, if 'e' reads a set of references Rd, and writes a set
of references Wr, then evaluating it once instead of twice will make no
difference so long as the intersection between Rd and Wr is empty. But
again, it'll get caught up in decidability.

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

Yes - I forgot to mention that the intersection between writes that the two
evaluations make has to be empty too... In summary, there are sets Rd1, Rw1,
Rd2, Wr2. *1 has to be disjoint from *2, except that Rd1 and Rd2 can
overlap. And it's undecidable! Matt's suggestion is a safe approximation.

George