Null is a pervasive concept in computing. Virtually all programming languages have a way of expressing nothing, nullity, no answer. But handling nulls correctly turns out to be tricky, and many of the contexts in which you find nulls, you'll also find confusing and error-prone semantics surrounding them.

The heart of the problem is that, in an attempt to make programming with null easier, nulls are often propagated implicitly through computations, allowing the programmer to write code that deals with nulls without explicitly contemplating how nulls should be dealt with.

My experience has been that this is a mistake; that if you want robust, easy-to-reason-about code, the programmer must think explicitly about how to handle null cases, and that programming languages would do well to provide programmers with good support for the requisite case analysis

The point can be illustrated by considering some of the contexts in which null arises.

## IEEE Floating point arithmetic

This is an oft-forgotten case, but an important one. The null value in this case is `NaN`

, which stands for not-a-number. `NaN`

is the value you get when a basic arithmetic operation has no reasonable answer, *e.g.* zero times infinity.

In the IEEE standard, `NaN`

behaves quite differently from other floats. The standard requires that applying the primitive arithmetic operations to `NaN`

always produces `NaN`

. At first glance, this seems sensible. What's `3`

times `I-don't-know`

? Clearly it's `I-don't-know`

!

But what about primitive operations that don't return floats, like comparisons? According to the standard, comparison functions return false when one of their arguments is `NaN`

. Now this should make you nervous, since it's not at all obvious that the value of `I-don't-know`

> `4`

should be false.

Indeed, this behavior violates a bunch of fundamental invariants. For example, it's simply not the case that x > y is equivalent to not (x <= y) when `x`

or `y`

are `NaN`

. Also, comparison functions don't give a total order on floats --- see what happens to your favorite binary tree when you throw in some `NaN`

s. Reflexivity doesn't even hold, since `NaN = NaN`

is false!

To see how weird the results of this can be, consider the following function for computing the max of two numbers (the example is in OCaml, but the same behavior will show up in any language that provides IEEE compliant floating point semantics):

let max x y = if x > y then x else y

If either `x`

or `y`

is `NaN`

, the test will return false, and `y`

will be chosen. Thus, `max NaN 3`

is `3`

, and `max 3 NaN`

is `NaN`

. Note that max doesn't have the null-propagation property that the IEEE standard wanted for primitive float-producing operations. `max`

doesn't even have the symmetry property you would expect: `max x y`

is not the same as `max y x`

.

Here's another example. Consider the following two functions, which are intended to validate whether the provided float is between 1 and 10.

type result = Fail | Pass let check1 x = if x < 1. || x > 10. then Fail else Pass let check2 x = if x >= 1. && x <= 10. then Pass else Fail

The two functions certainly look equivalent, and if you're not clued in to the strange semantics of `NaN`

, you might be surprised to discover that `check1`

returns `Pass`

for `NaN`

, whereas `check2`

returns `Fail`

.

## SQL's NULL

Much ink has been spilled about the problems associated with SQL's `NULL`

. The wikipedia page on `NULL`

is a pretty good summary, so instead of trying to give a complete picture here, I'll just give a taste of how `NULL`

works in SQL, and what the associated problems are.

At first glance, SQL's `NULL`

looks a lot like `NaN`

. If you call a simple function and give it `NULL`

as one of its arguments, the result will be `NULL`

as well *e.g.*, `3 + NULL`

is `NULL`

. But unlike `NaN`

, SQL's `NULL`

is not restricted to floating point numbers; You can have a `NULL`

in a column of arbitrary type.

Let's see what happens when we start doing comparison functions in SQL. It turns out that SQL propagates a kind of `NULL`

into boolean expressions as well. This seems more consistent than the behavior with `NaN`

. Indeed, the odd way that `NaN`

propagates into comparison functions is what sunk our implementation of `max`

, and so you might expect `max`

implemented in SQL will work properly. Let's try. Assume we have a table `t`

which contains some `NULL`

s:

`| i | j |`

|------+------|

| 1 | 2 |

| NULL | 2 |

| 1 | NULL |

If we compute the `max`

of these two columns, we should expect the result to be:

`| i | j | max |`

|------+------+------|

| 1 | 2 | 2 |

| NULL | 2 | NULL |

| 1 | NULL | NULL |

Here's some SQL code code for computing the max from two columns.

SELECT i, j, CASE WHEN i > j THEN i ELSE j END AS max FROM t

Sadly, we see the exact same bizarre behavior we got out of our floating-point `max`

function.

`| i | j | max |`

|------+------+------|

| 1 | 2 | 2 |

| NULL | 1 | 1 |

