5 ms·

And regretful inventor of the null reference! His “billion dollar mistake”: https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Ton

And regretful inventor of the null reference! His “billion dollar mistake”: https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/ https://www.infoq.com/presentations/Null-References-The-Bill...

adrian_b 8mo ago
The null reference was invented by Hoare as a means to implement optional types, which works regardless of their binary representation. Optional types were a very valuable invention and the fact that null values have been handled incorrectly in many programming languages or environments is not Hoare's fault.
- tialaramex 8mo ago
  Having "Optional types" only makes sense if your type system is powerful enough. There are two ways this might happen, both will solve the Billion Dollar Problem but I think one is the clear winner. The first way is explicit optionality, often retro-fitted to languages for example in C# the difference between the types Goose and Goose? are that (in a suitable C# project enabling this rule) the first one is always a Goose and the second might be null instead. The second way is if you have Sum types you can just add "or it's null" to the type. I think sum types are better because they pass my "three purposes" rule where I can think of not one (Option<T> replaces optionality) or two (Result<T,E> for error handling) but at least three (ControlFlow<B, C> reifies control flow) distinct problems I don't need separate solutions for any more if I have this feature. If your type system is too weak you suffer the Billion Dollar problem with Hoare's idea and perhaps if this "feature" had never been invented we'd have all migrated to languages with a better type system decades ago.
  - adrian_b 8mo ago
    I agree that for the correct use of both Optional types and Sum types (a.k.a. Union types) a type system that is powerful enough is essential. Moreover, a convenient syntax is also important. In my opinion, besides being passed as arguments of functions whose parameters are declared as having the corresponding Optional or Sum type, there is only one other permissible use of values of such types. Variables of an Optional type shall be allowed in the Boolean expression of an "if" or equivalent conditional statement/expression, while variables of a Sum type shall be allowed in an expression that tests which is the current type in a select/case/switch or whatever is the name used for a conditional statement or expression with multiple branches. Then in the statements or expressions that are guarded by testing the Optional- or Sum-type variable, that variable shall be used as having the corresponding non-optional type or the type among those possible for a Sum type that has been determined by the test. This syntax ensures that such variables will not be misused, while also avoiding the excessive and unhelpful verbosity that exists in some languages.
    - tialaramex 8mo ago
      I disagree. Only true is true and only false is false, Some(1234) isn't true and None isn't false, for the same reason the string "A" isn't the ASCII byte 'A' and the 8-bit unsigned integer 10 isn't the 64-bit floating point number 10.0 When you muddle these things it makes life very slightly easier, very briefly and then you introduce impossible to find bugs and ruin your life. People tend to imagine that OK, maybe C went too far with coercions, but I can handle smaller things, that'll be fine, and in my experience they're wrong. I like the fact that in Rust I'm expected to write if opt.is_none() rather than just treat it as if it was a boolean when it isn't. The resulting machine code isn't different, so we're talking about communicating our intent to human programmers, such as our future selves or our colleagues and I'm certain opt.is_none() communicates that intent better than coercing it to a boolean. I don't like the other idea you propose, but it's less of a footgun and so I don't mind that e.g. C# programmers often write this way. I wouldn't choose it myself in many cases, but I don't write "No, fix this" in reviews of such code.
