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.

Statements and expressions: an exploration of ambiguity

I've been working on the parser for Effes a bit, and I got a bit stuck on an ambiguity in case constructs; I want them to work as either statements or expressions.

To anchor things a bit, here are two uses of case, one of which is used as an expression, and the other as a statement:

-- as an expression
firstInt = case ints of
    (): 0
    (head, tail): head

-- as a statement
case ints of
    (): print "empty list!"
    (_): print "list has one element"
    _: print "list has #{intsList size} elements"

Languages handle this in various ways that make things simple. For instance:

• In Java, it's always unambiguous whether something is expected to be a statement or an expression.
• In Haskell, each function is just a single (potentially complex) expression; there are no statements, and thus no ambiguity
• In Scala, you can put an expression anywhere in a function body, and the last expression is the function's return value — so again there's no ambiguity, because you can just make case constructs (match as they're called in Scala) always be expressions.

Scala's approach works, but it also lets you define a function as def g() = { 1; 2; 3; }, which I don't like. Statements and expressions are different beasts to me, and conflating them seems like a lazy and inelegant solution.

So then, is the case in that f example above about to introduce a statement or expression?

One solution is to take a hint from Java and have method bodies always consist of statements. If we take that approach, f... : case ints of is a statement. To make it be an expression whose value is returned, we'd have to write f... : return case ints of....

That's not the end of the world. In fact, I've never liked the Ruby-style return statements, where you just plop an expression at the end of a method:

def ugly
    123
end

There are a few reasons I don't like this, but the main reason is that in an imperative context (which a Ruby/Scala/etc method is), returning a value is an action. It should look like one! When I write imperative code, I'm telling the computer a series of actions to take. An implicit return feels like this to me:

• First, ask the user how many apples they want.
• Then find out how many apples are available.
• Then, the minimum of that number and the number of apples requested.

That last sentence feels wrong, because it's not a sentence; it's a phrase. You can figure out what it means, but it feels stilted.

On the other hand, when writing one-liners, the return feels superfluous. Here's a nice size function for a list:

size -> Int: case this of
    (): 0
    _: 1 + (list tail)

One option I'm considering is to look at the return value if the method is a one-liner (that is, just a single statement or expression — even if it's complex). If it's Unit, that one line is a statement; otherwise, it's an expression. (If the function's body is a block instead of a one-liner, that block consists entirely of statements, including possibly a return statement.)

This feels a bit subtle and potentially confusing, and maybe that should be a big warning. On the other hand, I think that for most cases, it'll "just work." Crucially, since this only applies to one-liners, nearly all the cases should hopefully be simple cases. I can't think of any that wouldn't be.

This approach also means that the compiler will have to know about the Unit type specially. My instincts are that this smells wrong, but maybe it's not so bad.

Ah, what the heck. Despite all these warning bells going off, I'll try it out. If nothing else, it'll be good to see if my intuition (that this is a sketchy idea) is right, and why specifically. As Batman Begins put it, we fall so we can learn to pick ourselves up.

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.

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.

Another blow against strict immutability

I know I've talked about mutability before, but I realized the other day yet another argument against taking immutability too far: it complicates logging.

I'll take Haskell as my usual favorite example, but this time I won't put it in a favorable light. Because it treats all I/O as non-pure, mutable behavior, any logging you do has to be within the IO monad. This means you have to change your application's structure to support logging. You have to do so within a monad, and, if that monad doesn't happen to be IO, it needs to be a transformer monad. If it's not, and you want logging — find a new monad.

(Full disclosure: I haven't written any real apps in Haskell, so I haven't needed logging past what the repl shell gives me. Maybe all of this is not a problem in practice.)

You can cheat a bit: there's a debug module that lets you log from pure code, but it's not meant for production. For the most part, pure code just can't be logged.

To me, logging is critical. It's important both for "interactive" debugging (as I'm writing new code) and for figuring out what went wrong when a bug crops up in the field. At the same time, it's orthogonal to the logic of the application, and so should dictate as little as possible about how the application is set up. If I have to turn a pure function into an impure one just so I can log some values, that seems like the tail wagging the dog.

Even though Effes is restrictive about mutable types, it considers loggers immutable because their actions (namely, printing bytes to a file) can't directly change the behavior of Effes objects. This means you can use a logger anywhere you like, which is good.

CoffeeScript should handle callbacks better

I want to add a quick addendum to yesterday's post about best practices. I mentioned the staircase problem caused by Node's reliance on callbacks: if one action is a prerequisite for other actions in a method (for instance, you query a database and then act on those results), the rest of that method ends up indented.

