Since dealing with state (reuse of storage) causes so much difficulty for parallel execution, we can ask if there are programming notations that avoid the notion of state completely, and whether such notations are adequate for general-purpose programming.

The answer to the first question is yes - such languages are called declarative languages - but the answer to the second question is no - some programming tasks are difficult, if not impossible, to express declaratively.

The efficient implementation of pure declarative languages is also very difficult (curiously, the implementation problem is the dual of the automatic parallelization problem, an observation that we will return to shortly). Nevertheless, declarative languages are an excellent basis for more complete parallel programming languages and, indeed pH, the language advocated in this series of articles, is based on this idea.

A well-known class of declarative languages is that of functional programming languages, such as Lisp, SML and Haskell [26]. Hughes provides an excellent articulation of the advantages of functional programming in "Why Functional Programming Matters" [18]. A second well-known class is that of logic programming languages, such as Prolog  and KL1 and their more modern derivatives, constraint logic programming languages, such as Oz . We will mainly discuss functional languages here (because of their relationship to pH), but many of our remarks also apply to the latter.

As an aside, we note that the adjective "declarative" is subjective. Intuitively it means that the program describes what is to be computed rather than how to compute it. Such a description is "higher level", or more "abstract" and hence presumably easier for humans to write and comprehend.

However, no programming language can ever get away completely from the how of problem solving. The most abstract descriptions of computations may not even be executable (such descriptions are the purest form of specifications).

For example, an abstract description of the square root function is "the function which, for argument n, produces x such that x2 = n." An abstract description of a sorting function is "the function which, for argument sequence xs, produces the sequence ys which is a permutation of xs and in which y(i) < y(i+l)."

It is unreasonable to expect any interpreter/compiler to actually execute these specifications systematically and efficiently. Thus, all programming, no matter how high level, fundamentally concerns algorithms, which specify how to compute an answer. So, the adjective "declarative" is mainly an assessment of how much non-problem-specific detail can be suppressed in a programming language.

At one extreme (least declarative) is architecture-specific assembler, where the programmer is intimately concerned with managing storage layout, movement of data between registers and memory, and sequencing.

Most architecture-independent programming languages such as C, Pascal, and Fortran abstract away from some storage-layout details and provide higher-level control structures such as if-then-elses, loops, and recursive procedures.

Some object oriented languages like Java provide even higher-level structures such as data abstraction and inheritance and further relieve the programmer from storage-management details by managing storage deallocation automatically.

Declarative languages like functional and logic programming languages abstract away from storage layout and storage management details completely and also abstract away from many sequencing details.