Milpotel 8mo ago
I'm pretty sure that this is not true. I talked to Bud Lawson (the inventor of the pointer) and he claimed that they had implemented special behaviour for null pointers earlier. When I talked to Tony later about it, he said he had never heard of Bud Lawson. So probably both invented them independently, but Bud came first.
- elch 8mo ago
  If we start playing the "who was first" game, then for the Soviet machine Kiev (Kyiv), an "address language" with a "prime operation" was created in 1957-59. The prime operation and address mapping. The prime operation defines a certain single‑argument function. Its symbol (a prime mark) is written above and to the left of the argument: 'a = b where a is the argument and b is the result of the operation. This is read as: "prime a equals b" (or "b is the contents of a"). The argument a is called an address, and the function value b is called the contents of the address. The prime function ' defines a mapping from the set of addresses A to the set of contents B, which we will call an address mapping. Page 36, chapter III https://torba.infoua.net/files/kateryna-yushchenko/Vychislitelnaya-mashyna-Kiev_VHlushkov_EYushchenko_1962.pdf https://torba.infoua.net/files/kateryna-yushchenko/Vychislit...
  - Milpotel 8mo ago
    Nice, and that was implemented and qualifies as high-level language?
  - adrian_b 8mo ago
    Pointers and indirect addressing were used in assembly languages and machine languages much earlier than that, perhaps even in some relay-based computers. In any case, by 1954 already most or all electronic computers used this. The only priority questions can refer to which are the first high-level programming languages that have used pointers. In my opinion the first language having pointers with implicit dereferencing was CPL, published in 1963-08, and the first language having pointers with explicit dereferencing was Euler, published completely in 1966-01, but this feature had already been published in 1965-11. The first mainstream programming language, with a large installed base, which had pointers, was the revised IBM PL/I, starting with its version from 1966-07. Thanks for the link to the book describing the "Kiev" computer. It seems an interesting computer for the year 1957, but it does not have anything to do with the use of pointers in high-level programming languages. At the page indicated by you there is a description of what appears to be a symbolic assembler. The use of a symbolic assembly language was a great progress at that early date, because many of the first computer programs had been written directly in machine language, or just with a minimal translation, e.g. by using mnemonics instead of numeric opcodes. However this does not have anything to do with HLL pointers and means to indicate indirect addressing in an assembly language have existed earlier, because they were strictly necessary for any computed that provided indirect addressing in hardware. In the very first computers, the instructions were also used as pointers, so a program would modify the address field of an instruction, which was equivalent to assigning a new value to a pointer, before re-executing the instruction. Later, to avoid the re-writing of instructions, both index registers and indirect addressing were introduced. Indirect addressing typically reserved one bit of an address to mark indirection. So when the CPU loaded a word from the memory, if the indirect addressing bit was set, it would interpret the remainder of the word as a new address, from which a new word would be loaded. This would be repeated if the new word also had the indirection bit set. The assembly languages just had to use some symbol to indicate that the indirection bit must be set, which appears to have been "prime" for "Kiev".
bazoom42 8mo ago
The mistake was not null references per se. The mistake was having all references be implicitly nullable. He states around minute 25 the solution to the problem is to explicitly represent null in the type system, so nullable pointers are explicitly declared as such. But it can be complex to ensure that non-nullable references are always initialized to a non-null value, which is why he chose the easy solution to just let every reference be nullable.
- deathanatos 8mo ago
  I think even having references that aren't necessarily null is only part of it. Image that your language supports two forms of references, one nullable, one not. Let's just borrow C++ here: &ref_that_cannot_be_null *ref_that_can_be_null The latter is still a bad idea, even if it isn't the only reference form, and even if it isn't the default, if it lets you do this: ref_that_can_be_null->thing() Where only things that are, e.g., type T have a `thing` attribute. Nulls are "obviously" not T, but a good number of languages' type system which permit nullable reference, or some form of it, permit treating what is in actuality T|null in the type system as if it were just T, usually leading to some form of runtime failure if null is actually used, ranging from UB (in C, C++) to panics/exceptions (Go, Java, C#, TS). It's an error that can be caught by the type system (any number of other languages demonstrate that), and null pointer derefs are one of those bugs that just plague the languages that have it.
  - bazoom42 8mo ago
    TypeScript actually supports nulls through type unions, exactly as Hoare suggests. It will not let you derefence a possibly-null value without a check. C# also supports null-safety, although less elegantly and as opt-in. If enabled, it won’t let you deference a possibly-null reference.
    - tialaramex 8mo ago
      > If enabled, it won’t let you deference a possibly-null reference. It will moan, it doesn't stop you from doing it, our C# software is littered with intentional "Eh, take my word for it this isn't null" and even more annoying, "Eh, it's null but I swear it doesn't matter" code that the compiler moans about but will compile. The C# ecosystem pre-dates nullable reference types and so does much of our codebase, and the result is that you can't reap all the benefits without disproportionate effort. Entity Framework, the .NET ORM is an example.

