[External] : Re: Proposal: java.lang.runtime.Carrier

[Remi Forax]

> From: "Remi Forax" <forax at univ-mlv.fr>
> To: "Brian Goetz" <brian.goetz at oracle.com>
> Cc: "Jim Laskey" <james.laskey at oracle.com>, "amber-spec-experts"
> <amber-spec-experts at openjdk.java.net>
> Sent: Saturday, March 5, 2022 11:54:14 PM
> Subject: Re: [External] : Re: Proposal: java.lang.runtime.Carrier

>> From: "Brian Goetz" <brian.goetz at oracle.com>
>> To: "Remi Forax" <forax at univ-mlv.fr>
>> Cc: "Jim Laskey" <james.laskey at oracle.com>, "amber-spec-experts"
>> <amber-spec-experts at openjdk.java.net>
>> Sent: Friday, March 4, 2022 3:11:44 AM
>> Subject: Re: [External] : Re: Proposal: java.lang.runtime.Carrier

>>>> Either way, we don't need to mutate or replace carriers.
>>> You want the same carrier for the whole pattern matching:

>> I think you're going about this backwards. You seem to have a clear picture of
>> how pattern matching "should" be translated. If so, you should share! Maybe
>> your way is better. But you keep making statements like "we need" and "we want"
>> without explaining why.

>>> - if you have a logical OR between patterns (not something in the current Java
>>> spec but Python, C# or clojure core.match have it so we may want to add an OR
>>> in the future)

>> OR combinators are a good point, but they can be done without a with operation.

>>> - if different cases starts with the same prefix of patterns, so you don't have
>>> to re-execute the de-constructors/pattern methods of the prefix several times

>> Agree that optimizing away multiple invocations is good, but again, I don't see
>> that as being coupled to the pseudo-mutability of the carrier.

>> Perhaps you should start with how you see translation working?
> Sure,
> the idea is that to execute the pattern matching at runtime, each step is
> decomposed into few higher order functions, things like testing, projecting a
> value (deconstructing), etc
> each higher order manipulate one kind of function that takes two values, the
> value we are actually matching and the carrier, and returns a carrier.

> Obviously, each simple function is a method handle, so there is no boxing in the
> middle and everything is inlined.

> Here is a possible decomposition
> - MH of(Object carrier, MH pattern)
> which is equivalent to o -> pattern.apply(o, carrier)
> - MH match(int index)
> which is equivalent to (o, carrier) -> with(index, carrier, 0), i.e. return a
> new carrier with the component 0 updated with index
> - MH do_not_match()
> which is equivalent to match(-1)
> - MH is_instance(Class type)
> which is equivalent to (o, carrier) -> type.isInstance(o)
> - MH is_null()
> which is equivalent to (o, carrier) -> o == null
> - MH throw_NPE(String message)
> which is equivalent to (o, carrier) -> throw new NPE(message)
> - MH project(MH project, MH pattern)
> which is equivalent to (o, carrier) -> pattern.apply(project.apply(o), carrier)
> - MH bind(int binding, MH pattern)
> which is equivalent to (o, carrier) -> pattern.apply(with(o, carrier, binding)
> - MH test(MH test, MH target, MH fallback)
> which is equivalent to (o, carrier) -> test.test(o, carrier)? target.apply(o,
> carrier): fallback.apply(o, carrier)
> - MH or(MH pattern1, MH pattern2)
> which is equivalent to
> (o, carrier) -> {
> var carrier2 = pattern1.apply(o, carrier);
> if (carrier2.accessor[0] == -1) {
> return carrier2;
> }
> return pattern2.apply(o, carrier2);
> }

> For the carrier, the convention is that the component 0 is an int, -1 means "not
> match", and any positive index means the indexth case match.

> In the detail, it's a little more complex because we sometimes need to pass the
> type of the first parameter to correctly type the returned MH and we also need
> an object CarrierMetadata that keep track of the type of the carrier components
> (and provides an empty carrier and the accessors/withers).

> Here is a small example

> record Point( int x, int y) {}
> record Rectangle(Point p1, Point p2) {}

> // Object o = ...
> //switch(o) {
> //  case Rectangle(Point p1, Point p2) -> ...
> //}

> var lookup = MethodHandles. lookup ();

> var carrierMetadata = new CarrierMetadata( methodType (Object. class , int .
> class , Point. class , Point. class ));
> var empty = carrierMetadata.empty();

> var op = of (empty,
> test ( is_instance (Object. class , Rectangle. class ),
> cast (Object. class ,
> or (carrierMetadata,
> project ( record_accessor (lookup, Rectangle. class , 0 ),
> test ( is_null (Point. class ),
> do_not_match (Point. class , carrierMetadata),
> bind ( 1 , carrierMetadata))),
> project ( record_accessor (lookup, Rectangle. class , 1 ),
> test ( is_null (Point. class ),
> do_not_match (Point. class , carrierMetadata),
> bind ( 2 , carrierMetadata,
> match (Point. class , carrierMetadata, 0 ))))
> )
> ),
> throw_NPE (Object. class , "o is null" )
> )
> );

> // match: new Rectangle(new Point(1, 2), new Point(3, 4))
> var rectangle1 = (Object) new Rectangle( new Point( 1 , 2 ), new Point( 3 , 4
> ));
> var carrier1 = op.invokeExact(rectangle1);
> System. out .println( "result: " + ( int ) carrierMetadata.accessor( 0
> ).invokeExact(carrier1));
> System. out .println( "binding 1 " + (Point) carrierMetadata.accessor( 1
> ).invokeExact(carrier1));
> System. out .println( "binding 2 " + (Point) carrierMetadata.accessor( 2
> ).invokeExact(carrier1));

> // match: new Rectangle(new Point(1, 2), null)
> var rectangle2 = (Object) new Rectangle( new Point( 1 , 2 ), null );
> var carrier2 = op.invokeExact(rectangle2);
> System. out .println( "result: " + ( int ) carrierMetadata.accessor( 0
> ).invokeExact(carrier2));
> System. out .println( "binding 1 " + (Point) carrierMetadata.accessor( 1
> ).invokeExact(carrier2));
> System. out .println( "binding 2 " + (Point) carrierMetadata.accessor( 2
> ).invokeExact(carrier2));

> The full code is available here:
> [
> https://github.com/forax/switch-carrier/blob/master/src/main/java/com/github/forax/carrier/java/lang/runtime/Patterns.java
> |
> https://github.com/forax/switch-carrier/blob/master/src/main/java/com/github/forax/carrier/java/lang/runtime/Patterns.java
> ]

> I believe, using a function with two parameters, the actual value we are
> switching upon and the carrier that will gather the bindings is better than
> using only a carrier as parameter because in that case, you need to use the
> carrier to store all the intermediary objects even if they are not kept as
> bindings.

Adding more information, 
we want the carrier to be a primitive type (to be able to optimize it away), which means that we can not use null to represent "do_not_match", 
we have to have a flag inside the carrier for that. 

For the runtime, they are 3 different contexts: switch, instanceof and assignment, 
- for a switch, the carrier contains an int (to be switched on) as component 0 and the values of the bindings 
- for an instanceof, the carrier contains a boolean as component 0 and the values of the bindings 
- for an assignment, only the values of the bindings are necessary. 

So for the switch, we can not use one carrier per case, because accessing to the component 0 will be polymorphic if we have multiple carrier objects. 

Rémi