Declarative versus Procedural

Appeared in Volume 7/3, August 1994

Keywords: declarative.

Torkel Franzen

In the comp.lang.prolog newsgroup, Andrew Donald Rickard wrote the following:

What I really want to know is how to think declaratively and how to think procedurally. What are the meanings of 'think declaratively' and 'think procedurally'?

A very reasonable question! I'll try to articulate some more or less commonplace answers.

There isn't any very exact meaning of "thinking declaratively", but the general idea of Prolog being declarative is clear enough. This means that a Prolog program admits a declarative reading, which is to say a reading as a conjunction of assertions. In your example:

foo(X):- bar(X), ack(X).

the standard or Horn clause reading would be "for all X, if bar(X) and ack(X) then foo(X)". That is, the clause expresses a logically sufficient condition for foo(X) to hold. The clause also admits a procedural reading, which is to say that it can be read as the instruction "to satisfy foo(X), try to satisfy first bar(X) and then ack(X)". "try" for procedures has a special meaning in Prolog as compared with procedures e.g. in C, since there may be further clauses giving other ways of satisfying foo(X), and these different ways will be tried in the order in which they appear in the program.

Now the most straightforward notion of "thinking declaratively" is this. When we write a program to decide whether or not foo(X), or to find an X such that foo(X), what we do is to write down assertions (in the form of clauses) that are true of "foo" in the intended sense, and that contain enough information for the desired answer to be a logical consequence of the clauses. We don't worry about how this answer is found, but only make sure that the clauses are "declaratively correct", i.e. true on our intended interpretation of "foo(X)".

This purely declarative thinking will not suffice, however, if we want to make actual use of Prolog. Indeed, an overemphasis on the declarative reading of clauses not infrequently results in comments from frustrated users.

He continued:

Prolog is the worst programming language because you can correctly define all the rules, but the language doesn't understand them.

This comment is justified in the sense that a set of clauses that are declaratively correct may well lead to a loop instead of the desired answer, even if that answer is a logical consequence of the program. This is because of the strategy used by Prolog in trying to find an answer, the strategy that is made explicit in the procedural reading of clauses. So in order to get a useful program we need to take the procedural reading into account as well. This is the "procedural thinking": how does Prolog go about in trying to find a solution?

Of course even if a program is declaratively correct, and even if we have formulated the clauses so that an answer will in fact be found by the search strategy of Prolog, the program may be useless because it engages in an enormously lengthy investigation of alternatives. A standard example of this is the "idiot algorithm" for sorting a list: generate permutations of the list until a sorted one is found.

So apart from the declarative reading of clauses and the procedural reading of clauses we also need to think about the efficiency of the algorithm that is in fact implemented given Prolog's particular way of going about things.

But there is more. The above remarks apply to the Horn clause reading of Prolog clauses. Often in Prolog programming this reading is not really relevant. A striking example is the use of negation as failure. The traditional Prolog definition of "not foo(X)" is:

not_foo(X) :- foo(X),!,fail.
not_foo(X) :- true.

Read as Horn clauses, these clauses simply state that not_foo(X) is always true (the cut having no declarative reading). But this has nothing to do with what is intended by the programmer. The traditional remedy here is to use a different interpretation of the program, not as a set of Horn clauses, but as a set of "completed definitions". There are some nonessential deficiencies in traditional expositions, but what the whole thing amounts to is that we can still use a declarative reading of programs provided we impose some restrictions on the execution of procedures such as the above ("sound negation").

But of course, with Prolog it doesn't end here. Prolog programs sometimes use constructs that "have no declarative reading". That is, we can no longer read the clauses as assertions about objects in some intended domain at all. A notable example of these constructs is "var(X)". Programs that use this admit a procedural reading, in the sense that a seasoned Prolog programmer will understand well enough what happens during execution of the program, but there is nothing resembling a reading of the clauses as assertions about terms in a Herbrand domain.

So then we face the question what "declarative thinking" means in actual Prolog programming. My idea about this, which others may wish to correct, is as follows. In actual Prolog programming, some procedures admit a declarative reading in the pure sense, and others do not. The declarative reading of clauses helps in several ways. First, it may actually be the case that trying to formulate true statements as clauses, while keeping in mind the way in which Prolog looks for solutions, helps in producing programs that are easy to understand and maintain and by no means necessarily inefficient. This is more or less the argument of those who regard pure or "purish" Prolog programming as a good way of programming. Second, declarative correctness is in many cases a useful tool for checking partial correctness of programs ("any answer obtained is correct in terms of what the programmer intends"). And finally, it helps in debugging: if programs (even when impure) are not even declaratively correct, something is wrong.

These comments, of course, are by way of an advertisement for a successor of Prolog, namely AKL. The advantages and uses of "declarative thinking" suggested above are more easily come by in AKL, because of the regimented use of conditional procedures (which cover negation as failure) in that language, and the "you will be clean whether you like it or not" method of simply not having any var(X). Other successors exist, I must grudgingly admit.

Torkel Franzen
SICS
Box 1263, S-164 28 Kista, Sweden
Email: torkel@sics.se