Null References, the Billion Dollar Mistake 612
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?"
Re:20 second explanation (Score:5, Informative)
"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:There was a bigger mistake: (Score:3, Informative)
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.
Algebraic data types (Score:5, Informative)
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.
Arrogance? (Score:1, Informative)
Is it not a tad arrogant to claim that he single-handedly is responsible for a billion dollars in mistakes? First, as an earlier poster remarked, the programmers themselves, or at least the current business context of programming, are perhaps more responsible. Second, while I'm aware that Tony Hoare is largely responsible for defining Algol -- though it was a committee effort -- it may just be on the edge of possibility that a high performance language such as C would have still included null references even if Algol did not. And Hoare's reference to Microsoft's work is nothing but PR; MSR is his current employer. Plenty of other earlier efforts have addressed null pointer dereferences; and of course certain classes of languages avoid the problem entirely.
Re:null or not null, that is the question (Score:2, Informative)
its not the memory allocation library that is at fault.
its the expectation of the app developer to instincively do
if(!ptr){ ... }
you have to change the fundimental way the compiler works and alter boolean logic to account for existing code which works like this to then accept 0xdeadbeef under some conditions and not others.
Re:There was a bigger mistake: (Score:5, Informative)
Which comes from Pascal - which has always had the length at the beginning. Hence why pascal strings always had limits.
Re:20 second explanation (Score:5, Informative)
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:null or not null, that is the question (Score:2, Informative)
Re:There was a bigger mistake: (Score:2, Informative)
what happen inside is opaque, and most probably std::string constructed with a grain of salt are the pascal kind (a memory allocation and a separate character counter)
*depending on your std implementor.
Pass by reference (Score:4, Informative)
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.
It's not that NULL pointers are a problem (Score:2, Informative)
It's unitialized pointers (and, for that matter, other variables) that are the problem. At least in assembly and C/C++. I don't think I ever had cause to use pointers in Perl or Python. Or C#. Null pointers or zero values in other variables are easy to test for anyway. It's the uninitialized variables that bite you in the ass.
Re:null or not null, that is the question (Score:1, Informative)
Please understand there is a difference between a null pointer and a null reference. The difference is very important in C++.
In C++ the difference is purely syntactical, and nothing that a * or a & won't fix.
Re:Pass by reference (Score:3, Informative)
... 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:An was an even Bigger mistake: (Score:3, Informative)
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 India. Their mathematics had evolved far enough to where they stopped asking the philosophical question of "is nothing a number?" and simply used it to get math completed.
Re:null or not null, that is the question (Score:5, Informative)
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:20 second explanation (Score:3, Informative)
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:
It's a bit weird, but it makes sense when you actually follow the logic.
Re:20 second explanation (Score:2, Informative)
What NULL "means" is undefined. There are at least two possible meanings, and it is up to the database designer to define, for every column in which null is allowed. The two meanings obvious meanings are either "unknown" or "has not got". For a Date Of Birth column, it is obviously "unknown", because everybody has a DOB. But what does a null Date Of Death column mean? In a commercial context, it probably means that, so far as the database is concerned, the person is still alive. But in a historical database, it could mean that the DOD is really unknown, or that the person is alive. Likewise an Address3 line might interpret NULL as Address3 is "unknown" if Address1 is null and "has not got" if Address1 is non-null. Good database design will always specify this.
Re:Pass by reference (Score:4, Informative)
Re:20 second explanation (Score:3, Informative)
It'll blow up in C# and Java.
Re:null or not null, that is the question (Score:2, Informative)
Of course nothing stops you from have a reference bound to an object that's gone out of scope, but that's different than a "null reference", which doesn't exist.
Re:20 second explanation (Score:3, Informative)
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 (Score:4, Informative)
I don't think you understand the argument. Having the following is incorrect:
THIS is correct:
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.
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:
FAIL.
Now look at this situation:
Re:null or not null, that is the question (Score:4, Informative)
Undefined behaviour. A reference must refer to a valid object. Also, dereferencing the null pointer (ip) is undefined behaviour.
Re:20 second explanation (Score:3, Informative)
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 them. ... except wait... I've got a bunch of nulls in the returned set. Even though my database doesn't contain any nulls, my simple query does...
So what was the point of eliminating them from the database?
Now in the real world, any amount of information might be missing, not just line 2. There are addresses without cities, without streets, Addresses in particular are difficult to model well. In fact the whole 'address line 1, line 2, line 3' thing is aready a cop-out because its too much effort to normalize addresses into separate fields. And when dealing with international addresses, it usually just simplest to give them a multiline text block and say, here, you fill it out the way you want...
Russian addresses for example are supposed to be upside down. In Canada the postal code is supposed to be after the province, in Sweden its before the city (and there is no province...)... etc. So even if you've got the right fields, the order is wrong. You could spend a year just modeling street addresses.
Re:null or not null, that is the question (Score:3, Informative)
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.
maybe type (Score:5, Informative)
Re:null or not null, that is the question (Score:3, Informative)
While there might be a aesthetic difference in C++, functionally they are identical since a reference is just a pointer with some syntactical sugar to make it look like it isn't.
Too pervasive (Score:3, Informative)
The problem with NULL/null/None as implemented in C++/Java/C#/Python/whatever is that it's pervasive - it always "adds itself" to the list of valid values of any reference type (= pointer type in C++, = any type in Python), in all contexts. At the same time, it isn't truly a valid value, because you can't do with it what you can normally do with any other value of the type. It's actually a lot like signalling NaN [wikipedia.org] for object references, and is an equally bad idea for the same reasons.
How to handle that? Why, with explicit "nullability markers", and languages which track nullability propagation, and require to check for null everywhere you try to perform an operation that won't work for a null value whenever you have a value that can potentially be null. In FP languages, this is naturally done with ADTs; for example:
Note that OCaml compiler, in the example above, won't let you omit the "None" branch. You have to handle that (well, you can just pass on the "int option" value, but only to another function that is declared as taking one, and not just "int"). Also note how the other branch is guaranteed to get some specific, "non-null" int value for x.
These enforced checks prevent silent null propagation, which is the bane of Java, C#, and other languages in the same league. All too often some code somewhere gets a null value where it shouldn't, stores it somewhere without checking for null, and then another piece of code down the line extracts that value (which is not supposed to be null!), passes it around to methods (which pass it to more methods, etc), and eventually crashes with a NullReferenceException - good luck trying to track down the original point of error!
Haskell's null-free behavior (Score:2, Informative)
I can illustrate the concept of a null-free language with examples from Haskell.
With Haskell types, you can specify all the valid values of a particular bounded type (the same is true for non-bounded types, but its more obvious for bounded ones):
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
Something of type "Day" cannot be NULL. It must be one of the days of the week. It's impossible to construct a value of a "Day" type without "assigning" it one of these values.
But then what if you want to handle a case where it might be none of these? There's another type for that called "Maybe", and you can wrap "Day" (or any type) in "Maybe" to indicate that it might be none of these. So "Just Monday" is a value simultaneously indicating non-null, and providing the Day value. "Nothing" indicates NULL or "none of the above".
For instance, if you write a function which gives the next day of the week, given a day of the week, it should input Day and output Day. It doesn't make sense for either its input or its output to be NULL. That is, it should have type "Day -> Day".
But if you want to handle for instance, a case of user input or parsing, where they might not give a valid day, then you should use the type "Maybe Day" or something similar.
Values of "Nothing" in Haskell roughly correspond to NULL except that the type system differentiates cases where something might be NULL and cases where something promises not to be NULL.
This turns out to be a useful distinction :)
peace,
isaac
Re:null or not null, that is the question (Score:5, Informative)
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):
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].
that constant is known to the compiler (Score:3, Informative)
The compiler depends on the OS to set up certain things, including the memory at address 0.
If I remember right, *(int)0==0 on this system.
It's totally legit. The C standard says nothing about how the assembly code behaves, or even that there is any assembly code. (C can be an interpreted language)
Re:Trouble is that even if you remove NULL-refs (Score:3, Informative)
We're not talking about not having null references at all. Nullable references are in fact very useful in many situations, as you point out.
The problem is that in many languages, it is not possible to describe a non-nullable type. I.e. a type that guarantees that the value it annotates is not null.
This is useful because the vast majority of actual code doesn't really deal with 'null' references, and in fact will break if 'null' references are passed in. Right now, there are two ways to ensure your code is safe:
1. make assertion-type checks everywhere. This is a pain in the ass to write and maintain compared to providing a non-nullable type. It's also slow to throw in unnecessary null checks everywhere during runtime.
2. don't check aggressively, but ensure in an ad-hoc way that all not-null preconditions are met. Basically, you just make sure to never call the relevant methods with null values. This has the problem that you have to keep track of EVERY SINGLE PLACE a null may be introduced and eventually find its way into the method. This may be easy in simple applications, but can become very tedious in large applications.
Providing a non-nullable type constructor saves all of those things. The compiler can ensure that a NULL never makes it into a variable marked not-null. You don't have to care about it. You can split your code up into the sections that are "pure" and sections that are "impure", and keep all your null-sanity-checking in the (what should be a relatively small) 'impure code', which calls into the pure code, with the compiler ensuring the calls are all valid.
No work, just a simple type annotation. That's the potential.
-Laxitive
Re:null or not null, that is the question (Score:3, Informative)
I think Microsoft Visual C uses 0xCCCCCCCC.
No, it represents a null pointer as an all-bits-zero value, as do almost all other C implementations.
But then you have to code:
No, you don't. In the C Programming Language, if p is a pointer, then !p, p != 0, and p != NULL mean the same thing, regardless of how null pointers are represented.
Re:20 second explanation (Score:3, Informative)
Variant types (or, put more generally, algebraic data types [wikipedia.org]) are indeed a general solution for this problem, that can be reused for countless others.
The simplest example here is the way you define linked list types in a functional language like Haskell. In pseudo-code (yes, I know this might not be valid Haskell code):
This is a data type declaration that says that the type "List of a" is either the singleton EmptyList value, or a 'Node a' value, which contains (as struct fields, basically) an element of type a and a List of a. (In case it isn't clear, 'a' is a type parameter here; so a list of strings would be 'List String', a list of integers would be 'List Integer', and so on.)
This works just as well to allow you to define generic nullable type constructors (which the standard Haskell library provides):
The type 'Maybe String' represents a value that might be either 'Nothing', or 'Just x' for some x of type String.
Re:null or not null, that is the question (Score:3, Informative)
NULL has always been implementation defined. The whole reason why the macro was put into ANSI C was to move people away from the practice of casting a 0 into a pointer as was done with K&R C. While rare today, there have been commercial computers that didn't use 0 for the null address. The comp.lang.c FAQ lists some of them [c-faq.com].
Stroustrup's unwillingness to implement a null keyword is the biggest single flaw in C++. It's pretty silly to pepper your code with magic 0's when the compiler could very well be changing them to something else if the target platform uses a different convention for nulls. It completely flies in the face of the type safety mechanism in C++ to have this sort of automatic conversion of a literal integer into something else that is decidedly *not* an integer.
Considering all the cruft that has been bolted onto C++, it's really annoying that B.S. couldn't see the wisdom of having a "null" keyword (or "_Null" a la C99 "_Bool").
Re:no such requirement at the assembly level (Score:3, Informative)
The optimizer wouldn't do it unless there were no side effects to the right hand side of the short circuit operator.
So
if (foo && (*foo == CONSTANT))
and
if (!foo || (*foo == CONSTANT))
would be optimized in this way
but
if (foo && baz(*foo))
would not (since function baz could have side effects).
It doesn't matter what was at location 0; the test for null was still evaluated, but condition code arithmetic rather than branches were used to handle it.
Re:null or not null, that is the question (Score:3, Informative)
> I'm sure it doesn't help things that Stroussoup made this explicit [att.com] in C++. So if your view is that C is a subset of C++, you'll get these trivia wrong. Unfortunately, C and C++ will penalize you for getting trivia questions wrong with great zeal.
You are wrong on two counts: first, his name is Stroustrup. Second, in C++, like in C, the literal 0 in a pointer context will be turned into the NULL pointer by the compiler.
void *p = (void*)0;
p will be a NULL pointer
int a = 0;
void *p = (void *)a;
p may not be a NULL pointer, as the 0 was not a literal in a pointer context.
Hence,
if (p)
means:
if (p==0)
so, if p is a pointer type, it means:
if (p==(void*)0)
which means
if (p is the NULL pointer)
The NULL pointer can be represented internally by whatever bitpattern or trick that the compiler writer wants.