Null References, the Billion Dollar Mistake

jonr writes "'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. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965.' This is an abstract from Tony Hoare Presentation on QCon. I'm raised on C-style programming languages, and have always used null pointers/references, but I am having trouble of grokking null-reference free language. Is there a good reading out there that explains this?"

null or not null, that is the question

[alain94040 (785132)]

It's hard to imagine life without the null pointer! That being said, the author is not really responsible for billions of dollars of mistakes, the programmers are.

If there is one thing I'll complain about, it's the choice of the value 0. It's almost impossible to trace it. When we do hardware debug of chips, we prefer to use a much more visible value such as 0xdeadbeef for instance. Otherwise a bad pointer will bland too much with all the uninitialized values out there.

In assembly, null has no particular meaning. If you dereference an address, you can do it in any range you like. It's just that 0 on most machines was not a good place to store anything, since it would typically be used to boot the OS or some other critical IO function that you don't want to mess up with. Thus null was born.

Re:null or not null, that is the question

[CTalkobt (81900)]

When debugging at the hardware level it's fairly common to fill uninitialized memory (or newly allocated in a debug version of the malloc libraries) with a value that will either cause the computer to execute a system level break ( eg: TRAP / BRK etc) or something fairly obvious such as ($BA).

If you don't like the 0's, then replace your memory allocation library.

Re:null or not null, that is the question

[cant_get_a_good_nick (172131)]

RE: malloc pattern initializer

what's a good one for x86 and AMD64 chips? While spelunking flags for valgrind, i remembered the thought process for 68k chips. Use an A-Line trap, unimplemented so execution would stop. Also, make it odd, so a dereference would trigger a bus error.

What's the best values for x86 debugging?

Re:

[clone53421 (1310749)]