Node has another big problem, which is that its target language, JavaScript, is awful. Luckily, one of Node's third-party modules, CoffeeScript, provides a decent language that compiles down into JavaScript. We get all the Node goodness without the CoffeeScript badness!

Since CoffeeScript is a new language that can evolve quickly, and since one of its main use cases is Node, and since Node relies heavily on callbacks... why not add some sugar to make callbacks a bit nicer? I propose a way to bind callback arguments to left-hand variables. This is actually pretty similar to what Haskell does with its do notation, and for pretty similar reasons.

Let's take a simple, imperative-with-exceptions snippet of code:

try
  res1 = func1 arg1
  [res2a, res2b] = func2 res1
  if res2a is "foo"
    doFoo()
  else
    res3 = func3 res2b
    doBar res3
catch err
  handle err

That's pretty simple. Watch how gross it turns when we use callbacks instead of just returning back the results:

func1 arg1, (err, res1) ->
  if err?
    handle err
  else
    func2 res1, (err, res2a, res2b) ->
      if err?
        handle err
      else if res2a is "foo"
        doFoo()
      else
        func3 res2b (err, res3) ->
          if err?
            handle err
          else
            doBar res3

My suggestion is to create some sugar for that. It would look something like this:

do and throw err...
  (err, res1) <- func1 arg1
  (err, res2a, res2b) <- func2 res1
  if res2a is "foo"
    doFoo()
  else do...
    (err, res3) <- func3 res2b
    doBar res3
  catch err
    handle err

Notice how similar this is to the original, easy-to-read, imperative style. The general idea is simple: the new do... syntax introduces a block of code in which callback variables can be bound on the left-hand side. Every time that happens, it starts a new callback nested in the previous one. If you provide the and throw varname syntax, then it treats left-hand bound variables of this name as errors, and if one ends up being non-null, its callback will run the code in the catch block and nothing else.

I won't pretend this is a small bit of sugar; it probably has some interesting edge cases, and the concept might be a bit weird to grok for someone who's new to it. But it's an elegant solution to a real problem that's pretty significant for a major part of CoffeeScript's target audience.

Immutability and randomness

In my last post, I proposed a working definition for mutability: in short, an object mutable if code can directly affect its state. I mentioned one odd implication of this rule: certain OS calls like getCurrentTime are considered immutable even though their results are different each time. An even trickier problem is that of randomness and pseudo-randomness.

Let's take a random number generator first. There are various ways to produce truly random (or very close to it) number sequences: using the weather, relying on hardware inputs, or even leaning on quantum mechanics. A language can't affect any of these, so random number generators that use them fall within the realm of immutable objects by my definition.

On the other hand, a pseudo-random number generator's sequence is completely based on code, once its initial state is set. The PRNG has some seed, and when asked it does some math to determine a new seed and a result for the random. This means that PRNGs are "normal" objects that have to participate in a language's mutability rules.

For languages that have immutable objects, this makes PRNGs awkward to work with; rather than just asking for the next random number, you have to ask for a pair (randomNumber, nextPrng). If you forget to do this, your pseudo-random sequence will be boringly predictable. Here's an example from Haskell (using ghci):

> prng <- getStdGen > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692)

As you can see, this is quite boring; the reason is that the second element of the returned pair (shown here as "750578441 40692") is the crucial next-immutable-PRNG, which we're not using. Here's that code done right:

> prng0 <- getStdGen > let (r1, prng1) = next prng0 :: (Int, StdGen) > let (r2, prng2) = next prng1 :: (Int, StdGen) > let (r3, prng3) = next prng2 :: (Int, StdGen) > r1 750537749 > r2 1579754317 > r3 1580611703

