Denotational vs operational

It's time to retire the imperative vs declarative dichotomy

It’s time again for the annual State of Clojure Survey. I fill it out every year. And I love to read the responses. Please give the survey 15 minutes and become a statistic. This is one important way we, as a community, understand ourselves. Please fill it out by the end of the year.

---

Denotational vs operational

I follow a number of people’s work, and one of them is Conal Elliott. I like that he’s very deliberate with his use of words. It makes me think a little harder. At some point, I heard him say that he didn’t think declarative was the right word. People tend to toss the word around and explain it as “saying what you want, not how to get it.” It’s the opposite of imperative, where you say how to get it. But Elliot is right. It’s not the word we want.

Like many problematic words, people use it in different senses. But the worst offense is that it’s not objective. It’s vibes. It’s relative. I’ve heard people say that map is declarative while a for loop is imperative. “With map, I just say what I want. But with a for loop, I have to say how to build the resulting array.” That may be true, but a for loop is very declarative relative to an if statement and a goto. Look at the anatomy of a for loop. You specify four things:

1. Initialization

2. Loop condition

3. Loop progress

4. Body of loop

And it magically executes the body of the loop until the loop condition is met. How does it do it? You never specified how. Which means it’s declarative. And I’ve implemented map many times over the years. I know how it’s working its wizardry. Which means it’s imperative.

These words just are not what we’re looking for. The main problem I have with the term declarative as we use it is that it’s all about ignorance. People say SQL is declarative because they don’t know how the query engine works. Once you learn how it works, you begin to write SQL to control how it runs.

Elliot suggests we instead use the term denotational, borrowed from the practice of Denotational Semantics. Denotational Semantics is a method for formally specifying the semantics of a programming language or construct in terms of lambda calculus. It contrasts with Operational Semantics, which is more like how a compiler might translate a language to machine code. If you squint, we want to replace declarative with denotational and replace imperative with operational.

In denotational programming, we specify how to derive the meaning of one expression by combining the meanings of the subexpressions. Even if we know what’s happening under the hood, the derivation of meaning is clear. Reasoning can be done locally. In operational semantics, we may get a good idea of how a feature can be implemented in assembly, but we have trouble simulating it in our head because of the many possible states the machine can be in. It is much harder to formalize and prove properties about it.

When we’re doing good functional programming, it’s much more on the denotational side. We’re defining one function in terms of other functions. We’re embedded in a lambda calculus, so it’s very comfortable to do.

I think there’s another correspondence, which is between operational/denotational and implementation/specification. I think one of the important skills that differentiates of senior from a junior engineer is the ability to separate implementation from specification. A junior is just trying to get something working. But a senior engineer thinks about the meanings they want to represent apart from how to represent them.

This brings me to the working title of my book, Runnable Specifications. The idea is one I borrowed from Alan Kay. He says the ultimate goal for a programming system is to be able to run the specification, not translate it into an implementation. You want to write down a question and run it to get the answer. He’s talking about a denotational way of programming where you write programs directly in the language of the domain.

Denotational differs from declarative in one other way. Denotational programming deals with how meanings are combined to form new meanings. Declarative can but often does not deal with combining meanings. I look at SQL again as an example of something that doesn’t make composition easy.

Well, I don’t think I really destroyed the term declarative as much I imagined I would at the beginning of this essay. That’s okay. I think denotational is a strong enough replacement that it doesn’t really need to be destroyed. The biggest downside to the word is that people don’t know what it means. But I do!