\section{\label{swap}The Swap Operation}

We have found that an operation that atomically writes a
new value into a location and returns the previous
value held by the location can be used to implement
typical instances of nondeterminate action in
computations. We have named this operation {\tt SWAP} and the
location it references is called a {\em guard}. The
{\tt SWAP} operation is requested by the following
message to the memory system
\begin{verbatim}
   (SWAP value address processor continuation)
\end{verbatim}
and is answered by the same format of reply as for the
{\tt READ} operation. The effect of the {\tt SWAP}
operation is specified by the addition to the memory state-transition
function given in Figure~\ref{rule-swap}.

\begin{figure}\small
\begin{verbatim}
  (SWAP value address node continuation)  ->
     let item = map [address]
     in case item of
        (UNDEF) | (QUEUE _) -> ERROR
        (DEFINED old_value -> let
              map' =
                  MapUpdate map address (DEFINED value)
           in SendReply old_value node continuation map'
\end{verbatim}
\caption{\label{rule-swap}Memory transition rule
   for the {\tt SWAP} operation.}
\end{figure}

The effect of executing the {\tt SWAP} operation is to substitute
a new value at the specified location and return
the old value to the requesting processor.
Note that, when no confusion may occur, we may omit the ``processor''
and ``continuation'' fields in specifying the swap operation in
a textual program. The default is the processor requesting the
swap and the continuation consisting of the data frame of the current
activation and the instruction index of the immediately following
action in the program text.

A location accessed by a {\tt SWAP} operation is called a
{\em guard} for the way it may be used to implement a critical
section as discussed below. In general, a guard is associated with
and controls access to some resource. The address of a guard may be
freely passed to any processes that needs to access the
resource associated with the guard.

In our abstract computer system implementation we assume that any memory
location used by a {\tt SWAP} operation is never accessed using any
other operation (that is, {\tt READ} or {\tt WRITE}).
A request message for a {\tt SWAP} operation is sent
directly to the home memory unit
for the specified location. No entry in cache memory
is ever made for a guard location.
A {\tt SWAP} is a long latency operation, so its invocation
from a thread specifies a continuation, and the processor
terminates thread execution.
