## Avoid a Void: eradicating null-pointer dereferencing

The problem of void calls, or null pointer dereferencing, plagues programs written in any language using pointers or references with a "null" or "void" value. Tony Hoare recently described it as his "one-billion dollar mistake". The problem is very simple to state: in the typical object-oriented call

x.f (args)

x, a reference, should normally denote an object but can be void, in which case the call will fail and produce an exception, often leading to a crash. This is one of the main sources of instability in today's software.

The void-safety mechanism of Eiffel, as defined in the ISO/ECMA standard (2006), is now fully implemented in EiffelStudio and guarantees the absence of void calls. With version 6.4, beyond the mechanism itself, all libraries have been updated to be void safe.

With Alexander Kogtenkov and Emmanuel Stapf I wrote an article describing not only the principles but also the delicate engineering issues that we have encountered and tried to address in making Eiffel void-safe. An abstract, and a link to the PDF of the article, can be found at http://bertrandmeyer.com/tag/void-safety/.

## Comment viewing options

### Comparisons?

It would be interesting to see this compared with other OO languages that have static null safety mechanisms, such as Nice and Spec#. (The authors said their design was influenced by Spec#'s but didn't include a comparison.)

### Comparisons

Good point.

The paper is focusing on the Eiffel mechanism and tries to stay focused, short, and easy to understand, rather than providing a comprehensive survey of all existing approaches.

You are right that a comparative paper would be nice and I hope to write it, in particular regarding Spec#, if possible with coauthors who know Spec# in depth. It would be nice in particular to have a formal model that covers both languages.

### NULL pointers, and another (possible) solution

are one thing that pretty much all mainstream statically-typed OO languages (including Eiffel), as well as SQL, managed to get wrong. The FP community got this one right--one can construct a nullable reference (or as the white paper puts it, a detachable refernce) simply with an algebraic sum; a language library can even provide a preferred and unique unit type simply for this purpose. (FP 1, OO 0).

As I understand the white paper, the Eiffel solution is similar to that found in numerous Java spinoffs I can think of--redefine references to exclude the distinguished unit type, provide new syntax for when you want a nullable reference (such as a recursive data structure), and a convenient downcasting operator ("if attached"). Being only casually familiar with Eiffel, I won't comment on the specifics of the specifics of the proposal.

One other idea, which corresponds to a common pattern in the code I write. My job calls for C++, so I find myself using references rather than pointers wherever I can. Refs have two desirable properties--the underlying pointer cannot be changed (fewer side effects to worry about), and are generally assumed to not be NULL (though there are numerous ways to cheat the type system, of course). But when I do have to use pointers (such as within a copyable object), I find the following code pattern creeping up quite a bit.

Foo default_foo;

/* lots of stuff */

Foo *pFoo = /* somthing */

Foo &foo = pFoo ? *pFoo : default_foo;

Essentially a default object is provided which null pointers are mapped to. However, use of this techniqe doesn't prevent me from crashing the app with pFoo->do_something().

I can use the above inside any function that takes a Foo * to make it NULL-safe. And indeed I find myself wrapping method calls in functions like this to perform this conversion. (FP 2, OO 0).

However, what if it were possible in the class definition to DEFINE the behavior of null-pointer method invokation? Say, in C++-ish syntax:

