The history of the NULL pointer

Question

As we know, in C to dereference a null pointer is undefined behaviour. From what I understand, the PDP-7 and the PDP-11 both have ordinary memory that can be written to and read from at address 0.

On the PDP-11, that address is part of a memory region used to specify EMT and TRAP vectors. An operating system probably needs to be able to initialise these to the entry point of device drivers or whatever. And depending on model and configuration, writing to this memory location might cause a trap -- but the same goes for all other memory locations. So location 0 is not unique in that respect on this platform.

From what I can tell, the PDP-7 had ordinary memory at that address, just as many other machines do. But I understand that UB is very useful to compilers which need to be able to not guarantee a particular behaviour so that a particular architecture can be targeted easily.

So my question is what led some C standard to treat the NULL pointer differently from any other pointer? Did K&R want to target an exotic architecture or something?

Answer 1

The definition of NULL is a syntactic crutch to allow a programmer a clear expression that a pointer is, at certain times, pointing nowhere. It's meant for readability - and with increased compiler bloat even for automated checks.

On a hardware level there is no such thing. A pointer is a word, and a word always holds a valid number. So by convention zero was chosen - it could have been any other. Like -1 for example. Selecting 0 offered the advantage that a simple if(pointer) could be used to check if it's a valid pointer (or more correct, not 0).

So my question is what led some C standard to treat the NULL pointer differently from any other pointer?

C also doesn't treat NULL different from any other pointer. The C-Lib in contrast does, but not because of NULL, but rather as its (runtime) value of 0 will make some functions fail, when used as input.

Did K&R want to target an exotic architecture or something?

Nop. It's a concept needed from a pure software engineering point of view. Having a syntactic construct to handle uninitialized pointers improves readability and possibly enables further checks.

---

Now, for the historic part, NULL is, like the related handling of TRUE/FALSE inherited from BCPL (through B). Just here it was called nil.

---

Even with that little historic bit, I'm not sure if Retrocomputing is the right place to ask for this, as it's about a basic concept in software engineering and not anything burdened with historic implication. So a quick search in Software Engineering and Stack Overflow shows that this question has been asked many times. It's something people always stumble on, isn't it?

Answer 2

The important thing you may be missing is that a null pointer in C is not required by the standard to have the same binary representation as the number zero. It is still a "normal" pointer, but it points to a special location that the program is not allowed to use.

The integer constant 0 is turned into nullptr when used as a pointer. Similarly, 0 will become 0.0 when used in floating-point calculations, or false in boolean operations. Coercions are not just one-way: if(ptr) will convert a pointer into a boolean which indicates whether the pointer is not null. All of these conversions serve to avoid requiring that a null pointer shares the same representation as zero.

Most machines represent integer zero as all-bits-zero and comparisons against that are particularly cheap, so it is worthwhile to arrange things so that sentinel values such as null pointers and end-of-string markers are all-bits-zero, and also that +0.0 and false are also all-bits-zero.

There is some subtlety in C in that a literal 0 is converted into nullptr, whereas casting an integer that happens to be zero into a pointer will produce a pointer to location zero. Because they are the same thing on modern platforms, a whole class of potential bugs go away.

Answer 3

Another relevant historical tidbit: You may have noticed that the values chosen for NULL - i.e 0xFFFFFFFF and 0xDEADBEEF - are both odd-valued addresses. Most architectures (certainly most at the time Unix was created) did not implement addressing down to the individual byte; they were only able to address words of two or four bytes - that is, only even-valued addresses were legal. By choosing an odd-valued address for the value of NULL, the C compiler and runtime system ensured that any attempt to actually dereference NULL would immediately trap to the OS; that is why the usual error for dereferencing NULL on Unix is 'Segmentation Violation'.

Answer 4

Tony Hoare somewhat-famously in 2009 said this:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

While I don't have any specific citations, I suspect that C was influenced by ALGOL, or just made the same decision separately since having a specific value to represent "not a valid reference" was an easy and useful thing to do. It wasn't so much about "how to point to a specific part in memory that's named 'zero'" as much as "we need to define a way to indicate that a pointer is not currently valid", particularly as a sentinel value. Given the constraints of computers at that time, it seemed a reasonable thing to do. So, one just creates a value called "NULL" which can be assigned to any pointer type, and there you have it.

Answer 5

