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.

Explaining Effes using easy words

I read a nice thing today: the person who wrote it was explaining what they do using only easy words. (He got that idea from another place.) That person works on some very hard problems, but he was still able to explain them. I thought I would do the same for Effes (which isn't as hard as what that other person does!).

In order to get a computer to do something, you have to say what you want in a different way than normal talking. There are many, many ways to do this, but only a few are used by most people. I want to come up with a new way of talking to a computer, but I know that it won't ever be used by most people. I'll probably be the only person to ever use it, if I ever finish it at all! So why do I want to do this?

First of all, it's fun. I like learning about new ways of talking to computers, so coming up with one of my own is interesting. This is the most important reason, and it's why I sometimes don't work on this for weeks, if I'm not in the mood. But I also have some ideas I haven't seen before, and which I think might be fun to try.

Most ways of talking to computers have a way of saying that one thing is a kind of another thing. This idea is very important. You can say that a dog is a kind of animal, and so is a cat. This means you can think of both a dog and a cat as being just an animal — in which case you can ask it to walk or eat — or you can think of a dog as exactly being a dog, in which case you can ask it to sit (which you can't ask a cat to do).

Most ways of talking to computers focus on that idea, but Effes focuses on another one: that a dog is an animal added with something that sits. This lets you add a dog with even more things — like something that chases balls. You can even say that something runs, eats, sits, and chases balls, without saying that it's a dog. That means if you have a horse, you can say easily that it does all those things, without having to say that there is such a thing as a "running, eating, sitting, ball-chasing animal," which a dog and horse are, but a cat is not (remember, the cat does all of those things except sitting).

This idea seems simple, but there are hard parts to it. A dog and a person can both eat, but let's say a person can get full while a dog never can (they like to eat a lot!). So if you have something, and all you know is that it eats (you don't know if it's a dog or a person), then it's hard to know if it should be full after it eats.

A bigger problem is if you add a dog and a person together. That doesn't really make sense, but you can still ask the computer to do it! If you have such a thing, and you ask it to eat, then is it full? Its person-half is full, but its dog-half isn't. But a thing can't be both full and not-full. (There are real cases that are like the dog-person but more normal, but for now let's focus on the dog-person.)

The answer to this problem in Effes is that sometimes the dog-person is both full and not-full, and the computer thinks about things both ways. But other times, you tell the computer that one of the halves is more important, and then the computer only thinks about that half's answer to the question, "are you full?" So if you ask if a dog-person is full after it eats, the answer could be "yes and no," or "yes" (if the person half is more important) or "no" (if the dog half is more important). You get to pick which it is.

So far, I have only thought about some of these ideas. My next step is to get the computer to actually start thinking in this new way.

An argument for using both composition approaches

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

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

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

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

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

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

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

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

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

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

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

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

Saving object composition from complexity

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

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

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

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

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

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

type Container:
  isEmpty -> Bool -- abstract method

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

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

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

... and here's the composition:

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

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

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

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

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

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

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

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

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

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