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

[John Rose]

On Jun 11, 2016, at 4:18 AM, Remi Forax <forax at univ-mlv.fr> wrote:

> 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).

That is an interesting use case for non-type class template parameters!

(The C++ world is full of non-type template parameters; the question there is which small slice of that complexity we might want to adopt.)

Even without int-typed or enum-typed template parameters, you could do what you need for ADTs by using enums and a sealed top type.

Here's a variation that works today:

abstract class Expr {
 private Expr() {} // sealed hierarchy

 enum $Kind { k$Value, k$Add };
 abstract $Kind $kind(); // direct dispatch hook

static final class Value extends Expr {
 $Kind $kind() { return $Kind.k$Value; }
 final int value;
 Value(int value) { this.value = value; }
}

static final class Add extends Expr {
 $Kind $kind() { return $Kind.k$Add; }
 final Expr left;
 final Expr right;
 Add(Expr left, Expr right) { this.left = left; this.right = right; }
}

}

class Client {
static int eval(Expr expr) {
 switch(expr.$kind()) {
    case k$Value:
      return ((Expr.Value)expr).value;
    case k$Add:
      Expr.Add add = (Expr.Add)expr;
      return eval(add.left) + eval(add.right);
    default:
      throw new AssertionError();
 }
}
public static void main(String... av) {
  System.out.println(eval(new Expr.Add(new Expr.Value(40), new Expr.Value(2)))); // => 42
}
}

/* Does not compile:
Expr bad() {
  class Bad extends Expr {  // error: Expr() has private access in Expr
    Expr.$Kind $kind() { return Expr.$Kind.k$Value; }
  }
  return new Bad();
}
*/

We will want to give users a way to code such things with values also.  But since values can cannot take part in subtype relations abstract classes, the pattern above would have to be reformulated to use wildcards or interfaces.  (Abstract classes are pretty old fashioned anyway.)

With wildcards, you could have Expr<Value>, Expr<Add>, and Expr<?>, where Value and Add would be contained in Expr instead of deriving from Expr; all would be values.

With interfaces, you'd have Value, Add, and Expr, where Expr is an interface and the others are values.

interface Expr {
 enum $Kind { k$Value, k$Add };
 $Kind $kind(); // direct dispatch hook
}

value class Value implements Expr {
 $Kind $kind() { return $Kind.k$Value; }
 final int value;
 Value(int value) { this.value = value; }
}

value class Add implements Expr {
 $Kind $kind() { return $Kind.k$Add; }
 final Expr left;
 final Expr right;
 Add(Expr left, Expr right) { this.left = left; this.right = right; }
}

In either case you'd want a way to seal the top type against unwanted subtypes (specializations or implementations).  Here's a straw man for the interface version.  I have zero desire to discuss source code syntax, and a range of options in mind for bytecode syntaxes.  A bytecode attribute would be straightforward, but a specially marked pseudo-constructor is also a possibility.

__Sealed({Value, Add}) interface Expr { // sealed hierarchy
  __Sealed({Value, Add}) Expr() {}  // empty pseudo-constructor accessible only to two subtypes
 …
}

In all of the sample code above, the use of enums and accessors, instead of lambdas and visitors, is a old fashioned "retro" style.  It is exactly analogous to the external iterators of early Java instead of the stream-shaped internal iterators of Java 8.  I like to work with the retro external decoding style because it leads to simple bytecode shapes, and can be sugared pretty well (cf. Java extended-for).  But in the end we might want to use a more modern lambda-driven style (unapply or some other "morphism").  The main design problem with internal iterators or matchers is they tend to require lots of auxiliary types to express the functional APIs.

— John