Nondeterminacy arises when the outcome of a computation
may be different for different runs with the same input.
Generally, nondeterminacy is undesirable because its
presence makes correctness of computations difficult to verify, and bugs
difficult to track down.
Yet nondeterminate computation is useful in some programs such
as those for transaction processing.

Functional programming is uniquely capable of achieving highly
parallel program execution without allowing the possibility
of nondeterminate results. In this paper, we discuss how
functional programming models may be augmented to support
nondeterminate computation.
We begin with a brief review of past concepts and
proposals for expressing nondeterminate computation.
Given the hypothesis that
functional programming is the best programming model for
expressing determinate computation, we introduce a
basic functional programming model and its
implementation by means of an abstract computer system.
We show how this abstract computation model may
be augmented to incorporate support for nondeterminate
computations by the simple addition of a {\em swap}
memory operation. The remainder of the paper
illustrates application of this base
to a transaction processing example, and compares this
approach with solutions using M-structures, as incorporated
into the Ph language, and with solutions for a conventional
shared-memory programming environment.


