Friday, April 8, 2016

Algebraic sum types in Java 8

I’ve been busy busy busy, so I haven’t had much time to work on Effes, but I did want to share a technique I developed for mimicking algebraic sum types in Java. Those are basically what Effes calls disjunctive types: Foo | Bar to represent an object that might be a Foo or a Bar.

Though they’re quite different in a lot of ways, you can think of subtypes as kinda-sorta like sum types. If you have an abstract class Animal with exactly two subclasses, Dog and Cat, then an animal must either be a dog or a cat: Animal -> Dog | Cat.

As it happens, this is how Antlr expresses alternatives within a grammar rule. For instance, my grammar includes this production:

singleType: TYPE_NAME singleTypeParameters # SingleDataType
          | GENERIC_NAME                   # SingleGenericType
          ;

The classes Antlr provides include the hierarchy:

class SingleTypeContext
SingleDataTypeContext extends SingleTypeContext
SingleGenericTypeContext extends SingleTypeContext

Since the grammar is fully defined within my compiler, I know that these are the only two subclasses of SingleTypeContext; I can treat it as a closed sum type. A lot of what I do involves translating ASTs, which in turn requires looking at the specific subtype (or, in sum type terms, the type’s tag).

The approach I take to these is implemented in a Dispatcher class, and it has three main parts:

  • a mapping from subtype to a function whose input is that subtype
  • a dispatcher that figures out which function to use, and invokes it
  • the ability to test that all subtypes are accounted for

To take a trivial example, let’s say I were describing the AST. The first thing I’d do is to translate each node to a string, and for that I’d use the mapping functionality. I’d say that a SingleDataTypeContext maps to a function _ -> "I'm a data type!" while SingleGenericTypeContext maps to g -> "I'm a generic named " + g.name(). I then pass an instance typed as the superclass, SingleTypeContext, to the dispatcher. The dispatcher figures out the specific class of the instance, finds its function, downcasts it and passes it to that function.

As for the test that all subtypes are accounted for, I basically declare as an invariant in my code (which is up to me to not break) that if I want to treat a type as a sum type, all of its specific types have to be nested classes of a single enclosing class. That makes it easy to find those subtypes, which in turn makes it easy to verify that they’re all in the mapping.

My code has a few places where I use the Dispatcher, but one example (with shorthand Java, to fit in a blog format) is in ExpressionCompiler, where I parse an “expression line” (basically a one-line expression or the first line of a case statement):

private static final Dispatcher<~> exprLineDispatcher
  = Dispatcher.builder(/*...*/)
      .put(SingleLineExpressionContext.class, ExpressionCompiler::singleLine)
      .put(CaseExpressionContext.class, ExpressionCompiler::caseExpression)
      .build(ExpressionCompiler::exprLineErr); // default, for err handling

Needless to say, this is not the most efficient approach; it’s basically a visitor-style dispatch, but backed by a HashMap instead of Java’s built-in polymorphism. For my (current) needs, it’s good enough. It’s also quite convenient for when I add a new alternative to a production in the grammar, since a quick run of the find-all-subtypes test tells me exactly where I need to add new code to handle that alternative.

Wednesday, January 6, 2016

Pattern matching reaches 1.0!

I finally finished implementing pattern matching!

I just looked to see when I last updated this blog, and holy crap, it’s been half a year! I tell ya, this had better be one nice feature.

For what it’s worth, I think it is. The pattern matching is recursive, meaning you can break components down as far as you want:

case myWhatever of
    Something(List(BlahBlah(5, a), _)) -> ...

That will match if myWhatever is a Something whose only argument is a List whose first element is a BlahBlah with two arguments, the first being an int 5 and the second being anything, and that thing is now bound to the variable a.

That took a bit of work, though it only gets me to parity with other pattern matching languages. What’s neat about Haskell is that the remaining type — that is, the next line in the case list — will take all of that into account. Taking a simpler example, this would fail to compile:

case coinFlips of
    List(Heads, List(Tails, _)): ...
    List(Heads, List(Tails, _)): ...
    _: ...

because the second line is trying to match against a pattern that’s already been matched. And likewise, without that last _ -> ... line, the statement would fail to compile because some coinFlips types have not been accounted for (namely, List(Heads, Empty | List(Heads, _) | List(Tails, _)).

There’s still room for improvements:

  • you can’t match against an alias or disjunctive type (ie, you can’t match for Boolean, you have to look for True and False separately)
  • the “remaining type” tends to be pretty exploded out; instead of List(Heads, Empty | List(Heads, _) it might say List(Heads, Empty) | List(Heads, List(Heads, _). After a few of these exploded forms chain together, it can get pretty hairy
  • There’s no tracking of values for what I call “large domain values,” such as ints (as opposed to small domain values, such as True | False. For instance, if you match an int against 5, nothing prevents you from matching against 5 again.
  • There’s no mechanism for variable arity destructors, which is why the List(...) pattern above had to be desctructed node by node, instead of just as List(Heads, Tails, _)

I may pick off one or two of these soonish, but frankly I’m ready to put pattern matching aside for a bit. It’s taken longer than I’d have liked, and it’s time to move on to some more features.

I think the next thing I’m going to do is exception handling, about which I have some neat ideas. After that, I’m going to fill in the built-in types (which currently only include ints), and for strings I intend to include string interpolation. After that, I’m going to do some I/O work of some sort. And at that point, I think I’ll be ready to start writing some real code in Effes, at lon