4 ms·

One of the greats. Invented quicksort and concurrent sequential processes. I always looked up to him because he also seemed very humble.

baruchel 7mo ago
Yes, but don't forget his formal work also (Hoare logic).
- rramadass 7mo ago
  To me, this is his most important contribution; Everybody else built on top of this. Hoare Logic - https://en.wikipedia.org/wiki/Hoare_logic https://en.wikipedia.org/wiki/Hoare_logic
  - lkuty 7mo ago
    Rediscovering it through the Dafny programming language. Brings back memories of a 1994 University course.
    - rramadass 7mo ago
      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 https://www.tu-braunschweig.de/en/isf/research/cbc A Course on Correctness by Construction - https://wp.software.imdea.org/cbc/ https://wp.software.imdea.org/cbc/
    - rramadass 7mo ago
      You might find this paper interesting (uses examples in Dafny) - https://news.ycombinator.com/item?id=47334375 https://news.ycombinator.com/item?id=47334375
wood_spirit 7mo ago
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 7mo 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 7mo 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 7mo 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.
embit 7mo ago
Talking about Quicksort, John Bentley’s deep dive in Quicksort is quite illuminating. https://m.youtube.com/watch?v=QvgYAQzg1z8 https://m.youtube.com/watch?v=QvgYAQzg1z8
- znpy 7mo ago
  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.
  - senderista 7mo ago
    much like google doodle
madsohm 7mo ago
They were never concurrent, they were communicating. https://en.wikipedia.org/wiki/Communicating_sequential_processes https://en.wikipedia.org/wiki/Communicating_sequential_proce...
- adrian_b 7mo ago
  That is indeed the correct title, but the processes were concurrent. However, they were not just concurrent, but also communicating.
adrian_b 7mo ago
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.
- BitsAndObjects 7mo ago
  And, of course, the Go programming language.
  - linhns 7mo ago
    I would not say he invented Go, although Go is probably the only relevant implementation of CSP nowadays.
    - BitsAndObjects 7mo ago
      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.

baruchel 7mo ago

Yes, but don't forget his formal work also (Hoare logic).

rramadass 7mo ago
To me, this is his most important contribution; Everybody else built on top of this. Hoare Logic - https://en.wikipedia.org/wiki/Hoare_logic https://en.wikipedia.org/wiki/Hoare_logic
- lkuty 7mo ago
  Rediscovering it through the Dafny programming language. Brings back memories of a 1994 University course.
  - rramadass 7mo ago
    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 https://www.tu-braunschweig.de/en/isf/research/cbc A Course on Correctness by Construction - https://wp.software.imdea.org/cbc/ https://wp.software.imdea.org/cbc/
  - rramadass 7mo ago
    You might find this paper interesting (uses examples in Dafny) - https://news.ycombinator.com/item?id=47334375 https://news.ycombinator.com/item?id=47334375

wood_spirit 7mo ago

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 7mo 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 7mo 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 7mo 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.

embit 7mo ago

Talking about Quicksort, John Bentley’s deep dive in Quicksort is quite illuminating. https://m.youtube.com/watch?v=QvgYAQzg1z8 https://m.youtube.com/watch?v=QvgYAQzg1z8

znpy 7mo ago
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.
- senderista 7mo ago
  much like google doodle

madsohm 7mo ago

They were never concurrent, they were communicating. https://en.wikipedia.org/wiki/Communicating_sequential_processes https://en.wikipedia.org/wiki/Communicating_sequential_proce...

adrian_b 7mo ago
That is indeed the correct title, but the processes were concurrent. However, they were not just concurrent, but also communicating.

adrian_b 7mo ago

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.

BitsAndObjects 7mo ago
And, of course, the Go programming language.
- linhns 7mo ago
  I would not say he invented Go, although Go is probably the only relevant implementation of CSP nowadays.
  - BitsAndObjects 7mo ago
    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.