Null Object

A special case of the SpecialCase pattern.

A Null Object can be useful in recursive structures, typical of CompositePattern. But it is also useful in other contexts too. For example, it's commonly used in StrategyPattern (where no particular strategy is needed).

See below for a criticism of this pattern

A recursive structure, like a list or a tree, requires some special marker to define those nodes at the structure's boundary. Also interior and edge nodes should be as similar as possible since one can become the other as the structure grows or shrinks.

Therefore: Mark the space just beyond the structure's edge with instances of an appropriate null object. Expect this object to participate in calculations by returning zero, null or empty, as appropriate for any particular algorithm.

For example, computing the depth of a binary tree involves computing the depth of its left and right subtrees ...

depth
^ (left depth max: right depth) + 1

To complete this calculation we define the value for null trees ...

depth
^ 0

Thanks for the SmallTalk, how about an example in Lisp:

   ;; CommonLisp, the first ANSI-standard OO language has the NullObject built in!

   ;; Here, the method parameter is implicitly specialized to type T, which catches
   ;; the method call if there is no other more specific match. See discussion below.

   (defmethod depth (tree) 
     (1+ (max (depth (left-child tree))
              (depth (right-child tree)))))

   ;; Here, the parameter is specialized to the NULL type, whose only value is NIL,
   ;; a.k.a. the NullObject.  This method catches specifically the call (depth nil).

   (defmethod depth ((tree null))
     0)

   ;; test case for NIL

   (depth NIL) ;; -> 0 yay!

   ;; Okay, NIL taken care of, now define LEFT-CHILD and RIGHT-CHILD methods over 
   ;; various tree-like types. Then we write a paper on NullObject, speak at conferences,
   ;; give workshops, etc.

-- SmugLispWeenies (taking over C2 Wiki! :)

Continuing with the above Lisp, how about turning rational numbers into trees? We just have to define LEFT-CHILD and RIGHT-CHILD methods in some way, for instance:

   (defmethod left-child ((num rational))
     (if (< num 1) nil (/ num 2)))

   (defmethod right-child ((num rational))
     (if (< num 1) nil (/ num 3)))

   (depth 0) ;; --> 1

   (depth 20) ;; --> 6

   (depth 1000) ;; --> 11

There we go.

Versions of this pattern by BobbyWoolf and BruceAnderson have been workshopped at EuroPLoP '96 and PLoP '96 respectively. NullObject is also part of a FunctionalPatternSystemForObjectOrientedDesign (here called VoidValue?). Bobby's version is to be included in PatternLanguagesOfProgramDesign-3.

http://home.att.net/~bwoolf/Null_Object/Null_Object.htm (BrokenLink, see 3 links at top of page, particularly the CiteSeer one)

Every recursive structure could expect to have one or more specialized classes implementing appropriate null object behavior. ExceptionalValue and BottomPropagation are related patterns that use an unspecialized object to serve in place of an error or exception.

[See NullObjectExamples for more examples.] See also NoNullBeyondMethodScope.

Here is the SmugLispWeenie take on NullObject: (Is this the "criticism"?)

It's a stupid reinvention of the object NIL in the Common Lisp language. The Lisp object system treats NIL as an object of type NULL, which is a subtype of every other type. By specializing methods parameters the NULL type, you can provide behaviors when the generic function call specifies NIL for the corresponding argument. Also, you can provide default matches by using the type T, whose instance is the object T. This is the supertype of every type. A method parameter specialized to T matches when nothing else does; every other type is simply a more specialized kind-of T, providing a more specific match. And of course there is just one NULL class. You don't need different kinds of null objects to satisfy some static inheritance constraints.

That's basically the BottomType. Which is commonly used to implement Nil/Null/etc. The problem with using BottomType for this purpose is that you can never have a reference to something that excludes nil; because nil is a subtype (and thus a valid value) for anything. While CeePlusPlus reference types are in many ways a dirty hack to make operator overloading tractable (what other language has both references AND pointers); they do have one useful property - you can generally assume that they are never NULL. Assuming, that is, some junior programmer doesn't write code like this:

 void foo (Bar *b)
 {
    Bar &bar = *b; // might not be check for b=NULL.  This is not kosher; however compiler is not required to emit
                   // runtime check for NULL-ness.  Lots of people assume that the *b in the expression will cause a 
                   // trap if b is NULL; but as nothing is really dereferenced; that often doesn't occur.
 }

The idea of providing sane behavior for NIL parameters did not originate in the object system. In Lisp (but not in related dialects like Scheme) there are many places in the language where useful behavior is provided over NIL instead of failing. This is a very simple idea. For example, NIL represents the empty list, and you are allowed to retrieve its elements. Rather than failing, expressions like (FIRST NIL), (SECOND NIL), (REST NIL) and so on just yield NIL. This doesn't use the object system at all, but conceptually, you can think of these functions as being methods that are specialized to a cons cell or to NIL. These behaviors simplify list processing code by eliminating a whole bunch of cases that would just deal with avoid doing the wrong operation on the empty list, or avoiding blowing up on accessing the seventh element of a six element list, etc.

I personally like keeping NULL separate from other types of nothingness, including the empty list. Of course, C/C++ has the bad habit of equating NULL with zero, which is just as bad... -- ScottJohnson

[One other problem with this particular use of nil; what if you have two different types, both of which implement a method (or support a function, whatever) with the same name (homonyms) but different semantics, and you want to provide default semantics for nil for both of the types, but different semantics for each... what do you do then? Use of NullObject allows you to keep your different "default types" separate.]

We now return you to Java and C++.

null used as sentinel

I'd like to emphasize that these objects are often used to boost performance in manipulating lists/trees. In these cases you will frequently find code like:

 for (p=&initialElement; (p!=0)&&(p->data<limit); p=p->next) { ... }

adding a null element (with the data element set appropriately), allows you to reduce the code to:

 for (p=&initialElement; p->data<limit; p=p->next) { ... }

thus saving half the comparisons. In this context the null-elements are often called sentinels.

Another example is a contour tracer. Here you will (depending of course on your algorithm) run around an image in a not predetermined way. You risk running over the border. If you mark the complete image border as non-contour you will:

save a lot of time previously wasted on border checks
likely make your algorithm more readable

So null-objects need not be objects at all. The principle is homogenizing your data-structure by changing the data at the end(s) of the datastructure.

(EditHint: is the sentinel idea important enough to create a SentinelPattern page? Apparently. CeeUnitTesting has another example of NULL being used as a sentinel. LinearSearch has a more general discussion of sentinels. )

Is there a name for the opposite pattern, the /dev/zero to NullObject's /dev/null? E.g., an empty Collection can be a NullObject. But what about a Collection that claims to contain any and all objects? (For example, a user has a Collection of authorized roles, and now we want to implement a superuser role.) Should this be a separate pattern? Could we call it InfiniteObject?. -- DavidBeutel

Hmm, I doubt, that this dual is well-defined. Null may correspond to the TOP element of a lattice. But your InfiniteObject? doesn't quite sound like the dual BOTTOM element. The BOTTOM element is mostly identified with erroneous program behavious (which means, that it stands for any possible value). -- GunnarZarncke

Thanks for your help. Maybe my Collection is more like a wildcard than like /dev/zero. But, I don't understand "lattice". Coming from Java, I see the NullObject pattern as a way to avoid the SentinelPattern (i.e., instead of using an actual null, use a NullObject that does nothing or contains nothing). I guess my Collection is just another way to avoid the SentinelPattern. Is there a name for the pattern of avoiding the SentinelPattern? -- DavidBeutel