\section{Introduction}

Nondeterminacy arises when the outcome of a computation
may be different for different runs with the same input. A good
example is transaction processing, where the order
in which commands take effect on a database depends on
the timing of asynchronous events within the computer system.
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. Furthermore, in some kinds of computing,
such as heuristic search problems, use of nondeterminacy can lead to more
efficient problem solving with parallel computers.

We believe computer systems should be designed so that programmers
can implement computations that do not require nondeterminacy in
a language or style that precludes nondeterminate effects. The
popular practical programming languages do not offer such a
guarantee when extended for the writing of parallel programs. This is because
explicit process synchronization commands are used which introduce
the possibility of nondeterminate behavior,
even when it may not be desired.\footnote{Imperative languages such
as Fortran 90 that include support for the data parallel
programming model provide the ability to write a limited class of
parallel programs with a guarantee (by the compiler) of
determinate results.}
Important questions include how nondeterminate computations should be
expressed in high-level languages, and what program execution model
should guide the design of computer systems intended to support such
computations.

Functional programming is uniquely capable of achieving highly
parallel program execution without allowing the possibility
of nondeterminate results. In this paper, we discuss how
a functional programming model 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 an {\em swap} memory
operation. The remainder
of the paper illustrates application of this base to a
transaction processing example. We use the
insert and search operations for integer sets to show how transactions,
including multiple updates, may be permitted to overlap in
time with a guarantee of correct results, and yet be written in
the functional style. We compare our proposal with solutions using
M-structures, as incorporated into the Ph language, and with
solutions for a conventional shared-memory programming
environment.
