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.

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

Pattern matching using recursion

(part 1 of 4ish) I’ve made a fair amount of progress in the past few weeks, and have mostly implemented the pattern matching I mentioned in my last post. All that remains now (famous last words…) is to hook up all this pattern matching stuff, which I created as a separate unit, to the compiler.

I ran into a few hurdles along the way, which I’ll split into a few posts. But first, to recap. The objective is to take something like this:

t : List[Maybe[Bool]]
case t of:
    Cons(Nothing, Cons(_, Cons(One(True), _))): ...

… and figure that after that first case matcher, t is any list except that whose first element is Nothing and whose third element is One(True).

This has a recursive feel to it, since at each argument you can drill down (Cons -> Cons -> Cons -> One -> True, for instance). I did end up using recursion, but for a while I was fumbling around without a plan, and getting nowhere. In the end, I had to take a step back and think like a CS 101 student: what’s my base case, what’s the recursive step, what kind of thing is being returned, and how is it combined?

• base case: a simple type (not a disjunction) with no args
• recursive steps:
  
  • disjunctive case
  • simple type with args
• return value: a struct that contains a set of matched types and a set of unmatched types.
  For instance, if the possibility is True | False | FileNotFound, and the match case is True, then return value is (matched={True}, unmatched={False, FileNotFound}).
• combining step:
  
  • for disjunctions, recurse down on each component, and combine the results (matched=<matched values from each component>, unmatched similar)
  • for simple types, recurse down on each argument. If any argument returns back no matches, the result is no match. Otherwise, do a cartesian product of all of the matched and unmatched arguments. For each row that corresponds only to matched arguments, create a match; for all other rows, create an un-match.

That last point is hard to explain succinctly, but an example will illustrate it. Let’s say you have:

VehicleType = Car | Truck
Color       = Red | Green | Blue
Vehicle(type: Car | Truck, color: Color)
t : Vehicle

You match t against Vehicle(Car, Red). Recursing down, you find that the first argument is (matched={Car}, unmatched={Truck}) while the second argument is (matched={Red}, unmatched={Green, Blue}). The cartesian product of these arguments (with matches marked with asterisks) is:

*Car,   *Red
*Car,    Green
*Car,    Blue
 Truck, *Red
 Truck,  Green
 Truck,  Blue

Of these six options, only the first row has all matched arguments, so it’s the match; the other rows are unmatched:

matched = {
  Vehicle(Car, Red)
}
unmatched = {
  Vehicle(Car, Green | Blue),
  Vehicle(Truck, Red | Green | Blue)
}

This gave me the overall approach, but I still had a couple problems. The first was dealing with laziness (which is needed to handle infinitely recursive types, like List[T]), and the second was in figuring out how to structure the recursion. I’ll talk about those in the next couple posts, in reverse order.

Getting clever with pattern matching

If I haven’t blogged much lately, it’s because I haven’t worked on Effes much lately. Some of it is because I’ve been busy, and some of it is because my current task is, well, a bit difficult. It’s been hard to find the time and energy to focus on it for more than a half-hour here or there, which is really what I need to do.

The problem I’m working on is pattern matching:

truthy : True | False
myValue = case truthy of
    True: 1
    _: 0

Okay, so that example is pretty easy. The problem is that I really want to disallow what Haskell calls partial functions: functions that might not apply to all inputs that the type system allows. Consider:

possiblyTruthy : True | False | Unknown
myValue = case possiblyTruthy of
    True: 1
    False: 0
    -- no match for "Unknown"

Haskell will happily compile the equivalent of this code, and unhappily throw a runtime exception if myValue is Unknown. For a language that prides itself on its awesome type system, that’s not super helpful!

The easy option is to require an “else” (_: foo) on all case expressions, but that’s annoying (or even dangerous) when you know (or think) that you’ve already specified all the possibilities. I want to do better: I want the compiler to know whether you’ve specified the possibilities. Specifically, I’d like it to require:

• that all possibilities are specified
• that nothing impossible is specified

To do this, I need a way of “subtracting” types.

t : True | False
myValue = case t of
    True: 1  -- t is now (True | False) - True,
             -- so t : False
    False: 0 -- t is now (False) - False
             -- so t : ()
    -- no need to specify a catch-all _: case

For simple expressions like this, the subtraction is easy. But it gets tricker when you allow more complex patterns, ones that let you peer into a value’s components. Consider:

Boolean = True | False
List[T] = Cons(head: T, tail: List[T]) | Empty
bools : List[Boolean]
v = case bools of:
    Cons(True, _): 0
    Cons(False, Cons(_, Cons(False, _))): 1
    Cons(False, Cons(_, Cons(False, _))): 2
    Cons(True, Empty): 3 -- error!
    _: 4

After the first pattern, bools is:

List[Boolean] - Cons(True, _)
=   List[True | False]
  - Cons(True, _)
=   Cons(True | False, List[Boolean]) | Empty
  - Cons(True,  _)

Let’s “factor out” the True | False from the first Cons. I’ll also use one-letter type names as shorthand, since this gets tricky: B for Boolean, T for True, etc.

=   C(T | F, L[B]) | E
  - C(T, _)
=   C(T, L[B]) | C(F, L[B]) | E -- factor out the T | F
  - C(T, _)
=                C(F, L[B]) | E

Okay, that wasn’t so hard. But then, the pattern I matched was pretty simple (“any list that starts with True). As the patterns get more complex, so does the logic; I might need to recurse down an arbitrary number of times on an given argument. I also need to do this lazily: List[T] is potentially infinite, so I can’t just factor everything out and subtract out the simple terms.

One way is to do a lazy breadth-first expansion: produce a sequence of types, each with one more layer expanded, and just keep going down that list until I either find the exact type I need, or find that it can’t possibly exist. That would work, but my spidey sense doesn’t like it. It feels like I should be able to hone in better on the expansions I actually want. That will probably also give me better error messages, if a user misses a possibility or types out something impossible (like the Cons(True, Empty) above, which is impossible since we’ve already covered all lists that start with True). I don’t think it’s super difficult; but it’s not trivial.

Sophisticated primitives

I mentioned built-in types (aka primitives) in my last post. It turns out, pattern matching lets Effes be a bit more expressive than the standard “here’s an int, go do int things with it” operations. For instance, imagine a world where divide-by-zero exceptions can’t happen! (Big disclosure: I don’t think I’ve ever actually triggered one, so they’re not actually that big a deal to me. Still, I like the idea of getting rid of them at compile time.)

Integers in Effes work something like this:

type Int = IntZero | InvValue

type IntValue @builtin:
  + (other: Int) -> Int: @builtin
  - (other: Int) -> Int: @builtin
  * (other: Int) -> Int: @builtin
  / (other: IntValue) -> Int: @builtin

type IntZero: @builtin
    ...

As you can see, there are actually two int primitives, one for zero and one for everything else. Int is just an alias for the disjunction of those two types, and most of the basic math operations take two Ints (this and other). Division is the exception: the denominator must be an IntValue specifically. That means it can’t be an IntZero — and thus that divide-by-zero errors are caught at compile time.

Here’s how you’d use it:

hitsPerMinute = case minutes of
  IntZero: Error -- or whatever
  IntValue: hits / minutes

In this snippet, minutes comes in as a standard Int. We can’t divide by Int, so we throw minutes into a case expression. If minutes is an IntZero, the result is explicitly some sort of error; if it’s IntValue, we can divide by it.

