The answer to why " despite their strengths - functional programming languages are not being widely used in programming complex multiprocessor designs is simple: they are not adequate to express all programming tasks. In part, this has to do with their inability to express nondeterministic computations; in part, some programs are simpler when expressed with state and, in part, it has to do with efficiency.

Some computing tasks are inherently nondeterministic. For example, when we benchmark programs, we expect that the timer readings taken before and after the computation will change, depending on the machine configuration, load, quality of compiled code, and so on.

Some computations, such as communication protocols, use explicit time-outs in a fundamental way. Storage allocators, such as the one that finds a free disk block when we write to a file, generally do not care which disk block is returned for use. None of these can be expressed in a functional language because the values returned by these operations are fundamentally not functions of inputs.

Although the nondeterminism of parallel access to shared state is usually an obstacle to parallelism, there are a number of situations where this nondeterminism may be exploited usefully to enhance parallelism and to enhance the clarity of the program.

An example is the nondeterministic summation discussed earlier in the inner product of matrix multiplication. It is a specific case of "accumulation" programs where the order of accumulation does not matter. Computing histograms is another example: the order in which samples are tallied in a histogram does not matter.

Another useful class of problems is nondeterministic search: for example, a robot motion-planning program may evaluate several alternative strategies in parallel and choose the best one it can find within a given time limit-there is no a priori way to predict which alternative will be chosen.

Some programs are simpler (and, counter-intuitively, more parallel!) when they use state explicitly. An example is graph traversal. Suppose we were exploring a maze and we have to find a path from the entrance to the exit. Suppose we had an army of lieutenants and we sent them down different paths in parallel.

In order to prevent duplication of work (and to avoid going round in circles), each lieutenant is provided with a stick of chalk, and he marks every corner that he visits. When he arrives at a marked corner he retreats, knowing that some other lieutenant (or even himself, if he walked in a circle), has already been there.

Unfortunately, there is no way of expressing this intuitive algorithm in a pure functional language. Every corner has state-it is either marked or unmarked-and this cannot be expressed functionally. Instead, the functional program looks like this: we have only one lieutenant, who carries a log book in which he records every corner that he visits.

More precisely, at every visited corner, he constructs a new log book which differs from the old log book by one additional entry-the entry for that corner. At each corner, he consults his log book to check whether he has been there before.

Not only is this solution totally sequential (just one lieutenant), it is potentially expensive (constructing and consulting log books), and it is also much less intuitive than the solution that uses state.

There is simply no way to express any of these nondeterministic programs in a functional language. This is true by definition; in fact, functional languages are so named because programs behave like mathematical functions-outputs are uniquely determined by inputs.