| 1 | NULL | NULL |

Why is this? Because SQL doesn't hold its ground when it comes to the way it handles `NULL`

in conditional expressions. A `NULL`

condition is treated as equivalent to false, where the more consistent behavior would be for the entire `CASE`

expression to evaluate to `NULL`

.

The root of the problem here is the attempt to pick a reasonable default behavior in the presence of `NULL`

in a way that doesn't just scuttle the entire computation. Saving such a computation isn't hopeless --- these null-handling heuristics often produce reasonable answers. But they can produce unreasonable answers as well, and the end result is that the behavior of SQL in the presence of `NULL`

is inconsistent and confusing.

The above example is really just the tip of the iceberg. You can see examples of strange behavior with aggregate functions, selects and joins as well.

Fundamentally, both SQL's `NULL`

and the floating-point `NaN`

fail because the choice of how to salvage a calculation that encounters null depends on things that can not be known by the heuristic.

One good aspect of SQL's `NULL`

handling is that SQL provides ways of enforcing constraints that given columns contain no `NULL`

s. Given the odd behavior of `NULL`

s, it's an essential feature.

## Null references

Another common form of null is the null reference (or null pointer). Null references appear in most mainstream statically typed programming languages, including C, C++, C#, Java. In the following, I'll talk about Java's null references, but the same basic issues show up in many languages.

Unlike IEEE floating point arithmetic and SQL, Java does not try to automatically salvage computations that encounter nulls. Instead, any computation that tries to make a method call on a null reference will result in an exception. In some sense, exceptions are their own kind of null, a special value that a function can return when it can't return anything else. (non-termination is yet another way for a computation to refrain from returning an ordinary value.)

The problem with null references is that while their handling is explicit at the level of values, it's implicit at the level of types. Java's type system allows for all object references to potentially be null references, even though for most variables most of the time, null will never show up. This is unlike SQL, where some values can be declared as non-`NULL`

.

Because the type system gives you no clue as to the presence of nulls, null reference exceptions are rather ubiquitous in Java programs. Indeed, elaborate systems like ESC Java (ESC stands for "Extended Static Checking") have been developed to enforce various static checks, prominent among them the elimination of runtime null reference exceptions.

As a side note, it's interesting that Java has such a loosey-goosey approach to null object references, when it has a fairly strict approach to exception handling. Indeed, Java requires one to be quite strict and explicit when dealing with so-called checked exceptions.

## ML's option type

The problem with Java's null references is different from the problem with SQL and IEEE floating point arithmetic. In those two cases, the system tries to "do the right thing" when null comes up, and that right thing turns out to sometimes be wrong; the problem with Java is that it doesn't provide sufficient tools in the language to ease the programmer's life in dealing with nulls.

Languages like ML and Haskell that are based on the Hindley-Milner type system, on the other hand, provide quite powerful tools for null handling. Rather than talk about such languages collectively, I'll talk in terms of the instance I know best, OCaml. In OCaml, null is not lurking in every type. If a variable has type `int array`

, then that variable is always populated with an `int array`

, and never with null.

When you need a variable whose value might or might not be there, it is modeled explicitly in the type system. One common way of doing so is using what's called an `option`

. The `option`

type is not a primitive of the language, but an ordinary data type, which can be declared as follows:

type 'a option = | None | Some of 'a

This is a tagged union with two cases: `None`

, indicating the lack of a value; and `Some`

, indicating the presence of a specified value. To see how this might be used in practice, consider the following simple hashtable interface:

module Table : sig type ('key,'data) t val create : unit -> ('key,'data) t val find : ('key,'data) t -> 'key -> 'data option val replace : ('key,'data) t -> 'key -> 'data -> unit end

Notice that `find`

returns an optional value. The reason is that `find`

may fail to find an entry corresponding to the given key. This fact is modeled in the type by the fact that the return value is of type `'data option`

rather than simply `'data`

.

In addition to allowing one to express in the type system that a value may be missing, OCaml also provides powerful tools for doing the corresponding case analysis. Here's a simple example deals with options explicitly using `match`

statements.

let increment_count table key = let current_count = match Table.find table key with | None -> 0 | Some x -> x in Table.replace table key (current_count + 1)

