[TYPES] Declarative vs imperative

[Will Cook]

I have been thinking about the use of the words "declarative" and "imperative" for some time. This is my understanding of how they are commonly used in computer science today:

Declarative: describing "what" is to be computed rather than "how" to compute the result/behavior

Imperative: a description of a computation that involves implicit effects, usually mutable state and input/output.

As others have pointed out, our usage originally came from the distinction between imperative and declarative statements in natural languages. However, I think that our usage has diverged significantly from this origin, so that the words no longer form a dichotomy.

For example, one might argue that a finite state machine is both declarative and imperative in the computer science senses. I think Uday made a similar suggestion. There is also Wadler's classic paper on "How to declare an imperative".

Another hint that "declarative" and "imperative" are not antonyms is that the definitions don't have any significant words in common. The antonym of "imperative" in common usage is "pure functional". I don't know of a widely-used word that acts as an antonym for "declarative", although "operational" might work. It may be that "imperative" has a connotation of "step-by-step", which hints at it being the opposite of "declarative", but this connotation is fairly weak at this point. If we wanted to we could try to force “declarative” and “imperative” to be antonyms, possibly by redefining what we mean by “imperative”, but I'm not sure that would be an improvement.

I agree with those who say that "declarative" is a spectrum. For example, some people say that Haskell is a declarative language, but I my view Haskell programs are very much about *how* to compute a result. It is true that many details about how are left out (memory management, order of operations, etc). But if you compare a Haskell program with a logical specification (pre/post conditions), they are quite different. Thus while I would say Haskell is more declarative than many other programming languages, Haskell is not a declarative language in the strongest sense of the word. Haskell programs are not specifications, they are computations, in the sense that they say how to compute and answer.

Here is a quick shot at a spectrum between "how" and "what". Each level has a quick summary of the "how" that is involved, and it also includes all the "hows" listed below them. I suspect that many of you might disagree with the placement or absence of various languages, so I cannot claim that this list is definitive.

** More "How"** 
How the machine works
   Assembly
How memory is managed
   C, C++, etc
Order of operations
   Java, Smalltalk, Python, Ruby, etc
How data flows (with issues like nontermination and cut)
   Haskell, Prolog, Lambda Calculus (in various forms)
----split between Programming and Specification Languages---
Restricted Specification Languages
   BNF, SQL, Excel, Statecharts
Logical specification languages
   VDM, Z, B, Alloy
*** More "What" ***

The idea that a specification language (by definition) cannot be executed is widely held but false. I consider BNF to be a simple counter example. BNF is clearly a specification language, and it clearly has efficient execution (parsing) strategies.

As for the objects/type distinction that sparked this discussion, I think the discussion was pretty reasonable, and I would like to thank Jonathan for presenting my views so articulately.

I agree with Uday that we need to get our own house in order. These kinds of discussions are a good start.

William


On Apr 22, 2013, at 1:15 PM, Uday S Reddy <u.s.reddy at cs.bham.ac.uk> wrote:

> [ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
> 
> Vladimir Lifschitz writes:
> 
>> The way I see it, the difference between declarative and imperative
>> programs is as clear-cut as the difference between declarative and
>> imperative sentences in natural languages: "I like it" vs. "Sit down".
>> A declarative sentence can be true or false; an imperative sentence
>> can be executed or not executed.
> 
> Indeed, "Sit down" is an imperative sentence.  "To sit down" is a noun.  "It
> is nice to sit down" is a declarative sentence.  In an imperative
> programming language, you will find all three.  So, to me, nothing is
> clear-cut about the distinctions that people make!
> 
>> A declarative program may look similar to a procedural program if they
>> use similar data structures.  Still, the difference is clear: a (truly)
>> declarative program describes what is counted as a solution; a procedural
>> program tells us which operations to perform.
> 
> Indeed, high-level programming languages that can automate a lot of the
> programming work are always brilliant.  However, I don't see what this has
> to do with the declarative-procedural spectrum.  There are high-level design
> tools using UML notations that also achieve a high degree of automation in
> program generation, and a good proportion of those notations are imperative.
> As I mentioned previously, the highest level programming systems that we
> might imagine for applications like stock-market trading systems or on-board
> flight control systems might indeed be imperative.
> 
> So, this is a false dichotomy, as far as I am concerned.
> 
> Cheers,
> Uday