Chapter 12 _______________________________________________________
Nondeterminism and Concurrency
A program is deterministic if its evaluations on the same input always produce the same out-
put. The evaluation strategy for a deterministic program might not be unique. For example,
side effect-free arithmetic addition can be implemented in more than one fashion:
Evaluate the left operand; evaluate the right operand; add.
Evaluate the right operand; evaluate the left operand; add.
Evaluate the two operands in parallel; add.
A program is nondeterministic if it has more than one allowable evaluation strategy and
different evaluation strategies lead to different outputs. One example of a nondeterministic
construct is addition with side effects, using the three evaluation strategies listed above. If an
operand contains a side effect, then the order of evaluation of the operands can affect the final
result. This situation is considered a result of bad language design, because elementary arith-
metic is better behaved. It is somewhat surprising that the situation is typically resolved by
outlawing all but one of the allowable evaluation strategies and embracing hidden side effects!
There are situations where nondeterminism is acceptable. Consider an error-handling
routine that contains a number of commands, each indexed by a specific error condition. If a
run-time error occurs, the handler is invoked to diagnose the problem and to compensate for it.
Perhaps the diagnosis yields multiple candidate error conditions. Only one correction com-
mand is executed within the handler, so the choice of which one to use may be made nondeter-
A concept related to nondeterminism is parallel evaluation. Some language constructs
can be naturally evaluated in parallel fashion, such as side effect-free addition using the third
strategy noted above. This ‘‘nice’’ form of parallelism, where the simultaneous evaluation of
subparts of the construct do not interact, is called noninterfering parallelism. In interfering