The Tale of Two Abstractions

Observing the software industry for a few decades from the inside is both depressing and instructive: what never ceases to astonish is how little actual progress is made by the efforts of huge numbers of really smart and talented people.  Especially jarring is the contrast with the progress in hardware: most people now carry small devices which have more computing power than supercomputers of 1980s  (and an array of sensors, an impressively detailed and bright display, and always-on radio data connection with more bandwidth than trunk links of biggest Internet backbones of mid-1990s). But the software which runs on it is seriously unimpressive.  In fact, compared with the feats of software engineering of 1970s - like landing on the Moon under guidance of 16-bit 1MHz computer with 19 instructions and 4KiB of magnetic core RAM - or designing software for Air Traffic Control which is still running the critical infrastructure on computers so old that finding parts for repair is a huge challenge - it seems that we've got a serious case of regression.  It's not really a regression in skills, just an effect of being able to get away with crappy software design because hardware is so powerful and reliable - and result of our inability to cope with ever-increasing complexity.

Complexity is Νέμεσις.  It's programmer's enemy № 1.  Human ability to deal with complexity is quite limited, both in terms of ability to understand non-spatial structures (an attempt to mentally visualize simple tesseract (not a projection, but the tesseract as it is, with equal-length straight edges and 90° angles) is going to be futile) - leave alone structures without any notion of continuous space such as computer programs - and in terms of very limited short-term/active memory (4±1 units). Meanwhile, software is the most complex of all human artifacts, by far.  How do we manage to build it at all?

The key to creating large and complex systems is abstraction: when we can think of a complex system as containing blocks which may be complex inside, but which perform conceptually simple functions and have relatively simple interfaces, we can focus our limited attention and memory on the currently relevant block at the abstraction level we're working at.  Splitting the design into blocks also allows to divide the labor of designing these blocks among many people.  This is daily bread for a software architect.  The principles of good software architecture are well understood (though often ignored), but the real issue is the gap.

Architecture is informal and somewhat nebulous (and when trying to steer system design towards sounder architecture the author of this post had been told to stop wasting time on philosophy by the lets-get-hacking geeks - on many occasions).  The code, however, is very specific.  This does not make architectural decisions any less consequential: it's just there's that gap between intention and implementation, and the more complex the system is, the wider is the gap.  So far attempts to close or at least reduce that gap were unsuccessful (the dismal failure of CASE is a topic worthy of separate discussion).  We just don't seem to be able to raise the level of abstraction of our programming systems to the place where intentions of a software architect could be trivially converted into a working code for any project of a meaningful size.  When creating software we are still mired in the tar pit of details.  It's as if there's an impenetrable abstraction level ceiling in our software development environments.  To understand how that ceiling came to be we'll need to re-examine our notion of abstraction.

To start with, there are two not very subtly different notions of abstraction: the first one is mathematical and another is common in engineering.  Abstraction in mathematics is, basically, stripping details of objects in order to arrive to a structure which has interesting set of algebraic properties.  The most familiar example of this is natural numbers (the set of natural numbers is usually designated as ℕ).  The notion of natural numbers abstracts away all properties of discrete natural objects (such as apples or oranges) to leave only their countability, which doesn't seem much, but gives raise to arithmetic.  The arithmetic is very useful in practice, its power coming from the ability to use the results of abstract calculations to predict results of manipulating any countable objects. Adding one apple to three apples gives four apples.  Adding one orange to three oranges gives four oranges, etc.  Note, however, that arithmetic fails when other properties are mixed in: adding one apple to three oranges gives us neither four apples nor four oranges.  A major part of mathematical reasoning is figuring out when a specific abstraction is applicable, and when it no longer gives meaningful answers.

The engineering abstraction is also about stripping details, but it aims to facilitate approximate, imprecise reasoning about larger blocks of the system.  It's a cognitive aid, not a search for algebraic structures.  No engineer ever believes that details are irrelevant, it's just that he chooses to defer thinking about them in order to avoid being cognitively overwhelmed by the complexity.

All software objects are engineering abstractions, they run on physical computers (rather than mathematical abstractions like Turing machine), and because of physical laws (such as the limit on the speed of light) they have physical properties, too: the real programs take time to execute, the side effects of their execution is release of heat (for both technological and fundamental reasons), they always have non-zero error and failure rates, etc, etc, etc.  These physical properties combine to create properties of higher-level software objects, and those are not trivial.

These abstracted-out properties are not inconsequential, the problem first described by Prof. Gregor Kiczales, and then formulated by Joel Spolsky as the Law of Leaky Abstractions: All non-trivial abstractions, to some degree, are leaky.  Spolsky seems to consider the leakiness to be the emergent property of complex software.  It is not:  it is the inescapable consequence of the nature of engineering abstractions. The very same phenomenon is found in every engineering discipline, although it is much less pronounced (but we still have to test designs of all complex machinery to detect overlooked "reality leaks").

The only reason this law comes as a surprise to software engineers is because they (and the practitioners of the discipline of Computer Science in general) tend to think of software in terms of mathematical objects, thus conflating two very different notions of abstraction.  This confusion exists at the very core of how we write programs: the mathematical idea of abstraction is fundamental to all existing programming languages.

The law of leaky abstractions also has a non-trivial consequence: imagine that we're building software running directly on a physical computer.  We have a pretty good idea of how it works, and thus we can select algorithms and data structures to make our program efficient on this computer.  Now, let's abstract common operations such as reading and writing disk blocks, adding some cache and a file system on top.  Now the application programmer can use these more abstract operations (instead of figuring our specifics of a particular disk controller) - but we also introduced new non-trivial details (cache behavior, file fragmentation, etc).  Then we write a database - which by necessity will be aware of these details.  And then one nice day we get a shiny new SSD - which, while offering the same "abstract" I/O, has radically different performance characteristics (and wants to be explicitly told when information is no longer needed, aka trim command).   Some database queries are much faster, some are just as slow as they were before.  We can not just blindly put more load on the application just because we made storage faster.  Instead, we have a huge amount of work to adapt the whole stack to make advantage of the new technology.  It may actually be simpler to rewrite everything from scratch.  Here comes the new "framework" doing pretty much the same work as the old one, but quite different, so all users now need to rewrite their applications.

The problem with abstraction leaks is that they are kept within the mind of a programmer: there is no way to write code which would adapt to the changing leaks.  Pile more layers on top, and the whole becomes intractably rigid, unable to cope with changes in a reasonable manner.

This phenomenon of specific "values" of abstraction leaks being baked into successive layers of software is the reason why we can't work up to high abstraction levels.  And we have to bake in these values when we write software because there's no way to express or handle the leaks explicitly (that's why they are "leaks").  Let's call it the Law of Abstraction Level Ceiling:

Abstraction leaks create abstraction level ceiling.

The situation looks fairly hopeless... we need engineering abstractions to cope with cognitive overload, and this results in the upper limit on the abstraction level at which we could program.
Fortunately there is an escape:  the whole mess with leaky abstractions is created by the use of the mathematical concepts which are inappropriate for dealing with engineering abstractions precisely because they were developed for dealing with ideal abstract machines.  The physical reality of engineering abstractions seems to be also amenable to mathematical description - it's just the description matching the reality may not be the same as the nice theory we have in our minds. Planets are not moving in perfect circles, but the real law governing their motion is not that complicated either, and in vast majority of cases we could get by with astonishingly simple approximation.

What exactly we got wrong half of the century ago, and what can we do about it will be the subject of further discussion in our future posts concerning spherical bovines in evacuated spaces.