One of my favorite quotes:
“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.”
I think about this a lot because it’s true of any complex system or argument, not just software.
This is indeed a great quote (one of many gems from Sir Tony) but I think the context that follows it is also an essential insight:
> The first method is far more difficult. It demands the same skill,
devotion, insight, and even inspiration as the discovery of the simple
physical laws which underlie the complex phenomena of nature. It
also requires a willingness to accept objectives which are limited
by physical, logical, and technological constraints, and to accept a
compromise when conflicting objectives cannot be met. No committee
will ever do this until it is too late.
One of my biggest accomplishments was shipping a suite of 5 apps from four divisions where three of them resented each other’s existence and seemed bound and determined to build rules in the system that made sure the other two couldn’t function. Which made no goddamn sense because it was a pipeline and you can’t get anything out one end if it gets jammed in the middle.
I was brought in to finish building the interchange format. The previous guy was not up to snuff. The architect I worked for was (with love) a sarcastic bastard who eventually abdicated about 2 rings of the circus to me. He basically took some of the high level meetings and tapped in when one of us thought I might strangle someone.
Their initial impression was that I was a prize to be fought over like a child in a divorce. But the guy who gives you your data has you by the balls, if he is smart enough to realize it, so it went my way nine times out of ten. It was a lot of work threading that needle, (I’ve never changed the semantics of a library so hard without changing the syntax), but it worked out for everyone. By the time we were done the way things worked vs the way they each wanted it to work was on the order of twenty lines of code on their end, which I essentially spoonfed them so they didn’t have a lot of standing to complain. And our three teams always delivered within 15% of estimates, which was about half of anyone else’s error bar so we lowly accreted responsibilities.
I ended up as principal on that project (during a hiring/promotional freeze on that title. I felt bad for leaving within a year because someone pulled strings for that, but I stayed until I was sure the house wouldn’t burn down after I left, and I didn’t have to do that). I must have said, “compromise means nobody gets their way.” About twenty times in or between meetings.
It's the committee vs the dictator issue - a small driven individual (or group) can achieve a lot, but they can also turn into tyrants.
A committee forms when there's widespread disagreement on goals or priorities - representing stakeholders who can't agree. The cost is slower decisions and compromise solutions. The benefit is avoiding tyranny of a single vision that ignores real needs.
One of the policies of The Rhinoceros Party in Canada was to increase the complexity of the taxation system so much that nobody could find the loopholes to exploit.
Reminds me of this quote... “A complex system that works is invariably found to have evolved from a simple system that worked. A complex system designed from scratch never works and cannot be patched up to make it work.”
Rest in peace, he hasn't seen the industry change.
"A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980 language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law."
-- C.A.R Hoare's "The 1980 ACM Turing Award Lecture"
As Dijkstra was preparing for his end of life, organizing his documents and correspondence became an important task. Cancer had snuck up on him and there was not much time.
One senior professor, who was helping out with this, asked Dijkstra what is to be done with his correspondences. The professor, quite renowned himself, relates a story where Dijsktra tells him from his hospital bed, to keep the ones with "Tony" and throw the rest.
The professor adds with a dry wit, that his own correspondence with Dijsktra were in the pile too.
That's a famous quote and age might have mellowed him. But he was not like that at all in person with his students. He did insist that one be precise with ones words.
The origin of the quote may have more to do with cultural differences between the Dutch and Americans.
That's a great point which never occurred to me about Dijkstra, even though I knew where he came from. My father in law used to like this joke: "He was Dutch and behaved as such."
Fun story - at Oxford they like to name buildings after important people. Dr Hoare was nominated to have a house named after him. This presented the university with a dilemma of having a literal `Hoare house` (pronounced whore).
I can't remember what Oxford did to resolve this, but I think they settled on `C.A.R. Hoare Residence`.
>our Reinforcement Learning reading group there //
Anyone else, like me, imagining ML models embodied as Androids attending what amounts to a book club? (I can't quite shake the image of them being little CodeBullets with CRT monitors for heads either.)
I mean, I like puns but they're a flash in the pan. Jokes get old after a while and you don't want to embed them in something fairly permanent like a building name.
"Surely you've all heard of the Hoare house on campus?" seems like a pretty timeless way to a) keep people from dozing off during that bit of lecture b) cause a whole bunch of people to remember who this guy was and what he did.
Imagine being a world-famous computer scientist and dying and one of the top threads in a discussion of your life is juvenile crap about how your name sounds like "whore".
The confusion is possibly almost appropriate, given so much of his work was on creating systems which avoid confusion through using proper synchronized communication channels. The null pointer stuff is famous, but it's occam and the Communicating Sequential Processes work that were brilliant. Maybe it's also brilliantly wrong, as I think Actor model people could argue, but it is brilliant.
My favourite quote of his is “There are two ways of constructing a piece of software: One is to make it so simple that there are obviously no errors, and the other is to make it so complicated that there are no obvious errors.”
While we hope it's not true, if it is a very deserved RIP.
He was the professor in the Programming Research Group (known universally as the PRG) at Oxford when I was doing my DPhil and interviewed me for the DPhil. I spent quite a bit of time with him and, of course, spent a lot of time doing stuff with CSP including my entire DPhil.
Sad to think that the TonyHoare process has reached STOP.
I lucked in to meeting him once, in Cambridge. A gentle intellectual giant.
I repeatedly borrow this quote from his 1980 Turing Award speech, 'The Emperor's Old Clothes'... "At last, there breezed into my office the most senior manager of all, a general manager of our parent company, Andrew St. Johnston. I was surprised that he had even heard of me. "You know what went wrong?" he shouted--he always shouted-- "You let your programmers do things which you yourself do not understand." I stared in astonishment. He was obviously out of touch with present day realities. How could one person ever understand the whole of a modern software product like the Elliott 503 Mark II software system? I realized later that he was absolutely right; he had diagnosed the true cause of the problem and he had planted the seed of its later solution."
My interpretation is that whether shifting from delegation to programmers, or to compilers, or to LLMs, the invariant is that we will always have to understand the consequences of our choices, or suffer the consequences.
Tony's An Axiomatic Basis for Computer Programming[1] is the first academic paper that I read that I was able to understand when I was an undergrad. I think it unlocked something in me because before that I never believed that I would be able to read and understand scientific papers.
That was 35ish years ago. I just pulled up the paper now and I can't read the notation anymore... This might be something that I try applying an AI to. Get it to walk me through a paper paragraph-by-paragraph until I get back up to speed.
Retrospective: An Axiomatic Basis For Computer Programming. This was written 30 years after An Axiomatic Basis for Computer Programming to take stock on what was proven right and what was proven wrong - https://cacm.acm.org/opinion/retrospective-an-axiomatic-basi...
I remember attending a tech event at MSR Cambridge, and a speaker made some disparaging comment about older developers not being able to keep up in this modern world of programming.
An older gentleman stood up and politely mentioned they knew a thing or two.
From his Oxford bio: "To assist in efficient look-up of words in a dictionary, he discovered the well-known sorting algorithm Quicksort."
I always liked this presentation. I think it's equally fine to say "invented" something, but I think this fits into his ethos (from what I understand of him.) There are natural phenomena, and it just takes noticing.
I've had the good fortune to attend two of his lectures in person. Each time, he effortlessly derived provably correct code from the conditions of the problem and made it seem all too easy. 10 minutes after leaving the lecture, my thought was "Wait, how did he do it again?".
Tony advised me to make money with the software model checker I have been writing. In contrast to the typical practice to make these tools open source and free for use. Would have loved to learn more from him. He was a great teacher but also a great and sharp listener. Still remember the detour we made on the way to a bar in London, talking too much and deep about refinement relations. RiP.
He also invented many other things, like enumeration types, optional types, constructors. He popularized the "unions" introduced by McCarthy, which were later implemented in ALGOL 68, from where a crippled form of them was added to the C language.
Several keywords used in many programming languages come from Hoare, who either coined them himself, or he took them from another source, but all later programming language designers took them from Hoare. For example "case", but here only the keyword comes from Hoare, because a better form of the "case" statement had been proposed first by McCarthy many years earlier, under the name "select".
Another example is "class" which Simula 67, then all object-oriented languages took from Hoare, However, in this case the keyword has not been used first by Hoare, because he took "class", together with "record", from COBOL.
Another keyword popularized by Hoare is "new" (which Hoare took from Wirth, but everybody else took from Hoare), later used by many languages, including C++. At Hoare, the counterpart of "new" was "destroy", hence the name "destructor", used first in C++.
The paper "Record Handling", published by C.A.R. Hoare in 1965-11 was a major influence on many programming languages. It determined significant changes in the IBM PL/I programming language, including the introduction of pointers . It also was the source of many features of the SIMULA 67 and ALGOL 68 languages, from where they spread in many later programming languages.
The programming language "Occam" has been designed mainly as an implementation of the ideas described by Hoare in the "Communicating Sequential Processes" paper published in 1978-08. OpenMP also inherits many of those concepts, and some of them are also in CUDA.
there was a time, 10-15 years ago, when they were super cool. at some point they """diluted""" the technicality content and the nature of guests and they vanished into irrelevance.
Hoare Logic + Dijkstra's weakest precondition + Meyer's Design-by-Contract is what should be used to get LLMs to generate proof with code in a correctness-by-construction approach to implementation.
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.
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.
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.
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.
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.
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.
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.
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".
You should provide a citation for where Bud Lawson has published his invention.
The use of pointers in assembly language does not count as an invention, as it was used since the earliest automatic computers. The use of implicit reference variables, which cannot be manipulated by the programmer, like in FORTRAN IV (1962) does not count as pointers.
The method for forcing another level of evaluation of a variable by using a "$" prefix, which was introduced in SNOBOL in January 1964, and which has been inherited by the UNIX shell and its derivatives does not count as a pointer.
The term "pointer" was introduced in a revision of the IBM PL/I language, which was published in July 1966. In all earlier publications that I have ever seen the term used was "reference", not "pointer".
There are 2 high-level programming languages that were the first to introduce explicit references (i.e. pointers). One language was Euler, published in January 1966 by Niklaus Wirth and Helmut Weber. However Hoare knew about this language before the publication, so he mentioned it in his paper from November 1965, where he discussed the use of references (i.e. pointers).
The other language was the language CPL, which had references already in August 1963. The difference between how CPL used references and how Euler used references is that in Euler pointer dereferencing was explicit, like later in Pascal or in C. On the other hand, in CPL (the ancestor of BCPL), dereferencing a pointer was implicit, so you had to use a special kind of assignment to assign a new value to a pointer, instead of assigning to the variable pointed by the pointer.
Looking now in Wikipedia, I see a claim that Bud Lawson has invented pointers in 1964, but there is no information about where he has published this and about which is the high-level programming language where the pointers of Bud Lawson had been used.
If the pointers of Bud Lawson were of the kind with explicit dereferencing, they would precede by a year the Euler language.
On the other hand, if his pointers were with implicit dereferencing, then they came a year after the British programming language CPL.
Therefore, in the best case for Bud Lawson, he could have invented an explicit dereferencing operator, like the "*" of C, though this would not have been a great invention, because dereferencing operators were already used in assembly languages, they were missing only in high-level languages.
However, the use of references a.k.a. pointers in a high-level programming language has already been published in August 1963, in the article "The main features of CPL", by Barron, Buxton, Hartley, Nixon and Strachey.
Until I see any evidence for this, I consider that any claim about Bud Lawson inventing pointers is wrong. He might have invented pointers in his head, but if he did not publish this and it was not used in a real high-level programming language, whatever he invented is irrelevant.
I see on the Internet a claim that he might have been connected with the pointers of IBM PL/I.
This claim appears to be contradicted by the evidence. If Bud Lawson had invented pointers in 1964, then the preliminary version of PL/I would have had them.
In reality, the December 1964 version of PL/I did not have pointers. Moreover, the first PL/I version used in production, from the middle of 1965 also did not have pointers.
The first PL/I version that has added pointers was introduced only in July 1966, long enough after the widely-known publications of Hoare and of Wirth about pointers. That PL/I version also added other features proposed by Hoare, so there is no doubt that the changes in the language were prompted by the prior publications.
So I think that the claim that Bud Lawson has invented pointers is certainly wrong. He might have invented something related to pointers, but not in 1964.
PL/I had one original element, the fact that pointer dereferencing was indicated by replacing "." with "->". This has later been incorporated in the language C, to compensate its mistake of making "*" a prefix operator.
The "->" operator is the only invention of PL/I related to pointers, so that is a thing that has been invented by an IBM employee, but I am not aware of any information about who that may be. In any case, this was not invented in 1964, but in 1966.
Tony Hoare was on my bucket list of people I wanted to meet before I or they die. My grad school advisor always talked of him extremely highly, and while I cannot seem to confirm it, I believe Hoare might have been his PhD advisor.
It's hard to overstate how important Hoare was. CSP and Hoare Logic and UTP are all basically entire fields in their own right. It makes me sad he's gone.
When I met him unfortunately I didn't realize how important he was (1987). The place where I worked used formal methods to verify the design of an FPU, in collaboration with the PRG. iirc the project was a success. I never heard of formal methods being successfully used again until TLA+ a few years ago.
David May was my PhD supervisor and always spoke very highly of Sir Tony Hoare.
Edit: I’m also lucky enough to have worked with Geoff Barrett, the guy that completed that formal verification (and went on to do numerous other interesting things). Some people may be interested to learn that this work was the very first formal verification of an FPU - and the famous Intel FPU bug could have been avoided had Intel been using the verification methods that the Inmos and University teams pioneered.
I actually had two PhD advisors [1]; Jim Woodcock and Simon Foster.
Both of them are legitimately wonderful and intelligent humans that I can only use positive adjectives to describe, but the one I was referring to in this was Jim Woodcock [2]. He had many, many nice things to say about Tony Hoare.
[1] Just so I'm not misleading people, I didn't finish my PhD. No fault at all of the advisor or the school.
“Inspired by” is an understatement of the century lol. David May and Sir Tony worked very closely together to enable the architecture to be as pure a runtime for CSP as you could get - at least in early versions of the architecture and accompanying Occam language. It expanded and deviated a bit later on iirc.
Source: David loved to tell some of these stories to us as students at Bristol.
It’s also worth highlighting that the mathematical purity of the designs were also partly the problem with them. As a field, we’re still developing the maths of Effects and Effectful Algebras that are needed to make these systems both mathematically ‘pure’ (or at least sound to within some boundary) and ALSO capable of interfacing to the real world.
Transputer and Occam were, in this sense, too early. A rebuild now combining more recent developments from Effect Algebras would be very interesting technically. (Commercially there are all sorts of barriers).
He came to give a lecture at UT Austin, where I did my undergrad. I had a chance to ask him a question: "what's the story behind inventing QuickSort?". He said something simple, like "first I thought of MergeSort, and then I thought of QuickSort" - as if it were just natural thought. He came across as a kind and humble person. Glad to have met one of the greats of the field!
Happy to meet you. I was there and I remember that question being asked. I think it was 2010.
If I remember correctly he had two immediate ideas, his first was bubble sort, the second turned out to be quicksort.
He was already very frail by then. Yet clarity of mind was undiminished. What came across in that talk, in addition to his technical material, was his humor and warmth.
Sad that his (and many others') dream of widespread formal verification of software never came true. He made really fundamental contributions to computer science but will probably be mostly known for quicksort and the quote about his "billion dollar mistake", not his decades-long program to make formal methods more tractable.
Makes me think of an anecdote where Dijkstra said that he feared he would only be remembered for his shortest path algorithm.
Random anecdote and Mr. Hoare (yep not a Dr.) has always been one of my computing heroes.
Mr. Hoare did a talk back during my undergrad and for some reason despite totally checked out of school I attended, and it is one of my formative experiences. AFAICR it was about proving program correctness.
After it finished during the Q&A segment, one student asked him about his opinions about the famous Brooks essay No Silver Bullet and Mr. Hoare's answer was... total confusion. Apparently he had not heard of the concept at all! It could be a lost in translation thing but I don't think so since I remember understanding the phrase "silver bullet" which did not make any sense to me. And now Mr. Hoare and Dr. Brooks are two of my all time computing heroes.
It is not usual to call people with an honorary doctorate "Doctor" except in the context of the awarding institution. Most likely the awarding institutions will have actually specified that the recipient should not give anybody the false impression and I can't imagine Tony is the type to do otherwise.
His title at Oxford was 'Professor', and he was addressed as 'Tony'.
He made incoming DPhil (PhD) students a cup of tea individually in his office at the Computing Laboratory. It was a small group, but still I appreciated this personal touch.
Sir Tony Hoare visited Institute for System Programming in Moscow and gave a lecture quarter of the century ago. It was unforgettable experience to see the living legend of your field. He was a senior person then already and today I am going to celebrate his long and wonderful life.
I first came across Tony Hoare about 24 years ago while learning C from The C Programming Language by Kernighan and Richie. I knew him only as C. A. R. Hoare for a long time. When I got on the Internet, it took me a while to realise that when people said Tony Hoare, it was the same person I knew as C. A. R. Hoare. Quoting the relevant text from the book:
> Another good example of recursion is quicksort, a sorting algorithm developed by C.A.R. Hoare in 1962. Given an array, one element is chosen and the others partitioned in two subsets - those less than the partition element and those greater than or equal to it. The same process is then applied recursively to the two subsets. When a subset has fewer than two elements, it doesn't need any sorting; this stops the recursion.
> Our version of quicksort is not the fastest possible, but it's one of the simplest. We use the middle element of each subarray for partitioning. [...]
It was one of the first few 'serious' algorithms I learnt to implement on my own. More generally, the book had a profound impact on my life. It made me fall in love with computer programming and ultimately choose it as my career. Thanks to K&R, Tony Hoare and the many other giants on whose shoulders I stand.
It had intrigued me due to its promise of designing lock-free concurrent systems, that can (I think) also be proven to be deadlock-free.
You do this by building a simple concurrent block that is proven to work correctly, and then build bigger ones using the smaller, proven blocks, to create more complex systems.
The way it is designed is processes don't share data and don't have locks. They use synchronized IPC for passing and modifying data.
It seemed to be a foundational piece for designing reliable systems that incorporate concurrency in them.
> On the topic of films, I wanted to follow up with Tony a quote that I have seen online attributed to him about Hollywood portrayal of geniuses, often especially in relation to Good Will Hunting. A typical example is: "Hollywood's idea of genius is Good Will Hunting: someone who can solve any problem instantly. In reality, geniuses struggle with a single problem for years". Tony agreed with the idea that cinema often misrepresents how ability in abstract fields such as mathematics is learned over countless hours of thought, rather than - as the movies like to make out - imparted, unexplained, to people of 'genius'. However, he was unsure where exactly he had said this or how/why it had gotten onto the internet, and he agreed that online quotes on the subject, attributed to him, may well be erroneous.
Somewhat off-topic, but it's cool hearing this from someone who's contributed so much to the fields of programming and mathematics. It makes me hopeful that my own strugglings with math will pay out over time!
You misunderstand the “billion dollar mistake”. The mistake is not the use of nulls per se, the mistake is type-systems which does not make them explicit.
Anti patterns are great, they act as escape hatches or pressure release valves. Every piece of mechanical equipment has some analogue for good reason.
Without things like null pointers, goto, globals, unsafe modes in modern safe(r) languages you can get yourself into a corner by over designing everything, often leading to complex unmaintainable code.
With judicious use of these anti-patterns you get mostly good/clean design with one or two well documented exceptions.
The "goto" in languages like C or C++ is de-fanged and not at all similar to the sequence break jump in "Go To Statement Considered Harmful". That doesn't make it a good idea, but in practice today the only place you'll see the unstructured feature complained of is machine code/ assembly language.
You just don't need it but it isn't there as some sort of "escape hatch" it's more out of stubbornness. Languages which don't have it are fine, arguably easier to understand by embracing structure more. I happen to like Rust's "break 'label value" but there are plenty of ways to solve even the trickier parts of this problem (and of course most languages aren't expression based and wouldn't need a value there).
That relies on a programmer doing the right thing and knowing when to use the escape valve. From the codebases I've seen, I don't trust humans in doing the right thing and being judicious with this. But it's a good point, knowing when to deviate from a pattern is a strong plus.
I wrote both my master thesis and PhD on Hoare's Communicating Sequential Processes. I really enjoyed it's simplicity, expandability, and was always amazed that it inspired and influenced language constructs in Go, Erlang, occam and the likes.
I saw a casual lecture given by Tony Hoare as a teenager. The atmosphere was warm and welcoming, even if I didn't fully understand all of the content. I remember he was very kind and answered my simple questions politely.
unless its greatly exagerated - he was quite mind sharp in his 80s
SIR_TONY_HOARE = μX • (think → create → give → X)
-- process ran from 1934 to 2026
-- terminated with SKIP
-- no deadlock detected
-- all assertions satisfied
-- trace: ⟨ quicksort, hoare_logic, csp, monitors,
-- dining_philosophers, knighthood, turing_award,
-- billion_dollar_apology, structured_programming,
-- unifying_theories, ... ⟩
-- trace length: ∞
The channel is closed. The process has terminated.
The algebra endures.
When I started university he gave a talk to all the new CompScis which as you can imagine was incredibly inspirational for an aspiring Software Engineer.
One of Billy Crystal's later standup bits was talking about how his parents have hit an age where their favorite game with their friends is called, "Guess Who Died". I've been thinking about that bit an awful lot the last couple of years.
Never made it as a wise man
I couldn't cut it as a poor man stealing
Tired of livin' like a blind man
I'm sick of sight without a sense of feeling
And this is how you remind me
This is how you remind me of what I really am
This is how you remind me of what I really am
It's not like you to say sorry
I was waitin' on a different story
This time I'm mistaken
For handing you a heart worth breakin'
And I've been wrong, I've been down
Been to the bottom of every bottle
These five words in my head
Scream, "Are we havin' fun yet?"
Yet, yet, yet, no, no
Yet, yet, yet, no, no
It's not like you didn't know that
I said, "I love you," and I swear I still do
And it must have been so bad
'Cause livin' with me must have damn near killed you
And this is how you remind me of what I really am
This is how you remind me of what I really am
It's not like you to say sorry
I was waitin' on a different story
This time I'm mistaken
For handing you a heart worth breakin'
And I've been wrong, I've been down
Been to the bottom of every bottle
These five words in my head
Scream, "Are we havin' fun yet?"
Yet, yet, yet, no, no
Yet, yet, yet, no, no
Yet, yet, yet, no, no
Yet, yet, yet, no, no
Never made it as a wise man
I couldn't cut it as a poor man stealin'
And this is how you remind me
This is how you remind me
This is how you remind me of what I really am
This is how you remind me of what I really am
It's not like you to say sorry
I was waitin' on a different story
This time I'm mistaken
For handing you a heart worth breakin'
And I've been wrong, I've been down
Been to the bottom of every bottle
These five words in my head
Scream, "Are we havin' fun yet?"
Yet, yet, are we havin' fun yet?
Yet, yet, are we havin' fun yet?
Yeah, yeah (These five words in my head scream)
Are we havin' fun yet?
Yeah, yeah (These five words in my head)
No, no
He was a professor at my old alma mater, Queen's University of Belfast. I remember hearing a story about him going to Harvard to give a lecture and, as he was presented, one of their professors referred to himself as the "Hoare of Harvard"
"The null reference was my billion dollar mistake responsible for innumerable errors, vulnerabilities and system crashes" (paraphrasing). I don't know. This design choice exposed the developer to system realities, and modern language approaches are based on decades of attempts to improve on it, and they are not necessarily better. Safer yes, but more weighty.
Can anyone suggest a better approach for a situation like this in the future? What's better than exposing addressing the problem with a light solution?
"The problem isn't the concept of 'null', but rather that everything can be null, which makes it impossible to distinguish between the cases where null is an appropriate and expected value, from the cases where null is a defect."
Which system reality? Plenty of architectures don't have a concept of a null pointer at the hardware level. Other architectures provide multiple address spaces, or segmented memory addressing. Even when a null pointer exists at the hardware level, it doesn't have to be the zero address.
Null pointers are a software abstraction, and nowadays we have better abstractions.
I think the first enlightenment is that software engineers should be able to abstract away these algorithms to reliable libraries.
The second enlightenment is that if you don't understand what the libraries are doing, you will probably ship things that assemble the libraries in unreasonably slow/expensive ways, lacking the intuition for how "hard" the overall operation should be.
One of my favorite quotes: “There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.”
I think about this a lot because it’s true of any complex system or argument, not just software.
This is indeed a great quote (one of many gems from Sir Tony) but I think the context that follows it is also an essential insight:
> The first method is far more difficult. It demands the same skill, devotion, insight, and even inspiration as the discovery of the simple physical laws which underlie the complex phenomena of nature. It also requires a willingness to accept objectives which are limited by physical, logical, and technological constraints, and to accept a compromise when conflicting objectives cannot be met. No committee will ever do this until it is too late.
(All from his Turing Award lecture, "The Emperor's Old Clothes": https://www.labouseur.com/projects/codeReckon/papers/The-Emp...)
"No committee will ever do this until it is too late."
The software I like best was not written by "teams"
I prefer small programs written by individuals that generally violate memes like "software is never finished" and "all software has bugs"
(End user perspective, not a developer)
Also, this software is free. Generally the authors were not paid to write it
One of my biggest accomplishments was shipping a suite of 5 apps from four divisions where three of them resented each other’s existence and seemed bound and determined to build rules in the system that made sure the other two couldn’t function. Which made no goddamn sense because it was a pipeline and you can’t get anything out one end if it gets jammed in the middle.
I was brought in to finish building the interchange format. The previous guy was not up to snuff. The architect I worked for was (with love) a sarcastic bastard who eventually abdicated about 2 rings of the circus to me. He basically took some of the high level meetings and tapped in when one of us thought I might strangle someone.
Their initial impression was that I was a prize to be fought over like a child in a divorce. But the guy who gives you your data has you by the balls, if he is smart enough to realize it, so it went my way nine times out of ten. It was a lot of work threading that needle, (I’ve never changed the semantics of a library so hard without changing the syntax), but it worked out for everyone. By the time we were done the way things worked vs the way they each wanted it to work was on the order of twenty lines of code on their end, which I essentially spoonfed them so they didn’t have a lot of standing to complain. And our three teams always delivered within 15% of estimates, which was about half of anyone else’s error bar so we lowly accreted responsibilities.
I ended up as principal on that project (during a hiring/promotional freeze on that title. I felt bad for leaving within a year because someone pulled strings for that, but I stayed until I was sure the house wouldn’t burn down after I left, and I didn’t have to do that). I must have said, “compromise means nobody gets their way.” About twenty times in or between meetings.
These are the projects that give us confidence.
It's the committee vs the dictator issue - a small driven individual (or group) can achieve a lot, but they can also turn into tyrants.
A committee forms when there's widespread disagreement on goals or priorities - representing stakeholders who can't agree. The cost is slower decisions and compromise solutions. The benefit is avoiding tyranny of a single vision that ignores real needs.
One of the policies of The Rhinoceros Party in Canada was to increase the complexity of the taxation system so much that nobody could find the loopholes to exploit.
We are poorer for him having waited to drop that sentence at his Turing Award acceptance speech. I use it all the time.
Tony might be my favorite computer scientist.
Good thing we now have technology that allows us to crank out complex software at rates never-before seen.
aged very well
Reminds me of this Pascal quote: "I would have written a shorter letter, but I did not have the time."
https://www.npr.org/sections/13.7/2014/02/03/270680304/this-...
Reminds me of this quote... “A complex system that works is invariably found to have evolved from a simple system that worked. A complex system designed from scratch never works and cannot be patched up to make it work.”
https://en.wikipedia.org/wiki/John_Gall_(author)#Gall's_law
The book is well worth reading.
https://news.ycombinator.com/item?id=9948767
Rest in peace, he hasn't seen the industry change.
"A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980 language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law."
-- C.A.R Hoare's "The 1980 ACM Turing Award Lecture"
As Dijkstra was preparing for his end of life, organizing his documents and correspondence became an important task. Cancer had snuck up on him and there was not much time.
One senior professor, who was helping out with this, asked Dijkstra what is to be done with his correspondences. The professor, quite renowned himself, relates a story where Dijsktra tells him from his hospital bed, to keep the ones with "Tony" and throw the rest.
The professor adds with a dry wit, that his own correspondence with Dijsktra were in the pile too.
John Backus had some correspondence with Dijkstra that's worth a read: https://medium.com/@acidflask/this-guys-arrogance-takes-your...
There's that immortal Alan Kay line "arrogance in computer science is measured in nano Dijkstras".
That's a famous quote and age might have mellowed him. But he was not like that at all in person with his students. He did insist that one be precise with ones words.
The origin of the quote may have more to do with cultural differences between the Dutch and Americans.
That's a great point which never occurred to me about Dijkstra, even though I knew where he came from. My father in law used to like this joke: "He was Dutch and behaved as such."
Alan Kay himself said this quote is taken out-of-context and so people need to stop repeating it - https://news.ycombinator.com/item?id=11799963
> and so people need to stop repeating it
That would seem to be your sentiment, not his, based on the link you shared. Rather than being censorious he shared a nice story on the matter.
Weirdly, that ten-year-old Alan Kay comment is shown as "1 day ago" by HN.
Fun story - at Oxford they like to name buildings after important people. Dr Hoare was nominated to have a house named after him. This presented the university with a dilemma of having a literal `Hoare house` (pronounced whore).
I can't remember what Oxford did to resolve this, but I think they settled on `C.A.R. Hoare Residence`.
There's the Tony Hoare Room [1] in the Robert Hooke Building. We held our Reinforcement Learning reading group there.
[1] https://www.cs.ox.ac.uk/people/jennifer.watson/tonyhoare.htm...
>our Reinforcement Learning reading group there //
Anyone else, like me, imagining ML models embodied as Androids attending what amounts to a book club? (I can't quite shake the image of them being little CodeBullets with CRT monitors for heads either.)
I had countless lectures and classes there
Cowards.
I was awarded the CAR Hoare prize from university, which is marginally better than the hoare prize I suppose
Shame the university takes itself so seriously. The illustrative example of overloading would have been pertinent to his subject of expertise.
I mean, I like puns but they're a flash in the pan. Jokes get old after a while and you don't want to embed them in something fairly permanent like a building name.
This particular word for the oldest profession goes back to Old English. I am fairly sure it would outlive the building.
If the problem is when the joke lives on amusing undergrads long after you've tired of it, that just makes it worse.
"Surely you've all heard of the Hoare house on campus?" seems like a pretty timeless way to a) keep people from dozing off during that bit of lecture b) cause a whole bunch of people to remember who this guy was and what he did.
"Hoare House" would trigger millions of idiots, from rude little children to pontifying alpha ideologues. In perpetuity.
The University was correct in saying "nope" to the endless distractions, misery, and overhead of having to deal with that.
Imagine being a world-famous computer scientist and dying and one of the top threads in a discussion of your life is juvenile crap about how your name sounds like "whore".
Imagine being an adult human but not being able to extract a tiny chuckle from such a silly thing.
Well, I do have a rather special last name which makes me susceptible.
The confusion is possibly almost appropriate, given so much of his work was on creating systems which avoid confusion through using proper synchronized communication channels. The null pointer stuff is famous, but it's occam and the Communicating Sequential Processes work that were brilliant. Maybe it's also brilliantly wrong, as I think Actor model people could argue, but it is brilliant.
My favourite quote of his is “There are two ways of constructing a piece of software: One is to make it so simple that there are obviously no errors, and the other is to make it so complicated that there are no obvious errors.”
While we hope it's not true, if it is a very deserved RIP.
CSP and Hoare logic were brilliant. He was a huge proponent of formal methods.
He famously gave up on making formal methods mainstream, but I believe there will be a comeback quite soon.
On generated code, verification is the bottleneck. He was right, just too early.
And here we are throwing all that brilliance away with Async abominations. Software can be so simple and elegant.
Actor model would also be brilliantly wrong: it doesn't compose smaller correct systems into larger correct systems.
(Software) Transactional Memory and other ideas inspired by databases have a much better shot at this.
He was the professor in the Programming Research Group (known universally as the PRG) at Oxford when I was doing my DPhil and interviewed me for the DPhil. I spent quite a bit of time with him and, of course, spent a lot of time doing stuff with CSP including my entire DPhil.
Sad to think that the TonyHoare process has reached STOP.
RIP.
I lucked in to meeting him once, in Cambridge. A gentle intellectual giant.
I repeatedly borrow this quote from his 1980 Turing Award speech, 'The Emperor's Old Clothes'... "At last, there breezed into my office the most senior manager of all, a general manager of our parent company, Andrew St. Johnston. I was surprised that he had even heard of me. "You know what went wrong?" he shouted--he always shouted-- "You let your programmers do things which you yourself do not understand." I stared in astonishment. He was obviously out of touch with present day realities. How could one person ever understand the whole of a modern software product like the Elliott 503 Mark II software system? I realized later that he was absolutely right; he had diagnosed the true cause of the problem and he had planted the seed of its later solution."
My interpretation is that whether shifting from delegation to programmers, or to compilers, or to LLMs, the invariant is that we will always have to understand the consequences of our choices, or suffer the consequences.
Tony's An Axiomatic Basis for Computer Programming[1] is the first academic paper that I read that I was able to understand when I was an undergrad. I think it unlocked something in me because before that I never believed that I would be able to read and understand scientific papers.
That was 35ish years ago. I just pulled up the paper now and I can't read the notation anymore... This might be something that I try applying an AI to. Get it to walk me through a paper paragraph-by-paragraph until I get back up to speed.
[1]:https://dl.acm.org/doi/10.1145/363235.363259
I can recommend NotebookLM [1] for reading through scientific papers. You can then ask it questions and even get a podcast generated.
1. https://notebooklm.google/
Followup on the above with these two classics;
Retrospective: An Axiomatic Basis For Computer Programming. This was written 30 years after An Axiomatic Basis for Computer Programming to take stock on what was proven right and what was proven wrong - https://cacm.acm.org/opinion/retrospective-an-axiomatic-basi...
How Did Software Get So Reliable Without Proof? More detailed paper on the above theme (pdf) - https://6826.csail.mit.edu/2020/papers/noproof.pdf
I remember attending a tech event at MSR Cambridge, and a speaker made some disparaging comment about older developers not being able to keep up in this modern world of programming.
An older gentleman stood up and politely mentioned they knew a thing or two.
That was Tony Hoare.
From his Oxford bio: "To assist in efficient look-up of words in a dictionary, he discovered the well-known sorting algorithm Quicksort."
I always liked this presentation. I think it's equally fine to say "invented" something, but I think this fits into his ethos (from what I understand of him.) There are natural phenomena, and it just takes noticing.
I've had the good fortune to attend two of his lectures in person. Each time, he effortlessly derived provably correct code from the conditions of the problem and made it seem all too easy. 10 minutes after leaving the lecture, my thought was "Wait, how did he do it again?".
RIP Sir Tony.
Tony advised me to make money with the software model checker I have been writing. In contrast to the typical practice to make these tools open source and free for use. Would have loved to learn more from him. He was a great teacher but also a great and sharp listener. Still remember the detour we made on the way to a bar in London, talking too much and deep about refinement relations. RiP.
One of the greats. Invented quicksort and concurrent sequential processes. I always looked up to him because he also seemed very humble.
He also invented many other things, like enumeration types, optional types, constructors. He popularized the "unions" introduced by McCarthy, which were later implemented in ALGOL 68, from where a crippled form of them was added to the C language.
Several keywords used in many programming languages come from Hoare, who either coined them himself, or he took them from another source, but all later programming language designers took them from Hoare. For example "case", but here only the keyword comes from Hoare, because a better form of the "case" statement had been proposed first by McCarthy many years earlier, under the name "select".
Another example is "class" which Simula 67, then all object-oriented languages took from Hoare, However, in this case the keyword has not been used first by Hoare, because he took "class", together with "record", from COBOL.
Another keyword popularized by Hoare is "new" (which Hoare took from Wirth, but everybody else took from Hoare), later used by many languages, including C++. At Hoare, the counterpart of "new" was "destroy", hence the name "destructor", used first in C++.
The paper "Record Handling", published by C.A.R. Hoare in 1965-11 was a major influence on many programming languages. It determined significant changes in the IBM PL/I programming language, including the introduction of pointers . It also was the source of many features of the SIMULA 67 and ALGOL 68 languages, from where they spread in many later programming languages.
The programming language "Occam" has been designed mainly as an implementation of the ideas described by Hoare in the "Communicating Sequential Processes" paper published in 1978-08. OpenMP also inherits many of those concepts, and some of them are also in CUDA.
And, of course, the Go programming language.
I would not say he invented Go, although Go is probably the only relevant implementation of CSP nowadays.
I was adding Go to the list at the very end of the comment:
>OpenMP also inherits many of those concepts, and some of them are also in CUDA.
Talking about Quicksort, John Bentley’s deep dive in Quicksort is quite illuminating. https://m.youtube.com/watch?v=QvgYAQzg1z8
oh man, google tech talks. what a throwback.
there was a time, 10-15 years ago, when they were super cool. at some point they """diluted""" the technicality content and the nature of guests and they vanished into irrelevance.
Yes, but don't forget his formal work also (Hoare logic).
To me, this is his most important contribution; Everybody else built on top of this.
Hoare Logic - https://en.wikipedia.org/wiki/Hoare_logic
Rediscovering it through the Dafny programming language. Brings back memories of a 1994 University course.
I think it is even more relevant today.
Hoare Logic + Dijkstra's weakest precondition + Meyer's Design-by-Contract is what should be used to get LLMs to generate proof with code in a correctness-by-construction approach to implementation.
References:
Correctness-by-Construction (CbC) - https://www.tu-braunschweig.de/en/isf/research/cbc
A Course on Correctness by Construction - https://wp.software.imdea.org/cbc/
They were never concurrent, they were communicating. https://en.wikipedia.org/wiki/Communicating_sequential_proce...
That is indeed the correct title, but the processes were concurrent.
However, they were not just concurrent, but also communicating.
And regretful inventor of the null reference!
His “billion dollar mistake”:
https://www.infoq.com/presentations/Null-References-The-Bill...
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.
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:
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: 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.
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.
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.
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.
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.
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/Vychislit...
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".
Nice, and that was implemented and qualifies as high-level language?
You should provide a citation for where Bud Lawson has published his invention.
The use of pointers in assembly language does not count as an invention, as it was used since the earliest automatic computers. The use of implicit reference variables, which cannot be manipulated by the programmer, like in FORTRAN IV (1962) does not count as pointers.
The method for forcing another level of evaluation of a variable by using a "$" prefix, which was introduced in SNOBOL in January 1964, and which has been inherited by the UNIX shell and its derivatives does not count as a pointer.
The term "pointer" was introduced in a revision of the IBM PL/I language, which was published in July 1966. In all earlier publications that I have ever seen the term used was "reference", not "pointer".
There are 2 high-level programming languages that were the first to introduce explicit references (i.e. pointers). One language was Euler, published in January 1966 by Niklaus Wirth and Helmut Weber. However Hoare knew about this language before the publication, so he mentioned it in his paper from November 1965, where he discussed the use of references (i.e. pointers).
The other language was the language CPL, which had references already in August 1963. The difference between how CPL used references and how Euler used references is that in Euler pointer dereferencing was explicit, like later in Pascal or in C. On the other hand, in CPL (the ancestor of BCPL), dereferencing a pointer was implicit, so you had to use a special kind of assignment to assign a new value to a pointer, instead of assigning to the variable pointed by the pointer.
Looking now in Wikipedia, I see a claim that Bud Lawson has invented pointers in 1964, but there is no information about where he has published this and about which is the high-level programming language where the pointers of Bud Lawson had been used.
If the pointers of Bud Lawson were of the kind with explicit dereferencing, they would precede by a year the Euler language.
On the other hand, if his pointers were with implicit dereferencing, then they came a year after the British programming language CPL.
Therefore, in the best case for Bud Lawson, he could have invented an explicit dereferencing operator, like the "*" of C, though this would not have been a great invention, because dereferencing operators were already used in assembly languages, they were missing only in high-level languages.
However, the use of references a.k.a. pointers in a high-level programming language has already been published in August 1963, in the article "The main features of CPL", by Barron, Buxton, Hartley, Nixon and Strachey.
Until I see any evidence for this, I consider that any claim about Bud Lawson inventing pointers is wrong. He might have invented pointers in his head, but if he did not publish this and it was not used in a real high-level programming language, whatever he invented is irrelevant.
I see on the Internet a claim that he might have been connected with the pointers of IBM PL/I.
This claim appears to be contradicted by the evidence. If Bud Lawson had invented pointers in 1964, then the preliminary version of PL/I would have had them.
In reality, the December 1964 version of PL/I did not have pointers. Moreover, the first PL/I version used in production, from the middle of 1965 also did not have pointers.
The first PL/I version that has added pointers was introduced only in July 1966, long enough after the widely-known publications of Hoare and of Wirth about pointers. That PL/I version also added other features proposed by Hoare, so there is no doubt that the changes in the language were prompted by the prior publications.
So I think that the claim that Bud Lawson has invented pointers is certainly wrong. He might have invented something related to pointers, but not in 1964.
PL/I had one original element, the fact that pointer dereferencing was indicated by replacing "." with "->". This has later been incorporated in the language C, to compensate its mistake of making "*" a prefix operator.
The "->" operator is the only invention of PL/I related to pointers, so that is a thing that has been invented by an IBM employee, but I am not aware of any information about who that may be. In any case, this was not invented in 1964, but in 1966.
Damn.
Tony Hoare was on my bucket list of people I wanted to meet before I or they die. My grad school advisor always talked of him extremely highly, and while I cannot seem to confirm it, I believe Hoare might have been his PhD advisor.
It's hard to overstate how important Hoare was. CSP and Hoare Logic and UTP are all basically entire fields in their own right. It makes me sad he's gone.
You can always check his entry on the Mathematics Genealogy Project: https://mathgenealogy.org/id.php?id=45760
I actually knew about that, but it says "advisor unknown".
Regardless, he certainly knew Tony Hoare, and spoke extremely highly of him.
When I met him unfortunately I didn't realize how important he was (1987). The place where I worked used formal methods to verify the design of an FPU, in collaboration with the PRG. iirc the project was a success. I never heard of formal methods being successfully used again until TLA+ a few years ago.
Inmos’ Occam-based verification of their FPU in collaboration with researchers at Bristol and Oxford iirc? Citation: http://people.cs.bris.ac.uk/~dave/formalmethods.pdf
David May was my PhD supervisor and always spoke very highly of Sir Tony Hoare.
Edit: I’m also lucky enough to have worked with Geoff Barrett, the guy that completed that formal verification (and went on to do numerous other interesting things). Some people may be interested to learn that this work was the very first formal verification of an FPU - and the famous Intel FPU bug could have been avoided had Intel been using the verification methods that the Inmos and University teams pioneered.
I actually had two PhD advisors [1]; Jim Woodcock and Simon Foster.
Both of them are legitimately wonderful and intelligent humans that I can only use positive adjectives to describe, but the one I was referring to in this was Jim Woodcock [2]. He had many, many nice things to say about Tony Hoare.
[1] Just so I'm not misleading people, I didn't finish my PhD. No fault at all of the advisor or the school.
[2] https://en.wikipedia.org/wiki/Jim_Woodcock
Inmos? Transputers were inspired by Hoare’s CSP.
“Inspired by” is an understatement of the century lol. David May and Sir Tony worked very closely together to enable the architecture to be as pure a runtime for CSP as you could get - at least in early versions of the architecture and accompanying Occam language. It expanded and deviated a bit later on iirc.
Source: David loved to tell some of these stories to us as students at Bristol.
It’s also worth highlighting that the mathematical purity of the designs were also partly the problem with them. As a field, we’re still developing the maths of Effects and Effectful Algebras that are needed to make these systems both mathematically ‘pure’ (or at least sound to within some boundary) and ALSO capable of interfacing to the real world.
Transputer and Occam were, in this sense, too early. A rebuild now combining more recent developments from Effect Algebras would be very interesting technically. (Commercially there are all sorts of barriers).
Further Reading for the curious:
On specifically the relationship between Occam and Transputer architecture: http://people.cs.bris.ac.uk/~dave/transputer1984.pdf
Wider reading: http://people.cs.bris.ac.uk/~dave
Yes.
He came to give a lecture at UT Austin, where I did my undergrad. I had a chance to ask him a question: "what's the story behind inventing QuickSort?". He said something simple, like "first I thought of MergeSort, and then I thought of QuickSort" - as if it were just natural thought. He came across as a kind and humble person. Glad to have met one of the greats of the field!
Happy to meet you. I was there and I remember that question being asked. I think it was 2010.
If I remember correctly he had two immediate ideas, his first was bubble sort, the second turned out to be quicksort.
He was already very frail by then. Yet clarity of mind was undiminished. What came across in that talk, in addition to his technical material, was his humor and warmth.
I remember this vividly! I believe he said that he thought of _Bubble Sort_ first, but that it was too slow, so he came up with QuickSort next
He discusses this and his sixpence wager here: https://youtu.be/pJgKYn0lcno
(Source: TFA)
Sad that his (and many others') dream of widespread formal verification of software never came true. He made really fundamental contributions to computer science but will probably be mostly known for quicksort and the quote about his "billion dollar mistake", not his decades-long program to make formal methods more tractable.
Makes me think of an anecdote where Dijkstra said that he feared he would only be remembered for his shortest path algorithm.
Almost all of the earliest cited works on concurrency management in software were authored by C A R 'Tony' Hoare.
I genuinely forget he authored quicksort on the regular.
Actually, thanks to AI, this may change soon! we may be in a place where widespread formal verification is finally possible.
Random anecdote and Mr. Hoare (yep not a Dr.) has always been one of my computing heroes.
Mr. Hoare did a talk back during my undergrad and for some reason despite totally checked out of school I attended, and it is one of my formative experiences. AFAICR it was about proving program correctness.
After it finished during the Q&A segment, one student asked him about his opinions about the famous Brooks essay No Silver Bullet and Mr. Hoare's answer was... total confusion. Apparently he had not heard of the concept at all! It could be a lost in translation thing but I don't think so since I remember understanding the phrase "silver bullet" which did not make any sense to me. And now Mr. Hoare and Dr. Brooks are two of my all time computing heroes.
"Sir", not "Mr." if you're going to be pedantic about titles ;)
Edit: Oh and he has multiple honorary doctorates (at least 6!), so would be just as much "Dr." too!
It is not usual to call people with an honorary doctorate "Doctor" except in the context of the awarding institution. Most likely the awarding institutions will have actually specified that the recipient should not give anybody the false impression and I can't imagine Tony is the type to do otherwise.
His title at Oxford was 'Professor', and he was addressed as 'Tony'.
He made incoming DPhil (PhD) students a cup of tea individually in his office at the Computing Laboratory. It was a small group, but still I appreciated this personal touch.
Lol you are totally right! ;-)
I am normally a casual guy but for a giant being a bit more formal (pun intended) seems appropriate. Or maybe I am a nerd through and through :-)
Sir Tony Hoare visited Institute for System Programming in Moscow and gave a lecture quarter of the century ago. It was unforgettable experience to see the living legend of your field. He was a senior person then already and today I am going to celebrate his long and wonderful life.
I first came across Tony Hoare about 24 years ago while learning C from The C Programming Language by Kernighan and Richie. I knew him only as C. A. R. Hoare for a long time. When I got on the Internet, it took me a while to realise that when people said Tony Hoare, it was the same person I knew as C. A. R. Hoare. Quoting the relevant text from the book:
> Another good example of recursion is quicksort, a sorting algorithm developed by C.A.R. Hoare in 1962. Given an array, one element is chosen and the others partitioned in two subsets - those less than the partition element and those greater than or equal to it. The same process is then applied recursively to the two subsets. When a subset has fewer than two elements, it doesn't need any sorting; this stops the recursion.
> Our version of quicksort is not the fastest possible, but it's one of the simplest. We use the middle element of each subarray for partitioning. [...]
It was one of the first few 'serious' algorithms I learnt to implement on my own. More generally, the book had a profound impact on my life. It made me fall in love with computer programming and ultimately choose it as my career. Thanks to K&R, Tony Hoare and the many other giants on whose shoulders I stand.
With respect I say that the one can only feel gobsmacked about how much complexity has grown.
In the 60s inventing one single algorithm with 10 lines of code was a thing.
If you did that today nobody would bat an eye.
Today people write game engines, compilers, languages, whole OS and nobody bats an eye cause there are thousands of those.
Quick sort isn't even a thing for leet code interviews anymore because it's not hard enough.
"Communicating Sequential Processes" by Tony Hoare: https://www.cs.cmu.edu/~crary/819-f09/Hoare78.pdf
It had intrigued me due to its promise of designing lock-free concurrent systems, that can (I think) also be proven to be deadlock-free.
You do this by building a simple concurrent block that is proven to work correctly, and then build bigger ones using the smaller, proven blocks, to create more complex systems.
The way it is designed is processes don't share data and don't have locks. They use synchronized IPC for passing and modifying data. It seemed to be a foundational piece for designing reliable systems that incorporate concurrency in them.
From the article:
> On the topic of films, I wanted to follow up with Tony a quote that I have seen online attributed to him about Hollywood portrayal of geniuses, often especially in relation to Good Will Hunting. A typical example is: "Hollywood's idea of genius is Good Will Hunting: someone who can solve any problem instantly. In reality, geniuses struggle with a single problem for years". Tony agreed with the idea that cinema often misrepresents how ability in abstract fields such as mathematics is learned over countless hours of thought, rather than - as the movies like to make out - imparted, unexplained, to people of 'genius'. However, he was unsure where exactly he had said this or how/why it had gotten onto the internet, and he agreed that online quotes on the subject, attributed to him, may well be erroneous.
Somewhat off-topic, but it's cool hearing this from someone who's contributed so much to the fields of programming and mathematics. It makes me hopeful that my own strugglings with math will pay out over time!
RIP.
His presentation on his billion dollar mistake is something I still regularly share as a fervent believer that using null is an anti-pattern in _most_ cases. https://www.infoq.com/presentations/Null-References-The-Bill...
That said, his contributions greatly outweigh this 'mistake'.
You misunderstand the “billion dollar mistake”. The mistake is not the use of nulls per se, the mistake is type-systems which does not make them explicit.
Anti patterns are great, they act as escape hatches or pressure release valves. Every piece of mechanical equipment has some analogue for good reason.
Without things like null pointers, goto, globals, unsafe modes in modern safe(r) languages you can get yourself into a corner by over designing everything, often leading to complex unmaintainable code.
With judicious use of these anti-patterns you get mostly good/clean design with one or two well documented exceptions.
The "goto" in languages like C or C++ is de-fanged and not at all similar to the sequence break jump in "Go To Statement Considered Harmful". That doesn't make it a good idea, but in practice today the only place you'll see the unstructured feature complained of is machine code/ assembly language.
You just don't need it but it isn't there as some sort of "escape hatch" it's more out of stubbornness. Languages which don't have it are fine, arguably easier to understand by embracing structure more. I happen to like Rust's "break 'label value" but there are plenty of ways to solve even the trickier parts of this problem (and of course most languages aren't expression based and wouldn't need a value there).
That relies on a programmer doing the right thing and knowing when to use the escape valve. From the codebases I've seen, I don't trust humans in doing the right thing and being judicious with this. But it's a good point, knowing when to deviate from a pattern is a strong plus.
That's why code reviews exist, it's good process to make code reviews mandatory.
It's too much of a stretch to call null an escape hatch, or to pretend that code reviews will somehow strip it out.
The OpenJDK HashMap returns null from get(), put() and remove(), among others. Is this just because it hasn't been reviewed enough yet?
> pretend that code reviews will somehow strip it out.
Code reviews 'somehow' strip out poorly thought out new uses of escape hatches.
For your example, it would be an use of get, put or remove without checking the result.
https://news.ycombinator.com/item?id=47316880
249 points by nextos 16 hours ago | 61 comments
Thanks! We'll merge those comments hither.
I wrote both my master thesis and PhD on Hoare's Communicating Sequential Processes. I really enjoyed it's simplicity, expandability, and was always amazed that it inspired and influenced language constructs in Go, Erlang, occam and the likes.
Tony Hoare on how he came up with Quicksort:
he read the algol 60 report (Naur, McCarthy, Perlis, …)
and that described "recursion"
=> aaah!
https://www.youtube.com/watch?v=pJgKYn0lcno
I saw a casual lecture given by Tony Hoare as a teenager. The atmosphere was warm and welcoming, even if I didn't fully understand all of the content. I remember he was very kind and answered my simple questions politely.
His paper on communicating processes was a great read when I was new to computer science research.
Incredibly sad news. His contributions to the foundations of computing will remain relevant for generations to come.
unless its greatly exagerated - he was quite mind sharp in his 80s
SIR_TONY_HOARE = μX • (think → create → give → X)
-- process ran from 1934 to 2026 -- terminated with SKIP -- no deadlock detected -- all assertions satisfied -- trace: ⟨ quicksort, hoare_logic, csp, monitors, -- dining_philosophers, knighthood, turing_award, -- billion_dollar_apology, structured_programming, -- unifying_theories, ... ⟩ -- trace length: ∞ The channel is closed. The process has terminated. The algebra endures.
RIP: https://youtu.be/tAl6wzDTrJA
I watched this video a few months ago.
Virtual HLF 2020 – Scientific Dialogue: Sir C. Antony R. Hoare/Leslie Lamport
https://www.youtube.com/watch?v=wQbFkAkThGk
“I never had a doctorate, so I had to make do with Quicksort.” —Sir Tony Hoare (unpublished interview for Algorithms to Live By)
This is devastating news.
When I started university he gave a talk to all the new CompScis which as you can imagine was incredibly inspirational for an aspiring Software Engineer.
Grateful to have had that experience.
RIP
One of Billy Crystal's later standup bits was talking about how his parents have hit an age where their favorite game with their friends is called, "Guess Who Died". I've been thinking about that bit an awful lot the last couple of years.
Absolutely the GOAT of concurrency. May his ring never die.
Never made it as a wise man I couldn't cut it as a poor man stealing Tired of livin' like a blind man I'm sick of sight without a sense of feeling And this is how you remind me
This is how you remind me of what I really am This is how you remind me of what I really am
It's not like you to say sorry I was waitin' on a different story This time I'm mistaken For handing you a heart worth breakin' And I've been wrong, I've been down Been to the bottom of every bottle These five words in my head Scream, "Are we havin' fun yet?"
Yet, yet, yet, no, no Yet, yet, yet, no, no
It's not like you didn't know that I said, "I love you," and I swear I still do And it must have been so bad 'Cause livin' with me must have damn near killed you
And this is how you remind me of what I really am This is how you remind me of what I really am
It's not like you to say sorry I was waitin' on a different story This time I'm mistaken For handing you a heart worth breakin' And I've been wrong, I've been down Been to the bottom of every bottle These five words in my head Scream, "Are we havin' fun yet?"
Yet, yet, yet, no, no Yet, yet, yet, no, no Yet, yet, yet, no, no Yet, yet, yet, no, no
Never made it as a wise man I couldn't cut it as a poor man stealin' And this is how you remind me This is how you remind me
This is how you remind me of what I really am This is how you remind me of what I really am
It's not like you to say sorry I was waitin' on a different story This time I'm mistaken For handing you a heart worth breakin' And I've been wrong, I've been down Been to the bottom of every bottle These five words in my head Scream, "Are we havin' fun yet?"
Yet, yet, are we havin' fun yet? Yet, yet, are we havin' fun yet? Yeah, yeah (These five words in my head scream) Are we havin' fun yet? Yeah, yeah (These five words in my head) No, no
1) ACM published this book in 2021; Theories of Programming: The Life and Works of Tony Hoare - https://dl.acm.org/doi/book/10.1145/3477355
See the "preface" for details of the book - https://dl.acm.org/doi/10.1145/3477355.3477356
Review of the above book - https://www.researchgate.net/publication/365933441_Review_on...
Somebody needs to contact ACM and have them make the above book freely available now; there can be no better epitaph.
2) Tony Hoare's lecture in honour of Edsger Dijkstra (2010); What can we learn from Edsger W. Dijkstra? - https://www.cs.utexas.edu/~EWD/DijkstraMemorialLectures/Tony...
Somebody needs to now write a similar one for Hoare.
Truly one of the absolute greats in the history of Computer Science.
He was a professor at my old alma mater, Queen's University of Belfast. I remember hearing a story about him going to Harvard to give a lecture and, as he was presented, one of their professors referred to himself as the "Hoare of Harvard"
always knew him as C.A.R. Hoare, takes me way back to freshman college years
RIP good sir
Assert early, assert often!
"The null reference was my billion dollar mistake responsible for innumerable errors, vulnerabilities and system crashes" (paraphrasing). I don't know. This design choice exposed the developer to system realities, and modern language approaches are based on decades of attempts to improve on it, and they are not necessarily better. Safer yes, but more weighty.
Can anyone suggest a better approach for a situation like this in the future? What's better than exposing addressing the problem with a light solution?
"The problem isn't the concept of 'null', but rather that everything can be null, which makes it impossible to distinguish between the cases where null is an appropriate and expected value, from the cases where null is a defect."
https://blog.ploeh.dk/2015/04/13/less-is-more-language-featu...
Which system reality? Plenty of architectures don't have a concept of a null pointer at the hardware level. Other architectures provide multiple address spaces, or segmented memory addressing. Even when a null pointer exists at the hardware level, it doesn't have to be the zero address.
Null pointers are a software abstraction, and nowadays we have better abstractions.
Some kind of an optional/variant type, enforced by the type system.
Or if even that feels too verbose, just a 'nullable' modifier on the variable or field definition, with the default being not nullable.
(Although Optional/Maybe types are definitely my preference based on the languages I've used)
RIP Sir Tony Hoare
Turing Award Legend.
One of the greatest figure of computing in history and an example of humility as a human.
Thank you for your work on ALGOL, you were multiple decade ahead of your time.
Rest in peace.
Rest in peace.
RIP Legend
Rest in peace
How many jobs were had or not due to the candidates ability to implement his algorithms?
As a junior dev, I loved to ask interview candidates to implement merge sort or quick sort on whiteboards.
As a non-junior dev I realize how stupid that was.
I think the first enlightenment is that software engineers should be able to abstract away these algorithms to reliable libraries.
The second enlightenment is that if you don't understand what the libraries are doing, you will probably ship things that assemble the libraries in unreasonably slow/expensive ways, lacking the intuition for how "hard" the overall operation should be.
Needs a black bar!
Seconded.
this is black bar grade great. give us black bar