I’m still not sure if I want to do any such trickery for other primitives. I think I won’t, because other primitives don’t have operations that are undefined (ie, throw an exception) for certain inputs. Floating points, for instance, let you divide by zero, add infinity, or do anything else and always get a value back. It may be NaN, but it’s still a value.

It’s actually a bit interesting to me that other languages don’t have this sort of behavior; all you really need to make it work is pattern matching. My guess is that it’s just not a very compelling problem (as I mentioned earlier, I don’t think I’ve ever actually gotten tripped up by it), so it’s not worth the work to catch it. Effes’ type scheme lets me catch it with minimal compiler trickery, which is probably about as much as it’s worth.

Embracing efficient exceptions in Effes

Generics are wrapping up, and I’ve just implemented built-in types at last, so I’m starting to think ahead to next tasks. One of them is exception handling, and I have an idea that combines throwables and standard return types in a way that should settle the “checked vs unchecked” exceptions battle for good. Take that, Java!

Checked exceptions in Java are useful for defining edge cases at API boundaries. For instance, all sorts of things can go wrong in a SQL query, and it makes sense for the entry point to the SQL API to declare, “hey, this method can throw a SqlException, and you should know that.”

But sometimes the best you can do with that exception is to propagate it. This results in a whole bunch of methods declaring throws SqlException (or throws IOException, or, if the programmer is a bit lazy, the infamous throws Exception). Eventually you get to a method like Runnable::run that can’t throw any checked exceptions, so you just handle the exception generically, probably by wrapping it in a RuntimeException and throwing that. Yo dawg, I heard you like exceptions.

So, the problem is that one piece of code wants to treat SqlException as a checked exception, while another wants to treat it as an unchecked exception. Java doesn’t let you do that.

In Effes, there’ll be two ways to handle an exception: by throwing it, or by returning it. This is where the dynamic nature of disjunctive types comes into play.

All exceptions will be unchecked in Effes, meaning that you can throw them willy-nilly:

executeQuery (query: String) -> QueryResult:
  throw SqlException("dummy SQL engine") -- unchecked

But a method can also include an exception as one of its return type disjunctions:

runQuery (query: String) -> QueryResult | SqlException:
  return SqlException("dummy SQL engine") -- "checked"

The latter method essentially turns the exception into a checked exception, because the resulting variable is a disjunction that has to be picked apart with a case statement:

query = runQuery "SELECT * FROM bobby_tables"
summary = case query of:
  SqlException(msg): throw query
  SqlResults: summarize query

Note that in this snippet, we converted SqlException from a “checked” exception (in that it was a disjunction in the result type) to unchecked, just by throwing it.

Moreover, if a method declares an exception as part of its return type, then it’ll never throw it. Trying to throw it from the method directly results in a compile-time exception, and if it’s thrown from down the stack, it’ll be returned immediately. It’s essentially shorthand for:

runQuery (query: String) -> QueryResult | SqlException:
  try:
    <whatever>
  catch (SqlException e)
    return e

This lets us easily convert unchecked SqlExceptions thrown from <whatever> to the equivalent checked exceptions — thus providing that API border we wanted.

Next up: generics!

I implemented open types in Effes the other day, so I’m gearing up for the next big push: generics! I was thinking of doing tuples first, but they have all of the same complexities as full-blown generics. (You can think of tuples as just sugar around predefined generic classes like Tuple3[A,B,C] — in fact, a bunch of languages do exactly that.)

Generics interact with type disjunction in interesting ways. For instance, what happens when you disjoin Box[A] and Box[B]? Is it a vanilla disjunction, or are disjunctions distributive, so that Box[A] | Box[B] becomes Box[A | B]? Both approaches have their pros and cons.

I’ll call the first one the “standard” option, and the second one the “distributive” one. I’ll illustrate withtype Maybe[A] = One[A] | Nothing, which uses type One[A](elem: A). When you disjoin Maybe[A] | Maybe[B], Effes will expand both Maybes, leading to Maybe[A] | Maybe[B] | Nothing | Nothing, which simplifies to just Maybe[A] | Maybe[B] | Nothing. And then what?

The standard option is straightforward. When you pattern match, you have to specify which of the alternatives you want, filled out completely (with the generic parameter and all). This has the chief benefit of being simple, though the syntax it suggests is a bit clunky:

case mysteryBox of
    One[A](elem): handleA elem
    One[B](elem): handleB elem
    Nothing: handleNothing

The disjunctive interpretation, on the other hand, feels really dynamic, which I like. I think one of the strengths of Effes is that it gives you the feel of dynamic typing with the protections of static typing. In this view of things, mysteryBox isn’t one of three concrete options as above; it’s one of two options, the first of which is itself fuzzy.

For instance, let’s say we’re painting a layer with transparency. A given pixel could have a color or not, and the color could be specified by RGB value or by name: Maybe[Rgb] | Maybe[ColorName]. If there’s already a method paintPixel(color: Rgb | ColorName), the distributive option works perfectly. You don’t need to specify the generic parameter in the pattern match, because it’s unamibiguous to the compiler:

case maybeColor of
    One(c): paint c -- c:(Rgb | ColorName)
    Nothing: paintTransparency

This is nice, but I think there are times when the user won’t want that flexibility; they’ll want to treat each option separately. In a differently-factored version of the above, we may want the non-distributive option, so that we can feed the color to paintRgb or paintNamed, as appropriate.

One argument in favor of the distributive option is that it can simulate the standard option pretty easily:

case maybeColor of
    One(c): case c of
        Rgb: paintRgb c
        ColorName: paintNamed c
    Nothing: paintTransparency

That looks promising, but it’s actually very limited: it breaks down when the container can hold multiple items, instead of just one. For instance, what if we want to paint a row of columns, typed as List[Rgb] | List[NamedColor]? The nested case doesn’t work naturally. At best, we can wait for lambdas, then perform an inline map on the list, but that’s more complicated than it should be.

And lastly, the distributive approach takes a huge liberty with the programmer’s semantics. A List[A] is a homogeneous list of As; a List[A] | List[B] represents either a List[A] or a List[B]. To change that to a heterogeneous list of (A | B) is a big departure from the explicitly-written code.

All of that is to say that the standard system, despite its increased verbosity and stodgy syntax, is almost definitely the right approach. But wait! We can throw a big of sugar at the problem to make the standard approach feel like the hip, distributive one!

The first problem with the syntax was that awkward combo of square brackets and parenthesis: One[A](elem). We can solve this by borrowing from our method declaration syntax, and putting the type inside the parens: One(elem: A). Feels better already.

Next, we can take that one step further. If no type is specified, then the compiler will try to rewrite the case with each of the possible patterns, using the one in the code as a template. So, this:

case mysteryBox of
    One(elem): handle elem
    Nothing: handleNothing

… is just sugar for:

case mysteryBox of
    One(elem: A): handle elem
    One(elem: B): handle elem
    Nothing: handleNothing

One of the things I like about this is that it adds to the sugar of the language without adding to the amount of sugar the programmer needs to think about, because it complements the invoke-on-disjunction sugar so nicely.

One area that’s important to keep in mind is how types with multiple generic parameters will interact with error messages. Consider this snippet:

case foo of
    Pair(o1, o2): doSomethingWith o1 [o2]
    ...

