Variants/case classes/algebraic data types/sums/oh my!

Sat Jun 11 18:40:06 UTC 2016

----- Mail original -----
> De: "org openjdk" <org.openjdk at io7m.com>
> À: "Remi Forax" <forax at univ-mlv.fr>, valhalla-dev at openjdk.java.net
> Envoyé: Samedi 11 Juin 2016 19:36:25
> Objet: Re: Variants/case classes/algebraic data types/sums/oh my!
> 
> 'Ello!
> 

Hi !

> On 2016-06-11T13:18:40 +0200
> Remi Forax <forax at univ-mlv.fr> wrote:
> 
> > In my opinion, you can breakdown the support of ADT into 3 parts,
> > - definition of a case class
> > - definition of a closed type
> > - pattern matching
> > 
> > The first two parts are not very interesting, at least not from the VM
> > point of view, the pattern matching part is in my opinion, the one that is
> > fun.
> > Also note that there are two different semantics for the pattern matching,
> > you have the Scala way, were each case is tested linearly so if a test do
> > a side effect, a further test can see the effect (this semantics is also
> > called predicate dispatching [1]) or you have the "switch on class"
> > semantics where you jump to the right action.
> 
> Interesting. Is this Scala you're referring to where the tests can have
> side effects? I'm mainly familiar with that style of linear matching
> from Haskell and OCaml, where the left hand side is simply a pattern
> and isn't something that's evaluated.

You should take a look to Scala, it's is a JVM language, i.e. it compiles to bytecode and run on the JVM.
The matching part is done by invoking a method unapply() on the constructed pattern [1], one goal of Scala (at least in the early days) was to try to implement most of the features of the language as library calls, the unapply() trick fits well that model. The ugly side effect :) of that trick is that you can do side effect when performing the matching.

> 
> > At runtime, the best way to implement the later semantics nowadays is to
> > implement a kind of dynamic visitor (a hashmap of lambda),
> > here is a way to implement it in Java [2].
> 
> Hah, I've not seen that formulation before.
> 
> It does have the unfortunate side effect in that you lose
> exhaustiveness checks. When an extra case is added to Vehicle, the
> compiler isn't going to tell you that you now need to add an extra
> method to all of your visitors. The traditional generic visitor
> approach does give you that property:
> 
>   http://io7m.com/documents/adt-jvm/#genvis
> 
> Add another subclass to the class being visited, add another case to
> the visitor type, and now the compiler tells you everywhere in your
> code where the anonymous visitor instances are now
> incomplete.

You can not change the Visitor interface without breaking the backward compatibility,
basically, with the Visitor of the Gof book, you can not add a new subclass.
That's why i've created this formulation, it lets anyone to create a new subclass,
as you said at the expense of loosing the precise type checking of the compiler.

BTW, ADT pattern matching and Design Pattern Visitor are dual, it was called the "expression problem" by Philip Wadler (see [2] and [3] for the full story).

> 
> > Now, what can be fun in the context of valhalla is to consider the way to
> > define the closed class 'hierarchy' as a kind of specialization,
> > as John said, switching on an integer or an enum value seems the most
> > promising. So an ADT can be seen as a specialization over an integer.
> > 
> > interface Expr<int K> {
> > }
> > value class Value implements Expr<0> {
> >   final int value;
> > }
> > value class Add implements Expr<1> {
> >   final Expr<?> left;
> >   final Expr<?> right;
> > }
> > 
> > static <int K> int eval(Expr<K> expr) {
> >   switch(K) {
> >      case 0:
> >        return ((Value)expr).value;
> >      case 1:
> >        Add add = (Add)expr;
> >        return eval(add.left) + eval(add.right);
> >      default:
> >        throw new AssertionError();
> >   }
> > }
> > 
> > because K is reified, there will be two methods eval() at runtime, one
> > specialized for K = 0 and an other for K = 1,
> > which means that the switch will be constant fold (the real 'switch' is
> > done when selecting the specialization).
> 
> I'm intrigued by this. Is the per-value specialization something that's
> currently implemented? That looks a bit dependently-typed to me...

It's not currently implemented but i see not reason to not try to (see my talk at the next JVM Summit (if the talk is accepted)). By example, i think that we need something like that if we want to re-implement method handle combiners as a kind of specialization.

> 
> > Obviously, one can come with a nice syntax sugar on top of that to avoid
> > users having to number things (enum are better here because they are an
> > indirection on an integer which is better for separate compilation) and
> > insert the cast automatically.
> 
> Right!
> 
> M
> 

Rémi

[1] http://www.scala-lang.org/old/node/112
[2] https://en.wikipedia.org/wiki/Expression_problem
[3] http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt