The Most Important Software Innovations (2021)

29 points by veqq

fanf

Some things I would add to the list:

Hindley-Milner, ie parametric/generic types definitely deserve a place.
Probably also Wadler+Blott typeclasses/traits.
Optimizing compilers, Fran Allen’s pioneering work. Dunno if continuations should be lumped in with SSA or not.
Macro generators, Strachey’s GPM, Mooers’ TRAC, etc.

doctor_eval

I thought we might see declarative systems in the list (eg: nix, k8s, terraform). It maybe it wasn’t prominent enough when this was updated in December 2021. Or maybe it’s just obvious, and I’m just easily impressed.

bitshift

I wonder if Wheeler would lump those in with the 1977 innovation "Make (automated build system using dependencies)"? There's a machine-readable specification, the user makes a request, and the computer figures out and runs the delta of tasks required to achieve it.
veqq

I don't think Wheeler's that kind of guy as there's no Prolog, but declarative systems have been around for ages; Windows NT used Small Prolog for network configuration.
- bitshift
  
  In 1965 on Wheeler's timeline:
  
  J.A. Robinson developed the concept of “unification”. This concept - and algorithms that implement it - become the basis of logic programming. No patent identified.
  
  That would cover Prolog. It might also cover some of the stuff @fanf mentioned like Hindley-Milner, but I admit I'm not an expert in this area.
  
  From Wheeler's criteria at the top, it sounds like he's looking for the first appearances of important ideas rather than a hall-of-fame approach for their implementations. Which is still kind of fuzzy because what constitutes a "separate" idea versus an evolution of a previous one? (So some judgement calls are still unavoidable. But I admire how thoughtful he was in drafting his criteria!)
icefox
Cuts off at a rather odd spot in time. But it is also the nature of such lists to be subjective and incomplete. I would add:
- Merkle-DAG's in general, though it does mention content-addressed storage
- Kademlia and other DHT-y things
- Onion routing
- Skiplists, hash-array mapped trees, bloom filters, maybe even robin-hood hashing (data structure R&D did not magically stop in 1980, even if a lot of the most foundational stuff had been discovered)
- Compiler-specific, but continuation-passing style and static-single-assignment form have certainly changed the world
- PRNG's in general
- Database theory
- Pubsub models maybe?
- Spacewar!
- fanf
  
  data structure R&D did not magically stop in 1980
  
  Oh! We have to mention of structured data types: records, pointers, leading to algebraic data types. McCarthy and Hoare around 1963.
  
  Databases (relational algebra and SQL) are on the list dated 1970.
Diana

I would add package repository, package managers, the idea of version and free and open source licenses to it.

But I also understand why it would not meet the criterias.
- icefox
  
  Ooh, yeah! I think CPAN and CTAN are the original public source-based package repositories?
justinpombrio
Missing the lambda calculus, from 1936! It is a model for:
- Functions (and is much earlier than the quoted 1951 invention of subroutines)
- Closures
- Computation, that's equivalent to Turing machines (1936-1937), but more closely matches how we program computers
- The stack principle (1955), if you think about how to efficiently model the lambda calculus using delayed substitutions. I don't know whether any of the inventors of the stack principle were actually thinking about the lambda calculus, but they could have been, and it would have given them most of the answer.
hao
- distributed version control: widely used, critically important, a new idea
- jails / cgroups / containerization: same, although more a gradual evolution?
- x3dh + double ratchet (signal): this essay leaves out crypto altogether, but the advent of semi-widely-adopted end-to-end encrypted communication seems pretty important to me. maybe more CS than software
- webassembly: if generalized markup language makes the list, then generalized (and safe to execute) low-level IR should make the list too, imo
this is a fun intellectual exercise! i do wonder how many of these things will be around in 20 years and in what form
- fanf
  
  Distributed version control is on the list, dated from 1991.
  
  Wasm is a combination of p-code (1966) and secure mobile code (1992). There’s another line back to UNCOL (1958, vapourware) via ANDF (1990ish, unsuccessful) and AS/400 TIMI (1988) which are distinguished from p-code by trying to be language-independent as well as target-independent.
- icefox
  
  I might generalize jails/containers to "virtual machines in general", particularly hypervisors that allow efficient sandboxing of OS-level things. I view containers as an evolution of that idea.
  - calvin
    
    Virtual machines have been well known for decades (since VM on the 360), but lightweight OS virtualization/containers feels much more recent. I think patient zero there is jails, but I'm wondering if there's prior art?
    
    koala
    
    The article seems to list them as containers, dated as 1979 due to chroot.
  - zie
    
    I would argue all of this is already on his list, except maybe the cryptography stuff.
    
    He either lumps it in as a child of RSA or skips all other cryptography. I dunno which.
    
    My take:
    
    VCS: He has it twice, CVS(1986) and DVCS(1991).
    
    Jails: Operating system level virtualization (containers) it literally says your words.
    
    webassembly: 1992 under Secure Mobile Code (Java and Safe-Tcl) literally has the word bytecode in the description.