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

[Remi Forax]

Thinking a little bit more about that ...
I we want to represent something like this,
  Expr = Value(int value) | Add(Expr left, Expr right)
instead of using an interface wich is wrong because we want Value and Add to be Exprs and not subtypes of Expr,
we can use the __Where clause to disambiguate between the Add and the Value.


// for the compiler, Value and Add are seen as specialization (species) of Expr:
typedef Add=Expr<ADD>
typedef Value=Expr<VALUE>
typedef Expr=Expr<?>

// and for the VM:
sealed enum ExprKind {
  VALUE,
  ADD
}

public class Expr<ExprKind K> {
  __Where(K == VALUE) final int value;
  __Where(K == ADD) final Expr<?> left, Expr<?> right;

  __Where(K == VALUE) public Expr(int value) { this.value = value; }
  __Where(K == ADD) public Expr(Expr<?> left, Expr<?> right) { this.left = left; this.right = right; }

  __Where(K == VALUE) public int eval() { return value; }
  __Where(K == ADD) public int eval() { return left.eval() + right.eval(); }
}

left.eval() which is typed as Expr<?>.eval() is sound because ExprKind is sealed and eval() is defined on both specialization (both species).

cheers,
Rémi

----- Mail original -----
> De: "org openjdk" <org.openjdk at io7m.com>
> À: valhalla-dev at openjdk.java.net
> Envoyé: Mardi 7 Juin 2016 16:05:47
> Objet: Variants/case classes/algebraic data types/sums/oh my!
> 
> Hello!
> 
> As a Java developer with a background in functional programming and
> type systems, I often (which is to say, more or less constantly) find
> myself writing emulations of algebraic data types to solve day-to-day
> problems in all of my Java projects.
> 
> For those that don't know what an algebraic data type is, you may
> possibly know them by one of the other names often used:
> 
>   * Variant types
>   * Case classes (from Scala, Kotlin, Ceylon, etc)
>   * Sum types (a term more common in literature than languages)
> 
> For those that still don't know them, I have a somewhat old article
> here aimed at Java programmers that will probably serve as a reasonable
> introduction:
> 
>   http://io7m.com/documents/ccat/
> 
> I won't spend a great deal of time advocating for their use here.
> Suffices to say that they are a very fundamental part of the type
> systems such as Haskell, O'Caml, etc, and are used to great effect in
> writing very concise code that enjoys many safety and correctness
> properties. The types themselves have also been adopted by the majority
> of statically typed JVM languages with varying degrees of completeness:
> 
>   http://io7m.com/documents/adt-jvm/
> 
> An excellent video on how Jane Street use algebraic data types to write
> software that absolutely must work correctly is Yaron Minsky's
> Effective ML:
> 
>   https://www.youtube.com/watch?v=DM2hEBwEWPc
> 
> The section at 18 minutes ("Make illegal states unrepresentable") is
> where the discussion on these types begins.
> 
> Currently, almost all of the statically typed alternative JVM languages
> implement some form of algebraic data types. Languages such as Scala
> and Frege support them as completely as languages such as Haskell, with
> full structural pattern matching. Languages such as Kotlin and Ceylon
> implement a more limited form known as case analysis.
> 
> There are also numerous library implementations of the types in Java,
> but they all have various shortcomings due to lacking the required
> support from both the virtual machine and the Java language itself.
> 
> I believe that all of the existing languages could benefit from both
> JVM and Java language support for the types, and I believe that support
> could be provided with minimal, non-intrusive changes to the virtual
> machine (an extra piece of class metadata, no new bytecode
> instructions, a couple of extra syntax rules in the Java language that
> likely build upon the existing switch statement, and no new keywords).
> 
> The reason for the additional virtual machine support is that I would
> hope that sooner or later the various language implementations would
> standardize on an internal representation for the types so that, for
> example, a type declared in Kotlin could be used from Java in the same
> manner that it could be in Kotlin, with the same static guarantees.
> Currently, each language implements the types using proprietary
> metadata stored as annotations, the types cannot interoperate properly
> between languages.
> 
> The reason for the Java language support is because currently, library
> implementations of the types have to rely on rather clumsy Visitor-based
> approaches, and incur a cost in both performance and ease of use.
> 
> I'm writing to this list because I believe there is significant overlap
> with the work being done on value types, as algebraic data types are
> almost always used in a value-typeish context. Naturally, additions to
> the language and VM will overlap other projects, but I had to start
> somewhere!
> 
> I recently wrote a very rough and low-detail proposal in a GitHub
> comment for a project that is looking to implement yet another
> generator for pseudo algebraic data types in Java:
> 
>   https://github.com/immutables/immutables/issues/47#issuecomment-221533004
> 
> I'm hoping that this can be the starting point for discussion. As with
> all language proposals: none of the syntax is final and is obviously
> subject to changes/improvements/outright destruction.
> 
> Regards,
> Mark
>