Here we explicitly state that we want the null case (where the key can't be found in the table of counts) to be treated as if the table had an entry with value equal to zero.

Explicit null handling like the kind shown above can be done in, say, SQL, using the `COALESCE`

statement. But in OCaml, the case analysis is obligatory --- you can't silently use an optional value without contemplating what will happen in the `None`

case. Consider the following implementation of `increment_count`

:

let increment_count table key = Table.replace table key (Table.find table key + 1)

While the analogous code would compile in SQL, the OCaml compiler will reject it, noting that the expression `Table.find table key`

was used as if it were an `int`

, but was in fact an `int option`

. This may seem cumbersome, but in reality, the explicit separation of cases where null is and is not possible is a great relief, since it frees the programmer from worrying about the cases not flagged by the compiler.

The requirement to handle nulls explicitly doesn't mean that we can't reduce the amount of boilerplate required. If we have a particular null-handling policy in mind, we can write helper functions to automate it. For example, we can write a function:

let option_get ~if_none option = match option with | Some x -> x | None -> if_none

This allows us to rewrite our `increment_count`

function as follows

let increment_count table key = let current_count = option_get ~if_none:0 (Table.find table key) in Table.replace table key (current_count + 1)

Indeed, in Jane Street's `core`

library there is an `Option`

module devoted to useful helpful helper functions of this sort, including an option monad which is a quite general and powerful technique for dealing with option-generating computations.

OCaml's approach is far from perfect. While OCaml is quite explicit about the use of options, it is quite the opposite when it comes to exceptions. Exceptions, like null references in Java, lurk in every function, and this is a very real problem. Indeed the inability to track exceptions in the type system has lead us to try to avoid exceptions except for truly exceptional conditions (and to use options instead).

*If you're interested in working at a place where functional programming meets the real world, you should think about applying to Jane Street. We're always looking to hire great programmers with an interest in functional programming.*

Thanks for the great article! I’ve only recently come across Jane Street, but

from what I’ve seen so far seems like some kind of functional-programming

paradise!

Before reading this article I hadn’t really thought about the possibilities of

using the type system to manage numerical corner-cases, but now I wonder

why I’ve never seen the technique applied to this situation before.

Haskell seems to have some of these weird numeric problems too:

Prelude> let inf = 1/0

Prelude> let ninf = (0/0)

Prelude> inf -- Infinity

Prelude> ninf -- -Infinity

Prelude> let nan = 0/0

Prelude> nan -- NaN

Prelude> inf > inf -- False

Prelude> inf >= inf -- True

Prelude> inf >= 2/0 -- True

Prelude> nan > nan -- False

Prelude> nan >= nan -- False

Prelude> nan < nan -- False

Prelude> nan < = nan -- False

Prelude> compare nan nan -- GT

Prelude> compare nan 1 -- GT

Prelude> compare 1 nan -- GT

Prelude> inf + ninf -- NaN

Prelude> inf / inf -- NaN

Prelude> inf / ninf -- NaN

Prelude> let i = 65000 :: Int

Prelude> i -- 65000

Prelude> i ^ 2 -- -69967296

`Prelude> import Data.Ratio`

Prelude Data.Ratio> 1%0 -- *** Exception: Ratio.%: zero denominator

Prelude Data.Ratio> 0%0 -- *** Exception: Ratio.%: zero denominator

I can’t think of any ideal solution for these situations. Numerical values

seem to be one of the few places where early optimization is justified. An

algebraic datatype wrapper would probaly add way too much overhead from

a computational perspective, and also be far too verbose. Actually, verbosity

might not be an issue if you have access to numeric generics:

import Control.Monad

instance Num n => Num (Maybe n)

where

(+) = liftM2 (+)

(*) = liftM2 (*)

abs = liftM abs

signum = liftM signum

fromInteger = Just . fromInteger

instance Fractional (Maybe Rational)

where

fromRational = Just

recip = (>>= \n -> if n == 0 then Nothing else Just (1/n))

a = Nothing

b = Just 2

c = Just 5

d :: Maybe Rational

d = b / c

e = Just 0

f = d * c / e

main = print [ a, b, c, d, a + b, b * c, c / d, f ]

Output:[Nothing, Just (2 % 1), Just (5 % 1), Just (2 % 5), Nothing, Just (10 % 1), Just (25 % 2), Nothing]

Overflow protection should also be able to be added if we created a newtype for bounded numbers.A configurable set of numeric excpetions might be a high-performance

compromise, but to avoid any overhead it would have to be architecture

specific.

How does Jane Street deal with this issue in practice? Does it come up at all?

P.S. Apologies for using Haskell rather than OCaml. I’m trying to avoid taking

a breadth-first approach to functional-programming

I think that for floating-point computations, overflow exceptions are better than NaN, I wonder why they aren’t enabled in Ocaml by default?

After all, we have them ‘for free’ thanks to IEEE-754 and Ada (a language which I think made many good choice) did enable them by default.

It’s a pity that exceptions for integer overflow are only free (in CPU usage) on MIPS (as far as I know), otherwise I think that more language would have chosen to have them..

I like your point about comparisons on NULL and NaN. 3 is neither greater than nor less than NaN? That’s crazy!

I have a 3 part reply: 1. fixing > and < in ocaml, 2. handling exceptions with the Either type, 3. cleaning up code using the either type. Note that I'm using Ocaml 3.11.1 on a PowerPC Mac.

Part 1

OCaml's compare function seems to work differently than < and > for NaN:

`# 3.0 < nan;;`

- : bool = false

# 3.0 > nan;;

- : bool = false

# compare 3.0 nan;;

- : int = 1

# compare nan 3.0;;

- : int = -1

So if we redefine > and < in terms of compare, it seems to work.

`# let ( > ) a b = compare a b > 0;;`

val ( > ) : ‘a -> ‘a -> bool =

# 3.0 > nan;;

- : bool = true

# nan > 3.0;;

- : bool = false

We can write a custom compare for floats. Although we give up polymorphism, we can use such a comparison function in functors like Set.Make.

EDIT: When I wrote the comparison function for floats, I think I had overwritten (=) in the toplevel and gotten mixed up about where OCaml's default behavior was correct. I'm on an x86 machine now, so maybe it's just the difference in the platform, but I'm seeing

`# nan=nan;;`

- : bool = false

# compare nan nan;;

- : int = 0

which means that the = operator should be replaced with a version using Pervasives.compare, while Pervasives.compare is safe to use in functor arguments as compare, instead of the other way around.

Part 2

Haskell's standard library has a type called Either. In OCaml, Either can be defined as type

`type ('a,'b) either = Left of 'a | Right of 'b`

. The convention is that if your function throws an exception, you return it in the Left constructor, while if your function returns the expected value, it's in the Right constructor.So if we're trying to open a file for reading, instead of using "try...with" you'd just do regular pattern matching to catch the exception:

`match open_in "file" with`

Left (Sys_error "file: No such file or directory") -> handle_not_found ()

| Right channel -> do_stuff_with_channel channel

The functions that come with OCaml don't behave this way, but they can be given wrapper functions to give the same behavior:

`# let new_open_in filename = try Right (open_in filename) with exn -> Left exn;;`

val new_open_in : string -> (exn, in_channel) either =

# new_open_in "some file";;

- : (exn, in_channel) either =

Left (Sys_error "some file: No such file or directory")

Part 3

This can all get pretty messy, and if you're familiar with Monads you probably know how to chain functions together without having to write "match ... with Some thing -> ... | None -> ..." over and over again. If not here's a brief overview.

Basically to avoid having to wrap every function call in match... with for the option type, we wrap our function calls inside a monad using

`# let return a = Some a;;`

val return : 'a -> 'a option =

# let ( >>= ) a f = match a with None -> None | Some a -> Some (f a);;

val ( >>= ) : 'a option -> ('a -> 'b) -> 'b option =

# return 3 >>= add2 >>= add2 >>= add2;;

- : int option = Some 9

You can do the same thing for exceptions with the Either type:

`# let return a = Right a;;`

val return : 'a -> ('b, 'a) either =

# let ( >>= ) a f = match a with

Left a -> Left a

| Right a -> try return (f a) with exn -> Left exn;;

val ( >>= ) : (exn, 'a) either -> ('a -> 'b) -> (exn, 'b) either =

Now you can use >>= to chain functions over some value, and if a function throws an exception you get it in the Left constructor.

The downside to this is that OCaml can't optimize away all the calls to >>= that occur after an exception occurs, so you end up having N identity functions performed on an exception where N is the number of function calls appearing after the function that throws the exception. So in

`return x >>= fun1 >>= fun2 >>= fun3`

if fun1 throws an exception, instead of immediately returning the exception, ( >>= ) is called two additional times.

`# let identity x = x;;`

val identity : 'a -> 'a =

# let ( >>= ) a f = match a with Left a -> print_endline "left"; Left a | Right a -> try return (f a) with exn -> Left exn;;

val ( >>= ) : (exn, 'a) either -> ('a -> 'b) -> (exn, 'b) either =

# new_open_in "some file that doesn't exist" >>= identity >>= identity;;

left

left

- : (exn, in_channel) either =

Left (Sys_error "some file that doesn't exist: No such file or directory")

Mr. M,

We haven’t really talked since the very early days of the SKS keyserver, so it’s really great to find you out on the net again and see that you’re still as ridiculously brilliant as ever. Great article, sir. Well-written and informative. I learned quite a bit!

– Erik