How about 0xCC (INT 3), which is typically used as a debug breakpoint? It will halt the execution (as long as you're running the code in a debugger, which is assumed), and it's a one-byte opcode which is good since that means if you somehow jump into unallocated space, you can't jump into the middle of the instruction.

Re:null or not null, that is the question

[marcansoft (727665)]

Wrong. A NULL pointer is implementation-defined in C and !p would work just as well if the bit value of p were 0xdeadbeef for a NULL pointer. The compiler is responsible for that.

0 is used because it's convenient for compilers and architectures, not for programmers. Programmers don't care, they never see the bit pattern of a NULL pointer unless they're doing things wrong (casting to integers) or working on lower level architecture-specific code. Most think they do, though. See the C-faq section on NULL pointers [c-faq.com].

Re:null or not null, that is the question

[geekgirlandrea (1148779)]

Actually, in C the null pointer constant is a distinct value from integer zero. The standard requires the following (see section 6.3.2.3 of ISO C99):

• That the integer value 0, when cast to any pointer type, yield a null pointer
• That a null pointer, when cast to any other pointer type, yield another null pointer
• That any two null pointers will compare as equal, regardless of type

As for constructions like if (!ptr), the standard requires that the if statement execute if its value is non-zero, and it would be entirely legal for the null pointer to have a non-zero in-memory representation, but convert to the integer zero. See, for example, the comp.lang.c FAQ [c-faq.com].

Re:

[clone53421 (1310749)]

Well, jumping into memory filled with 0xBA would repeatedly execute the instruction 0xBABABA, or MOV DX,0xBABA. I'm thinking that's probably not what GP meant by $BA, but... well, that's all I came up with.

Re:null or not null, that is the question

[Toonol (1057698)]

MOV DX, BABA; GET UP N DANCE

Re:null or not null, that is the question

[jeremyp (130771)]

That's all very well, but in a production environment when dereferencing a NULL pointer you'd probably rather have the program crash than carry on merrily with bad data. With a zero null value, you can easily arrange for this to happen by protecting the bottom page of memory from reads and writes. That way, even an assembly language program can't dereference a null pointer.

Re:

[belmolis (702863)]

If that is true, the language compiled by the IBM POWER XLC compiler is not C. The C standard requires short-circuit evaluation of logical and.

Re:no such requirement at the assembly level

[thethibs (882667)]

You are confusing C with...well, I'm not sure what...Haskell, maybe? In many cases with C, the sequence of events is as important as the end result. C code can have side-effects.

C is not an expression evaluator, it's a control language; A && B is an instruction to copy A and if it is non-zero, replace the copy with B, in that order. A++ says copy A and then increment it.

Most of the people on slashdot can tell you why that's important and a few of them have; there are more than a few scenarios where not getting the sequence right would have undesirable effects even if the returned value was correct. Look up memory-mapped I/O.

Re:null or not null, that is the question

[johny42 (1087173)]

That being said, the author is not really responsible for billions of dollars of mistakes, the programmers are.

Who am I to argue with someone that is taking resposibility for my mistakes?

Re:

[rickb928 (945187)]

The first time I saw an ethernet MAC address of 02DEADBEEF20 I went on a 20-minute snipe hunt through the switches.

It was the /dev/net0 adapter in the standby member of a Sun cluster.

A month later, I got the inevitable frantic voicemail from the telecom guy, asking what the '^&(*ing 02DEADBEEF20 address' was, and would I pay more attention to these things and secure our network, please and thank you. I told him it belonged to the Teleradiology project, not to worry. He accused me of being an imbecile,

Re:null or not null, that is the question

[Thiez (1281866)]

> Another behaviour by default that C got wrong is initialisation: by default your variables are not initialised so if you forget to initialise your variables your program may act randomly which is a pain to debug, the correct default would be to have all variables initialised by default but with the option to let variables non-initialised which can be useful as a performance optimisation.

C did NOT get it 'wrong'. C just gives you a lot of rope to hang yourself with. You are free to write you own version of C that protects you from yourself (tweaking an open source C-compiler to initialise all variables by default (to what value?) should take you a few hours at most, and most of that time will go to finding the right source file to edit...), but I like it when C obliterates my foot every now and then. Alternatively you could write a program that goes through your code to look for situations where variables that may be uninitialised are used (I believe Java does this) and whines about it.

Re:null or not null, that is the question

[jvkjvk (102057)]

Mods are on crack.

Of course there is more than a syntatic difference between a reference and a pointer in C++.

For one, references CANNOT be null, while pointers are allowed to be null. I'd say that is an indictor of a pretty big semantic difference, wouldn't you?

To say that * or & "fixes" the difference is handwaving around the fact that pointers and references are two different, yet related concepts (that is, they have more that a "purely syntatical" difference).

To be pendatic, you can't even write a null reference in C++; the compiler will complain (more pendantic - although you can delete the underlying object sometimes, this does not make the reference null, merely dangling) so it is also nonsensical to talk about "null references" vis a vis "null pointers" per se, except in a most general way.

Regards.

Re:null or not null, that is the question

[Amazing Quantum Man (458715)]

Undefined behaviour. A reference must refer to a valid object. Also, dereferencing the null pointer (ip) is undefined behaviour.

Re:

[Carewolf (581105)]

You have much to learn. Don't mix how the language is supposed to work and what is actually possible.

P *p = 0;
P &r = *p;

References that are NULL are the worst kind.

20 second explanation

[AKAImBatman (238306)]

I am having trouble of grokking null-reference free language.

If you're familiar with SQL, then a simple "MyColumn NOT NULL" definition should explain it. Basically, the value can never be set to a null value. Attempting to do so is an error condition itself.

In fact, DB design is a pretty good analogy for the concept as databases often are forced to wrestle with this issue.

Consider for a moment how you would design a database that has absolutely NO null references. Not a one. Zip, zero, nada. Obviously the best way of accomplishing such a database is to denormalize any value that might be null. So if Address2 is optional, you would want to split Address into its own table with a parent key pointing back to the user entry. If the user has an Address2 value, there will be a row. If the user does NOT have an Address2, the row will be missing. In that way, empty result sets take the place of null values.

In terms of programming languages, there are a varity of ways to map such a concept. Collections are a 1:1 mapping to result sets that can work. If you don't have any values in your collection, then you know that you don't have a value. Very easy. Similarly, you can be sure that none of the values passed to a function or method will ever contain a null value. Cases where you might want to pass some of the values but not all can be handled either by method overloading (e.g. Java) or by allowing a variable number of parameters. (e.g. C)

Some pieces of programming would become slightly more difficult. For example, 'if(hashmap.get("myvalue") != null)' would not be a valid construct. You'd need to perform a check like this: 'if(hashmap.exists("myvalue")'

Of course, the latter is the "correct" check anyway, so the theory goes that the software will be more robust and reliable.

Re:

[Anonymous Coward]

doesn't NULL in SQL represent "unknown", which is something entirely different that a NULL reference, which in the context of programming languages is a discrete value?

Re:20 second explanation

[AKAImBatman (238306)]

doesn't NULL in SQL represent "unknown", which is something entirely different that a NULL reference

No. NULL in SQL represents an absence of data. Which is occasionally used to cover for unknown values. However, NULL is a piece of data that says there is an absence of data. Which is incorrect. Absence of data means that it doesn't exist. Therefore, nothing should exist in its place.

Normalizing the database can create a situation where the NULL is unnecessary. Therefore, the concept is not needed by computer science. The problem is that real-world considerations often override the ivory tower of comp-sci. And one of those considerations was the fact that RDBMSes have traditionally been organized according to a fixed column model. The inflexibility of the model is driven by the on-disk data structures which are optimized for fast access. OODBMSes (which are really fancy RDBMSes with many "pure" relational features that work around the traditional weaknesses of RDBMSes) attempt to solve this issue by introducing concepts like table-less storage, columns that may or may not exist on a per-row basis, and a dynamic typing system that potentially allow for any data type to show up in particular column. (Note that columns are often handled more as key-value pairs than what we normally think of as columns. This does not undo the theoretical foundation of the Relational model, only results in a different view on it.)

Re:

[BigHungryJoe (737554)]

Ok, I'm far from an expert on SQL, but if NULL doesn't represent "unknown" in SQL, then why does

select 1 from dual where 1 not in (2,3,NULL);

return an empty set?

Re:

[AKAImBatman (238306)]

That's a misunderstanding of the spec. NULL has no type, so evaluating NULL = 1 results in an unknown. That does not imply that NULL is an unknown value. I believe this reply [postgresql.org] on the PostgreSQL mailing list explained it best:

0 <> NULL (Indeed nothing equals NULL, other then sometimes NULL itself)

0 <> 1

Therefore, the statement: 0 NOT IN (NULL, 1)
Should always equate to false.

Therefore No rows returned. Ever.

It's a bit weird, but it makes sense when you actually follow the logic.

Re:20 second explanation

[jadavis (473492)]

It's a bit weird, but it makes sense when you actually follow the logic.

Not really.

The expression "0 <> 1" is true, but the poster you referenced also says "0 <> NULL", which is NOT true, it is NULL.

Additionally, NULL is not always treated as false-like. For instance, if you added the constraint "CHECK (0 NOT IN (NULL, 1))", that would always succeed, as though it was "CHECK(true)".

And if you think "it makes sense", consider this: ... WHERE x > 0 OR x <= 0
If x is NULL, that statement will evaluate to NULL, and then be treated as false-like, and the row will not be returned. However, there is no possible value of x such that the statement will be false.

I'm not a big fan of NULL, but I think the most obvious sign that it's a problem is that so many people think they understand it, when they do not.

Re:20 second explanation

[thePowerOfGrayskull (905905)]

And if you think "it makes sense", consider this: ... WHERE x > 0 OR x <= 0 If x is NULL, that statement will evaluate to NULL, and then be treated as false-like, and the row will not be returned. However, there is no possible value of x such that the statement will be false.

If x is NULL, the statement evaluates to false. This isn't "false-like"; NULL is the state of not having a value. Comparing a non-value to /any/ value of or range of values is logically false: X is neither LTE 0 nor is it GT 0; a non-value has no relation to the value 0.

While you can use it to derive a true/false value, NULL is not a (in the RDBMS context) value at all. Would you say in mathematics "empty set" makes no logical sense?

Re:

[vux984 (928602)]

Normalizing the database can create a situation where the NULL is unnecessary.

Not reallly. Suppose I'm going to do a mail out to my customers... so I need a table of addresses

select *
from addresses inner join addressline2s on addresses.pkey = addressline2s.fkey

And what happens? I'm now missing all the addresses that don't have a line 2. Well that's worthless.
how about:

select *
from addresses left outer join addressline2s on addresses.pkey = addressline2s.fkey

Yay, all my addresses. And I can cursor through th

Re:

[geekoid (135745)]

You can disagree all you like, but read the spec. NULL is absences of data. Undefined data is still data, just not defined, since NULL isn't a type, it can't be any type data. IT was specifically created to show absence of data.

Look it up.

Re:20 second explanation

[AKAImBatman (238306)]

You need to have NULL to represent missing data, anything else is actual data.

I don't think you understand the argument. Having the following is incorrect:

ID|Name|State|Address|Address2
5|Bob|MN|12 East St.|NULL

THIS is correct:

ID|Name|State
5|Bob|MN
 
ID|Parent|Address|Order
22|5|12 East St.|1

Note how there is no NULL value. In fact, NULL is antithetical to relational theory as all set values should have a value. Missing data should be normalized away.

There are only people who can't intuitively understand 3VL.

3 value logic has nothing to do with it. 3VL actually creates problems in this case. In fact, your very own snarky comment above is a perfect example of how things go wrong with 3VL:

ID|Contestant|Prize
2|AKAImBatman|NULL
 
resultset = sql("select Prize from Contestants where Contestant = 'AKAImBatman');
 
//Prints the stupid "NULL" answer
while(resultset.next()) print("He leaves with " + resultset["prize"] + " the home game.");

FAIL.

Now look at this situation:

ID|Contestant
2|AKAImBatman
3|geekoid
 
Parent|Prize
3|Remedial 6th Normal Form
 
resultset = sql("select Prize from Prizes join Contestants on Contestants.ID = Prizes.Parent where Contestant = 'AKAImBatman'");
 
//Correctly prints nothing
while(resultset.next()) print("He leaves with " + resultset["prize"] + " the home game.");

Re:20 second explanation

[MattRog (527508)]

"Obviously the best way of accomplishing such a database is to denormalize any value that might be null"

That's normalizing -- the table in this example is de-normalized

Re:

[clone53421 (1310749)]

...this: 'if(hashmap.exists("myvalue")'

...is the "correct" check anyway...

Well, it'd be "correct" if it had the right number of parentheses, anyway! ;p

Re:20 second explanation

[AKAImBatman (238306)]

Consider the situation of apples. If you have an apple, then something is in your possession. If you don't have an apple, what do you have? Do you have some sort of object that depicts your lack of an apple? Obviously not. Yet in the world of computers, we have this special piece of data that shows our lack of data. It's a bit like getting a certificate that you have no apples. The certificate accomplishes nothing except to fill a space that does not need to be filled.

Re:

[pi_rules (123171)]

It'll blow up in C# and Java.

Wouldn't help

[corporate zombie (218482)]

Fine. No null references. So I create the same thing by having a reference to some unique structure (probably named Null) and I still *fail to check for it*.

Null references don't kill programs. Programmers do.

    -CZ

Re:Wouldn't help

[nuttycom (1016165)]

If you use a sane class for references that could possibly be null (like Option [scala-lang.org] (aka Maybe in haskell) then your compiler will *force* you to handle the null case.

This is where null went wrong, at least in statically typed languages: it's a hole in the type system that errors fall through into your program. When coding in Java, I make an explicit point to never return null from a method; if I have a situation where no reasonable return value might exist, I use the Option class from functionaljava.org [functionaljava.org] and thus force the client to handle the possibility of the method not returning sensible data. Since Option obeys the monad laws [blogspot.com], it's easy to chain together multiple things that might fail (with the bind or flatMap operations.)

maybe type

[j1m+5n0w (749199)]

Maybe types are wonderful. I first thought they were inconvenient, since you have to pattern match against them any time you want to extract the value, but then I realized that that was something I ought to be doing anyways, and the advantages of never accidentally dereferencing a null pointer vastly outweigh a little extra typing. And then, more recently, I figured out how to use the maybe monad to string together a bunch of things that might fail without having to manually pattern match every time.

Algebraic data types

[Sneftel (15416)]

The concept of "no null references" would be very limiting in a language without algebraic datatypes [wikipedia.org]. You can think of null references as a sort of teeny limited braindead algebraic data type, actually. I get the feeling that much of the incredulity here stems from the posters not being familiar with languages that support them. If this describes you, check out Haskell and OCaML! They're the sort of languages that make you a better programmer no matter what language you're using.

Pass by reference

[hobbit (5915)]

I'm raised on C-style programming languages, and have always used null pointers/references, but I am having trouble of grokking null-reference free language.

Take a look at C++, in which you can declare methods to be "pass by reference" rather than "pass by pointer". Although the former is actually really just passing a pointer too, the semantics of the construct make it impossible to pass NULL.

Re:

[johannesg (664142)]

... the semantics of the construct make it impossible to pass NULL.

void bar (int &intref)
{
    intref++;
}

void foo ()
{
    int *intptr = NULL;

    bar (*intptr);
} // learn something new every day!

Re:Pass by reference

[Chris_Jefferson (581445)]

According to the C++ standard, as soon as you dereference NULL, you are off into the nasty old land of undefined behaviour, and all kinds of horrible things can occur to you.

An was an even Bigger mistake:

[Wargames (91725)]

Zero. The bane of all. It was the gateway math to all modern problems. It would be so much simpler with just countables. Surely the current crisis, measured in trillions would look so much better without all those zeros.
Whoever it was who invented zero should take responsibility for all the worlds problems, ex nehilo.

Re:

[AKAImBatman (238306)]

Null predates zero in the western world. The Romans had no number for zero, but they did represent the concept of nothing with the word 'nulla'. Thus if I had IIII denarii and spent all IIII, I would have nulla remaining. i.e. "nothing".

As an aside, the numbering is correct. The subtractive form of IV for four is a more modern construct that was not in common use during the Roman empire.

If you're still hell-bent on finding who defined zero as a legitimate numerical value, you'd need to look to 9th century I

Null as a concept

[JustNiz (692889)]

Stroustrup's "C++ Programming Language" book introduces a concept called "resource acquisition is initialisation" that was eye-opening enough to me that it forever changed the way I think about code, and also seems relevant to your point.

The basic idea is that an object is always meant to represent something tangible. As an example, consider the design of file object that abstracts file I/O operations. As a developer, I've come across this one several times, it is normal that such objects have open and close methods, however that makes the design of the object in contradiction with Stroustrup's concept because open/close provided as methods rather than only called in the constructor/destructor means the object may be in existence yet be in a state where it is not associated with an open file. You basically have to grok that having a file object around that doesn't directly map to an open file just adds overhead to the system and is basically bad OO design in that in some sense that object is meaningless.

Apply the same concept to a reference and you have your answer. If a reference is pointing at nothing, then what is its purpose? The only thing a NULL reference is good for is when the software design ascribes a special meaning to the value NULL. Instead of just meaning address location 0, it gets subverted to mean "variable unassigned" or the "tail node of list" or somesuch. Ascribing multiple meanings to a variable value (especially pointers/references that are only ever meant to hold memory addresses) is one example of bad programming practice known as programming by side-effect which most people agree should be avoided.

Another point is that in most OO lanugages, references have an extra benefit of being more strongly typed than pointers, menaing that reference is guaranteed to only ever be pointing at an instantiated object of its specific type. That guarantee also gets broken when a reference can be NULL.

Lying to the language - the real problem.

[Animats (122034)]

A useful way to think about troubles in language design is to ask the question "When do you have to lie to the language?" Most of the major languages have some situations in which you have to lie to the language, and that's usually a cause of bugs.

The classic example is C's "array = pointer" ambiguity. Consider

int read(int fd, char* buf, size_t len);

Think hard about "char* buf". That's not a pointer to a character. It's a pass of an array by reference. The programmer had to lie to the language because the language doesn't have a way to talk about what the programmer needed to say. That should have been

int read(int fd, byte& buf[len], size_t len);

Now the interface is correctly defined. The caller is passing an array of known size by reference. Notice also the distinction between "byte" and "char". C and C++ lack a "byte" type, one that indicates binary data with no interpretation attached to it. Python used to be that way too, but the problem was eventually fixed; Python 3K has "unicode", "str" (ASCII text only, 0..127, no "upper code pages"), and "bytes" (uninterpreted binary data). C and C++ are still stuck with a 1970s approach to the problem.

The problem with NULL is related. Some functions accept NULL pointers, some don't, and many languages don't have syntax for the distinction. C doesn't; C++ has references, but due to backwards compatibility problems with C, they're not well handled. ("this", for example, should have been a reference; Strostrup admits he botched that one.) C++ supposedly disallows null references (as opposed to null pointers), but doesn't check. C++ ought to raise an exception when a null pointer is converted to a reference.

SQL does this right. A field may or may not allow NULL, and you have to specify.

Look for holes like this in language design. Where are you unable to say what you really meant? Those are language design faults and sources of bugs.

Re:

[RetroGeek (206522)]

A null terminated String is a misnomer. It is actually an array of chars which uses a special character to signify its upper boundary. So that a second variable is not needed to hold the upper boundary. Zero was chosen by K&R.

In some languages, a String is an object, and the object holds the upper boundary, so a terminator flag is not required.

Re:There was a bigger mistake:

[Rik Sweeney (471717)]

Null-terminated strings. The bane of modern computing.

Yeah! Let's abolish them, life would be much simplerasdjkaRGfl$!jaekrbFt6634i2u23Q0CCA;DMF ASDJFERR

Re:There was a bigger mistake:

[Anonymous Coward]

I agree.ï½ï½ï½ï½ï½ï½ï½cï½ï½A
5ï½)ï½"ï½ï½ï½lï½3åï½ï½ï½SLï½4ï½54Vï½iï½ï½ï½D.O%N|ï½ï½ï½Tï½2nï½ì'iï½ï½ï½;ï½
                                                  ï½,ï½ï½(85ï½Iï½{ï½ï½ï½ï½)ï½Oï½Æ¼ï½%Cï½iwï½ï½ï½ï½ï½ï½I!,.ï½Õ'ï½ï½ï½ï½!ï½òfsQï½ï½zï½ï½Gï½ï½ï½aï½zï½-@ï½ yï½Ë+ï½ï½ï½Xï½ï½ï½ï½"ï½cï½âï½ï½ï½ï½ï½ï½ï½ï½ï½ï½dï½nbÕoeï½ï½ï½ï½lï½ï½ï½ï½ï½;hmï½ï½

Re:There was a bigger mistake:

[Anonymous Coward]

Just allocate the same amount of memory for everythi

The mistake was actually not having a standard

[Nicolas MONNET (4727)]

for Pascal type strings in C. The fact that null-terminated strings existed wasn't the problem, they make some sense in some respects, such as when you want to pass text of arbitrary length. But the real problem, the real bug was not having a standard way of doing real strings in C. Everybody had to do it himself, poorly. Had there been a standard, no matter how poor, it would have been a starting point to do something better if needed, and would have been better anyway for many uses than C strings. It would have avoided MANY vulnerabilities from common software.

Re:

[Vanders (110092)]

The problem with Pascal strings is that it's easy for a short-sighted implementer to paint themselves into a corner. It's all very well and good to say "The first two bytes in a string are used to indicate the length of the string" but then what do you do a decade from now when a 16bit string is laughably small? The benefit of NUL terminated strings is that there length is only limited by the memory available to you and yet are forward and backward compatible by decades.

Re:There was a bigger mistake:

[Panaflex (13191)]

Which comes from Pascal - which has always had the length at the beginning. Hence why pascal strings always had limits.

Re:

[Sneftel (15416)]

Actually, if you were defining a "null" value, you'd make it a Top-type, meaning it would be a subclass of all other types. Otherwise you couldn't set an arbitrary reference to point to null, because null would be insufficiently derived.