Greenspun’s tenth rule of programming says
Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
Here I’m going to take seriously a rule that was only not entirely serious. It’s saying three things about Lisp.
- It’s a frequently rediscovered technology. There’s something inevitable about it.
- It’s not completely widely known. Not everyone knows about it, so they don’t know that they’re reinventing it.
- It’s not easy to implement, hence all the poor implementations.
The same could be said of state machines. A number of projects have grown until they contained an ad hoc, informally-specified, bug-ridden, slow implementation of state machines.
What are other ideas like Lisp and state machines that are frequently and poorly reinvented?
I’d propose configuration options and command line arguments. Many different programs come up with new (and often broken/fragile) ways to configure their options, be they in a ini-style file or command line arguments that have inconsistent formatting.
Most distributed systems seem to recreate failures when building distributed consistency (via CAP, most everyone gives up consistency for speed and availability)
Mordern build systems for web applications often re-invent build tools that are supposed to make development easier (Make and Watch unix commands).
Unification is one of the most notoriously reinvented technology.
Any sufficiently complicated server program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Erlang.
More generally, my experience is that large and highly concurrent servers tend to reinvent the actor model because shared-state concurrency becomes overwhelming
Automation tools, like Hrishikesh says. Everyone writing build management tools should be required to spend a month with GNU Make first. I expect 90% of new build tools would then not exist. (Or we’d get some good patches for Make.)
Also, typing. Javascript is slowly re-adding TypeScript. PHP recently added scalar typing. The “weak typing, scripted, duck typed, we don’t need no steenkin’ types limiting what I do” languages are all rediscovering that once you get past a certain size/complexity of application, formal data definition (types) are really really useful!
Another good example: The Go community is doing everything they possibly can to not reach the same conclusion for package management as every other language. Despite the rather obvious prior art, they’re actively trying to avoid “being like everyone else”, because reasons. They’ll eventually end up with the same conclusions as every other language, but they’ll go through as much pain as they possibly can before giving in. More information: http://engineeredweb.com/blog/2016/path-go-pkg-mgmt/
PAXOS
Recursive descent compilers
Distributed Coordinators
Monads
I suspect lisp is not difficult to implement, but only when done intentionally. When done unintentionally you will make poor design decisions from the start that impede you. Not having a clear direction from the start makes it difficult to reach a goal.
I take issue with this quote because it implies (or at least I see a lot of lisp zealots use it to imply, I’ve no idea if Greenspun felt this way) that lisp is somehow the platonic ideal, and that anything with similar ideas is “similar to lisp”. Many of the ideas in lisp are good ones, but that doesn’t mean that lisp is the best possible implementation of those ideas. It is however a system where those ideas are implemented intentionally, which does make it better than those where they are implemented unintentionally (like the ones referenced in the quote).
I find that famous quote harmful. Not because it is wrong, but because it might be mistakenly interpreted as an advice to use Lisp instead. That interpretation has the implication in the wrong direction, though: just because some Lisp features become necessary for your purposes, it doesn’t mean they are also sufficient.
I’m more interested in the pattern it suggests than what it says about Lisp in particular.
Window managers. Desktop OSes spent ages working out consistent window behaviour, widgets, etc. Then came along software that would write code to manage multiple windows inside the same interface (Forget the older examples, but Excel, Adobe Photoshop and Paint.net still do this). Reinvented. That falls out of favour. Then along comes tabbed software that can spawn windows, and that write their own window management (Chrome, for example). A lot of them are even writing their own scrollbars and things now that don’t work as well as the default ones (For example, no up and down arrows that I can use to move a line or two at a time, which makes scrolling through very long documents a pain if I only want to move a line or two and don’t have my mouse plugged in)
What’s the “right way” to implement a state machine?
Any sufficiently complicated software with enough developers will rely on solving KSAT in polynomial time.
Reasononing
Dependencies will result in boolean in equalities defining the domain of stability of the software based on the constraint.
Software version X = (python2.7 . ( 0.91 < matplotlib < 1) || ( ( ( 3.2 <= py3 = 1 ) + …
This can be develop in a set of independent equations and some terms influence others by the game of lib availability (coupling).
KSAT is NP and hard to code already with.
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
Solving arbitrarily this equation by adding more dependencies just does not scale. And most developers lack the formal knowledge to lay down these equations and recognize the class of problem it belongs to.
Other caveat : confusing exact vs precise. (fixed point with control of errors vs floats without control (IEEE754)).
It is the art of numerical analysis that seems to be puzzling 90% of developers.
Any sufficiently complicated machine learning library will have at least two poorly implemented logistic regression classifiers.
Any sufficiently large concurrent memory allocator will contain a half implemented garbage collector for the allocation metadata.
Any sufficiently deep processor pipeline will contain an in-order, scalar microprocessor (viz. Sutherland’s Wheel of Innovation)
Rule engines – often designed by many companies for variety of reasons ending up with multiple same old problems.
Query builders for making database queries are frequently reinvented, though I think they lack (2) in your list of attributes.
Query builders are an obvious idea (since database query languages like SQL tend to be pretty verbose and inflexible), they’re *extremely* difficult to implement in a correct and secure manner (even major frameworks like Rails have had significant bugs come up in their implementations), but they’re also widely known. I think they reasons they keep getting reinvented are:
(a) The existing implementations are less flexible than SQL, so for performance or expressiveness reasons, programmers start using raw SQL strings.
(b) They’re frequently bundled with other functionality, so many web frameworks or ORMs implement a database interface and associated query builder.
(c) They don’t *look* as hard as they *are*. (This is basically your (3) restated.) Interpolating an input (possibly a buggily escaped input) into a SQL string looks like correct code, but you should be parameterizing inputs, not escaping/interpolating them. The underlying logic of databases *looks* like classical predicate logic, but it’s actually nullary predicate logic, which has significantly different semantics. Database backends *look* like they implement SQL the same way, but they don’t quite, etc. It’s easy to get something that works on your examples in your database backend, but it won’t be secure, and won’t be correct.
In this case (3) is so strong that people keep reinventing them because they think they can do better.
In (a), it starts out easy: plop a string into your code using all the SQL goodies you want (CTEs, window functions, complex joins, etc.), and you’ve shipped your code. But then requirements change (new input and predicate types, applying the same thing to different tables), and you need to start adding more and more features, until you have an ad hoc, informally-specified, bug-ridden, insecure implementation of half of a query builder. This is why there are so many SQL injection vulnerabilities, despite technology to completely prevent them having existed for decades.