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?"
There was a bigger mistake: (Score:2, Insightful)
Null-terminated strings. The bane of modern computing.
Re:20 second explanation (Score:3, Insightful)
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:null or not null, that is the question (Score:5, Insightful)
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.
Wouldn't help (Score:5, Insightful)
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:There was a bigger mistake: (Score:5, Insightful)
Null-terminated strings. The bane of modern computing.
Yeah! Let's abolish them, life would be much simplerasdjkaRGfl$!jaekrbFt6634i2u23Q0CCA;DMF ASDJFERR
Re:Null is just a value (Score:3, Insightful)
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.
Re:null or not null, that is the question (Score:4, Insightful)
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.
The mistake was actually not having a standard (Score:5, Insightful)
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:null or not null, that is the question (Score:1, Insightful)
Re:20 second explanation (Score:5, Insightful)
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.
Wrong - wrongly using valid pointers causes most (Score:1, Insightful)
If what Windows Update sends me on Patch Tuesday is any judge null pointer dereferences are actually quite rare. Almost all appear to be buffer overflows and things like that (such as accidentally overwriting your stackframe - oops) and as such are caused by erroneously using a perfectly valid pointer. So the lack of range checking, and would, I guess, include the effects null-terminated strings, would probably be the most expensive. I think the reason null pointer issues are rarer is because these usually indicate a predictable fail state which is checked for. You usually only get them when you know that you not only can get them, but that you must necessarily check for them because there would be no other way to implement your algorithm. End of a linked list, for example. A map from which you retrieve items that you might not have put in there is another one. Oh, and of course I don't think all the blame can fall on the language designer even if he were really the cause behind the problem (as is highly debatable in this case) because the programmers implemented their programs, they thought they had enough prowess to use the language, and if they didn't they should have used something else. If you're drunk, you shouldn't be using a chainsaw, and the manufacturer can't be blamed if you saw your leg off.
Re:20 second explanation (Score:5, Insightful)
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:null or not null, that is the question (Score:5, Insightful)
> 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.
Lying to the language - the real problem. (Score:4, Insightful)
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:null or not null, that is the question (Score:2, Insightful)
Or you could simply define that "!ptr" means "ptr is not a valid pointer" rather than "the value of ptr is 0".
Re:null or not null, that is the question (Score:1, Insightful)
cool, great offtopic story about what a huge asshole you are.
Re:20 second explanation (Score:4, Insightful)
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:null or not null, that is the question (Score:4, Insightful)
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.
no such requirement at the assembly level (Score:3, Insightful)
The compiler can do anything it damn well pleases, as long as the end result acts like it should.
The compiler certainly can dereference the pointer. It can also throw in a call to sin(42), a write to some memory containing the current line of code, and a system call to check for pending debugger stuff.
None of this would make the high-level view of things be anything other than the required short-circuit evaluation of the given code.
Re:A pointer may be a reference. (Score:3, Insightful)
But a reference is not necessarily a pointer.
In the context of this article, it sure as hell is. The entire point is that the concept of "NULL" can be dangerous. And pointers and references both support this concept, and are thus dangerous for the exact same reasons.
how it works (Score:3, Insightful)
We do "if (foo && *foo == CONSTANT)" like so...
The programmer wants to access *foo, unless it is NULL. We will thus do so. Additionally, we know that *NULL will not fault (on the AIX operating system) and that it will give us a zero. Thus, we can access *foo in any case.
The code becomes:
tmp=*foo; if(foo && tmp==CONSTANT)
The C standard only places requirements on an abstract machine. Underneath it all, the code could be getting executed by a bunch of monks who chisel computations into blocks of granite. It doesn't matter if one of the monks takes a bathroom break or whatever. The C standard doesn't care.
Re:20 second explanation (Score:2, Insightful)
See my post right above yours. Basically, one way of "abolishing null" is to replace it with more general variant type features that allow you to guarantee that nulls can only occur where your program declares they may. In that case, the answer to your question is simple: if your hash table's if of type Map, then the get operation's signature is something like this:
The idea behind this sort of solution is that the nulls problem isn't the existence of nulls, but rather, the fact that the language type system forces every type in your program to admit null in its domain. The solution is to distinguish between the type of a Foo and the type of "Foo or nothing."
Re:no such requirement at the assembly level (Score:4, Insightful)
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 (Score:2, Insightful)
>I like it when C obliterates my foot every now and then.
Once again reinforcing the stereotype that people who enjoy programming in C are masochists at heart.
Re:no such requirement at the assembly level (Score:3, Insightful)
Re:An was an even Bigger mistake: (Score:3, Insightful)
Ki>Zero. The bane of all. It was the gateway math to all modern problems. It would be so much simpler with just countables. ... Whoever it was who invented zero should take responsibility for all the worlds problems, ex nehilo.
Heh. I'm glad someone managed to bring up what should be obvious to anyone competent in basic math. While reading the posts here, I kept thinking "Yeah, and you have the same sort of problems if you allow your numbers to include zero." But I figured that the folks making the silly arguments probably wouldn't understand that sort of verbal irony, so I just let it pass.
I can easily imagine variants of most of the arguments here being used thousands of years ago against the individuals in India and Central America that started casually using that weird "0" symbol in their calculations. "What's the need for something that doesn't represent anything?" "I only need to count things that exist; there's no reason to count things that don't exist." And on and on.
This whole discussion does sorta put a limit to any claims of technical competency on the part of the "tech nerd" population of /.
(And to I need an extra . at the end of that sentence? That oughta be good for a long discussion, as well as the question of whether or not the final ')' in this sentence balances the initial '('. ;-)
Its about Types (Score:2, Insightful)
I think the main issue here is that when you're developing a type system, you generally want the types to classify objects into certain categories that tell you things about them. So if I define some kind of a reference type, what I am saying is that an object of that type is a kind of a pointer to something.
So now, if I allow null references, then my reference type is really saying that "objects of this type are pointers to either something or nothing". That's all well and fine, but it makes the type less precise, in that it conveys less information about the object it is categorizing.
As it turns out, this lack of information is quite important because one of the most common things you have to check when you're given a possibly-null reference is whether or not it is null. You need to insert "if (ptr == NULL)" all over the place. Thus reference types which allow null references ultimately give me less expressive power.
Most of the time null references are created because either an error condition must be reported (e.g. malloc fails), or it is unclear at some point in time whether or not an object exists. Error conditions can be better signalled using exception handling. As for cases where you're not sure if the object exists or not, then one possibility is to use an option type like in Standard ML:
datatype 'a option = SOME of 'a | NONE
This is a polymorphic type that says that either the object exists or it doesn't, and you can find out what the situation is by using a "case" statement on the datatype constructors:
case foo of ... [do something with x] ... ... [the object doesn't exist] ...
SOME(x) ==>
| NONE ==>
Thus by combining a reference type without nulls with an option type, you can create "reference option" types, which have all the flexibility of "with-null" reference types.
But the cool thing is, you only ever need to check the "null-ness" of the object only once; once you do the check, you're handed a reference object which is guaranteed to be non-null. Thus you can easily partition your code into parts that will do the non-null check and those that assume all references handed to it are valid.
This is why a good type system can make programming so much cleaner and easier :)