Crazy Coding Conundrums

Very technical programming post about having a ‘no value’ concept in statically typed languages. Specifically: the difficulty of representing this in a static typing system.

Quick intro: Right now most static languages either have a concept called ‘null’, which means no value, and every object reference can point to null, such as Java or C#, -or-, there’s no ‘null’, and instead you can use a so-called ‘Maybe’ type to represent an optional value. Haskell does this. From here on out I’m assuming a Java-model static language (Fan and C# are similar enough to count).

Recently there’s been some push to add the possibility of null to the typing system itself, for Java. Stephen Colebourne reports that Fan recently added null to its typing system. However, his post is severely lacking in actual technical detail. The way he writes it, Fan’s support for null is fundamentally incomplete. Unfortunately, most people I talk to about this think adding nullity is a matter of tossing in a suffix-! to indicate definitely-not-null, or for the default is not-null fans (Like Fan, the language), suffix-? to indicate that null is allowed. This isn’t sufficient.

The notion that there are only two different states (allows-null and never-null) is wrong. Think of java generics; List<Number> foo = new ArrayList<Integer>(); is not legal, even though Number foo = new Integer(5); is legal. In generics, we have a convoluted but necessary trifecta of ways to say that your type contains Numbers:

List<Number> t; //allows reading Numbers out and writing Numbers in. List<? extends Number> t; //allows reading Numbers out, but no writing. List<? super Number> t; //allows writing Numbers in, but reading gives you 'Object'.

In the above, the most flexible option (the first, where we can both read and write) is also the least accepting: Only a List<Number> would do; you cannot give either a List<Integer> or a List<Object> legally, whereas in the second and third option, where we restrict ourselves to reading or writing, we can accept more.

We need the same trifecta for nullity:

List<String!> t; //allows reading non-null out. List<String?> t; //allow writing null in. List<String> t; //neither, but more accepting.

In the above example, those three are distinct. Specifically, While you can obviously assign a String! to a String?, as in: String! f = "foo"; String? t = f; //legal, obviously, you can NOT assign a List<String!> to a List<String?>. Here’s why: If it would be legal, you can sneakily add nulls to a non-null list. In the next snippet, we’ll assume for a moment that you could assign List<String!> to a List<String?>

List<String!> t = new ArrayList<String!>(); List<String?> f = t; f.add(null); String! s = t.get(0); //this returns null. WHOOPS!

This is entirely analogous to why a List<Number> does not allow you to assign a List<Integer> to it; you can secretly add a Double to a List<Integer>, which is bad.

So, List<String!> cannot be assigned to a List<String?> and a List<String?> is not assignable to a List<String!>. Okay, but, what do we do if we want to write a method that should accept either form? The need to do that is perfectly legit: If we only read and null check, or we only write non-nulls, or a combo of those two, then we really don’t care about the nullity of the incoming parameter. It would be ridiculous if it was impossible to convey this. And yet I don’t see how you’d do this in Fan.

For example, let’s say we have a method that sets the values for a row in a GUI table. The table has a sparse mode, where a column entry isn’t rendered and its space is provided to the cell to its left. ‘null’ is used to indicate this. However, obviously, lots of tables will be rendered from data out of, say, a database, where this feature just isn’t needed. Worse, if the data is also used elsewhere, it would be perfectly legit for the data to be handed to the code that renders the GUI in List<String!> form. To now pass this to the method that sets the row data, the only option is an unsafe cast and a @SuppressWarnings annotation, or copy the list, just to satisfy the type system. Eeeeugh. You need a way to say that you don’t care about the nullity type of a generics parameter.

The IDEA java editor has support for a @NonNull annotation, but they cop out entirely and don’t support it in generics bounds, which, in my opinion, means its useless.

You also need this trifecta (never-null, definitely-allows-null, either way) for generics bounds; for example:

List<?? super Integer> t; //You can add null to this. List<? super Integer> t; //Can't add null, returns Object? on read. List<?! super Integer> t; //Can't add null, returns Object! on read.

List<?? extends Number> t; //Can't write, returns Number?
List<? extends Number> t; //same as above
List<?! extends Number> t; //Can't write, returns Number!

Etcetera, etcetera. Incidentally, <? extends Foo> and <?? extends Foo> and ‘Foo’ and ‘Foo?’ are the only two in the entire lineup that are synonyms. You can construct a table of assignment compatibilities (can you assign a List<Integer!> to a List<?? extends Number?> – yes, you can), but that process is already complicated due to generics. Adding nullity to it makes it even more complicated.

