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.

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.