For the PDP-11, you're thinking of physical address 0 for interrupt vectors. Logical address 0 in a user program just contains the first bytes of program code, i.e. the primary entry point ("start" from crt0.s). On a default executable, nothing stops you from reading it or writing to it, though if you write after the address returned to by main, you're gonna have a bad time. With ld -n, it'll be read-only and attempting to write it will cause SIGSEGV.

So in that sense, a null pointer and a pointer to the "start" routine were identical, but it wasn't actually possible to reference assembly routines that did not begin with underscores from C. The PDP-11 probably wasn't the only architecture to put machine code (particularly startup code) that was not a valid C function at the zero address... it's a natural place to begin execution at, it wasn't something you could intentionally make a C pointer to, and it's something you need anyway.

The other solution is just to waste some small amount of space ensuring that that address is not used for anything. On "split I/D" executables on the PDP-11, data address 0 contains a zero explicitly put there for that purpose in crt0.s - in my test program, this was followed immediately by character data for the string literals I used with printf. (As has been pointed out, this could be at any address, not necessarily 0.)

Answer 6

As we know, in C to dereference a null pointer is undefined behaviour.

It is now, but the PDP-11 was an obsolete architecture before the first standard C was published. At the time when the PDP-11was current hardware, the only thing close to a standard was The C Programming Language by Kernighan and Ritchie (henceforth referred to as K&R).

The null pointer wasn't a formal a concept back then and pointers were generally considered to be interchangeable with ints although that wasn't always the case (a primary source of pain for portability). A pointer whose value was 0 was considered special and there was a macro NULL whose definition was something like ((char *) 0). Note that K&R C has no void type.

Dereferencing a null pointer is only designated as undefined behaviour so that the compiler doesn't have add a check to every dereference to make sure the pointer is not null. It's perfectly acceptable for your architecture to have that work as with any other address. In fact, if your program crashes with a SIGSEGV when you dereference a null pointer, it is not because the compiler put a check in but because your operating system has made it illegal for user space programs to access the location.

So an operating system writer could set up the PDP-11 trap vector table in C as long as he is confident that the compiler will treat address 0 like any other. Since, in early versions of Unix the OS team and the compiler team overlapped, this was obviously not an issue.

So my question is what led some C standard to treat the NULL pointer differently from any other pointer? Did K&R want to target an exotic architecture or something?

No. The C standard came a decade after C and Unix were written. By this time it was obvious that null pointers were causing issues.

Edit

OK, so I had a look at my copy of The C Programming Language (first edition) and it turns out that I was wrong. On page 97 we have (in relation to implementing a custom allocator)

C guarantees that no pointer that validly points at data will contain zero, so a return value of zero can be used to signify an abnormal event.

On page 190

A pointer may be compared to an integer but the result is machine dependent unless the integer is the constant 0. A pointer to which 0 has been assigned is guaranteed not to point to any object, and will appear to be equal to 0; in conventional usage, such a pointer is considered to be null.

[my emphasis]

Setting up an interrupt table for an operating system would not be considered conventional usage.

Answer 7

C treats NULL differently because it is undefined behaviour.

Undefined behaviour is very different to implementation defined behaviour. Implementation-defined behaviour can simplify portability by allowing different implementations to make different choices (for example, different platforms have different native integer representations).

Undefined behaviour is only partly related to portability - there's no requirement that undefined behaviour be consistent, even on the same platform (so even if C had only targetted a single platform, it may still have included undefined behaviour). In addition to the portability gains, undefined behaviour allows implementations to emit simpler or faster code, by making error handling optional for certain error conditions. To quote the C rationale document (copied from here):

The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. The goal of adopting this categorization is to allow a certain variety among implementations which permits quality of implementation to be an active force in the marketplace as well as to allow certain popular extensions, without removing the cachet of conformance to the Standard. Appendix F to the Standard catalogs those behaviors which fall into one of these three categories.

Unspecified behavior gives the implementor some latitude in translating programs. This latitude does not extend as far as failing to translate the program.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior.

Implementation-defined behavior gives an implementor the freedom to choose the appropriate approach, but requires that this choice be explained to the user. Behaviors designated as implementation-defined are generally those in which a user could make meaningful coding decisions based on the implementation definition. Implementors should bear in mind this criterion when deciding how extensive an implementation definition ought to be. As with unspecified behavior, simply failing to translate the source containing the implementation-defined behavior is not an adequate response.