This is the behavior we want, but look how much more code it took! Even ignoring the ":: (Int, StdGen)" bits (that's Haskell needing some help with its type inference), it took twice the lines of code and required littering the block with one-time-use prngN variables.

This is a case where I think Effes' semi-mutability really shines. Once you get the PRNG object, you can use it all you want, and it'll mutate its internal state to update its seed as it goes. If you pass it to a function, that invalidates (at compile time) your copy; you have to get a different one if you want to continue generating random numbers. This is a tad more cumbersome, but not much (there are ways to alleviate it, such as "forking" the PRNG before passing it to the function).

Immutability isn't an exact science with these clowns

The last few posts have read like a reference manual more than a blog, so I'm going to switch things up a bit and write about immutability at a high level. This post will have an Effes-based perspective, but it won't tie in directly to the language.

The question of the day is: what makes an object immutable? The easiest and (almost) most restrictive definition is that nothing about the object can change — its bytes are determined at construction time and never altered afterwards.

Well, what about an object that lazily caches the result to some method — a lazy-evaluated asString field for the object's toString representation? The first invocation of toString will modify the object's bytes, but I would argue that it's still immutable because its observable behavior has not. This is my version of the equivalence principle: if you can't tell from your rocket ship that the universe has changed, then it hasn't in any real sense.

Let me take it a step further: is stdout mutable? Let's assume that a write to stdout never fails, that the stream is never closed, and that the stdout object doesn't contain state such as "how many bytes have been written so far." In this case, from the language's perspective, the stdout object has no state, which is just about the most immutable a thing can be.

On the other hand, most output streams are mutable, because they can be closed. Streams can also fail due to things like a full disk or dropped connection, but I see those as two different scenarios: in one, the behavior of the object changed due directly to an action the code took, whereas in the other, the behavior changed due to an external event.

This is an important distinction, because otherwise even the original, "most restrictive" definition above is not enough. Let's say we want to define immutability strictly as "the object's behavior never changes," so that an uncloseable output stream is mutable (because it may fail, thus altering its behavior). Now consider an object with no pre-calculated string representation; its toString method generates a new string each time. This requires allocating memory, which itself may fail — so with our super-strict definition of immutability, even this object isn't immutable. With this definition, the only immutable objects are one with immutable, public fields and nothing else: even a getter could fail due to a stack overflow.

And so, I submit this as a working definition of mutability, at least for Effes: an object is immutable if its behavior can't change in a deterministic way as a direct result of actions expressible in the language.

This definition has an interesting implication: a method that gets the current date/time from the OS is immutable, even though it gives a different result each time! (Let's assume the language doesn't have features built into it that set the system clock.) As weird as this sounds, it actually makes sense, given the problems that I think immutability solves — specifically, no scope can change the date/time for another scope. You won't ever invoke getCurrentTime expecting it to have been set by another scope even though it wasn't; and you won't ever invoke getCurrentTime from one scope expecting it not to have been changed, even though somebody else changed it.

When is a new object really a new object?

Since I just brought up object construction, it's worth discussing when a new object is really created, as opposed to when a previous object can be reused. This will also anticipate some of the function resolution requirements, which I'll introduce in a few posts. As usual, I'll lead by example.

First, some data types to work with:

data Red; Green; Blue nicknamed Color
data Colorful(color : Color)
data Box(size : Int)
data Fragile

Hopefully this should be getting familiar by now. We start with three stateless traits, the union of which is nicknamed Color. We then introduce two stateful traits, followed by a third trait to mark fragility. Now let's create some objects:

a = Colorful Box where
    color = Red
    size = 27
b = Fragile b
b2 : Box = b
c = Fragile b
c2 = Fragile b2
d = Colorful c where
    color = Blue

The first assignment just creates a composite object, as I described in the last post. Easy.

The second assignment (the one to b) creates a new object. It has to, because (as I'll elaborate in the upcoming function resolution post) the object's runtime type is maintained even if the object is "upcasted" later, as happens with b2. We need some way of knowing that b is Fragile while a is not, and the easiest (onlyest?) way to do that is by creating a new object.

But Fragile has no state, which means all Fragile objects are identical. In fact, internally, Fragile could be just a metadata marker on the object. That means that when we re-add the Fragile trait in c = Fragile b, we can actually reuse the same b object. This optimization can be done at compile time.

The c2 assignment is also a no-op, but only at runtime. Even though the compile-time type of b2 doesn't include Fragile, at runtime we can see that the b2 object is already Fragile, and so we simply return it.

Contrast that to the d assignment, which also re-sets the state of one of the component traits. In this case, we do need to create a new object in the general case: objects are immutable, so we can't change the state of c, but we definitely need to store the fact that we now have a blue box where we used to have a red one. (If the new color happens to be the same as the old one, we reuse the object in principle; I'm not sure if this check would be cheaper than unconditionally creating a new object.)

Implicit in all of the above is that there is not a way to check for referential equality — that is, that the programmer won't ever care (or know) if the runtime reuses an object. I think this is a good idea even without these optimizations, so I'm going to throw that into the Effes "spec." Truth be told, I've been assuming it all along.

Incidentally, since the compile-time type of c is Fragile Colorful Box, we could have just written d = Colorful c (without the where clause). This would say that we want to change none of the fields, in which case the whole thing is a no-op at compile-time (as c was). If Colorful had more than one field (maybe it has an alpha : Float), we could have used this syntax to change only one of the fields. This would obviously still create a new object.

On the other hand, if we'd written d2 = Colorful c2, then we'd have to provide the field values. c2 has a compile-time type of Fragile Box, and the compiler would require that if we add color to this box, we need to specify which color. The fact that c2 already has a color at runtime is irrelevant; the compiler will require that the program specific values for all Color fields (in this case, just the one), and the runtime will create a new object that overwrites these fields.

Sugar and the "data" keyword

In my last post, I discussed the data keyword as sugar for stateful, struct-like traits. This is mostly pure sugar, although it's also the only way to define a stateless, methodless trait (like Nothing). I'd like to justify those decisions, and also introduce two more pieces of sugar.

As I touched on in an earlier post, there is a balance to be had between deep abstractions vs. ease of use. Syntactic sugar, if designed correctly, can help that balance by highlighting certain aspects of an abstraction. This is useful both for the language design, which can now have a high-level abstraction whose concrete implications are clearer; and from an individual program's design, where it's more obvious which part of the abstraction is important for a given type or object.

The data syntax aims to do this by recognizing that a type whose only functions are getters feels different than one with abstract virtual methods. The first is used purely to store state, whereas the latter doesn't even care about state directly — just about behavior. Effes combines both of concepts into traits, so sugar can help clarify which aspect is more important for a a given type. When you want to focus exclusively on the state-storing ability of a trait, data is a better option, and when you need the behavior-defining aspect of a trait, the default syntax is a better (well, only) option.

As for requiring data syntax for stateless, methodless traits, this is partly pragmatics and partially a philosophical consideration. Given that the syntax for an abstract trait is something like this:

Sizeable:
  size : Int

... how would Nothing look with this syntax? It'd probably be something like one of these:

Nothing:
-- rest of your code here, unindented

Nothing -- no colon
-- rest of your code here, unindented

Nothing:
  pass

The first two feel like weird, dangling tokens; I don't like them from an aesthetic perspective. The last one borrows from Python's pass statement, which inserts a runtime no-op. It was designed for exactly the kind of situations Nothing would have using default trait syntax: the language requires something, but you want nothing. I've always thought this was a bit ugly. Within the context of a function, one could just use return instead; and within the context of a class definition, pass suggests that something weird is going on — a methodless, init-less, stateless class is a weird beast. In Effes, such a thing is indeed useful, but it feels very much like a data type; so, rather than introducing new syntax for it, or generalizing the default syntax to allow weird, ambiguous-looking constructs (like the first or second examples above), I just require the data syntax, which does the job just fine.

Finally, as promised, here are two more minor pieces of sugar for the data syntax. Firstly, you can define multiple types on one line, separated by a semicolon. And secondly, you can follow a data definition with "nicknamed foo" to automatically create a nickname for the union of all of the types defined on that data line. So this:

data LT
data GT
data EQ
nickname Comparison = LT | GT | EQ

...can be expressed more succinctly as:

data LT; GT; EQ nicknamed Comparison

Again, this tries to smooth the transition between abstractions and ease of use. One common use case for a type system is to define enum types; a comparison is either less than, greater than, or equal to. In a language like Haskell, these are different constructors of the same type. In Effes, they would be defined as the union type of the three traits, and one would almost definitely want a nickname for that union type. This sugar allows us to emphasize the enum-like characteristics of the union of stateless, methodless traits.

The use case for this sugar is definitely enum-like types, so I'm tempted to declare that the sugar only works if all of the data types are stateless. This feels slightly more hacky, but it's also easier to reverse: generalizing the syntax will be backwards compatible, whereas restricting it (from all data types to just stateless ones) in the future could break code. I don't anticipate that backwards compatibility will be a major problem for Effes, but I think I'll take the safer approach for now, as an exercise in language evolution if nothing else.

Assumption by any other name make an ass of u and mptions

Until now, I've been using the term "assumption" to describe several ideas: interfaces that define behaviors, stateful traits that include implementations, polymorphism and more. Why haven't I used more standard terminology?

Before I get there, a slight diversion. People who work in Java will sometimes ask a question along the lines of, "I want a Map<K,V> where the keys can be of any type, and the values will depend on the key type." For instance, an Integer key would correspond to a value of MyVal<Integer> (for both gets and puts), a String key would correspond to MyVal<String> values, and so on.

The short answer is that you can't define a Map of that sort in Java. The next question is: why not? Isn't that reasonable? And then the real answer comes in: a type system is just a limited theorem checker, and we've known since Turing that we can't come up with an algorithm that will prove everything you want to prove; so we'll always have to draw a type system's line at some place, and this is where we happened to draw it. If Java allowed for those kinds of types, there'd always a slightly more sophisticated use case that you could ask about and wonder why not.

That got me thinking: what if I designed a type system that, though still limited, had an expanded scope? Most type systems define what types a given object can work with (based on its type). What if I designed one that defined what values an object can work with?

Take a quicksort as an example. The "main" recursive step will look something like:

return (quicksort left) + pivot + (quicksort right)

Well, what happens if you get confused (it's late and you're watching TV while coding) and instead flip the two sides:

return (quicksort right) + pivot + (quicksort left)

My idea was that you could define an assumption called Sortable that would describe which values can be, for instance, pushed into a stack:

Sorted Stack[A] requires A :: Ordered st
    push a requires
        size == 0 or
        a >= pop

Now, in order to push into a Sorted Stack[A], firstly the A type has to have an ordering defined (as it does in any statically typed language that would deal with sorted structures), and secondly, you must have proven in the code that the input is >= the stack's head. For instance:

A :: Ordered ->
badPush(s :: Stack[A], v :: A) :: Sorted Stack[A] st
    push s v -- compilation error!

A :: Ordered ->
tryPush(s :: Stack[A], v :: A) :: Sorted Stack[A] st
    if (size s == 0) or (v >= pop s)
        push s v
    else
        s

In the first example, the code couldn't prove that the assumption required of a Sorted Stack[A] is true, so the code failed to compile. In the second example, it could prove it, and everything's fine.

So, that's why I went with the term "assumption." The idea was that the basic components of a program wouldn't be types, but a bunch of assumptions of a more general nature asserted on objects.

The more I played with it, though, the less promising it looked. All but the most trivial examples became too difficult to express, and I kept needing an "escape hatch" for assumptions that would be cumbersome or impossible to prove in the code. The escape hatch would be in the form of telling the compiler, "I know you can't prove this, but trust me on it." Basically, I felt that the escape hatch would be needed so much that it would become the primary form of typing, in which case the language effectively becomes a dynamically typed language that requires static compilation — the worst of both worlds.

So, I've decided to abandon this effort, and instead focus on a more standard definition of types. I'm going to call these traits, though they're different from traits in some other statically compiled languages in that they're attached to individual objects, and not to other types (as they are in Scala, for instance).

Elegance with a balance

In my introduction to Project Effes, I talked a bit about why I want to create a new programming language (tl;dr: because I think it'd be fun). I didn't talk much about what I'd want that language to look like, though. Time to start building.

So to start, let me say that I like languages with an ethos. Haskell is a great example of such a language; it takes just a few core concepts and runs with them in a very elegant way. Where the concepts are different, they're often parallel; you can curry functions, but you can also curry generic types. Pretty cool!

That makes for a beautiful language, but can also make it hard to use. As powerful as the abstractions are, sometimes you want a cigar to just be a cigar. To that end, Haskell does make some concessions in the name of usability. Its do notation makes functional programming seem imperative-ish, and its record syntax is a bit of a hack.

Ruby, on the other hand, feels like it's almost all hack. Lambdas, procs and blocks are kindasorta similar, but they don't quite fit together; it feels like the language didn't know which direction it wanted to go in, so it chose to go in all of them and didn't care that it got pulled apart. The decision to make everything an expression seems principled in a Haskell-type way, except that a lot of those expressions are actually pretty meaningless; a for loop isn't something you'd typically expect to have a value, and it's not clear to me what that value should be, anyway. Other than the ability to say "neat, everything is an expression," what does that actually buy you?

Then there are languages that draw lines in the sand and immediately tip-toe over them. Scala seems to do this by declaring that static functions are Wrong and Can't Be Done In Scala, but then inventing companion objects that let you define singletons with instance methods. Am I crazy, or does that sound very static-function-esq? (Full disclosure: I haven't actually used Scala yet, and I'm sure there are subtle differences between companion objects and static functions; I don't know if they're enough to justify crossing over the philosophical line in the sand. It could also be that I've misinterpreted how strong of a line that is.)

I think it comes down to picking a few abstractions — resisting the temptation to force everything into a single, base concept — and ensuring that they're cohesive and complementary. Features that are similar should be similarly constructed; those that are fundamentally different should be treated as such; and if you have a set of features that are so similar that they're basically a bikeshed problem, just pick a color and go with it. There's a balance to be struck between a Haskell-like level of abstraction and the simplicity of adding a couple more base concepts. Easier said than done.

What I think this means for Effes is a blend of functional and imperative programming styles. I want each one of those components to work well on its own, and I hope they work well together, but I don't want to artificially define either one in terms of the other. A fold and a for loop are different. They feel different, they act different, and they make you think differently. I want each to be a well-formed, first-order construct. Going back to the Haskell case of do notation, rather than having sugar that makes a functional idea look kind of imperative, I'll create a context where the design is imperative, with all of the bells and whistles you'd expect.