Variants/case classes/algebraic data types/sums/oh my! (original) (raw)

org.openjdk at io7m.com org.openjdk at io7m.com
Sat Jun 11 17:36:25 UTC 2016

'Ello!

On 2016-06-11T13🔞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.

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.

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 { } value class Value implements Expr<0> { final int value; } value class Add implements Expr<1> { final Expr<?> left; final Expr<?> right; } static int eval(Expr 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...

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

More information about the valhalla-dev mailing list