adrian_b 8mo ago

The null reference was invented by Hoare as a means to implement optional types, which works regardless of their binary representation. Optional types were a very valuable invention and the fact that null values have been handled incorrectly in many programming languages or environments is not Hoare's fault.

tialaramex 8mo ago
Having "Optional types" only makes sense if your type system is powerful enough. There are two ways this might happen, both will solve the Billion Dollar Problem but I think one is the clear winner. The first way is explicit optionality, often retro-fitted to languages for example in C# the difference between the types Goose and Goose? are that (in a suitable C# project enabling this rule) the first one is always a Goose and the second might be null instead. The second way is if you have Sum types you can just add "or it's null" to the type. I think sum types are better because they pass my "three purposes" rule where I can think of not one (Option<T> replaces optionality) or two (Result<T,E> for error handling) but at least three (ControlFlow<B, C> reifies control flow) distinct problems I don't need separate solutions for any more if I have this feature. If your type system is too weak you suffer the Billion Dollar problem with Hoare's idea and perhaps if this "feature" had never been invented we'd have all migrated to languages with a better type system decades ago.
- adrian_b 8mo ago
  I agree that for the correct use of both Optional types and Sum types (a.k.a. Union types) a type system that is powerful enough is essential. Moreover, a convenient syntax is also important. In my opinion, besides being passed as arguments of functions whose parameters are declared as having the corresponding Optional or Sum type, there is only one other permissible use of values of such types. Variables of an Optional type shall be allowed in the Boolean expression of an "if" or equivalent conditional statement/expression, while variables of a Sum type shall be allowed in an expression that tests which is the current type in a select/case/switch or whatever is the name used for a conditional statement or expression with multiple branches. Then in the statements or expressions that are guarded by testing the Optional- or Sum-type variable, that variable shall be used as having the corresponding non-optional type or the type among those possible for a Sum type that has been determined by the test. This syntax ensures that such variables will not be misused, while also avoiding the excessive and unhelpful verbosity that exists in some languages.
  - tialaramex 8mo ago
    I disagree. Only true is true and only false is false, Some(1234) isn't true and None isn't false, for the same reason the string "A" isn't the ASCII byte 'A' and the 8-bit unsigned integer 10 isn't the 64-bit floating point number 10.0 When you muddle these things it makes life very slightly easier, very briefly and then you introduce impossible to find bugs and ruin your life. People tend to imagine that OK, maybe C went too far with coercions, but I can handle smaller things, that'll be fine, and in my experience they're wrong. I like the fact that in Rust I'm expected to write if opt.is_none() rather than just treat it as if it was a boolean when it isn't. The resulting machine code isn't different, so we're talking about communicating our intent to human programmers, such as our future selves or our colleagues and I'm certain opt.is_none() communicates that intent better than coercing it to a boolean. I don't like the other idea you propose, but it's less of a footgun and so I don't mind that e.g. C# programmers often write this way. I wouldn't choose it myself in many cases, but I don't write "No, fix this" in reviews of such code.

Milpotel 8mo ago

I'm pretty sure that this is not true. I talked to Bud Lawson (the inventor of the pointer) and he claimed that they had implemented special behaviour for null pointers earlier. When I talked to Tony later about it, he said he had never heard of Bud Lawson. So probably both invented them independently, but Bud came first.

elch 8mo ago
If we start playing the "who was first" game, then for the Soviet machine Kiev (Kyiv), an "address language" with a "prime operation" was created in 1957-59. The prime operation and address mapping. The prime operation defines a certain single‑argument function. Its symbol (a prime mark) is written above and to the left of the argument: 'a = b where a is the argument and b is the result of the operation. This is read as: "prime a equals b" (or "b is the contents of a"). The argument a is called an address, and the function value b is called the contents of the address. The prime function ' defines a mapping from the set of addresses A to the set of contents B, which we will call an address mapping. Page 36, chapter III https://torba.infoua.net/files/kateryna-yushchenko/Vychislitelnaya-mashyna-Kiev_VHlushkov_EYushchenko_1962.pdf https://torba.infoua.net/files/kateryna-yushchenko/Vychislit...
- Milpotel 8mo ago
  Nice, and that was implemented and qualifies as high-level language?
