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
True | False to the matched type. For instance,
b in the last line is typed as
True | False. This means that
(b: toTrue) compiles and runs fine. Next, the result type. Since
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
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
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
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
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
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.