(The syntax is a bit funky, and I may change it; but that just calls doSomethingWith with two arguments, o1 and o2. You can essentially ignore the square brackets.)

Here, o1 may be of type A or B, and o2 may be C or D. But we don’t get all four combinations: if o1 is A, then o2 must be C, and if o1 is B, then o2 must be D. That’s simple enough if you write the expansion out, but if you make a mistake in your head, the error message could confuse you more than it helps. For instance, imagine if doSomethingWith takes an A and a D and you get an error message saying something like “doSomethingWith expected types [A| B, C | D] but saw [A, D].” Doesn’t that look like it’s complaining that it got good inputs? A better message would be doSomethingWith expected types [A, C] or [B, D] but saw [A, D].” Even then, I’m not sure this would be clear to someone who’s new to the language.

Syntax for open types

In my last post, I talked about open aliases and how they can be used to achieve polymorphism. Since then, I’ve been a bit stuck on the exact syntax for them. I don’t know if that’s silly or useful; syntax seems like such a superficial concern, but then again, it makes a difference if a language looks nice.

Here’s the syntax I used in that last post:

open type Boolean:
    def negate -> Boolean

type True:
    def negate -> False: return False
Boolean |= True

This has some nice elements, but it also has some negatives.

• Pro: open type is pretty explicit
• Con: Requires adding open as a keyword, but it’s a natural function name for I/O (like opening a stream)
• Pro: Boolean |= mirrors the familiar |= operator (from other languages we know and love), so that we naturally read it as “Boolean is whatever it previously was, or True”

• Con: |= doesn’t lend itself to being put in the type definition, as opposed to top-level as above. It would have to look something like this:

  type True:
      |= Boolean
      def negate -> False: return False
  

  … but that’s not good because it reads as True |= Boolean, which is the flip of what we really want to say. If we want to say that True is an alternative for Boolean from within True’s definition, we really need the open type to be on the right of the statement.

