Slashdot Mirror
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?"
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.
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.
Javascript + Nintendo DSi = DSiCade
Null-terminated strings. The bane of modern computing.
Website Hosting
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
The concept of "no null references" would be very limiting in a language without algebraic datatypes. 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.
The opinions stated herein do not necessarily represent those of anybody at all. Deal with it.
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.
The opinions stated herein do not necessarily represent those of anybody at all. Deal with it.
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.
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.
"Wise men talk because they have something to say; fools, because they have to say something" - Plato
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.
-- Each tock of the Planck clock is a new world and here we are still life. --
Could you try a better analogy. I think we might all understand a car analogy better...
My blog
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.
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.
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.
The first OS I encountered was tape-based. And it prefilled user memory with a "core constant".
This was a subroutine jump to an abort routine which printed the return location - which in turn told you where you had improperly jumped to and dumped all your registers, followed by the memory itself if that was authorized. (That was all the info that was left by the time the OS got control.)
The walls of the computing center contained posters giving this value as it would appear if printed as various types of values (integer, floating point, complex, ...).
Another machine I dealt with back then was a typesetting device using a Data General Nova and the company's homebrew OS (designed by Mark Weiser of Xerox Parc fame, based on work by Djikstra and Riddle). It had a debugger entry that could be reached by a one-word instruction which we would insert as breakpoints and also use to fill unused memory. The hex form of this was "0c0f". When the machine hit a breakpoint we said it had "coughed".
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
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 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!
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
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.
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)
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.
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.
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
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 :)
These two strings walk into a bar and sit down.
The bartender says, So whatll it be?
The first string says, I think Ill have a beer quag fulk boorg jdk^CjfdLk jk3s d#f67howe%^U r89nvy~~owmc63^Dz x.xvcu
Please excuse my friend, the second string says, He isnt null-terminated.