Consider this a soft vote for the Maybe principle, however, because there’s so much legacy code out there, going that route just isn’t feasible. I’m still in favour of adding type-checked nullity to java, just like I think generics was a great idea even with the complexities introduced. However, make no mistake about it: It’s a complicated issue. And Stephen’s explanatory page about how Fan does it seems like they didn’t get it right.

ADDENDUM: The fourth nullity state.

Java language changes, or for that matter, any programming language change, does not live in a vacuum. There’s old ‘legacy’ code to consider, written before the feature existed. New code should be capable of interoperating with legacy code relatively painlessly, otherwise no project can move on to any of the new features without completely overhauling every last snippet of code they use. Thus, if nullity-in-the-type-system is to be adopted, it needs to interoperate with pre-nullity code. How do we do that?

Let’s look at generics, which is the closest relative. In generics, there’s a concept called a ‘raw’ type. In source, raw types are always easy to find: Its the ones without ANY generics bound, not even the < and > symbols. Java handles raw types by letting everything go (you can assign anything to a raw type, and a raw type can be assigned to anything; List<String> = methodThatReturnsARawList(); is legal). However, anytime you do so, you get a warning that basically says: Okay, if you say so, but the type system doesn’t take any responsibility for the correctness of your code.

A nullity proposal really should work the same way. If I KNOW a method will return a List of things that never contains null, and the list itself is also never null, but it was written before the addition, then, it would be nice if I could just assign the result to a List!<String!> and get a warning which I can then suppress, instead of a flat out refusal, or, also suboptimal, an unsafe cast, which would later have to be removed when the library I’m using gets updated.

Unfortunately, with our three modifiers (definitely not null, definitely allows null, and don’t know), we’re out of luck; unlike generics, the way it used to be written is also valid in the new way (specifically, in the examples above, it meant ‘don’t know’). We need a ‘raw type’ for nullity, which is distinct from the most null-accepting type. Here’s the difference:

a method that takes a List?<?? super Number> – explicitly written just like that, will simply not accept a List<Number!> as input. (after all, the method could add nulls to this list due to the ??). If you try, you get a compiler error. The method itself is allowed to write in nulls, and when reading, gets Objects out, that could be null.

On the other hand, a method that is legacy and has as signature: List<? super Number>, has the same behaviour: Writing nulls into the list is allowed, and when reading, you get Objects back which might be null. However, it isn’t the same as List?<?? super Number> for the same reason generics ‘raw’ types aren’t quite the same as any specific generics bound: In the legacy case, you CAN give a List<Number!> to the legacy method that accepts a List<? super Number> – however, because the type system does not know what the legacy method does, it will give you a nullity warning message that simply states: Okay, if you say so, but I cannot guarantee that this legacy method you’re calling will never write null into your list of Number!s.

So, we now have a 4th nullity state: legacy. That makes 4 states:

Definitely-allows-null, Definitely-not-null, Don’t care, and Legacy. How do we separate these states?

Here’s a modest proposal:

All new files only get parsed as java7 syntax if they start with “source 1.7;”. Then, never-null is the default, ‘*’ is ‘Don’t care’, ‘?’ is ‘definitely allows null’, and its not possible to actually create a legacy type; you can just interoperate with them. Without the source keyword, all your types are legacy-null. ! is no longer used except to promote a generics parameter to non-null. An example for that last one: Let’s say list has a method that returns the value if it isn’t null, and a default if it is, where the default may itself not be null, you could write:

public T! getIfNotNull(int index, T! default) { T x = get(index); return x == null ? default : x; }

There’s a bit of weirdness in the notion that a generics name (such as ‘T’) carries its null-nature with it, whereas a plain type, like, say, ‘String’, doesn’t. Therefore, you need both ? and ! to promote/demote whatever it was to the definitely-not-null or definitely-allows-null variety, with no modifier meaning: Whatever nullity state the type name was bound to.

In other words, if you go: new ArrayList<String!>, then The ‘T’ in the ArrayList class source is bound to ‘String!’, using ‘T!’ would also be ‘String!’, and using ‘T?’ would be ‘String?’. ‘T’ by itself works a bit like ‘don’t care’ – where relevant you must null check when reading, but you must not write in nulls when writing, because you don’t know if null is allowed or not.