I tried various other alternatives. For instance, I thought about using ellipses to mark open types (type Boolean = ...), but ellipses are commonly used in code fragments to say “some code goes here,” and I didn’t want to introduce that ambiguity. For adding to an open type, I even went as far as considering True (- Boolean, where (- was supposed to look like ∈. Nice try, but nope.

Here’s the syntax I settled on in the end:

type Boolean = ?
    def negate -> Boolean

type True:
    def negate -> Boolean
    is Boolean
    ...

(Note that in this latest snippet, ... is back to its usual, informal definition of “some code goes here.”) This does require adding is as a keyword, but I’m not too worried about that. My bigger concern with is is that it evokes the “is a” concept from OO, but I think I’m just going to have to bite the bullet on that; everything else I can think of is worse.

Polymorphism using disjunctive types

I haven’t updated this blog in a while, but I’ve actually been making some pretty decent progress on Effes. I’ve got basic types working, method invocation, basic pattern matching and — wait for it! — disjunctive types!

My first attempt at the Effes compiler was a bit messy. I wrote the grammar first and tried to write the compiler over it, but I found I was getting confused as to which parts were complete, which were half-done, which were fully TODO, etc. So I took what I’d learned, chucked the code (and grammar) and started from scratch. This time I worked incrementally, adding features to the grammar and compiler/interpreter in sync and one at a time.

I haven’t made any progress on conjunctive types yet, but I realized I can go a long way without them. I can even get polymorphism, with just a touch of magic. Barely any at all, really.

Let me walk you through it, starting with a pretty simple program:

data type True:
    def toFalse -> False: return False
data type Fale:
    def toTrue -> True: return True

def not (b: True | False) -> True | False:
    return case b of
        True: (b: toFalse)
        False: (b: toTrue)

There are two things going on here: “downcasting” a disjunction to a simple type within each alternative, and disjoining the result types for the case expression as a whole.

First the downcasting. In each of the alternatives (the last two lines), the compiler is able to cast b from True | False to the matched type. For instance, b in the last line is typed as False, not True | False. This means that (b: toTrue) compiles and runs fine. Next, the result type. Since True::toFalse returns False, and False::toTrue returns True, the whole expression returns False | True (which is the same as True | False). If False::toTrue had returned True | FileNotFound, the expression would return False | True | FileNotFound.

So, there’s a tad of cleverness going on, but nothing too weird. If we rename both toTrue and toFalse to negate, we get two unrelated methods with the same name. It works exactly as above, but it’s starting to look polymorphic-ish:

data type True:
    def negate -> False: return False
data type False:
    def negate -> True: return True

def not (b: True | False) -> True | False:
    return case b of
        True: (b: negate)
        False: (b: negate)

Okay, neat. But it’s still not really polymorphic, since there’s no “supertype” to speak of. There’s a bit of repetition with the negate methods, so what about this as a shortcut?

def not (b: True | False) -> True | False:
    return (b: negate)

b is still a disjunctive type in the last line, but the compiler is able to figure out that all of its alternatives have a method negate that takes zero arguments. It thus expands this invocation to the case expression as in the previous snippet. But I can’t provide a new implementation of a boolean type — that is, I can’t make FileNotFound a subclass of boolean — because b in the method arguments is typed specifically to True | False.

What would we even want a boolean type to be? A simple answer is to just make it an alias for True | False.

type Boolean = True | False

The left-hand side defines a type name, and the right-hand side defines a target type (simple type or disjunction). There’s no extra type checking; in this example, the compiler just replaces every instance of Boolean with True | False, as if you had written True | False out. The following methods are identical in every aspect except their names:

f1 (b: Boolean) -> True | False: return b
f2 (b: True | False) -> Boolean: return b

Extending aliases a bit, we can define an “open alias” which is just an alias to which other types can add themselves as disjunctive alternatives. Open aliases also declare methods, which all of their alternatives must also declare (and implement).

-- declare an open alias, Boolean
open type Boolean:
    def negate -> Boolean

-- declare True and False, which each declare a "negate" method
data type True:
    def negate -> True: return False
data type False:
    def negate -> False: return True

-- Add True and False as disjunctive alternatives to Boolean
Boolean |= True
Boolean |= False

Note that True::negate and False::negate are totally unrelated methods. Neither relates to Boolean::negate, because there really such a method. All there is is a requirement that any type that adds itself to the Boolean alias also declare a method named negate that takes no arguments and returns a type that’s contained within Boolean (for instance, True is contained within True | False). For that matter, Boolean itself doesn’t really exist: it’s just shorthand for True | False.

When we put all of the above together, we get polymorphism! To illustrate, I’ll start with the finished program and show how it gets rewritten:

open type Boolean:
    def negate -> Boolean

data type True:
    def negate -> False: return False
Boolean |= True

data type False:
    def negate -> True: return True
Boolean |= False

def not (b: Boolean) -> Boolean:
    return (b: negate)

First, let’s rewrite the open alias as a standard alias:

type Boolean = True | False

data type True:
    def negate -> False: return False
data type False:
    def negate -> False: return True

def not (b: Boolean) -> Boolean:
    return (b: negate)

Next, expand the Boolean alias:

data type True:
    def negate -> False: return False
data type False:
    def negate -> True: return True

def not (b: True | False) -> True | False:
    return (b: negate)

And finally, rewrite (b: negate) as a case expression.

data type True:
    def negate -> False: return False
data type False:
    def negate -> True: return True

def not (b: True | False) -> True | False:
    return case b of
        True: (b: negate)  -- True::negate
        False: (b: negate) -- False::negate

Effes programs don’t have dynamic linking yet, so the translation is really that literal. If and when I do implement dynamically linked programs, obviously that won’t work; the last step, to translate b: negate, will have to do something vtable-like.

Inheritance is dead, long live composition

One aspect of the type system that’s always left me unsatisfied is its asymmetry against traditional object-oriented languages. Most OO languages formally recognize inheritance within the type system, but not composition. Given that Effes formally recognizes composition, shouldn’t it not recognize inheritance?

This is important to me for more than just aesthetic reasons. Recognizing both patterns makes for a more complicated type system, but worse, it gives the programmer a too-easy crutch. One of the reasons I turned to Haskell when I was interested in learning about functional programming was that I wanted to force myself to really start thinking in FP terms. If I were learning on a language like Scala, which combines OO and FP patterns, it’d be too easy to fall back on familiar ways of looking at a problem.

In the same way, I want Effes to force me into thinking with a composition-based perspective, rather than letting me have another inheritance-based language with a shot of composition flavoring.

The hurdle, though, has been polymorphism. It’s useful to have a method that takes Sizeable objects, whether they’re List, Map or anything else that’s Sizeable. It’s also nice to have that size method on both List and Map.

My solution is to replace “List is-a Sizeable” with “List has-a Size component:”

type List[A]:
    has Size
    add A -> List[A]
    -- etc...

For a user of List to get to the size method, they’ll need to access its Size component, which can be done explicitly with (list @ Size) size. But, if the Size component doesn’t conflict with any other of List’s components, you can implicitly access it: list size. And similarly, if a method takes a Size argument, you can explicitly give it the list’s Size component by calling theMethod (list @ Size), but you can also just call theMethod list, and the compiler will figure out that you want to pass it the Size component.

A nice side benefit of all this is that it provides a nicer answer to the question of conflicting components, which I addressed in earlier posts. Rather than handling conflicts at composition time by knocking out some components, I’ll allow the conflict there, and force the user into stating which component they want, when there’s a conflict. So for instance, if List and Set both have an add method, you can’t write listAndSet add foo. You have to explicitly call out the component you want: (listAndSet @ List[Foo]) add foo.

There are two syntax details I have yet to work out with this all-composition scheme.

The first involves cleaning up the code when a type has only one component: ConsList[A] “implements” List[A], for instance. Everything is fine from a useage perspective, but it’s a bit awkward to write out:

type ConsList[A]:
    has List[A]:
        -- all of the ConsList code goes here

So, I’m thinking of allowing a special “is-a” statement for this situation, which just lets you inline the second line in the above:

type ConsList[A] is List[A]:
    -- all of the ConsList code goes here

The second is in cleaning up implementations of nested types. Remember how List had a Size component above? Does that mean we have to implement it as:

type ConsList[A] is List[A]:
    add elem: ...
    Size:
        size: ...

or can we just write:

type ConsList[A] is List[A]:
    add elem: ...
    size: ...

My inclination here is to mirror the call site rules: you can inline the method definitions for a given component if that component doesn’t conflict with any other components. That keeps things simple, consistent and clean.

An alternative to function overloading

Method overloading has always struck me as a bit clunky. It separates a method’s main code from helper code, adds clutter, and doesn’t play nicely with inheritance (at least in Java). On the other hand, its ability to provide variants for a given method is useful. I think Effes provides a better alternative.

Overloads provide two axes by which you can create variants of a method: they let you omit arguments by supplying a reasonable default, and they let you pass in a value whose type is similar to (but different from) the “main” type. For instance, you can imagine a method add(double n, RoundingMode mode) with an overload add(long n). That second overload would call the first variant, casting the long to double and using RoundingMode.HALF_UP.

Lots of languages let you omit arguments by providing default values: add(n, mode=HALF_UP) or similar. Effes will, too, but it’s tough for a statically typed language to handle the arg-of-similar-type problem. The only thing you can really do is to accept a supertype, like add(Number n). But to do that, you need control over the type hierarchy, which you obviously may not have.

In Effes, you can use disjunctive types instead:

add(n: Double|Long):
  d = case n of
    Double: n
    Long: n toDouble -- e.g., if there's no automatic type promotion
  ...

Of Optional and nulls

Here at last is that rant about Optional<T> I've promised for so long. Let me preface it by saying that I am not about to propose an ideal way of handling nulls in Java; I don't think Java's null handling will ever be great. That said, there are better and worse ways of doing it, and I think Optional<T> isn't the best way. What's worse, it's edging out a better way.

For the unfamiliar, Optional<T> is a Guava class that aims to eliminate NullPointerExceptions. It has two forms: Optional.absent() and Optional.of(T item). Rather than a method passing back a nullable Foo, it returns an Optional<Foo>. You then call isPresent(), followed by get() iff the item is present.

Optional<Foo> myFooOpt = tryGetFoo();
if (myFooOpt.isPresent()) { // like a != null check
    Foo myFoo = myFooOpt.get();
    // work with the foo
} else {
    throw NoFooFoundException(); // or whatever
}

The idea is that since you have to call get() to get at the Foo, you'll probably remember to check isPresent first — and thus, no NPEs. It seems reasonable enough, but there are two big problems with it. First, it's verbose; and second, it's not backwards compatible.

The verbosity comes down to a lack of pattern matching in Java. Optional<T> is inspired by functional programming languages that have pattern matching — think of it (very roughly) as an instanceof check combined with an un-constructor. Here's how you'd use Haskell's equivalent of Optional<T>:

case tryGetFoo of
    Just foo -> handleFoo foo
    _ -> handleNoFoo

See how much cleaner that is? Optional<T>-type constructs really benefit from a terse way to get at the wrapped object. Pattern matching lets you do this two ways: by combining the isPresent() and the get(), and by therefore eliminating the need for that temporary, throwaway reference to myFooOpt.

Java is trying to move away from verbose boilerplate; one could argue that the driving force behind both Java 7 and 8 is conciseness, not new features. So why is the Java world embracing the overly-verbose Optional<T>?

The backwards compatibility problem is more clear-cut: existing libraries can't be retrofitted with Optional<T> without huge changes to how overload and method resolution is handled. For instance, Map.get returns V — you can't just change it to return Optional<V> without breaking a lot of code.

Before Optional<T> got cool, one idea people had was to use annotations to do static analysis on the code. Mark a field as @Null, and you know it can be nullable; try to use it without checking for nullity, and you'll get a warning. Nullity can be propagated through result types and arguments, and it all checks out at compile time.

The best part is that you can retrofit it to existing classes. Map.get will never return an Optional<V>, but it could return a @Null V.

There were a few different attempts at these checks, each leading to different sets of annotations. If I had it my way, we'd see one of these — preferably a concise one — get Oracle's official blessing and widespread usage.

A type checker has to be conservative, and that means that you'd have to assume that legacy code always returns nullable references. On the other hand, for new code you'd want an un-annotated method to be assumed to be @NotNull (to cut down on verbosity). This mismatch could be solved in three ways.

• Classes compiled annotated with a new @NullChecked annotation would also have their methods assumed to be @NotNull.
• All newly compiled code would assume @NullChecked
• The type checker could take additional inputs in the form of files that list methods which should be treated as @NotNull regardless of their bytecode.

The third one of those would mean that you could mark methods as not-nullable without touching their bytecode at all. This could be useful for some serialization issues, but more importantly, it would let people locally update projects without waiting on their maintainers.

With that migration path in place, compilers could start treating unsafe dereferencing as errors rather than warnings. And maybe, just maybe, Java can recognize it as important enough as to warrant syntactic sugar: T? as shorthand for @Null T. Kotlin employs a similar trick, and while I haven't actually used it, it sure looks nice.

There are other tricks you can do with annotations that expose a lot of power (including how it interacts with subtyping, etc), at the cost of more complexity. I'm not sure Java needs all those — but even without any of them it's still at least as powerful as Optional<T> — with the added benefit of backwards compatibility.

I'm not sure why annotation-based static analysis never caught on. Maybe the pushes were too fragmented, and developers weren't willing to hack in ugly ways to solve backwards compatibility (like my "additional inputs" file)? Maybe the edge cases are just too many and complicated? A quick google search didn't give me any answers.

An argument for using both composition approaches

A recap of where we are with object composition: In my last few posts about object composition, I initially thought that simple composition methods don't work because of mismatches between compile-time and run-time information.

Instead, I thought I'd have to go with a model analogous to Schrodinger's cat, where a composed object's methods can be bound to multiple implementations at the same time. Each of those implementations is run, and the results are themselves composed into a single object for the result value. Like a cat that's both alive and dead, the method is bound to both implementation A and implementation B — and its result is both A' and B'.

There's a certain beauty to that, but it's pretty complicated. I also suspected it may result in slow code as objects get more and more complicated at runtime. So I thought some more and came up with a solution that leads to a simple, non-Schrodinger object.

But maybe these concerns are premature on my part. I'm basically trying to do two optimizations — for simplicity, and for performance — without having measured how bad they are.

On the other other hand, back when I first proposed the Schrodinger approach, I noted that eventually you'll need to collapse the wave function, so to speak. At the end of the day, you need to print "I'm a tea pot" or 3.14159; you can't print their superpositioned composition.

So then, maybe the solution is to use both approaches. The Schrodinger approach will be the standard composition mechanism (not in any formal way, but as a coding recommendation), while the "simple" approach will be used to collapse the wave.

To anchor things, let's call the standard composition operator <>, and the simple one </ (you'll see why in a bit).

I'll also define a reserved type Simple which can only be composed into other objects using the simple composition operator. So, if a method takes Simple Foo Bar and you have a Foo Bar (which may be superpositioned), you need to compose it using the simple operator: Simple </ myFooBar.

This handles the print case, for instance. stdout.print will take a Simple String, and it's up to the caller to ensure that its variable is already Simple, or to collapse it otherwise.

One of the lingering questions I had in the back of my mind was what to do when two objects of the same type are composed: SomeInt(1) <> SomeInt(2). Now the answer seems obvious. With the Schrodinger composition operator, just superposition them both in. With the simple operator, the left one will get folded in first, and the right one will then collide and be discarded.

That's why I picked </ as the operator. It looks like it points to the left, and thus conveys that the left operand has precedence in case of collisions.

There's not really a compelling argument for this complexity. Why don't I just stick with the simple composition approach? Basically because I think the Schrodinger variant seems fun and worth playing around with.

Saving object composition from complexity

In my last post about object composition, I concluded that simple composition approaches don't work because of the mismatch between compile-time and run-time information. But I realized a few days later that I can define a simple composition.

The trick is to cheat: come up with the answer I want first, and then work backwards to fill in the rest!

What I do is to add a new step at the beginning of composition. In this step, we start out with a "composition target." We then fold the composition operands' components in two phases: first the ones that are part of the target, and then the rest.

What's the target type? At compile time, it's empty; at run time, it's the compile-time type.

As always, I'll illustrate with an example. In fact, I'll use the same example as before. Here's the background stuff:

type List[A] =
    ... (put/get)
    size -> Int
type Box[A] = ... (put/get)

type Container:
  isEmpty -> Bool -- abstract method

type Container Box[A]:
  @override isEmpty -> Bool = TODO

intsList : List[Int] = list(1, 2, 3)
intsBox : Box[Int] = box(4)

tmp = intsBox <?> Container
intsContainer : Container = tmp

... and here's the composition:

composed = intsContainer <?> intsList
composedSize = composed2.size

The problem we had before was that intsContainer is only a Container at compile-time, but it's a Box[Int] <?> Container at runtime. When Container is composed with List[Int] at compile time, no conflicts are found, so the resulting type is Container <?> List[Int]. But at run time, Box[Int] and List[Int] collide and cancel each other out, and the resulting object is only a Container, which doesn't have a size method.

The composition target saves the day. Everything works the same at compile time, leading to a type of Container <?> List[Int]. At run time, we take the following steps:

1. Decompose both operands, so that the composition is (Box[Int] <?> Container) <?> List[Int].
2. The target type is Container <?> List[Int], so take those components out of the composition and fold them into the resulting object. We now have:
   • A folded object of Container <?> List[Int]
   • Remaining object of (Box[Int] <?> ∅) <?> ∅, which simplifies to just Box[Int].
3. Fold the rest of the components (just Box[Int]). Box[Int] collides with List[Int], so discard it — and there's nothing else to fold.

So the resulting object is a Container <?> List[Int], which is exactly what we expected at compile time!

I wrote above that the target type at compile time is empty, but even that can be improved upon: it's the closest available explicit type declaration, if any. So, if you had:

boxContainer = intsBox <?> Container
composed2 = boxContainer <?> intsList

... then it would result in a compile-time error, since intsBox : Box[Int] collides with intsList : Box[Int] (they both define put and get methods). But if you had:

composed3 : List[Int] = boxContainer <?> intsList

... then the target type is List[Int], meaning that this gets folded in first. When the conflict with Box[Int] is detected in the second folding stage, Box[Int] is discarded. The resulting type of the composition (this is all at compile time, remember) is List[Int] <?> Container, which is then "upcast" to List[Int] when it's assigned to composed3.

I'm going to have to maybe-kill the cat

In my last post, I discussed problems with the runtime binding of composed objects: if object a has a method foo, and object b also has a method foo, then how does the composed object (a <?> b) behave? In this post, I'd like to explore a separate but related pair of problems: what's the type of a <?> b, both at run-time and compile-time?

(Before you get too far into this post, a disclaimer: this post describes a method of composition and then explains why it doesn't work. If that strikes you as meandering and pointless — if you prefer to read about ideas that might work, rather than those that definitely won't — then you might want to skip this post.)

As before, let me set this up with an example. As an added bonus, you'll get to see the latest revision of Effes' syntax, which is pretty close to complete (now I really mean it!). Since I haven't laid out how composition works, I'll use <?> as a placeholder for "some variant of composition." With that said:

type List[A] = data Node(head:A, tail:List[A]) | Nothing
  put e:A -> List[A] = TODO
  get -> (Maybe[A], List[A]) = TODO

type Box[A] = Maybe[A]:
  put e:A -> Box[A] = TODO
  get -> Maybe[A] = TODO

myList : List[Int] = TODO
myBox : Box[Int] = TODO
myContainer = myList <?> myBox

Here we have two simple types: one representing a linked list, and one representing a box that can contain zero or one items. Their details aren't important. We also have three references: one of type List[A], one of Box[A], and one representing the composition of the first two.

As I discussed in the last post, we have some options with a call like myContainer.put 1. We can take the Schrodinger approach, in which we invoke put on both components of myContainer and then compose those two results; or we can pick one as the "winning" binding and only invoke it.

Let's say we pick the single-bound, "winner" approach; that's the option I was leaning towards in the last post. To make it concrete, let's say that the left-hand side always wins out. That seems reasonable, but what about this situation:

myContainer2 = myContainer.put 123
myVal : Maybe[Int]
myVal = case myContainer2 of
  Box[Int] -> myContainer.get
  _ -> Nothing

In this snippet, we check to see if myContainer is a Box[Int]. It is, so the first pattern will match. This casts myContainer2 to Box[Int] and, within that new context, invokes get. Note that get here has to be bound to the Box version; the List[A] version has a different return type (it returns a pair containing the list's possible head and its tail).

The problem is that myContainer.put was bound to the List[A] method, meaning that the Box component of myContainer never had 123 inserted into it: the value of myVal is Nothing, not 123! This is fully consistent, but it's confusing and violates the principle of least surprise. There has to be a better way!

One possibility is to limit composition such that myContainer2 does not have a runtime type of Box[Int]: the second (catch-all) pattern matches, and the value of myVal is Nothing.

Of course, we always want the runtime type to be a subtype of the compile-time type, so this new approach means that the composed object's compile-time type can't include Box[Int]. We can't generalize that to all compositions, or else the whole idea of composition falls apart and becomes shorthand for the not-very-useful function a <?> b = a.

We can come up with a more precise limit on composition, one that doesn't just throw away the RHS altogether. One approach to compose objects in multiple phases. Here's one such algorithm, in rough terms:

1. Decompose the RHS object to its constituent objects.
2. Fold each one of those into the LHS, one at a time. As you fold each object, check to see whether it has any methods that conflict with methods on the composed object; if so, ignore that object (don't fold it in).
3. Check whether the resulting object has any abstract methods (that weren't given a concrete definition in the composed object). If so, remove the objects that introduced those methods.

These three phases happen separately for both the compile-time type and the runtime type. Here's an example, starting with some types and some objects:

type List[A] =
    ... (put/get, as above)
    size -> Int
type Box[A] = ... (put/get, as above)

type Container:
  isEmpty -> Bool -- abstract method

type Container Box[A]:
  @override isEmpty -> Bool = TODO

intsList : List[Int] = list(1, 2, 3)
intsBox : Box[Int] = box(4)

intsContainer1 = intsBox <?> Container

The List[A] and Box[A] types are as before, except that List[A] now also has a size method.

Let's look at that last line. The LHS is Box[Int] with methods put and get, while the RHS is Container with just one method, isEmpty. There's no overlap in methods, so the composition is straightforward and results in Box[Int] <?> Container for both the compile-time and runtime type.

Okay, so that case works fine. But what about this?

intsContainer2 : Container = intsContainer1
composed2 = intsContainer2 <?> intsList
composedSize = composed2.size

At compile time, that last line looks like Container <?> List[Int], which has no conflicts and thus doesn't remove any types. But the Container component's isEmpty method isn't implemented, so it's removed: the resulting type is List[Int]. We call its size method, which is a pretty reasonable operation to call on a list.

At runtime, the composition looks like (Box[Int] <?> Container) <?> List[Int], and there is a conflict: List[Int]'s methods collide with Box[Int], and we therefore don't fold List[Int] into the composition. That means that the resulting type is just Box[Int] <?> Container — the inverse of the compile-time type! And in particular, there's no size method on that object. Boom.

I've tried a few variants on this sort of decompose-and-recompose theme: decomposing both sides, different handling of abstract methods, etc. Inevitably, the mismatch between runtime and compile-time types always blows up in my face. I don't think there's a way around it.

Unfortunately, I think this leads me to the conclusion that if I'm going to do composition, I have to do composition all the way: Schrodinger-style. This means I'll need to figure out various issues about collapsing the wave form: how does pattern-matching work, and what happens when an object is composed with an object of the same type? For instance, how does "foo" <?> "bar" work?

Of object composition and a maybe-dead cat

There's a problem with Effes that could prove deadly, at least to object composition: composed objects can conflict in ways that can't be caught at compile time, and there's no satisfying, simple way to resolve the conflicts. It's a problem I realized a few weeks ago while thinking about various use cases for composition.

To warm up, consider these types:

• Animal
• Dog is Animal
• Happy
• (Happy Dog) is Animal

Dog and Happy are simple types, and (Happy Dog) is their conjunction. Animal is an "interface-y" type with implementations provided by Dog and (Happy Dog). Let's say balto has a compile-time and runtime type of Happy Dog, and that Animal provides a method speak. Does balto speak invoke the implementation for Dog or Happy Dog?

That's not so tricky (I said it was a warmup!). Happy Dog is intuitively more specific than Dog, so we should invoke its speak. Let's try something just a bit trickier:

type Animal:
  speak -> String
data Dog is Animal:
  speak = "Woof!"
data Cat is Animal
  speak = "Meow!"

balto = Dog
felix = Cat
dogCat = balto @ felix
spoken = dogCat speak

This is trickier. The object dogCat is both a Dog and a Cat, both of which provide equally-specific overrides of Animal::speak. Which gets invoked? If your instinct is to just reject that at compile-time, consider this slightly more dynamic variant:

type Animal:
  speak -> String
data Talking, Dog, Cat -- no inherent relationships to Animal
type Talking Dog is Animal:
  speak = "Woof!"
type Talking Cat is Animal:
  speak = "Meow!"

balto = Talking Dog
felix : Cat = Talking Cat
dogCat = balto @ felix
spoken = dogCat speak

Here, felix has a run-time type of Cat but a compile-time type of Talking Cat, which is Animal. This means we can't detect a conflict at compile time, but dogCat still has two equally-specific implementations of speak at runtime.

We can come up with something clever based on compile-time contortions: take only the left object's implementation when they're composed, for instance, or take only the one whose compile-time type provides an implementation and fail to compile if they both provide an implementation. These would all work for the examples so far, though they're not very inspiring.

The problem is that Effes, like other functional languages, lets you do pattern matching — that is, runtime type checks. This is the killer:

type Animal:
  speak -> String
data Talking, Dog, Cat
type Talking Dog is Animal...
type Talking Cat is Animal...

balto : Dog = Talking Dog
felix : Cat = Talking Cat
dogCat = balto @ felix

spoken = case dogCat of
  Animal: dogCat speak
  else: "whatever"

balto and felix never have a compile-time type of Animal, and neither does dogCat (its compile-time type is just (Cat Dog). Yet both of them have a runtime type of Animal, and we intuit that dogCat should, too. The question, again, is what that speak method does.

There aren't many good, simple solutions to this that I can think of. There are bad, simple solutions; and there are interesting, complex ones. These are the ones I came up with:

1. A runtime failure at balto @ felix, since it would create a possibly ambiguous object.
2. A runtime failure when dogCat is matched against Animal and then invokes speak, since this is the aforementioned ambiguity.
3. Pick one of the implementations by some arbitrary rule, like the left-hand side of the conjunction.
4. Run both methods and return the conjunction of their results.

I really want to avoid runtime failures here: it's too easy to stumble into this case. The last option is interesting in a computer sciencey way, but it creates a possibly complex world. Let's call this the Shroedinger approach, since it creates an object that's like a superpositioning of barks and meows. What if we then run that object through a pattern match?

who = case spoken of
  "Woof!": "It was a dog"
  "Meow!": "It was a cat"
  else: "What was it?"

If we took the Shroedinger approach for speak, then spoken is ("Woof!" @ "Meow!"); it can match against either of the first two cases. Pattern matching traditionally executes just the first branch that matches, but this approach is inconsistent with the Shroedinger approach that got us this spoken in the first place. So, let's stick with the Shroedinger philosophy of taking all of the cases and conjoining them: the resulting object is a conjunction ("It was a dog" @ "It was a cat"). Of course, the expression "It was a dog" could instead be some method, one which itself might return a "superpositioned" object; and the same could be true of "It was a cat". By the time we finish the case statement, who might be pretty darn complex!

In short, we have three options for handling ambiguity: runtime failure, subtle behavior that depends on composition being non-commutative, or subtle behavior in which each ambiguous decision split the program into a more ambiguous runtime state. The last of those options is the most novel and interesting, but eventually we have to collapse the wave-form: most of the time, we need to end up printing either "the dog says woof" or "the cat says meow."

One option is to provide both philosophies: two parallel case statements, one of which executes all branches and the other of which executes the first it finds. A similar option is to provide a sort of decomposition; given an object with a compile-time type Foo, return an object which is only a Foo, with all other composed objects removed.

Even if we take this approach, all this superpositioning makes the code a lot less strictly typed. The type system provides a very low bound on each object's guarantees! Traditional type systems generally make guarantees like, "it'll be a list, but we don't know what kind of list." Shroedinger-Effes will be able to say "it's an empty list, but we don't know if it's also a non-empty list."

It also raises the question of whether methods are overridden, or if they're always superimposed. Remember our first Balto, the Happy Dog? We intuited that its speak should override the "less specific" implementation provided by Dog. Does that still happen, or do we Shroedinger it up and invoke both?

There is one simpler option. I wrote above that because balto and felix each have a runtime type (but not compile-time type) of Animal we'd want their composed object to also have a runtime type of Animal. What if this weren't the case? That is, that runtime behavior could only ever override types and methods that are known at compile time, but not to perform arbitrary runtime checks such as whether dogCat is an Animal? That may be the way to go; I'll think on it for a bit.

Maybe it's optional?

A lot of functional and functional-inspired languages don't have the concept of null. Instead, they have types called Maybe or Optional — basically a box of 0 or 1 items. Effes is going to take that approach, but I might put a twist on it.

In a nutshell, the idea behind Maybe (I'll settle on Haskell's terminiology) is that there's a Nothing that represents the absense of something, a Just Foo that represents one Foo, and a Maybe Foo type which can be either a Nothing or a Just Foo.

Like other functional languages, Haskell has syntax (called pattern matching) that's kinda-sorta like an instanceof check plus a downcast in Java. Putting it all together looks something like this:

sayHi :: (Show e) => e -> String
sayHi Nothing = "Nothing to say hi to!"
sayHi (Just e) = "Hello, " ++ (show e) ++ "!"

(The (Show e) => syntax just means that e has a show method, which is like Java's toString.) In Effes, a direct translation would be a disjunctive type:

data Nothing
data Just[A] = elem : A
type Maybe[A] = Nothing | Just[A]

sayHi (m:Maybe[A Stringable]) -> String:
  case m of
      Nothing: "Nothing to say hi to!"
      Just e: "Hello, {{e}}!"

Because Effes has a more flexible type system, we can actually get away without the Just part of the Maybe pair. Instead, it looks something like this:

data Nothing
type Maybe[A] = Nothing | A

sayHi (m:Maybe[A Stringable]) -> String:
  case m of
      Nothing: "Nothing to say hi to!"
      e: "Hello, {{e}}!"

There's not a really strong driving force for this, except that it seems a bit cleaner. Instead of a Maybe being "either nothing or a box of one something," it's "either nothing or one thing." Plus it takes advantage of my cool new type system, so that's nice too.

The problem is when the A type is itself a Maybe: Maybe[Maybe[A]]. If we see that it contains a Nothing, does that mean we didn't have anything, or that we had one Nothing? To prevent unreachable code, I'd probably want the type checker to reject this altogether: Maybe[Maybe[String]] would be a type error.

That's not terrible, I guess, but the erroring type could be nestled in some data structure. For instance, if a linked list uses Maybe to signify an end, then LinkedList[Maybe[String]] wouldn't compile — and probably with some unintuitive or frustratingly un-actionable error message.

On balance, I'm leaning towards keeping the Just type. It doesn't add much complexity to the Maybe type, pattern matching keeps the call sites simple, and it eliminates ambiguity.

(Finally!) A use case for composed objects

I've been playing with Effes syntax off and on for the last couple weeks, and I happened across a use case for conjunctive types. I'll admit: even though I thought the idea was neat when I came up with it, I never knew what I'd use it for — it just seemed like it should be useful for something. So it was nice that a use case came up without me actively looking it.

Having mostly settled on the smaller syntax stuff like function declarations, I decided to start putting it together by writing a JSON parser. The JSON type itself is a disjunctive type, which is very intuitive:

type Json = Null | String | List[Json] | ...

But as it turns out, conjunctive types — informally, "TypeA = TypeB and TypeC" — are useful as the parsing function's result type.

Parsers often break the principle of single responsibility for the sake of usability: they're responsible for parsing text and providing context in the event of failure. It's not a major problem, but it does pose some design questions. For instance, how much context should the parser keep? The current line number? Column number? Previously seen text? How much previous text? Note that it doesn't need any of this for its main task, which is parsing.

In my parser, I solved this by having the parser return either a Json object or a failure composed with the remaining string: Failure("expected a comma") @ string (I've picked @ as my composing token.) The full result type is Json | (Failure @ String).

That doesn't sound exciting at first, but remember that a string is just a list of characters, and a character is itself an object — meaning it can itself be composed! In other words, what the parser thinks of as List[Character] might actually be List[Character @ MyContextFoo]. That context component could contain the current line and column position, the previous few chars of context, etc.

That means that the parser is agnostic of all that contextual information, which after all it doesn't need. It keeps chipping away at the string, oblivious of the fact that the characters it sees are in fact rich objects instead of plain Chars; in fact, the string is oblivious of that, itself.

At the application level, parsing is now a three-step process: get the input string, transform it into a string of "rich" characters (basically by mapping each character and then using those mapped characters to create a new string), and parsing that enriched string.

One problem I haven't resolved yet is how to statically type all this. It's not enough for the programmer to know that the string is enriched; how can they convey this to the type system in such a way that the information gets through to the result type? This is important, because otherwise the language devolves to a static-dynamic hybrid. That's a slippery slope that will probably lead to mostly dynamically-typed programs.

I don't want the parser to have to know that it's working with a subtype of String if that's only relevant to the result type. If nothing else, that puts the onus on the API author to always use general (and presumably more verbose) declarations; the strength of this idea is that it puts the power in the call site's author's hands. On the other hand, I do want the input string's "subtype" to bubble back up, so that the return type is promoted to something like Json | (Failure @ MyCoolString). I have some ideas, but the devil is in the details...

Conjunction disjunction, what's your function?

It's time to turn my attention to functions. Like virtually any language, Effes has functions; like any language written in the last few years, those functions are data. (At what point does the term "functional programming language" start to lose its meaning, given that every language these days incorporates FP principles?)

Every function in Effes has a type, which is just its signature. For instance, doubler(i : Int) = i * 2.0 would have a type of Int -> Double. Subtyping basically follows the Liskov substitution principle: f : Vehicle -> Door is a subtype of g : Car -> Part because you can use f anywhere you'd be able to use g.

Like data types, function types can be composed into conjunctive and disjunctive types. Take the following:

data Cat, Person
countLegs : (Cat -> Int) = c -> 4
sayHi : (Person -> String) = p -> "Hi, I'm #{p.name}"

countHi = countLegs sayHi

countHi is a conjunction of countLegs and sayHi. Invoking this function doesn't chain or compose them; only one will get invoked. Think of it as a box that contains both functions: invoking this box means opening it, taking out one of the functions, and using it.

This follows the data trait analogy: a Cat Person type refers to an object that is both a feline and a human; it also can be thought of as two separate objects stuck together. When you have a Cat Person and ask for its fur type, you're looking at its cat-like nature; when you ask for its social security number, you're looking at its person-like nature. Similarly, countHi has both a countLegs-like nature and a sayHi-like nature.

(There's a slight difference here in that a conjunctive data type can be used in functions that look at both of its aspects; this doesn't apply to functions.)

This means that the input to countHi can either be a Cat (in which case countLegs is invoked) or a Person (in which case sayHi is invoked). In the first case, the result is an Int, and in the second case it's String. Putting that together, we get a type of (Cat | Person) -> (Int | String). More generally:

(Ia -> Ra) (Ib -> Rb) : (Ia | Ib) -> (Ra | Rb)

Disjunctions follow the same analogy; a Cat | Person type refers to a single object which is a feline or person, so functional disjunctions work the same way. Imagine a type that said "I'm either countLegs or sayHi". To pass an argument into it, you'd have to guarantee that the argument could be passed to either function; it would have to be both a Cat and a Person. Depending on which function got invoked, the result would be either an Int or a String.

(Cat -> Int) | (Person -> String)
 : (Cat Person) -> (Int | String)

(I0 -> R0) | (I1 -> R1) : (I0 I1) -> (R0 | R1)

Notice the symmetry here: The input to a conjunction of functions is the disjunction of their inputs, while the input to a disjunction of functions is the conjunction of their inputs. In both cases, the result is a disjunction of their results.

One edge case is when the input to a conjunction is composed of both input types. For instance, what happens if we break out the beakers and engineer a Cat Person? If we pass it to a conjunction countLegs sayHi, both functions in that composed function can process it. Which gets to? (This isn't a problem for a disjunctive type, since its object is just a single function.)

I'm not positive how to handle this case. One solution is to have both functions process it, and then compose the result. So, passing Cat Person to countHi = countLegs sayHi would result in a (4 "Hi, I'm Yuval") : (Int String).

Subtyping and function resolution (at last!)

I've been putting off for too long my ideas for subtyping and function resolution, because I've wanted to get things juuust right. Instead, I'm going to just outline my ideas and move on, because I want to start coming up with a grammar and writing some actual Effes. I've been dragging my feet for too long!

So, subtypes first, then function resolution.

Type hierarchy in Effes

• A is a subtype of B if there is a "class-based" implementation that says B is A. For instance, if we declare that Stack[A] is Sizeable where..., then Stack[A] is a subtype of Sizeable
• A is a subtype of B if A is a conjunction type whose parts include B. For instance, FourWheeled Vehicle is a subtype of FourWheeled and Vehicle.
• Union types act as a single unit and don't establish any subtype relationships with their components. So:
  
  • Cat | Mouse isn't a subtype of Cat or Mouse.
  • Neither Cat nor Mouse are a subtype of Cat | Mouse.
  • However, since Cat | Mouse is a single unit, Cute ( Cat | Mouse) is one of its subtypes.
• Any type is of course a subtype of itself.
• Without getting into too much details, subtypes work with the components of conjunction types, not just the full conjunction. For instance, if Box is a subtype of Container, then Big Box is a subtype of Big Container.
  

I think for generic types, I'll say that Box[Gum] is a subtype of Container[Candy] if Box is a subtype of Container and Gum is a subtype of Candy. This is extremely up for grabs; it can wreak havoc on collections, but that's because they're mutable. Effes has a much stricter set of restrictions on mutability, which I think eliminate the problem.

Function resolution

In a nutshell: functions are bound to an object according to the most specific type information known about it at compile time. (That last bit is important!) For each function f, find the most specific subtype that defines f, and bind that version of f to that object.

-- Define some types
data Animal; Ascii; Cat; Dog
Dog is Animal
Cat is Animal

-- Define some methods
speak(a:Animal) : String = "Zzzz" -- all animals sleep
speak(c:Cat) : String = "Purr"
speak(c:Ascii Cat) : String = ">^-^<"

-- Invoke them
speak(Cat) -- Purr
speak(Dog) -- Zzzz
speak(Ascii Cat) -- >^-^< 
peak(Dog Cat) -- compile-time error
speak(Ascii Animal Cat) -- >^-^<

The first three of the function invocations should be pretty straightforward. The fourth case is a compile-time error because Dog Cat is "equally subtype-y" to both Dog and Cat, so the compiler doesn't know which method to use. (Maybe I'll provide some overriding behavior in the future, but for now I'm just going to disallow it altogether.) The last one is an edge case — hey, every language has to have 'em! The reason is that type conjunctions are commutative and associative: (A B) C is the same as B (C A). So, even though Ascii Animal Cat doesn't look like anything meaningful, it can also be expressed as (Ascii Cat) Animal, which is a subtype of both Ascii Cat and Animal (as well as of Ascii and Cat, but that's not important for this example). Since Ascii Cat is itself a subtype of Animal, it is the most specific subtype and thus supplies the function. One last thing, which is the bit about binding at compile time. Let's tweak the menagerie a bit:

data Ascii; Hungry; Cat

speak(c:Ascii Cat) : String = ">^-^<"
speak(c:Hungry Cat) : String = "Meow!!" -- at 5am...
speak(c:Hungry Ascii Cat) : "4d 65 6f 77 21 2`"

getKitty() : Cat = Ascii Cat
c1 = getKitty() c2 = Hungry c1

In this example, c1 has a compile-time type of Cat and a runtime type of Ascii Cat. However, where the object was created (namely, the only expression in the body of getKitty), it had a compile-time type of Ascii Cat, so speak(c1) is bound to speak(c:Ascii Cat) and would result in ">^-^<". The last line is where things get potentially unfamiliar. Even though c1 has a runtime type of Ascii Cat, it has a compile-time type of just Cat, so Hungry c1 has a compile-time type of Hungry Cat, not Hungry Ascii Cat. This means speak(c2) would result in "Meow!!".

This feels a bit weird at first blush: it's a blend of polymorphism and... something that feels un-polymorphic. I may change my mind, but the reason I like it is that you can know, easily and deterministically, how functions will be bound just by looking at where an object is created. That is, you don't have to reason about where the object came from and what its runtime type might be; you just look at what it is, and there you go.

The basic rule is that you can't know exactly how an object will behave unless you create it.