Software Calculus - The Missing Abstraction
Posted by Uncle Bob on Monday, July 05, 2010
The problem of infinity plagued mathematicians for millennia. Consider Xeno’s paradox; the one with Achilles and the tortoise. While it was intuitively clear that Achilles would pass the Tortoise quickly, the algebra and logic of the day seemed to suggest that the Tortoise would win every race given a head start. Every timeAchilles got to where the tortoise was, the tortoise would have moved on. The ancients had no way to see that an infinite sum could be finite.
Then came Leibnitz and everything changed. Suddenly infinity was tractable. Suddenly you could sum infinite series and write the equations that showed Achilles passing the tortoise. Suddenly a whole range of calculations that had either been impossible or intractable became trivial.
Calculus was a watershed invention for mathematics. It opened up vistas that we have yet to fully plumb. It made possible things like Newtonian mechanics, Maxwell’s equations, special and general relativity and quantum mechanics. It supports the entire framework of our modern world. We need a watershed like that for software.
If you listen to my keynote: Twenty-Five Zeros you’ll hear me go on and on about how even though software has changed a lot in form over the last fifty years, it has changed little in substance. Software is still the organization of sequence, selection, and iteration.
For fifty years we have been inventing new languages, notations, and formulations to manage Sequence, Selection, and Iteration (SSI). Structured Programming is simply a way to organize SSI. Objects are another way to organize SSI. Functional is still another. Indeed, almost all of our software technologies are just different ways of organizing Sequence, Selection, and Iteration.
This is similar to Algebra in the days before calculus. We knew how to solve linear and polynomial equations. We knew how to complete squares and find roots. But in the end it was all just different ways to organize adding. That may sound simplistic, but it’s not. Subtracting is just adding in reverse. Multiplying is just adding repeatedly. Division is just multiplication in reverse. In short, Algebra is an organizational strategy for adding.
Algebra went through many different languages and notations too, just like software has. Think about Roman and Greek numerals. Think how long it took to invent the concept of zero, or the positional exponential notation we use today.
And then one day Newton saw an apple fall, and he changed the way we thoughtabout mathematics. Suddenly it wasn’t about adding anymore. Suddenly it was about infinities and differentials. Mathematical reasoning was raised to a new order of abstraction.
Where is that apple for software (pun intended). Where is the Newton or Leibnitz that will transform everything about the way we think about software. Where is that long-sought new level of abstraction?
For awhile we thought it would be MDA. Bzzzzt, wrong. We thought it would be logic programming like prolog1. Bzzzt. We thought it would be database scripts and 4GLs. Bzzzt. None of those did it. None of those can do it. They are still just various ways of organizing sequence, selection, and iteration.
Some people have set their sights on quantum computing. While I’ll grant you that computations with bits that can be both states simultaneously is interesting, in the end I think this is just another hardware trick to increase throughput as opposed to a whole new way to think about software.
This software transformation, whatever it is, is coming. It must come; because we simply cannot keep piling complexity upon complexity. We need some new organizing principle that revamps the very foundations of the way we think about software and opens up vistas that will take us into the 22nd century.
1 Prolog comes closest to being something more than a simple reorganization of sequence, selection, and iteration. At first look logic programming seems very different. In the end, however, an algorithm expressed in prolog can be translated into any of the other languages, demonstrating the eventual equivalence.
Comments
matt parker 6 minutes later:
agreed… though how much can the languages change if the underlying hardware is a calculator?
Cachiom 19 minutes later:
Agreed, but you have to consider that:
“Practical mathematics has been a human activity for as far back as written records exist” (accordingly to wikipedia about math). So it took time for Newton to come out with calculus. Considering software is a relatively new way to solve contemporary problems, it’ll probably take time for this watershed. Hope I’m wrong.
denstar 37 minutes later:
Um… I don’t think that was quite the point of that paradox. We haven’t exactly “solved” it, either. It’s a logical deal…
I think the Arrow in flight paradox is a fun take:
* The Arrow Paradox
Zeno’s arrow paradox appears to show that motion is impossible.
It works by taking a snapshot of an arrow at a point (either in space or in time) in its flight. At that point, and at every other, the arrow is motionless. If there is no point, spatially or temporally, at which the arrow is moving, though, then the arrow is motionless. Contrary to appearances, an arrow in flight cannot move.
*
Contrary to appearances (apparently) I think we’ve been evolving /constantly/.
From “inside” it may seem like not much is changing, but holy cow, how things have changed!
And seem to be changing faster, but maybe that’s an illusion. ;)
Mike Wilson about 1 hour later:
While it’s an exciting and hopeful notion, I have to ask:
Why is it inevitable? Why MUST it be coming?
It sounds delightful and I’d love to be around to see it. But aside from frustration with working on projects measured in ‘mlocs’ instead of ‘klocs’ I don’t see ‘us’ pushing towards a strata change of that nature.
denstar about 1 hour later:
I don’t think it’s just “one” thing. I think it’s a combination of a lot of ideas, that are constantly refined and combined with other ideas.
To look for that “one” change is to look at the one moment in time and to see motion (the arrow ref).
Or something like that.
Keith about 1 hour later:
I don’t think such a mythical beast exists in the way you present it.
What we are involved in is a rich branch of discrete mathematics that allows many kinds of abstractions already. We will learn more about the capabilities by solving some of the unsolved problems like P=NP. However the overall nature is not really going to change. I don’t think there is a magical abstraction thats going to be any more magic than the kinds of abstractions we have already created, and quite likely, keep creating.
However the kinds of “programming” we may be able to do with genetic materials might create the magic you are wanting? But it will be an entirely different beast. Or possibly at a quantum level we may find and entirely different beast also, where we break out of the branch of mathematics we are in.
Asling about 2 hours later:
The problem lies with the programming community. It is dealing with a static set of rules that work. As humans we take the easy or known way to solve problems every time. Fable: a society wants to experience the most amazing music ever made so they take the child of talented musicians as a baby and allow him to grow up, surrounded by musical instruments as toys but never allowing him to hear another’s work or have a teacher teach him how to play the instruments. The society enjoyed wonderful, inventive music for as long as the child remained pure. But on the day he heard another musicians music, he began to mimic and his music lost it’s charm.
You want to change programming? – lose the rules.
munch about 2 hours later:
“You want to change programming?—lose the rules.”
We Forth programmers have been trying to tell you that since the 60s. You keep laughing at us. Now that you thought up this hip little sound-bite, you think it’s cool all of a sudden? I don’t know if I should be flattered that you’re finally coming around or deeply offended for taking what’s rightfully our position in the programming community as your own while concurrently maintaining Forth’s unsuitability as a genuine programming tool.
Seriously, though . . .
The problem isn’t with the software or the language used to write it. The problem is with the equipment we’re given in the best case, and just plainreality in the worst. Von Neumann and Harvard architectures, and indeed pretty much anything based on Church or lambda expressions like data-flow engines and the like, absolutely will suffer from the very conceptual bottlenecks Uncle Bob speaks of.
They operate according to a finite vocabulary, the words of which programming languages are intended to combine in useful ways. You can only express that which is expressable in the most basic of forms.
Since no machine language, data flow or otherwise, can process an infinite amount of data in infinitesimally small amounts of time, you’re just plain going to have to deal with sequential behavior. Period.
(And, even if such hardware DID exist, Amdahl’s Law will limit how much you can apply this new-fangled hardware anyway.)
And if we agree that sequential execution and notation is inherent in the design (notice that my words are laid out sequentially, and that I can communicate only one thought at a time), it follows directly that iteration will just have to do as a substitute for operating on collections of things. The fact that it takes you time to read my paragraphs (that is, to iterate over them) one after another is proof enough that iteration will always be with us.
And, one of the problems facing quantum computing now is precisely the problem of selection. How DO you make a general purpose quantum computer without it? You have two ways: you either program it (e.g., you “select” what it can do at any given time), or you have it evaluate the entirety of all solutions to all problems, and you somehow “select” the one you want. In either case, you’re dealing with selection. Iteration requires selection to control the scope of the domain of items you’re working with, and selection is required for sequential execution so you don’t execute the wrong instructions.
We should not be looking for ways to avoid SSI. We should be looking for ways to embrace it to our advantage, to recognize that writing programs == discrete math, NOT analysis.
The only way to work around SSI is to rely on computers where programs != discrete math, which basically implies analog computing. But, again, how do you make a general purpose analog computer without selection?
MeBigFatGuy about 2 hours later:
I would think that step would be synaptic programming, where solutions are ‘programmatically’ stumbled upon through trial and error, through applying the collective intelligence of what has come before through associations to what is trying to be solved now.
When programs act like minds then we may have something new.
anon about 3 hours later:
We already have the missing abstraction. SICP refers to it as metalinguistic abstraction. The reason that we haven’t noticed it yet is that computer science (unlike mathematics) is governed by those who are popular, not those who are rigorous.
pathsny@gmail.com about 5 hours later:
I didn’t quite follow the last bit about prolog. As long as it is software that will execute on today’s hardware, it will be expressible as SSI. Isn’t the challenge not to write software thats inexpressible as purely SSI but to not be bound to just SSI.
While conceptualizing the solution to a problem or describing our solution, we would like a richer vocabulary. But it should not dismay us that this can be re-expressed as merely SSI, perhaps at the cost of being longer or harder to understand.
L. about 6 hours later:
We could change the way we think about software and hardware, indeed. Studies have shown that symmetrical ternary computer hardware (as opposed to our binary stuff) implements addition and substraction in much simpler ways. Some ternary marchines exist buried deep down russian university labs. I’m giving this as an example, as well as I could have talked about q-computers.
For now, we have to accomodate everything that’s already existing, be it hardware, software, or knowledge accumulated on our binary way of thinking.
When we are programming a solution to a problem in a given language on a given target platform, nowadays, what we are looking for is not only a result, but a result that can be achieved in a predictably finite amount of time. SSI gives predictability, as the resulting mathematical state is a direct function of the input mathematical state that can be reached in a really short amount of time.
There are sound mathematical models that exist to embrace the complexity of SSI programs, with practical results. You may want to look up Pr. Martin Ward’s WSL and Fermat engine for expressing and performing program transforms. This mathematical model has incredibly few kernel constructs (7, counting atoms and composition), and everything is layered on top of it in a proven manner. These constructs are a radical shift from mainstream thought, as two of them are unimplementable on their own. (“guards”, that remove ambiguities in previous statements, and “undeterministic branching” that states that at some point in the program, two branches may be the “next part”) This language enables one to prove correctness of program transforms. Yet, the model resorts to first-order infinitary logic to express loop weakest preconditions, and is unable to perform automatic proof for anything that involves loop. All proofs still have to be made by humans.
My point with the previous paragraph is: SSI is already expressable as mathematics, with rather simple/puny/lousy mathematical tools compared to what’s available. The problem would be, instead of simply thinking in terms of sequence, to reintroduce mathematics into computer programs.
Eiffel does this with the specific purpose of expressing contracts. The C++ committee wants to be able to express program transforms through “concepts” and “axioms”, expressing mathematical knowledge into rewrite rules for the compiler. On the opposite, “Lambdas” (sic) have been introduced into the C# language, yet they are merely syntactically sweetened anonymous functions that are not first-order citizens, with nothing fundamentally mathematical about them.
It’s true, I’d like to be able to express mathematical truths about a chess board and have a bug-free chess program that is able to tell me the possible moves in a given position, and to fold the alpha-beta tree just by reasoning. All this, in a predictably finite amount of time. Not possible yet, and I doubt it will in any close future.
anonyjoe about 7 hours later:
I nominate javascript method chaining as the missing abstraction. jquery & nodejs mean even a syntax-leery designer like me can code both client & server. oh, and it seems to perform pretty well as a bonus.
Paul Johnson about 7 hours later:
I think you need to re-evaluate functional programming, and especially some of the stuff going on in the outer reaches of Haskell. Type-directed programming and Functional Reactive Programming (FRP) spring to mind as paradigms that are not just about sequencing, selection and iteration.
Also, think about what a 17th century shipwright would have said about differential calculus.
PaulB about 8 hours later:
A very interesting article, however the more interesting thing will be the leap that takes us forward.
As a mathematics graduate, I remember back in school first being shown calculus and seeing it as merely a solution to a particular problem – namely how to find the slope of a graph of a non-linear function. Similarly the leap forward here may not be some grand new software design but something that may in fact be a solution to a particular problem.
For example, let us take neural networks. They are currently something used to solve particular problems where non-standard algorithms take a long time. Granted they are a lot more than this but one of their primary solutions at the moment is to identify patterns that emerge. If a neural network could be built that was more generally adaptive however and followed a more natural way of working as a neural system then it could be taught to do a lot of the jobs which are often performed by standard software as algorithms (if we have this type of setup then do this else do this and then for each on of these objects do this etc.)
Reminds me of a talk a recently viewed by Douglas Crockfordhttp://fr.video.yahoo.com/watch/529579/2724346
Jason Y about 11 hours later:
I’m not sure what the OP is asking for. If Prolog is not “something more than a simple reorganization of sequence, selection, and iteration” because “an algorithm expressed in prolog can be translated into any of the other languages, demonstrating the eventual equivalence,” then I think all of mathematics is just a reorganization of SSI as well, because it can be translated into Prolog or C# or some other language. Indeed, much of it has been translated to a computer language.
Underlying computer hardware runs sequence, jump, and unconditional jump. If you want to get away from selection and iteration, you could just use goto’s. Then you’re “simplifying” the language with which you express programs. But you’re giving up a higher level of abstraction that, though more complex in itself, simplifies the process of actually getting a program right.
We have many other, elegant abstractions that are simple in themselves, powerfully expressive for a variety of purposes, and help us get our programs right. Major examples include true functions, structures (SSI), and method and type abstractions. I think these effectively do the job of calculus in math. In a few areas, we could certainly use some more things like these, and we need these, but I expect that no single one will be what calculus is for math.
Psi about 11 hours later:
I don’t think it’s logical at all to hope for some unspecified, unknown, unheard of advance in software that will change everything, not even knowing if such a thing could exist. The whole thing sounds kind of messianic to me, and I would point out that this is supposed to be a science, not a religion. We should not spend long days hoping for liberation from the limitations of our medium. If we think that we have some new idea for software, that’s great. Let’s build on it. If not, I think our only recourse is to try to overcome these limitations within the current paradigm. I am not at the point where I think that that is unreasonable.
zvolkov about 12 hours later:
Uncle Bob, did you forget Dijkstra’s Philosopher Stone?http://userweb.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD898.html
Shayne about 15 hours later:
If this revolutionary concept came, would you recognize it?
Konrad Garus about 17 hours later:
Well, programming is about solving problems. When you as a human recognize a solution (in real life as well), you think of it in algorithmic terms. Do this, then do that, and if this happens do that. All about SSI.
The only alternative would be software finding the solution for you. It’s hard to think of a reasonable possibility in this direction…
Max Guernsey, III about 18 hours later:
It’s a little more incremental than you are making it out to be. You are right that it was all just ways of organizing abstracting adding and testing up until calculus. I would argue that calculus itself is just another increment of abstraction built atop all of the other discoveries that preceded it and ultimately trickling down to the notion of adding and testing.
What distinguishes calculus from earlier attempts at math was not that it is somehow different, merely that it is better at solving certain problems. In other words: it was a small discovery with a big impact.
Software developers have made great strides in that front – the thought leadership in this industry has built us the tools we need to do this right. Sure. Something better will come along than the tools we have; that always happens. The real problem is education.
We are not struggling for want of abstractions. We are struggling because so few people use the really good set of tools we already have.
Keith about 21 hours later:
@Jason Y, its worth remember we approximate math on computers. Which is super useful. But has limits that the underlying math doesn’t.
Gaboto about 21 hours later:
I think good designed Object Oriented models encapsulates “Sequence, Selection, and Iteration”. I mean, a good object model should be seen as a set of different objects collaborating by sending messages. That is the metaphor that prevent us from thinking about SSI. There is not silver bullet, but good designers…
Steven Gordon about 24 hours later:
I mostly agree with Munch.
If logic programming is still considered SSI because it can be translated into SSI, then any language that can be executed on a Turing-equivalent machine is still SSI.
I suspect that software written for quantum computers could be executed on any Turing-equivalent machine, albeit more slowly and/or requiring much more memory space. Analog computing, which I know little about, would seem to be the only other possibility.
Neural nets are an interesting counter-example that could perhaps be consider an analog model if the weights were true real numbers rather than rational approximations. Would businesses really want to rely on software that has unpredictable results on novel inputs? We might be able to bound the error rate of a neural net, but I do not think we could ever guarantee an error rate of 0.
James Iry 1 day later:
Bob,
I have to say I’m perplexed by what you’re saying or asking for. Seehttp://lambda-the-ultimate.org/node/4007#comment-60751
David Broderick 1 day later:
“For fifty years we have been inventing new … ways to organize SSI.”
All all of them are stiff and inflexible. What we’re discovering is that, in the end, we need to move toward lighter, more dynamic membership in sets. If we can weigh inclusion to be expression-based, we can make the jump in abstractions we need. For example, Kayia (http://www.kayia.org).
gregor 1 day later:
Perhaps you’re looking for this? http://vpri.org/html/work/ifnct.htm
Jason Y 1 day later:
@Keith, Certainly we approximate some math (e.g. arithmetic with floats, or deciding if a given class follows or violates LSP), but other math is exact (most arithmetic, boolean logic, dependency DAG’s, eliminating side effects, etc.).
Anyway, was that what you were talking about?
David Workman 3 days later:
‘At first look logic programming seems very different. In the end, however, an algorithm expressed in prolog can be translated into any of the other languages, demonstrating the eventual equivalence’
Well, unfortunately we are working on turing machines, so no matter what abstraction we think up this will always be the case. Unless some new technology comes along that is more powerful than a turing machine in what is calculable then your new concept will always fall down at this point. Currently, this is possibly either a Quantum Computer or (if that fails to be more than a turing machine) a Quantum Gravity Computer.
However, if you relax this constraint that it not be transformable into ‘traditional’ methods then your abstraction may be along quicker (I do agree that it hasn’t arrived yet… we haven’t had a paradigm shift that changed the fundamental way we think about software and programming, just incremental improvements in how we manage complexity)
QC 3 days later:
“Some people have set their sights on quantum computing. While I’ll grant you that computations with bits that can be both states simultaneously is interesting, in the end I think this is just another hardware trick to increase throughput as opposed to a whole new way to think about software.”
I’d recommend reading up on quantum computing more, it is fundamentally different from existing (classical) computing. There are problems that can be solved with a quantum computer that you couldn’t do on a classical computer no matter how fast you made it.
Qubits (quantum bits) operate differently than classical bits. For example, measuring one qubit may impact the state of another via entanglement. Measurements are not reversible. You cannot copy the state of an arbitrary set of qubits (no-cloning) and so on. Classical programming doesn’t handle this well- hence all the work into developing new methods to program quantum computers.
Furthermore a quantum computer won’t have any increase in speed for many tasks.
Therefore quantum computing isn’t just another trick to squeeze out more speed. Additionally since it represents a whole new way of computing (bits vs qubits) it requires a new way to write software as well.
Arturo Hernandez 8 days later:
It is true that Newton had reality on his side. Computer scientists have to deal with humans.
Nevertheless I do belive that there is something fundamentally different that may revolutionize computer programming.
I have a few ideas like doing away with the current notion of state in applications. It will be radical ideas that will bring about real change.
ApostolypseNow 9 days later:
What about representing multiple threads and how the processing is allocated? The next step is creating a programming environment that can represent the code in many different forms at once using graphics concurrently with the editor. You should always be able to easily flip through the myriad of model form representations your code can take on. I have many ideas for how to do this and hopefully it will eventually allow me to retire.
Phil Markgraf 11 days later:
Perhaps I’m being a bit thick, but what problem would this new level of abstraction solve? It seems like we won’t find “Software Calculus” without first wrestling a while with our “Software Achilles and the Tortoise Paradox”.