Semantics of multiple patterns with the same prefix in a switch

[forax at univ-mlv.fr]

> De: "Guy Steele" <guy.steele at oracle.com>
> À: "Brian Goetz" <brian.goetz at oracle.com>
> Cc: "Remi Forax" <forax at univ-mlv.fr>, "amber-spec-experts"
> <amber-spec-experts at openjdk.java.net>
> Envoyé: Lundi 1 Février 2021 05:56:57
> Objet: Re: Semantics of multiple patterns with the same prefix in a switch

>> On Jan 31, 2021, at 5:57 PM, Brian Goetz < [ mailto:brian.goetz at oracle.com |
>> brian.goetz at oracle.com ] > wrote:
>> . . .
>> Your question, I believe, is whether in such a switch, we may, may not, or must,
>> run the deconstructor twice when we get to the second Box(...) case. We haven't
>> yet written down the rules for this, though of course we've thought about it.
>> As you point out, if the deconstructor has a side-effect, the number of
>> invocations would be visible.

>> I think there are two realistic options:

>> - The compiler and runtime _cannot_ try to optimize away the redundant
>> invocation.
>> - The compiler and runtime _may_ try to optimize away redundant invocations, but
>> there is no guarantee it does so.

>> The third option -- that we _must_ do so -- can be quickly seen to becomes
>> unrealistic as patterns get more complicated and harder to analyze. So the
>> first question is do we just give up and guarantee the obvious execution, or do
>> we give ourselves license to be clever, but less deterministic.

> There is a fourth option (a variant of the second one), which I believe best
> conforms to The Java Way of Doing Things, of which WORA is theoretically a
> substantial part:

> - The compiler and runtime _may_ try to optimize away redundant invocations (but
> there is no guarantee it does so), _provided_ it can prove that such
> optimization cannot result in observable behavioral differences in execution
> (appropriately defined).

> This principle allows, for example, evaluation of the expression `(n+1)*(n+1)`
> to perform only one execution of `n+1` (where `n` is of primitive type).
> Special knowledge about libraries allows `Math.max(x,y)*Math.max(x,y)` to be
> treated in similar fashion if desired. But in general this cannot be done for
> `User.method(x)*User.method(x)`.

I agree with WORA. 
Usually the compiler does nothing because of separate compilation and the work of sharing common sub expressions is done by the JITs which inline methods so the computation of Math.max and User.method may be shared or not depending if there is a side effect or not. 

> In the general case of user-defined patterns, the compiler may not be able to
> prove this. At the other extreme, in the specific case of deconstructors
> automatically provided for records, it may always be safe to perform such
> optimizations (we should look at this). In between, maybe some flow analysis
> would allow a simple proof of safety for some common cases of user-defined
> deconstructors or patterns.

Even if the deconstructor is not specified and it's a record, you can still have side effect inside the accessors given they are user definable. 

> So in Rémi’s example, the compiler may well be able to get away with calling the
> Box deconstructor only once if Box is a record type with default deconstructor,
> but almost certainly cannot if Box has a user-coded deconstructor that has had
> a side effect inserted.

>> Note that nested translation you wrote down is _not_ the obvious one; it is
>> already a "clever" one. THe obvious if-else chain is:

>> if (object instanaceof Box(Circle circle)) { ... }
>> else if (object instanceof Box(Square square)) { ... }

> I agree.

>> which can be further unrolled to:

>> if (object instanaceof Box(Shape s) && s instanceof Circle circle ) { ... }
>> else if (object instanceof Box(Shape s) && s instanceof Square square ) { ... }

> Yes.

>> ...

>> But, we're already in the weeds of translation details and optimization. A much
>> simpler question that has to be answered first is: are we even willing to say
>> "side effects in patterns can't be relied on to happen with the obvious arity
>> and order, and if you have them, good luck to you"? Similarly, if we have a
>> nested pattern P(Q, R), do we promise that the Q and R tests happen left to
>> right, or let the compiler do what it likes?

> I believe that WORA would dictate that, yes, pattern invocations, like
> expressions, must appear to be evaluated in a well-defined, predictable order,
> and the standard order in Java is left-to-right.

I fully agree, whatever we decide, the order should be left-to-right. 

Given that the VMs/JITs are already able to share common sub expressions if a method can be inlined and there is no side effect, and that allowing optimizations to maybe occur is not WORA. 

I see two possible semantics, 
- either the compiler and runtime metafactory do not share of the computation of the same pattern (the VM/JIT still can) 
- or we allow the computation of patterns with the same prefix (to keep the left-to-right order) to be shared even if they are maybe side effects. 
"With the same prefix" meaning that the patterns on the left that share the same surface syntax will share the same computation results. 

In the first case, we only rely on the VM/JIT magic, in the other case, we hope that no sane user will write a pattern method with side effect. 

So said differently, does the second proposed semantics make sense or is too clever ? 

Rémi 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/amber-spec-experts/attachments/20210201/df578029/attachment.htm>