Effective expressiveness

I keep reaching for a term that I have nowhere to link to, so I decided to write this note.

Nearly every general-purpose programming language is Turing complete. In terms of raw computational power, x86 assembly, C, JavaScript, Prolog, Haskell, and even Microsoft Excel are equivalent: each can express any computable function. If you only care about what a language can do, they’re all the same.

How it feels to use these languages is a different story. Each one makes some things easy and other things painful. Each gives you a different way to think about a problem, and some of those ways fit a given class of problems far better than others. Alan Perlis called this the Turing tarpit, “in which everything is possible but nothing of interest is easy.” Computational power tells you almost nothing about what a language is good for.

Programming language researchers have a better term for talking about this sort of thing. In his paper “On the Expressive Power of Programming Languages”, Matthias Felleisen proposes that [warning: I’m loosely paraphrasing here!] a feature adds expressive power to a language if removing it would force a global rewrite of your program (rather than a local one). First-class continuations are more expressive than plain procedure calls because you can’t eliminate them without restructuring the whole program. That’s a step toward what I mean. But it’s still about what can be expressed, not about how it feels to express it.

What I care about is the effective expressiveness of a language: how naturally it lets a programmer express solutions to a particular kind of problem, in practice.

Take an expert system, for instance. I could write one in C. But Prolog has rules, queries, and backtracking built in, so I’d have a much easier time there. I could of course “just” write a library that introduces these abstractions in C as an embedded DSL, getting fancy with macros and everything. But that’s a lot of work, and the result still wouldn’t be as nice to use as Prolog. The gap between “possible with enough effort” and “natural” is what I’m talking about.

So here’s my working definition. The effective expressiveness of a language is the answer to the following question: what kinds of problems make me want to reach for it?

Of course this depends on who’s asking, what they already know, and what they’re trying to build. “Expressiveness” in the formal sense is a property of just the language. Effective expressiveness is a property of a language and a problem and a programmer.

This matters a whole lot, because effective expressiveness doesn’t just shape how you solve a problem. It influences which problems you actually bother to work on! Every programmer carries around a rough sense of what’s worth the effort in a given language, and so much of what gets built (or doesn’t!) comes down to where we draw that line.