Tony Hoare, Turing Award-Winning Computer Scientist Behind QuickSort, Dies At 92 (i-programmer.info) 32
Tony Hoare, the Turing Award-winning pioneer who created the Quicksort algorithm, developed Hoare logic, and advanced theories of concurrency and structured programming, has died at age 92.
News of his passing was shared today in a blog post. The site I Programmer also commemorated Hoare in a post highlighting his contributions to computer science and the lasting impact of his work. Personal accounts have been shared on Hacker News and Reddit.
Many Slashdotters may know Hoare for his aphorism regarding software design: "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. The first method is far more difficult."
News of his passing was shared today in a blog post. The site I Programmer also commemorated Hoare in a post highlighting his contributions to computer science and the lasting impact of his work. Personal accounts have been shared on Hacker News and Reddit.
Many Slashdotters may know Hoare for his aphorism regarding software design: "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. The first method is far more difficult."
I remember learning quicksort in college (Score:5, Interesting)
And I've heard that if you have a background in mathematics that it all kind of makes sense and follows from that however that just kicks the can down the road to whoever first figured out those mathematical concepts.
Re:I remember learning quicksort in college (Score:5, Interesting)
I remember proving to myself that it works as well as he did by sorting a deck of cards using the method. I was shocked at how quickly it worked. I rarely ever have to roll my own sort, the library ones work better than good, but when I do, its always a quicksort, just because its one I know works and works well. Its not the fastest, but it IS fast.
Re: (Score:3)
Re: (Score:2)
Selling advertising [quoteinvestigator.com].
Re: (Score:3)
Re:I remember learning quicksort in college (Score:5, Informative)
And I've heard that if you have a background in mathematics that it all kind of makes sense
Which is a good argument for getting a well rounded education. The software is only tool to implement an algorithm and solve a problem. One has to understand the problem domain to begin with.
This will be LLMs Achilles Heel. It doesn't really 'understand' anything.
Re: (Score:2)
And I've heard that if you have a background in mathematics that it all kind of makes sense and follows from that however that just kicks the can down the road to whoever first figured out those mathematical concepts.
I'm not saying it was the aliens... But it was the aliens.
Really? (Score:2)
I find the quicksort algo way easier to understand that some other sorts. eg good luck figuring out wtf is going on with a cycle sort.
Also the guy who created null (Score:4, Informative)
Re: (Score:2)
Well, I liked this guy when I read that he created QuickSort, that's cool.
But now that you tell me he created null, curses be upon him! :-)
Re: (Score:2)
Don't forget NaN
Re: (Score:3)
NaN was developed by William Kahan, to be part of the IEEE-754 1985 specification for floating-point numbers. So, not Tony Hoare.
Honestly, I don't get all the null-hating here, even from the guy who created it and changed his mind. Is it not useful to have a value that means 'nothing?'
Re: (Score:2)
Vale Professor Hoare (Score:3)
Thankyou for your contributions, sir. So many things are possible now because of your work.
One of his lessor known contributions (Score:5, Informative)
One lessor known contributions was Hoare Semantics. This allowed one to use modal logic to prove logical statements about sequential computation. The idea uses a necessity operator from modal logic. The trick he supplied was you could "compute" the effect of that operator on statements. Very toy example:
x = 1
x = x + 1
{x = 2}
where {x = 2} is a statement in equational logic. His idea was to drag the statement backwards through the x = x + 1, so you got
x = 1
{x = 2}[x replaced with x + 1]
x = x + 1
{x = 2}
The [x replaced with x + 1] is a modal logic operator (in suffix position). Then
{x = 2}[x replaced with x + 1] .... =.... x + 1 = 2
The using arithmetic, subtract 1 from both sides of x + 1 = 2 yielding x = 1 (the .... =.... is equality in the metalanguage and the second = is equality in the equational logic language). Now your x = 1 as program code clearly makes x = 1 as an equational logic statement true.
This simple, it gets more complicated when you include if and while statements, and function calls. There are rules for them (see David Gries, the Science of Programming). This does the job at the syntactic level. There's another method, which is equivalent, done model theoretically where you abstract the memory into a function mapping variables to values and then interpret the program language in that model theoretic system. I prefer the latter.
He invented quicksort in college (Score:2)
I was told he invented quicksort in college while learning about bubblesort and being told that was the fastest known way, though lower bound should be possible, but no such algorithm had been found. Then he suggested quicksort to the professor..
Re:He invented quicksort in college (Score:4, Informative)
That's not how he tells it [blogspot.com]. He says he invented it after independently inventing insertion sort and realising that he wanted something subquadratic. He was "in college" in the sense that he was a postgraduate student. Mergesort had been published more than a decade before, but it had the disadvantage of not being in place.
Love it (Score:2)
"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. The first method is far more difficult."
Love that. So true!
Re: (Score:2)
The second one is what LLM "coders" seem to be doing today.
Re: (Score:2)
I thought it was already the point behind a lot of enterprise software development processes. No AI required for that...
The AI does make it worse though. Really leans into that paper thin responsibility mitigation that wont mean a thing when an actual problem happens.
Re: (Score:2)
Probably. And likely the reason why so much "professionally created" software sucks so badly.
Come to think of it, the success of LLM coding tools may be connected to this broken approach being widespread.
Introduction to Sorting (Score:1)
One Of My Favourite Computing Quotes (Score:3)
I've always liked this quote from Tony Hoare's Turing Award Lecture [archive.org]
"I conclude that 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.
The first method is far more difficult."
Like learning multiplication tables (Score:1)
Learning the various sorting algorithms is like learning the multiplication tables. It's important to know them and know how they work, but few people (or programmers) actually do these things these days. In fact, for most applications it would be a mistake to roll your own sorting algorithm, but it's important to know how and why they work.
Quicksort is an abomination (Score:2)
Using it is grounds for immediate termination IMO. Hoare should really have stayed out of that area or make it much more clear that Quicksort is not fit for practical use.
That said, his other contributions are very good. Hoare logic finally gave us reasonably well working ways to argue about code in a mathematically sound way. Of course, the WP-Calculus (Weakest Precondition Calculus) is much better, but somebody has to make the first step and then others can improve on that. (I learned both...)
Re: (Score:2)
Re: (Score:2)
Quicksort has no assured performance. And that makes it a target for Algorithmic Complexity Attacks. Something you very much do not want. One of these "clever" hacks that turn out to be pretty dumb.