Shriram Krishnamurthi
Brown University
On the Expressive Power of Programming Languages
Papers are like poems. Some are dazzling, some are pedestrian, some are insightful, and some reward long periods of quiet contemplation. They stir up an emotional reaction that goes beyond the strictly rational, and can often be deeply personal.
In graduate school, during a period of identity crisis, I came across Matthias Felleisen's “On the Expressive Power of Programming Languages”. At a time when the world was ruled by C++, I had immersed myself in Scheme, so I always looked skeptically at mainstream linguistic claims. However, the language wars seemed beyond rational discourse. So the idea that someone could take a concept as nebulous as “expressiveness&rdquo and formalize it was already a revelation. But the beauty of this paper goes well beyond that: it also lies in the cleanliness of the approach, the correspondence of the formalism to intuition, and the tautness of its execution.
It was the most stunning paper I had ever read, and remains so. It's like the poem that never leaves your soul.
Unfortunately, this paper may not be easy to read for the uninitiated: it depends on a certain amount of “cultural knowledge” of programming language theory. I hope to peel off some of those layers and help you, too, understand the paper — hopefully while preserving the joy and beauty I experienced.
Shriram is the Vice President for Programming Languages at Brown University in Providence, RI, USA. He’s not, really, but that’s what it says on his business card. At heart, he's a person of ill-repute: a Schemer, Racketeer, and Pyreteer. He believes tropical fruit are superior to all other kinds. He is terrified of success, because he may be forced to buy a suit. He is known to interrogate his audiences to ensure they’re paying attention. So, be alert. You can read email later.