class Foo {

static Foo defaultFoo;

void do_something() default defaultFoo { /* body * };

};

In this example, if do_something is invoked with a null pointer; there is a runtime check for this condition, and defaultFoo is used as the target of the method call if this is the case. A more generic syntax might permit an entirely different (static) method body for the null case.

This sort of thing slightly resembles a weak form of pattern matching, but I can't think of any OO languages which permit NULL-safe methods to be declared in this fashion.

### Well

The FP community got this one right--one can construct a nullable reference (or as the white paper puts it, a detachable refernce) simply with an algebraic sum

Well, the corresponding problem in an FP setting is incomplete pattern matching. If you insisted that every nullable reference be Maybe[T] instead of T, that just forces your code to pattern match for null everywhere.

The Eiffel solution seems to be an ad hoc set of idioms that the compiler identifies as establishing the non-NULL-ness of a reference in a given context (like inside an if not NULL guard).

Your alternative solution seems like it would be good if that idiom was the only way nulls were used, but I think they are commonly used as the Nothing branch of Maybe[T], so I'd think often the client using the reference needs to decide what to do with null rather than the class.

### You can't completely avoid downcasting or partiality functions

the mistake I was referring to is making nullable references the default (and in many cases the only) means for referencing objects.

If you introduce Maybe in a program, or some other means for creating a nullable value, then yeah, you got to check for it. (But you can do the check at a given point, and then have a reference to Just T for which no longer checking is necessary. A common thing I see in OO code--especially Java--are reams of functions each of which tests args for NULL; to avoid the exception.

Agreed that the proposal as outlined is not a complete solution--if the caller wants to handle null, it should do so as before. OTOH, for those methods where there is a sensible handling of NULL->do_something(), it can be provided.

(And in the C++ context, you can make the null-pointer handler actually throw an exception, rather than segfault the program).

### The Eiffel solution seems to

The Eiffel solution seems to be an ad hoc set of idioms that the compiler identifies as establishing the non-NULL-ness of a reference in a given context

Inevitable if a wholesale retrofit of algebraic data types and pattern matches over them is not an option. There is no difference between:

if attached x as l then l.f(x) end

and:

match x with Some l -> f l x | None -> ()

except one of syntax (one would hope the else clause has been elided for clarity, and not because it is illegal in the construct).

### I can't think of any OO

I can't think of any OO languages which permit NULL-safe methods to be declared in this fashion.

Here's a silly idea for C++: use your own reference class instead of the native pointer types. This way you have control over the behaviour of null references. E.g.:

class Foo {
char* str_;
public:
Foo (char *str) : str_(str) {}
char *msg() { return str_; }
};

Foo default_foo("default");

class FooPtr {
Foo *p_;
public:
FooPtr(Foo *p) :  p_(p) {}
Foo& operator*() {
return p_ ? *p_ : default_foo;
}
Foo* operator->() { return &operator*(); };
FooPtr& operator=(FooPtr& src)  { p_ = src.p_; }
};

int main () {
Foo f("hello");
FooPtr pf = &f;
FooPtr pn = 0;

printf("%s %s\n", pf->msg(), pn->msg());
}


Using templates it would even be possible to write Ptr<Foo> instead of FooPtr. Then you would have a traits class for the default behaviour, which defaults to 0 but could be specialized on a per-class basis. This seems fairly close to what you are asking for, except that you need to re-write code to use the new reference type in order to reap the benefits.

### More solutions in C++

Another pattern that can be quite useful, and an appropriate model, is to have pointer class templates that check for 0 in the constructor, and throw an exception if they are constructed with 0 -- that's still a null-pointer exception, but it happens when the pointer is created [from a potentially 0 plain pointer], and never when the pointer is used.

(This can of course be done in a simple wrapper around a plain pointer, a ref-counted pointer, ...)

### Generic functions

I can't think of any OO languages which permit NULL-safe methods to be declared in this fashion

With Common Lisp's generic functions, one could define a method on nil, of course (you wouldn't have a default object).

### NullObject

using defaultFoo for null is quite close to the NullObject pattern. In Fowler's Patterns of Enterprise Application Architecture, he has a pattern called SpecialCase which covers NullObject and any time you use a special designated object to handle those special edge cases.

Your example is different from NullObject usage but it's so similar. It's supposed to deal with code that looks like:
 if (thing == null) { return null; } else { thing.mutate(); return thing.getResult(); } 
The NullObject would have a no-op for mutate and getResult always returns null. In some ways, it's also an approach for eradicating the annoying null and null check.

### Messaging nil is safe in Objective-C

It's valid in Objective-C to send messages to nil objects making checks such as if(obj != nil) unnecessary.
Sending Messages to nil

In Objective-C, it is valid to send a message to nilâ€”it simply has no effect at runtime. There are several patterns in Cocoa that take advantage of this fact. The value returned from a message to nil may also be valid:

### "valid"

* If the method returns an object, any pointer type, any integer scalar of size less than or equal to sizeof(void*), a float, a double, a long double, or a long long, then a message sent to nil returns 0.
* If the method returns a struct, as defined by the Mac OS X ABI Function Call Guide to be returned in registers, then a message sent to nil returns 0.0 for every field in the data structure. Other struct data types will not be filled with zeros.
* If the method returns anything other than the aforementioned value types the return value of a message sent to nil is undefined.

shudder

### Having an arithmetical value

Having an arithmetical value type returned when messaging to nil is helpful in not having null checks.

if((anObject != nil) && [anObject isBiggerThan: anotherObject]) {
...
}


becomes

if([anObject isBiggerThan: anotherObject]) {
...
}


At least with Objective-C 2.0, all the arithmetical return types default to 0.

### Ewww.

I'd rather have an exception be the default behavior.

It's nice when writing GUI apps; if you forgot to hook up a menu item or button to an action, the whole program doesn't die with a NullPointerException. It lets you build an application functionality a little at a time, while experimenting with the interface.

Not always what you want but it's helpful in most circumstances especially Objective-C being a late binding language.

### But you can achieve the

But you can achieve the same, for example, in Java if you catch NPEs inside the main method:

public static void main(String[] args) {
try {
// the entry point to the application
} catch (NullPointerException npe) {
// handle the npe
}
}


Or is there something superior about the way Objective-C treats null variables? To me it is a gateway for shipping products with uncaught bugs.

In your java example about all you can do once a npe has been caught is print a message and terminate the program since the stack has been unwound. The closest you could get would be to catch any exceptions while dispatching each event and skip to processing the next event. This is what Swing/AWT and I assume SWT do. In a language where exceptions carry a continuation (such as common lisp) you could implement the Objective-C behavior with an appropriate handler. For instance in a Java-like language extended in this fashion

 public static void main(String[] args) { try { // the entry point to the application } catch (NullPointerException npe) { npe.continuation.continueWith(defaultValue(npe.continuation.expectedType)); } } 

In mathematics we want zero and we also want to divide numbers (by non-zero denominators); the difficulty is to avoid ever applying a division to a zero denominator. In programming, we want void references and we also want to apply operations to objects (through the associated non-void references);

The problem with this analogy is that 0 is a useful zero in the set of numbers and it's hard to design an easy to use type system that allows one to express "all numbers except zero." Void/null, on the other hand, is not a useful zero for any domain except the domain of pointers and the domain of optionality. A case in point is:

This problem is, at its core, the need to terminate linked structures...

And here's where I disagree. The domain of lists already has a meaningful zero: the empty list. Void/null adds a second zero that does not behave like a list at all. For instance, all lists have a length property including the empty list. But null does not have a length property. Having a sentinel ensures that list.length is always valid. Having a null/void (with all its non-list behavior) as a sentinel is elevating the pointer domain into the list domain which muddles things up.

first_element.right might be void[/null]

An unavoidable consequence of finite lists is that "right" is either a partial function for lists or a total function on non-empty lists (which can be a pain in practice). If we make it a partial function by allowing emptyList.right then the result type can be a "detachable list" to indicate that we might or might not get a list. At the very least, if we make the return type just "list" then we can make the error message the specific "attempt to take right on an empty list" rather than the generic "null pointer exception." In either case, a proper sentinel seems like a clear win.

Use inheritance to distinguish between two kinds of LINKABLE cells: proper linkables and end
markers. The last right would be of the second kind. This complicates the inheritance structure,
and requires checking every use of right for its type. The effect on performance (in particular the
extra load on the garbage collector) can also be noticeable.

There no reason that the sentinel can't be represented with a singleton. It should even be possible to represent the end of list by a null pointer and let the compiler insert the appropriate void/null checks to simulate dynamic dispatch.

### The error of Lisp

or at least early dialects thereof, is that "nil" means simultaneously the empty list, the boolean false, the missing option, and a whole bunch of other semantically distinct things. I tend to dislike Lisp's nil even moreso than Java's null; such semantic overloading I think causes more problems than it solves.

The suggestion to use inheritance is, I think, a bit of OO golden-hammerism. What you want, again, is an algebraic type sum; and in many OO languages, the popular way to simulate that is with an inheritance hierarchy--class List, subclass ConsNode, and subclass EmptyList. Which to me is just as ugly (if not uglier) than a list implementation using a possibly null pointer.

### See CJ Dates rants against nil in SQL in "Third Manifesto"

Date and Darwen pretty much agree with you. Nil is a heavily overloaded term. Does it mean "Not Applicable", "Zero", "No Thing", "Nothing", "False", "Uninitialized", "Terminate"?

The NullObject pattern described in one of the other posts (although not called that) where nil accepts any message and does nothing... corresponds quite nicely to the notion of nil == nothing. (What should happen if you tell nothing to do something. Obvious.. nothing.)

The "Ewww" response to the NullObject pattern comes from those who treat nil as having one of the other meanings.

Date's and Darwen's solution to the nil problem is sort of inline with Meyers... redo your DB design so it is properly factored and hence has no nils.

Personally I'd liked it if programming languages _did_ have formally distinct versions of nil, which they used in the appropriate place.

For example in languages like Ruby where an uninitialized variable has value nil, I'd rather it had a special value "Uninitialized". After all, there are many valid paths by which a variable can come to have a value of nil, but invoking a method on "Uninitialized", or copying or assigning "Uninitialized" is always a bug.

There are instances where the NullObject pattern results in remarkably clean and elegant code. It is nice to formally have a "Nothing" class that was distinct from "Uninitialized".

The paragraph that stood out the most in the "void-safe" Eiffel paper was this...

Two of the major obstacles to void safety turned out to be multithreading and arrays. It was not clear to us, at the beginning of this effort, that they would even figure in the discussion. The original article [10] does not mention them; their importance
became clear as we started applying the mechanism to the mass conversion of existing programs and libraries.

The "Arrays" bit is sort of obvious if you watch all the hoops the STL designers have to go through with traits and containers...

### To clarify

I have no issues with NullObject, I use them all the time.

My issue is precisely with assinging potentially harmful default behaviors to a nil, at the language level.

> The domain of lists already has a meaningful zero: the empty list.

You are talking about lists, the abstract concept, for which the problem of null references does not arise. It arises for linked implementations of lists. In Eiffel, for example, there is usually no reason for an instance of LIST or its descendant LINKED_LIST to be void. It's the individual list cells, of type LINKABLE, that have a reference field right which, for the last element, will be void. This has nothing to do with lists in general, but involves a particular linked representation.

### If you use inheritance

to create a distinct EmptyList class; then why permit the right field to be void? It seems it would be more consistent to have it point to an instance of EmptyList; such a solution would avoid VOID entirely.

### related work by Cobbe

Richard Cobbe's dissertation is also very related work.

### Thanks

Thanks for the pointer, I didn't know about this work. (Interestingly, the author for his part doesn't seem to know about the initial attempt at void safety in Eiffel, even though it is in my keynote in the ECOOP 2005 proceedings.) It seems to have some good ideas which we will examine further.

### Splint and C

Combining Splint with C get's you most of the way.

With the appropriate flag on Splint assumes a pointer is non-null unless you have annotated it's declaration with /*@null@*/.

It disallows assignment of null, or possibly null pointers to non-null pointers unless they have been proved clean via an "if" or splint checking is turned off via a cast or annotation.