RFC: Enriching ADTs

[EliasC]

This RFC can be thought of as the "Future work" #869, i.e. features that we might add to our abstract data types. They are divided into two categories, depending on the amount of work needed to implement it.

Minor features

These are minor issues that should be fairly simple to fix. Some of them could probably be converted to issues of their own, but I include them here to encourage discussion.

Parentheses for field-less ADTs should be optional

Since ADTs are implemented as syntactic sugar, for each case of a data type, there is a corresponding class and function of the same name. When a programmer writes Some(42) it is an actual call to a function Some of type int -> Option (assuming the existence of a data type Option). However, this means that constructing an ADT value with no arguments is written as None(); just None is a function of type () -> Option!

This is especially annoying for pattern matching, the case declaration and corresponding case in the match do not look the same:

case None : Option
...
match x with
  case Some(n) => ...
  case None() => ... -- Ugly!

Even more annoying is the fact that writing case None in a match is currently interpreted as a (catch-all) variable!

It would be more ergonomic to automatically translate None to None(), wherever it appears. This however raises the question of how capitalised variable names should be interpreted when there is no corresponding ADT constructor. There are two obvious options:

1. Give an error message like "Unknown ADT case 'Noone'.
2. Simply interpret it as a variable.

While 2. is more permissive, it also opens up for errors like misspelled patterns:

match x with
  case Noone => ... -- This is now a catch all!
  case Some(n) => ...

Therefore I am leaning more towards 1. The sad thing about this is that all-caps variables, which a programmer may want to use to denote a constant, can no longer be used. This could in turn be fixed by applying option 1 from above, but only to patterns. I am not convinced that all-caps variables are important enough to motivate this discrepancy.

Type inference should be improved

The type inference machinery currently does not handle the following case:

data List[t]
case Cons[t](hd : t, tl : List[t]) : List[t]
case Nil[t] : List[t]
...
Cons(1, Cons(2, Nil()))

Cannot infer the type of parameter 't1' of function 'Nil'

Instead, the programmer has to write Cons(1, Cons(2, Nil[int]())). My feeling is that this would be fixed if someone could just implement proper type inference for Encore in general (a thesis project perhaps?).

Allow abstract methods in data declarations

The desugaring process turns data declarations into traits and cases into classes. A data declaration can have methods, which will be inherited by the cases of this data type. Because of the close connection between traits and data declarations, it should be straightforward to support abstract methods by allowing a data declaration to require methods, which each case must then provide. I believe this is as simple as extending the parser to recognise requirements, and the desugarer to move them over to the resulting trait.

Major features

These are features that require more thought (and effort) to implement than the features in the previous section. They also have more open ends and less clear use cases.

Allow match expressions to specialise types in cases

The correspondence between data/case and trait/class gives us that all values of a data type are actually instances of classes typed using the same trait type. Due to the nature of our desugaring, when we use match we learn something about which class type the value being matched on actually has. This would allow us to do downcasts in a safe way:

val x = Some(42) : Option[int]
match x with
  case Some(n) => ... -- x : Some[int]
  case None => ... -- x : None[int]
end

Since matching on ADTs already gives access to all the fields of that value, the reason for doing this would be to access case specific methods. It would be like allowing instanceof for a limited set of types.

Allow cases belonging to several data types

Since a case is actually a class implementing a (data) trait, it should be straightforward to have a case which is part of several data types:

data Expr
data Binary

case Addition(l : Expr, r : Expr) : Expr + Binary

This could be useful if Binary contains methods that need to be reused for multiple (but not all) instances of Expr. One could imagine using this for concurrency as well, but since ADTs are immutable, there's not a lot to be gained as far as I can see.