Nice. Didn't know the text although I should have. Would have helped me a lot in ongoing discussions about design fads with junior devs, though it's not much fun to be the nihil sub sole novum guy.
Maybe ACID, CAP, and blockchain deserve a honorable mention as well?
I certainly thought about lambda calculus. My current thinking is that is really a mathematical construct, not software. LISP was where it seriously got implemented, and I already have that listed.
Interesting that "Big O / Complexity theory" is only considered and is not yet classified as an innovation. It's hugely important and non-obvious. Also "Hashes" are extremely important.
I don't think that Google's 'PakeRank' algorithm is that special however; it's just applied graph theory; not so different from Facebook's social graph algorithms.
Also, I don't think that 'Design Patterns' should make the list. Design patterns depend heavily on the kinds of technologies being used. It's more like philosophy than science.
Design Patterns should definitely be on there. It was very important at the time. These days we take them for granted because they are baked into the numerous frameworks that most things are now built on top of.
Content Based Addressing is a late, distributed, and rather distant relative of hash tables. Hashing itself is item #5 under "Appendix: Software Innovations Being Considered".
For anyone reading the title as: "Innovations from 2001-2017" and wondering if Big O and Hashes aren't older, the source goes back all the way to 1837!
It's quite likely that there are things being published now which will be seen as hugely significant in a decade. This sort of thing is a bit of a trailing indicator.
The author aludes to this and observes that as time goes by more software ideas are getting patented, which was barely done in the old days, and which he believes slows down the innovation rate.
I guess that maybe it also has something to do with (relatively) low hanging fruit, as many of the core problems got eventually solved.
As for AI and NN, he has included backpropagation, which is the innovation that made NN practical. Also, the key innovation that is behind the current deep learning craze, GPUs, is a hardware innovation, so it's excluded.
EDIT:
The author says at the end:
Note that there are few software innovation identified in recent times. I believe that part of the reason is that over the last number of years some key software markets have been controlled by monopolies. Monopolies typically inhibit innovation; a monopoly has a strong financial incentive to keep things more or less the way they are.
EDIT:
From the article: it’s difficult to identify the “most important” innovations within the last few years. Usually what is most important is not clear until years after its development. Software technology, like many other areas, is subject to fads. Most “exciting new technologies” are simply fashions that will turn out to be impractical (or only useful in a narrow niche), or are simply rehashes of old ideas with new names.
The way to make backpropagation work properly (for "Deep Learning") was only worked out a few years ago. However, this article dates it from the first idea.
Perhaps similar to how relarional databases weren't practical until SQL and weren't workable until B-trees, but it's dated to Codd (which is fair).
The backpropagation principle itaeld is the same. But gradient computations and techniques to accelerate it or stabilize its convergence have progressed much
The article is OK... but there's so much underestimating and so many innovations left down...
The article can just be so much better...
it's mainly correct but it also feels a lot like the writer personal opinion
Without many factors that would have simplified and made the article so much better...
basic factors such as impact on the world/...
Wont we all agree that data maps are much less important then the tcp internet by a factor of lets say 500 (personal opinion.)
maps are a great thing but without them we'd have another system
Without the classical internet protocols who knows how the internet would've looked today
it would've been just a network of computers not "THE" internet as we know it...
We can't imagine how would it be probably very different maybe it'd evolve the same -we don't know
But the fact it that the www boosted human development with all other innovations software and not software
Could you imagine a world without big data/...?
Could you imagine a world without the internet?!
You probably can but could you imagine our modern 2018 world without the internet/....?
and that's just a shitty example... your article just compares world changing innovations to so new "original" bullshit innovations that might be nice but are nothing that even comes close to anything else...
and i chose these examples with a lot of consideration... u must all understand what a difference that is..
Without trees or big data we would have a pretty limited world with no such things as machine learning and such...
With Map/Reduce you really also have to include in GFS/HDFS or similar like Casandra.
You need both really together. One I would consider adding to the list is again has two parts. Containers (Cgroups/namespaces/Docker) and then Borg/K8S.
So the organizing the work and then the scheduling. I would think this would be high on the list as it is the canonical way to do things in the cloud.
K8S = Kubernettes
I really like the innovations that require two pieces together to get the result.
Pagerank is (rightly) excluded, but surely tf-idf and graph theory should make the list? It was essentially the marriage of these two concepts with map-reduce that allowed high volume search engines to actually work and become the most important piece of infrastructure on the internet.
First of all, Google doesn't use Pagerank any more, it has become a marketing term for the nearest seeds algorithm they are using.
Second, Pagerank isn't an invention it would be immediately declared as a pliagarism of academic influence measure by USPTO - that stat has been measured and reported by the index of academic citations for DECADES.
Clearly there are other things that need to be put on that list. One challenge I had was finding clear citations to the very first example. It is often very hard to find where some idea comes from. In addition, sometimes there is no one single place, because there's this gradual improvement.
Thanks for the list, it is food for thought. Yesterday there was a discussion about pseudocode in HN with many interesting observations: https://news.ycombinator.com/item?id=18691446
Howdy, I have a slight correction to the page. You note "no patent identified" for Ken Thompson's regular expression work from 1968. To the contrary, Bell Labs was granted a patent in 1971 for ken's work, with a priority date of 1967. See https://patents.google.com/patent/US3568156A/en.
I humbly submit a lamentation: the tabulated format is inconvenient to read on a phone, since the right column gets very slim and tall. Simple paragraphs with headings would do much better―the olde HTML 2.0 without tables generally has excellent usability on phones. (However, on desktop it's recommended to limit paragraph width to ~80 characters, to not make the eye travel too far back and forth, losing the next line.)
Also, just in passing, I'm tempted to note that afaik few fonts are generated automatically, and vast majority are still done by hand―partly, I think, because computers aren't trusted to do the right thing for different sizes and widths, but likely primarily because font authors don't seem to be inclined to learn all the necessary mathematical parameters (of which Knuth's Metafont has ~60). There are some automatic features in font renderers, but that's far from full generation of a font.
A couple of suggestions: Immutable Data Structures. And perhaps something that captures the kind of type inference Haskell/Elm/etc. can do. Not sure if they're big enough to compete with something like B-trees :-)
Video compression seems like a big one. So does FFT. Even if they were conceptually around for a long time (Gauss instead of Tukey probably originated FFT, Fano -compression in general, etc), particular implementations of them made for huge differences in what people could do with computers.
If not compression, certainly coding theory in general, which is so all-pervasive now, people forget it exists.
FWIW I recently read "The Dream Machine" by Mitchell Waldorf, and it has interesting details that bear on the "1945 Stored Program" entry in your list.
Basically it said that von Neumann was reporting the work of others in "draft", and he didn't include the people who actually did the work as authors because it was a draft. In other words, it was prematurely circulated without proper attribution.
Ironically, I don't remember their names. It may have been Eckert and Mauchly as you list on your page. If anyone wants to know more, e-mail me (address in profile) I will look it up.
There was also a patent dispute between von Neumann and the other party, IIRC, and that is why there is no patent.
So basically the "von Neumann machine" is probably not a great name. You don't call it that in your page, which is good, but that's how I always thought of the stored program! I believe I was taught that in computer architecture class in college.
----
EDIT: Yes now that I googled, the way the Dream Machine portrayed it, Eckert and Mauchly had a stronger claim to inventing the stored program than is portrayed on your page.
You did say von Neumann "described" the stored program rather than invented it, and that's the issue that is discussed at some length in the book. Some snippets here:
Apparently there was a whole team of people participating in the design:
> some on the EDVAC design team contended that the stored-program concept had evolved out of meetings at the University of Pennsylvania's Moore School of Electrical Engineering predating von Neumann's activity as a consultant there, and that much of the work represented in the First Draft was no more than a translation of the discussed concepts into the language of formal logic in which von Neumann was fluent.
The elegiac Stigler's law of eponymy is mentioned there: “no scientific discovery is named after its original discoverer.”
Should PLT be included? There's the Backus lecture on why functional programming matters, the ML language and hindley milner type inference, object oriented programming, polymorphism, dependent types, lambda calculus, curry howard isomorphism, Martin lof type theory, Automath, coq...
It's embarrassing that many of these supposed innovations are based on the messenger, not the message. For example my officemate (Andrew Grimshaw, 1990) published a PhD on a practical dataflow distributed system infrastructure a decade before mapreduce implemented a subset of his PhD but hyped it to death from Google, a very hype-driven company in general. These days Apache airflow is Grimshaw's work on steroids.
i dont know if its hype. its seems like a very deliberate form of technical marketing. when I was being programmed to be a Googler, they stood up in front of us and listed all the foundational contributions the Google made out of whole cloth, and could only keep repeating 'but, but, but..' to myself. (which isn't to say there isn't alot of new technical meat behind them, but collectively they sure do rush to claim exclusive credit)
thanks for the thesis pointer, i went down the distributed dataflow path later (but also before Google), and I'd love to read it.
it’s difficult to identify the “most important” innovations within the last few years. Usually what is most important is not clear until years after its development. Software technology, like many other areas, is subject to fads. Most “exciting new technologies” are simply fashions that will turn out to be impractical (or only useful in a narrow niche), or are simply rehashes of old ideas with new names.
While an important concept and useful technique , I find it nowhere near as fundamental as compilation, the mouse or datagram network protocols. Maybe a more fundamental principle is used by virtual dom that can be the real innovation?
I totally agree. Purely functional components are more fundamental but even that might not warrant a place on a list like this although it's significant in the JavaScript UI realm today.
This list makes me think about the biggest hypes, innovations that would be important but never fulfilled the hopes people placed on them (e.g.: expert systems, digital assistants, perhaps cryptocurrencies)
Pretty sure digital assistants are on the rise right now. Afaik expert systems are used in medicine, and I suppose some chat bots qualify as them too, though I think people will try to drop manually programming the rules at some point. Since we're finally marching straight into a scifiey cyberpunkish future, I'm sure these two things will be around.
At a time where there's more software engineers, better communication and faster development than ever before... Why does it feel like less innovation is occurring?
Are people less creative when everyone's watching, learning and copying from everyone else? ...
One issue is it takes time for an innovation to become widely adopted; a criterium for this list (e.g. git is young, but the idea of distributed version control is old).
First, the low-hanging fruit has already been picked.
Second, it can take time - possibly decades - for an idea to bear enough fruit that we can see its importance. Look how long the idea of hypertext had been around before it became a household name.
>Why does it feel like less innovation is occurring?
Specialization + Copypasting what works.
You wouldnt notice if a fortune 500 company saved a million dollars with a software innovation. But it affects their prices and future.
re-copypaste- When a problem is solved, you would not re-invent the wheel. With digital products, its easy to copy and paste. With physical products, you still need to produce.
And I find that recently tech is in the form of application. Giving non-tech people the ability to do database + front end work. Or using the tech to solve a niche problem.
> Note that there are few software innovation identified in recent times. I believe that part of the reason is that over the last number of years some key software markets have been controlled by monopolies. Monopolies typically inhibit innovation; a monopoly has a strong financial incentive to keep things more or less the way they are.
I disagree. It is hard to talk about software innovation without mentioning Xerox PARC. The PARC existed because Xerox was a monopoly with too much money on their hands. Kind of like Google X today.
Monopolies in the software industry are actually quite fragile. Today's monopolies started small and took over the monopolies of the past in a relatively short amount of time. And the same fate will happen to them unless they keep innovating.
Tech is not like railways, where you can't build tracks anywhere you want because of things like land ownership and city planning. It is not like heavy industry where capital investments are huge and margins are low. Even their trove of personal data doesn't mean much: these get outdated rather quickly and machine learning rely less and less on huge datasets (see AlphaZero). Unsurprisingly, AlphaZero is a Google initiative, that's the kind of innovation that could be disruptive in someone else's hands, so they invest in it in order to keep their position.
Seems like it's just an S curve. At first nobody knows what they are doing so it starts off slowly. Then you get the phase where the low hanging fruit gets picked off rapidly by everybody in the field. Lots of names get attached to fairly basic but important concepts. After some time the easy stuff is mined out and the pace of discovery slows substantially. Worse, it may take a good chunk of a lifetime to learn about everything that has already been discovered so you have an idea of where to look next. Or at least to get an idea of what not to investigate because it has already been discovered.
Xerox PARC is certainly important to computing and software history, but it was important as a research unit rather than an innovator.
I may be just arguing semantics but my take is that researchers discover and innovators make it useful and bring it to the masses. Xerox PARC may have discovered the GUI but it was APPLE who made it useful and brought it to the masses.
Although monopolies can innovate, there is no denying that monopolies are risk averse and have internal incentive to quash any innovations that may negatively affect their cash cows. Younger and smaller companies are more likely to take chances and be disruptive.
> I disagree. It is hard to talk about software innovation without mentioning Xerox PARC. The PARC existed because Xerox was a monopoly with too much money on their hands. Kind of like Google X today.
Xerox PARC can be understood as putting a bunch of smart people in one place and giving them essentially basic income. This seems to be a great way to do research work; beyond corporate monopolies, another successful source of basic income for researchers was DOD grants during the Cold War. A software monopoly that actually tries to monetize the research output directly interferes with this scheme a bit.
> Tech is not like railways, where you can't build tracks anywhere you want because of things like land ownership and city planning.
We don't have that, but we now have software patents, which are even worse in the way - not only you have to pay a lot of money to just be able to work, with software patents it's easy for existing players to just lock out whole areas of development by speculatively applying for, or buying, patents.
Personally, I think C deserves mention, not because it became THE portable language after 8 x n-bit implementations became standard, but rather, it was the first neutral, agnostic language about control structures (for, while, and do .. until) and argument-passing methods (call by name, value, reference, ...), and block-terminating methds (begin .. end?
Begin ... End.? no, {}=;) and it buried all the idiotic academic flame wars claiming one of each choice was THE ONLY "right" way to build a programming language. C was also the first language to popularize access to nearly the entire instruction set of a machine with it's rich set of operators. C++ DOES NOT deserve mention because it once again tried to "force" programmers to follow "the one true way" to write object oriented programs, by outlawing a number of useful programming constructs that Stroustroup judged unworthy (such as consts without storage in base classes, which could not be subclassed so he nuked them even though they are useful, e.g. for the gravitational constant etc.)
What about the first algorithm for back-propagating neural networks? I can't remember who did that but I am sure someone on HN will remember. When Minsky's "Perceptrons" was written there were all these problems with neural networks that back-propagation solved. That seems like kind of a big deal. It also seems like a lot deep learning is built off of or related to that work.*
* I am not that knowledgeable about deep learning so please correct me if I am misinformed.
Out of genuine curiosity, what exactly is novel about this? Isn't back-propagation just the chain rule (i.e. as old as calculus). And I figure 'gradient descent' was discovered not long after?
I am not an expert, but Marvin Minsky wrote a whole book about the kinds of problems that Neural Networks can't solve, that didn't take into account back-propagation. No one refuted it, as far as I know for a long time. This may all seem obvious now but I don't think anyone actually did it until the mid-eighties.
76 comments
[ 2.7 ms ] story [ 140 ms ] threadMaybe ACID, CAP, and blockchain deserve a honorable mention as well?
Also, I don't think that 'Design Patterns' should make the list. Design patterns depend heavily on the kinds of technologies being used. It's more like philosophy than science.
Design Patterns should definitely be on there. It was very important at the time. These days we take them for granted because they are baked into the numerous frameworks that most things are now built on top of.
I'm wracking my brains for something in the NN or AI or something space, but yet... yeah, maybe innovation is tailing off?
Maybe GAN if all those fake voice recordings & fake photos & fake videos end up causing major problems for society.
I guess that maybe it also has something to do with (relatively) low hanging fruit, as many of the core problems got eventually solved.
As for AI and NN, he has included backpropagation, which is the innovation that made NN practical. Also, the key innovation that is behind the current deep learning craze, GPUs, is a hardware innovation, so it's excluded.
EDIT: The author says at the end: Note that there are few software innovation identified in recent times. I believe that part of the reason is that over the last number of years some key software markets have been controlled by monopolies. Monopolies typically inhibit innovation; a monopoly has a strong financial incentive to keep things more or less the way they are.
EDIT: From the article: it’s difficult to identify the “most important” innovations within the last few years. Usually what is most important is not clear until years after its development. Software technology, like many other areas, is subject to fads. Most “exciting new technologies” are simply fashions that will turn out to be impractical (or only useful in a narrow niche), or are simply rehashes of old ideas with new names.
Perhaps similar to how relarional databases weren't practical until SQL and weren't workable until B-trees, but it's dated to Codd (which is fair).
The article can just be so much better... it's mainly correct but it also feels a lot like the writer personal opinion Without many factors that would have simplified and made the article so much better...
basic factors such as impact on the world/...
Wont we all agree that data maps are much less important then the tcp internet by a factor of lets say 500 (personal opinion.)
maps are a great thing but without them we'd have another system
Without the classical internet protocols who knows how the internet would've looked today
it would've been just a network of computers not "THE" internet as we know it...
We can't imagine how would it be probably very different maybe it'd evolve the same -we don't know
But the fact it that the www boosted human development with all other innovations software and not software
Could you imagine a world without big data/...?
Could you imagine a world without the internet?!
You probably can but could you imagine our modern 2018 world without the internet/....?
and that's just a shitty example... your article just compares world changing innovations to so new "original" bullshit innovations that might be nice but are nothing that even comes close to anything else...
and i chose these examples with a lot of consideration... u must all understand what a difference that is..
Without trees or big data we would have a pretty limited world with no such things as machine learning and such...
Without the turing machine "data structure"
I'll let you imagine how our world could be.....
- Gesture-based UI: this forms the basis of the smartphone industry
- sync communications like IRC, chat, voice, video chat (since email which is async is included)
- Consensus algo like Paxos and Raft
- Computer game: Spacewar
Cryptocurrencies
Distributed file transfer (such as bittorrent)
Tor
You need both really together. One I would consider adding to the list is again has two parts. Containers (Cgroups/namespaces/Docker) and then Borg/K8S.
So the organizing the work and then the scheduling. I would think this would be high on the list as it is the canonical way to do things in the cloud.
K8S = Kubernettes
I really like the innovations that require two pieces together to get the result.
Second, Pagerank isn't an invention it would be immediately declared as a pliagarism of academic influence measure by USPTO - that stat has been measured and reported by the index of academic citations for DECADES.
Clearly there are other things that need to be put on that list. One challenge I had was finding clear citations to the very first example. It is often very hard to find where some idea comes from. In addition, sometimes there is no one single place, because there's this gradual improvement.
Also, just in passing, I'm tempted to note that afaik few fonts are generated automatically, and vast majority are still done by hand―partly, I think, because computers aren't trusted to do the right thing for different sizes and widths, but likely primarily because font authors don't seem to be inclined to learn all the necessary mathematical parameters (of which Knuth's Metafont has ~60). There are some automatic features in font renderers, but that's far from full generation of a font.
If not compression, certainly coding theory in general, which is so all-pervasive now, people forget it exists.
Basically it said that von Neumann was reporting the work of others in "draft", and he didn't include the people who actually did the work as authors because it was a draft. In other words, it was prematurely circulated without proper attribution.
Ironically, I don't remember their names. It may have been Eckert and Mauchly as you list on your page. If anyone wants to know more, e-mail me (address in profile) I will look it up.
There was also a patent dispute between von Neumann and the other party, IIRC, and that is why there is no patent.
So basically the "von Neumann machine" is probably not a great name. You don't call it that in your page, which is good, but that's how I always thought of the stored program! I believe I was taught that in computer architecture class in college.
----
EDIT: Yes now that I googled, the way the Dream Machine portrayed it, Eckert and Mauchly had a stronger claim to inventing the stored program than is portrayed on your page.
You did say von Neumann "described" the stored program rather than invented it, and that's the issue that is discussed at some length in the book. Some snippets here:
https://books.google.com/books?id=7HpQAAAAMAAJ&dq=dream+mach...
Apparently there was a whole team of people participating in the design:
> some on the EDVAC design team contended that the stored-program concept had evolved out of meetings at the University of Pennsylvania's Moore School of Electrical Engineering predating von Neumann's activity as a consultant there, and that much of the work represented in the First Draft was no more than a translation of the discussed concepts into the language of formal logic in which von Neumann was fluent.
The elegiac Stigler's law of eponymy is mentioned there: “no scientific discovery is named after its original discoverer.”
thanks for the thesis pointer, i went down the distributed dataflow path later (but also before Google), and I'd love to read it.
it’s difficult to identify the “most important” innovations within the last few years. Usually what is most important is not clear until years after its development. Software technology, like many other areas, is subject to fads. Most “exciting new technologies” are simply fashions that will turn out to be impractical (or only useful in a narrow niche), or are simply rehashes of old ideas with new names.
Maybe that's the reason it's not in list (yet?).
Are people less creative when everyone's watching, learning and copying from everyone else? ...
First, the low-hanging fruit has already been picked.
Second, it can take time - possibly decades - for an idea to bear enough fruit that we can see its importance. Look how long the idea of hypertext had been around before it became a household name.
Specialization + Copypasting what works.
You wouldnt notice if a fortune 500 company saved a million dollars with a software innovation. But it affects their prices and future.
re-copypaste- When a problem is solved, you would not re-invent the wheel. With digital products, its easy to copy and paste. With physical products, you still need to produce.
And I find that recently tech is in the form of application. Giving non-tech people the ability to do database + front end work. Or using the tech to solve a niche problem.
I disagree. It is hard to talk about software innovation without mentioning Xerox PARC. The PARC existed because Xerox was a monopoly with too much money on their hands. Kind of like Google X today.
Monopolies in the software industry are actually quite fragile. Today's monopolies started small and took over the monopolies of the past in a relatively short amount of time. And the same fate will happen to them unless they keep innovating.
Tech is not like railways, where you can't build tracks anywhere you want because of things like land ownership and city planning. It is not like heavy industry where capital investments are huge and margins are low. Even their trove of personal data doesn't mean much: these get outdated rather quickly and machine learning rely less and less on huge datasets (see AlphaZero). Unsurprisingly, AlphaZero is a Google initiative, that's the kind of innovation that could be disruptive in someone else's hands, so they invest in it in order to keep their position.
Physics had a time of rapid innovation.
I may be just arguing semantics but my take is that researchers discover and innovators make it useful and bring it to the masses. Xerox PARC may have discovered the GUI but it was APPLE who made it useful and brought it to the masses.
Although monopolies can innovate, there is no denying that monopolies are risk averse and have internal incentive to quash any innovations that may negatively affect their cash cows. Younger and smaller companies are more likely to take chances and be disruptive.
Xerox PARC can be understood as putting a bunch of smart people in one place and giving them essentially basic income. This seems to be a great way to do research work; beyond corporate monopolies, another successful source of basic income for researchers was DOD grants during the Cold War. A software monopoly that actually tries to monetize the research output directly interferes with this scheme a bit.
> Tech is not like railways, where you can't build tracks anywhere you want because of things like land ownership and city planning.
We don't have that, but we now have software patents, which are even worse in the way - not only you have to pay a lot of money to just be able to work, with software patents it's easy for existing players to just lock out whole areas of development by speculatively applying for, or buying, patents.
* I am not that knowledgeable about deep learning so please correct me if I am misinformed.
Log-structured file systems (and append-only I/O)
Alpha-beta search
TF-IDF