Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!lll-winken!unixhub!shelby!neon!craig
From: craig@Neon.Stanford.EDU (Craig D. Chambers)
Newsgroups: comp.object
Subject: Re: Void references
Message-ID: <1990Nov12.003645.26615@Neon.Stanford.EDU>
Date: 12 Nov 90 00:36:45 GMT
References: <1990Nov7.220902.13393@Neon.Stanford.EDU> <1990Nov9.010930.26493@Neon.Stanford.EDU> <447@eiffel.UUCP>
Organization: Stanford University
Lines: 103

In article <447@eiffel.UUCP> bertrand@eiffel.UUCP (Bertrand Meyer) writes:
>From <1990Nov9.010930.26493@Neon.Stanford.EDU>,
>craig@Neon.Stanford.EDU (Craig D. Chambers) writes:
>> In Self we are rewriting our code to avoid using a
>> generic nil object, always initializing variables to "real" objects.
>> In some cases we have type-specific null objects that implement all
>> the messages that should be understood by objects of the type,
>> typically by doing nothing and terminating a recursion.
>
>	This is the worst idea I have heard in a
>long time (which means something). When you find that an operation
>is impossible to execute, you just ignore it! What about the
>specification - the contract - that your client expects?

OK.  Let me try to be clear here.  I'm not just calling nil a new
name, and implementing messages that mask errors.  That's clearly
silly, and I try not to advocate silly things.  Give me a little
credit.  This business with type-specific null/empty objects is a
useful technique for writing programs in a good object-oriented
language; I had hoped it was a little more widely known.

Let's consider a linked-list abstraction, implemented with cons-cell
objects and some sort of end-of-list object.  In most implementations
of this abstraction, the end-of-list object is either a void reference
(null pointer) (e.g. Eiffel) or a pointer to the generic nil object
(e.g. Lisp, Smalltalk).  The code for iterating down the list,
starting at a cons-cell, typically tests whether the next element
(cdr) is nil, and if so, returns.  If the next element is non-nil,
then the iteration recursively invokes the iteration function on the
next element of the list.  Here's some Smalltalk code for this
function:

"In class ConsCell"

do: aBlock
	aBlock value: car.
	cdr isNil ifTrue: [ "do nothing " ]
		 ifFalse: [ cdr do: aBlock ].

Most routines in the ConsCell class will have similar tests for nil of
the cdr instance variable.  Plus all users of a list will have to test
for empty list (i.e. isNil) before sending a message like "do:" to the
cons-cell.  This is pretty ugly, and all the testing operations are
contrary to the spirit of object-oriented programming.

A better way of implementing this list abstraction is to recognize
that there are two representations of a list link (ConsCell and
EndOfList) and that both have the same interface.  EndOfList is an
example of a type-specific null object, but it isn't just another name
for the generic nil, since it is a perfectly reasonable representation
of an instance of the list abstraction, namely, an empty list.  Here's
some Smalltalk code for this kind of implementation:

"In class RevisedConsCell"

do: aBlock
	aBlock value: car.
	"continue the recursion with the next list element"
	cdr do: aBlock.

"In class EndOfList"

do: aBlock
	"end of the list; do nothing"
	self.

Both RevisedConsCell and EndOfList are subtypes/subclasses/whatever of
some List abstraction, but are different representations appropriate to
different subsets of the instances of List.  Since EndOfList is a
perfectly reasonable List instance, understanding all the List
protocol, neither the code in the RevisedConsCell class, nor the users
of the list, need to check for some nil object.  This is a more
object-oriented way of implementing lists, and this same style works
for other kinds of "behavior modes" that exist within an abstraction:
expanded-vs.-iconified windows, empty-vs.-non-empty collections, etc.

To preempt the next comment/criticism of this scheme, I'll claim that
it works well even for mutable objects, given the right language
support.  One problem with the EndOfList class above is that it's hard
to add an element to an empty list in place, mutating an empty list
into a non-empty list.  Self offers a natural solution to this problem
using dynamic inheritance.  The list instance is represented by an
empty object that is initially a *child* of the EndOfList object.  To
allow the user to add an element to a (currently) empty list, the
EndOfList object defines the "append:" method that creates a new
ConsCell object containing the new element, and then switches the
parent pointer of the child list instance to point to the new instance
of ConsCell.  No references to the list object need to be updated
(i.e. no "become:" was used), but the list now behaves as if it were a
singleton list object, since it inherits from the ConsCell object.

To find out more about dynamic inheritance and its usefulness for
dynamically-changing behavior modes within an abstraction, you can
read the paper "Organizing Programs without Classes" in the set of
papers available via anonymous ftp from otis.stanford.edu.  It is also
scheduled to appear in an upcoming issue of "Lisp and Symbolic
Computation" devoted entirely to Self.

I hope this discussion is a little more clear on what I mean by
type-specific null/empty objects and why they are a better way of
writing many kinds of abstractions.

-- Craig Chambers