Pattern Matching

[John Rose]

On Mar 18, 2017, at 10:22 AM, Remi Forax <forax at univ-mlv.fr> wrote:
> 
> Hi guys,
> i've already implemented a kind of pattern matching in a language that run on the JVM (still closed source :( ),
> so i've said to Brian that i will send a summary of how it is done.

Thanks, Remi. This is useful.  At many points it parallels thinking that we have been doing.

I'm glad to see you use indy.  As with the string-concat work, there is an opportunity to perform
run-time optimizations that way, which an eager bytecode spinning approach can't touch.
For example, the static compiler can inspect type relations among different case branches,
and it can make requirements such as no dead cases, but it's only at runtime that the final
type relations are available.  And even if the static compiler ignores some type relations,
the BSM for the switch can use such information to flatten the decision tree semi-statically.

(My thought ATM is to forbid dead code at compile time but allow it at runtime if
the type relations have changed.  I think that's in keeping with the way we manage
other binary compatibility questions.  The runtime optimization can ignore the
static presuppositions.  This means that the semantics of switch need to be
"as if" the switch is "really just" a linear decision chain.  We save performance
by using a declarative formulation to the BSM which allows the BSM code
generator to reorganize the chain as a true switch, or shallow cascade of
switches.  BTW, we forgot the switch combinator.  Maybe we can fix this in
the next release?  More indy leftovers!  It should be used to compile switching
on strings and enums, as well as any future pattern matches on constants.
It should be optionally lazy and open, which is what I think you are also
calling for at the end of your message.)

The theory of type safety of multiple dispatch has moved forward with Fortress.
Alternatively, if you can sugar up a visitor deployment as if it were multimethods
added as extensions, you could prove type-safety and still define apparent methods,
outside the type capsule.  When we get value types visitors will become cheaper.
Maybe at that point we can think about doing multi-method sugar that compiles
to invisible visitor classes.  (I'm not suggesting we do this now!)

Maybe one of our lambda leftovers will help with the problem of flow-typing.
   switch (val) { case A val: … }  // relax shadowing rule for some bindings??
It's a fraught question, because the anti-shadowing rule prevents confusions
which a relaxation re-introduces, if users misuse the freedom of expression.
The goal would be to guide users to shadow variables only when the shadowing
binding is somehow a logical repeat of the original binding.  This cannot be
done automatically in all cases we care about.  Tricky tradeoffs.

We are also struggling with unapply.  There are several hard parts, including
the encapsulation model and the API for delivering multiple components.
The low-level parts probably require more indy-level combinators with
special JVM optimizations.  I wish we had full value types today so we
could just do tuples for multiple-value packages.  But even that is a
simulation of the true shape of the problem, and simulation has overheads
even if we stay out of the heap.  A lower-level solution which requires
no companion types at all (not even tuples) would be to reify argument
lists per se, at the same level of abstraction as method handle types.
That's a building block I am currently experimenting with, as a value-based
class which can be upgraded to a value type.  The type information is
encoded as (wait for it) a MethodType, interpreted with the arrows reversed.

Thanks for the brain dump!

— John