The Law of Leaky Abstractions (2002)

For example, after discussing the subject of promises (in the sense of the tool to manage and abstract asynchronous program flow) with a colleague, it occurred to me that the reason we care about async behaviour is that a "function call" is a leaky abstraction, in that it takes a variable amount of time.

We think of a function call as "doing X, Y and Z". The fact that it takes time to do it, blocking our 'thread of execution' causes us the problem that we can solve with the overhead of async programming (or threading, or...)

(By 'function call' I'm glossing over system call, library call, embedded cpu-eating loop.)

From this perspective, you can see that an alternative to working around the leak is plugging (some of) the leaks - which is the approach golang takes, by shuffling around threads of execution to avoid them being stalled by blocking system calls.

That perspective is useful to me and helps me understand why I think I prefer the golang approach, "more robust abstraction".

An abstraction in mathematics is a simple, small idea that we use to describe and understand a large variety of objects. For example the concept of an algebraic group is an abstraction that can be applied to numbers, functions, matrices, etc. We can understand all these objects using the same concept.

Are all words this way? Take the word "orange". Are all oranges the same? They all have variations in taste, texture, color, etc. They are all physically separate objects. But we use the same idea to understand and describe them. Maybe this is more clearly seen with the word "fruit".

This applies to verbs too - think of the verb "to run". Usain Bolt runs in a very different way from normal people, but we use the same concept to understand what they do.

These abstractions "leak", i.e. cause confusion when the underlying reality doesn't match up. Is a tomato a fruit? If I trained as an Olympic sprinter would I have to abandon misconceptions about how to move my body, misconceptions caused by a lifetime of using the word "run"?

Is every word an abstraction?

I've seen a single-platform JVM bug. once. The only definite OS failure I've ever seen was bad RAM, and you could write a bootable program that ran without an OS and that wouldn't protect you from bad RAM. I've seen one CPU flaw, and linux abstracted over it seamlessly. I've never seen a failure that was the result of analogue chip behaviour. There are plenty of non-leaky abstractions around.

I think most of his abstractions are not leaky, but they come at the cost of poor performance in certain cases.

In any case, his point is correct: it's hard to use complex systems to implement a simple interface, because it's hard to create the glue code so that the simple interface drives the implementation in the "right" way in every circumstance.

There is, of course, another approach that the author didn't mention, which is providing a mechanism in the interface for "hints", e.g. "please store this matrix in column-major format". That is not a perfect solution, but it is another tool for better abstractions.

    > All non-trivial abstractions, to some degree, are leaky.

I've been thinking about different philosophies behind abstraction for a while. My ideas are a little unformed, but I think they're still useful. Basically, as I see it, there are two different ways to define abstractions.

There's the usual way: you come up with a new notion that has additional capabilities. The abstraction adds to the underlying concept. Perhaps it also hides some detail, but the main action is adding. Some of the leaky abstractions from the post really fit this: TCP, for example, adds new capabilities and behavior over the underlying protocol; C++ strings add a bunch of string-specific capabilities over char arrays; NFS adds filesystem capabilities to a network connection.

These abstractions are largely "leaky" because what they add does not always map nicely to what's underneath. They're also interesting because each abstraction only fits one thing--TCP is just for network communication, C++ strings are just text in char arrays and so on. Ultimately, all these abstractions are just more structure over whatever they're based on. Again, the key idea is adding.

The other sort of abstraction is what I think of as "algebraic" or "Haskelly". Instead of adding, these abstractions take away. They expose some feature of the underlying concept and throw everything else away. A monoid, for example, just exposes an associative operation from whatever set (or type) it's defined over. It can't really be "leaky" (at least in the same way) because it's showing what's already there. The normal sort of abstraction is like a structure built on top of a foundation; this sort of abstraction is like a lens or a view into a property of its foundation.

A very important result is that these abstractions are very independent of any basis or use-case. Monoids come up everywhere. Strings form a monoid. Numbers form a monoid (in many different ways, even!). Booleans form a monoid. Certain classes of functions form monoids. Note how I said "form": even if we ignored it, the monoidal structure would still be there. Talking about these things as monoids doesn't add anything but just highlights something already present.

Instead of adding capabilities to the underlying object, this sort of abstraction instead exposes structure shared by otherwise distinct objects. Monoids represent things you can combine; groups represent things that are somehow symmetric; rings represent things that are sort of like numbers; fields represent things that are really quite a bit like numbers; F-algebras represent things that are like any of the other abstractions I've listed (meta-abstraction!); functors represent things that can be transformed while preserving structure and so on.

These abstractions also let us talk about different things uniformly and generically. We can reason about and write code against these abstractions without worrying about any particular underlying object. By doing this, nothing but the abstracted structure can do anything--details of any given thing can't leak through because we have to be generically compatible with every instance of the abstraction.

Functors are a great example of this. If we wrote code using lists, we could do all sorts of things: always return an empty list, add elements to the end, drop elements from the front, change the order... If we wrote a code just using a functor, it would still work for lists but all we'd be able to do is map a function over the elements. Nothing else. Always returning an empty lists wouldn't even be a meaningful construct! Clearly, using this abstraction has taken away our capabilities, but it turns out this is often a good thing.

But this is where "non-trivial" comes to bite us. Are any of the abstractions I listed actually "non-trivial"? I'm not sure I could claim that. To be generally applicable, all of them have as little structure as possible. Ideally, you want to limit your capabilities as much as possible to express whatever you care about. This usually means limiting them a lot. All of the things I listed can be expressed as a handful of functions and a handful of algebraic laws--a few lines of description is enough to understand them completely. They are nowhere close to something like TCP!

Ultimately, I am not even sure it really makes sense to compare the two sorts of abstractions. But they are certainly both approaches to abstracting, albeit in different ways. It's something that's worth thinking about the next time you have to design or use an abstraction yourself.

http://ttic.uchicago.edu/~dreyer/course/papers/wadler.pdf

Every programmer or computer scientist should read that paper. Wadler is clear enough that even without knowing typed lambda calculus, you can understand his point.