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.

Generics are kinda done

So, fun story: I haven’t updated this blog in forever and a day. (Fun corollary: “forever” is 292 days in my world.)

Basically, other stuff came up (new job, life stuff, blah blah) and Effes got put on the backburner for a while. I started revisiting it about a month ago, a couple hours a week, and I’m now more or less officially back on the project.

Generics are… done? Well, not done, but far enough along that I feel comfortable moving on to other things. The syntax is a bit clunky because I don’t have type inference yet (so, maybeInt = Maybe[Int](5) instead of maybeInt = Maybe(5)), and methods can’t declare generic parameters. I’m convinced that what I have will be a good basis for those, though.

The whole exercise was more challenging than I expected. My code ended up being confused as to when a type was reified, and in the end, I went with the approach that a type is always considered reified, but can be “re-reified” at will. That is, Foo[T] is considered reified to the generic type T on Foo, but that can be re-reified to map T on Foo to, say, Int to produce Foo[Int].

So, I’m going to leave generics not-quite-finished and move on to other projects. My next one is built-in types. Despite the examples above, you can’t actually declare or instantiate integers yet — or strings, floats or any other primitive type. (The only thing close to a primitive you can use today is a Boolean, and that’s because it’s just a disjunction of two normal, no-arg types, True and False.) The lack of primitive types makes for some un-interesting tests (maybeTrue = Maybe[True](True)… Zzzzz), which is as good a motivator as any to get things done.

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.