Indirection Mechanisms and Expressive Power

February 04, 2012

What defines a language's expressive power?

Expressive power is hard to pin down in programming languages. In this post, I want to explore how indirection mechanisms lend expressiveness to a language. By indirection, I mean something that happens at compile time or run time which was not explicitly specified in the code. By mechanism, I mean something with well-defined, rule-governed semantics.

Indirection mechanisms are typically what makes a program shorter, easier to write, and easier to reason about. Instead of writing machine code directly, you are relying on the compiler or runtime to do the heavy lifting.

I posit that the development of indirection mechanisms closely follows the development of multiplicative expressive power. One line of Python is worth far more than 100 lines of C and more than 1000 lines of Assembly. And rather than debate about expressive power in different languages, I'd like to simply catalog some of the more obvious and important indirection mechanisms out there.

While many languages might share a given indirection mechanism, I don't know all languages, so I am just going to go with my personal experience and group them roughly by programming languages I am familiar with. I would love to hear of more mechanisms, if you know of them.


Depending on the features available, Assembly can be seen as simply a more convenient language to write in than machine language. But this convenience comes from a indirection.


C has many indirection mechanisms. Most of them were not invented in C. However, from a historical and pedagogical perspective, C is a good contrast to Assembly. Both are relatively low-level and ubiquitous, yet C is a huge leap beyond Assembly in terms of indirection.


Lisp's main evaluation semantic is the source of much veneration and arguably is the Ur indirection mechanism. I am talking about the eval function as defined in the original Lisp paper by McCarthy. There are more mechanism, but they are too many to list here.


Smalltalk defined object-oriented programming as we know it today, based on a simple indirection mechanism: message passing. It also was the first language (that I know of) to make significant use of development tools. Like Lisp, I cannot list all of the indirection mechanisms in Smalltalk. They are too numerous.


Self is a prototype based object-oriented language.



Clojure also deserves a mention for its championing of various mechanisms for controlling concurrent state.

Indirection mechanisms are semantic abstractions afforded by the language. Like all abstractions, they are prone to leakage. How a language deals with the leaks might be just as important a choice as which mechanisms the language supports. For instance, what happens when you pass an object a message it doesn't understand? Some common options include: compiler error, thrown exception, silent failure, magic, or undefined behavior. These are damage control at best.

A lot of the leakiness of abstractions has to do with how mechanical the indirection is, and how simple the rules of the mechanism are. A complex mechanism is hard to understand, while a non-deterministic mechanism will sometimes give unwanted behavior. And when things go wrong, it is hard to distinguish between complexity and non-determinism. We should therefore strive for simple, deterministic abstractions. And we should also strive to bake the failure into the model, and build systems to deal with abstraction failures upfront.

I want to complete this list and keep it updated. Please if you have other ideas for indirection mechanisms and I'll add them here and credit them to you!

To conclude: Different languages make different choices of which mechanisms to provide, and hence the endless variety of languages we see today. It is my hope that we will find more such abstractions which allow programmers to be even more productive in the future. Further, perhaps there are ways to make existing mechanisms more robust and which fail in more appropriate ways.