Dealing with absence of value

You are designing a new statically-typed programming language. You’ve heard (and maybe even experienced yourself) that “Null is a billion dollar mistake”, so you have firmly decided that you are not going to have this concept in your programming language. However, as you start programming in your new language, you quickly run into a situation when you need to represent an “absence of value”. Maybe it is a field that was not initialized yet or was missing in configuration, maybe a function needs to report a failure, but not that kind of panic/exception/crash failure. So, what are your choices to represent this “absence of value” if you don’t have the concept of null for that? There are two of them.

Tagged union

If your language has support for any kind of tagged unions (aka sum types, variants, choices, etc) and has some mechanism for parametric polymorphism or another way to abstract over types (aka generics, templates, etc), then you can define a type constructor Optional.T, so that for every type T it represents a union of eitherSome(T), holding a value of type T, or None, representing an absence of value.

Let us write it as Optional.T = Some(T) | None.

If you are designing a pragmatic language and expect that the case of missing value is going to come up pretty often, then you can provide a syntactic shortcut in the form of T? instead of a longer-named Optional.T. You might also find that explicit wrapping of values of type T into Optional.T using Some(T) is too wordy and design some kind of implicit conversion from T to Some(T) as well as some convenient syntax for unwrapping a value of Optional.T into a value of T when it is not None.

Untagged union

If your language can handle a limited form of untagged union types in a type-safe way, then you can define Optional.T = T | None. It is similar to a tagged case, with a difference being that T is of type Optional.T without having to explicitly or implicitly wrap it into an instance of your Optional.T type.

In the same vein, you can call it T? for short and provide some additional syntactic sugar to make it nicer working with it.

Null reinvented

Either way, you have just reinvented null. Make no mistake, your None value represents the concept of null in its full glory. However, since you framed your solution in a type-safe way, you did not repeat the “billion dollar mistake”. Whew! You can proudly say to your users that your language has no null, but do not mislead them into thinking that it is so because you gave your concept of null a different name. It is because you added it to your language in a type-safe way — they cannot simply call T’s operations on a variable of type T? without unwrapping/checking it for None value first. You could have boldly named your None as null and it would have been just as safe to use. More on that was said in the previous story —“Null is your friend”.

Some type theory

So, is there any difference between a tagged union and untagged union for representing an absence of value and how can we tell them apart? From the standpoint of type-theory the difference is quite big. Moreover, historically, the only known efficient approach to parametric polymorphism was Hindley-Milner type system circa 1985 and it only supports tagged unions, so you’ll find a plethora of languages that handle an absence of value via some form of tagged union Option type.

There has been significant progress since then. Limited forms of union types can be incorporated into a language without compromising its type-safety or ability to infer types (aka type deduction), so nowadays untagged unions show up as a solution, too.

But what if a language has T? syntax with syntactic sugar, implicit conversions, etc. How do you know which solution it actually uses? There is a simple test. If T? stands for a tagged union, then T? and T?? represent different types:

T?? = Optional.Optional.T 
    = Some(Some(T) | None) | None 
    = Some(Some(T)) | Some(None) | None 
   != T?

However, if T? stands for an untagged union, then T? and T?? are the same types:

T?? = Optional.Optional.T 
    = T | None | None 
    = T | None 
    = T?

Some practice

Is there any difference between tagged and untagged unions in practice? It turns out that there is not much. Given enough syntactic sugar, the difference between the two shows only in situations like T??, which is a bad style to get yourself into anyway. If you strive to write readable code, then you naturally avoid writing code that tries to represent two different kinds of “absent values” with a type like Optional.Optional.T, so you should not be often running into a situation where tagged/untagged distinction matters in practice.

Interestingly, lots of people find Swift and Kotlin programming languages quite similar in the way they handle null, even though these two languages were designed independently of each other without any influence onto each other. Both have concise T? syntax and a bunch of convenient null-handling facilities. Yet, under the hood, Swift’s approach is based on tagged unions, while Kotlin’s one is based on untagged unions. The overall impression you get when dealing with absence of value in any of the languages is similar and even the basic syntax if the same, yet it is helpful to understand the difference to appreciate its deeper effects.

Kotlin shuns implicit conversions but embraces flow-sensitive typing, which interplays extremely well with its untagged union approach to nullability, where a nullable value (a Kotlin-speak for Optional.T) is automatically of type T when statically checked not to be null (not None).

Swift follows a more traditional tagged union approach, but adds a handy implicit conversion of T to Some(T) plus a plethora of guard constructs to simplify unwrapping of optional types, which makes it look more like an untagged union from a developer’s ergonomics standpoint.

All in all, modern languages typically provide a pragmatic solution for dealing with an absence of value and it does not matter much how exactly it works and how it is named, as long as it is type-safe.

Further reading

This story has lots of links to articles and presentations embedded inside. Feel free to explore.