- adrian_b 8mo ago
  Pointers and indirect addressing were used in assembly languages and machine languages much earlier than that, perhaps even in some relay-based computers. In any case, by 1954 already most or all electronic computers used this. The only priority questions can refer to which are the first high-level programming languages that have used pointers. In my opinion the first language having pointers with implicit dereferencing was CPL, published in 1963-08, and the first language having pointers with explicit dereferencing was Euler, published completely in 1966-01, but this feature had already been published in 1965-11. The first mainstream programming language, with a large installed base, which had pointers, was the revised IBM PL/I, starting with its version from 1966-07. Thanks for the link to the book describing the "Kiev" computer. It seems an interesting computer for the year 1957, but it does not have anything to do with the use of pointers in high-level programming languages. At the page indicated by you there is a description of what appears to be a symbolic assembler. The use of a symbolic assembly language was a great progress at that early date, because many of the first computer programs had been written directly in machine language, or just with a minimal translation, e.g. by using mnemonics instead of numeric opcodes. However this does not have anything to do with HLL pointers and means to indicate indirect addressing in an assembly language have existed earlier, because they were strictly necessary for any computed that provided indirect addressing in hardware. In the very first computers, the instructions were also used as pointers, so a program would modify the address field of an instruction, which was equivalent to assigning a new value to a pointer, before re-executing the instruction. Later, to avoid the re-writing of instructions, both index registers and indirect addressing were introduced. Indirect addressing typically reserved one bit of an address to mark indirection. So when the CPU loaded a word from the memory, if the indirect addressing bit was set, it would interpret the remainder of the word as a new address, from which a new word would be loaded. This would be repeated if the new word also had the indirection bit set. The assembly languages just had to use some symbol to indicate that the indirection bit must be set, which appears to have been "prime" for "Kiev".

bazoom42 8mo ago

The mistake was not null references per se. The mistake was having all references be implicitly nullable. He states around minute 25 the solution to the problem is to explicitly represent null in the type system, so nullable pointers are explicitly declared as such. But it can be complex to ensure that non-nullable references are always initialized to a non-null value, which is why he chose the easy solution to just let every reference be nullable.

deathanatos 8mo ago
I think even having references that aren't necessarily null is only part of it. Image that your language supports two forms of references, one nullable, one not. Let's just borrow C++ here: &ref_that_cannot_be_null *ref_that_can_be_null The latter is still a bad idea, even if it isn't the only reference form, and even if it isn't the default, if it lets you do this: ref_that_can_be_null->thing() Where only things that are, e.g., type T have a `thing` attribute. Nulls are "obviously" not T, but a good number of languages' type system which permit nullable reference, or some form of it, permit treating what is in actuality T|null in the type system as if it were just T, usually leading to some form of runtime failure if null is actually used, ranging from UB (in C, C++) to panics/exceptions (Go, Java, C#, TS). It's an error that can be caught by the type system (any number of other languages demonstrate that), and null pointer derefs are one of those bugs that just plague the languages that have it.
- bazoom42 8mo ago
  TypeScript actually supports nulls through type unions, exactly as Hoare suggests. It will not let you derefence a possibly-null value without a check. C# also supports null-safety, although less elegantly and as opt-in. If enabled, it won’t let you deference a possibly-null reference.
  - tialaramex 8mo ago
    > If enabled, it won’t let you deference a possibly-null reference. It will moan, it doesn't stop you from doing it, our C# software is littered with intentional "Eh, take my word for it this isn't null" and even more annoying, "Eh, it's null but I swear it doesn't matter" code that the compiler moans about but will compile. The C# ecosystem pre-dates nullable reference types and so does much of our codebase, and the result is that you can't reap all the benefits without disproportionate effort. Entity Framework, the .NET ORM is an example.