\section{An Example: Insertion and Search in an Integer Set}
\label{example}

A simple example for transaction processing
is the processing of commands for
inserting and searching in a set of integers.
Figure~\ref{insert-search} shows the
functions that, respectively, insert integers
into an ordered list, and search for an integer in
the list.

\begin{figure}[tb]\small
\begin{verbatim}
  data Set =
     EMPTY |
     NONEMPTY int Set

  Insert set n :: Set -> Int -> Set  
  Search set n  :: Set -> Int -> Bool

  Insert set n =
    case set of
      EMPTY -> NONEMPTY n (EMPTY)
      NONEMPTY m rest ->
        if m > n then
          NONEMPTY n set
        else
          NONEMPTY m (Insert n rest)

  Search set n =
    case set of
      EMPTY -> FALSE
      NONEMPTY n rest -> TRUE
      NONEMPTY _ rest ->
        Search rest n
\end{verbatim}
\caption{\label{insert-search}The {\tt Insert} and {\tt Search}
  functions.}
\end{figure}

We define search and insert commands and the corresponding
responses as follows:
\begin{verbatim}
  data Command = SEARCH int | INSERT int
  data Response = SEARCH bool | INSERT
\end{verbatim}
We must provide for continuing operation of an arbitrary caller
following completion of each instance of the critical section.
For this purpose we include a {\tt continuation} with the
arguments and result values for the critical section function.

\begin{verbatim}
  data Input = (INPUT Command Continuation)
  data Output = (OUTPUT Response Continuation)
\end{verbatim}

The {\tt CritSect} function for this example has a set
as its state and invokes the insert or search function
according to the command given as input.
For the search command it returns a boolean value and the same set
as it was given. For the insert command it returns the given set
with the given integer inserted.

\begin{verbatim}
  CritSect :: Input -> Set -> (Output, Set)

  CritSect input set = let
        (cmnd, cont) = input
        (resp, set') = case cmnd of
           SEARCH n -> SEARCH (Search set n), set
           INSERT n -> INSERT, (Insert set n)
        output = (resp, cont)
     in (output, set')
\end{verbatim}

This critical section function, together with the insert and search
functions, form the complete application-specific code for the
integer set example. The other program modules ({\tt MakeGuardian},
{\tt Transact}, and {\tt Process}) are unchanged and are common to all
transaction processing implementations.

This example illustrates how the use of I\_structure synchronization can
yield substantial parallelism from the concurrent processing
of many transactions. The {\tt CritSect} function may return its
set output component even though its activity (searching the set
or scanning for the correct insertion point and constructing a
new list) has not completed.  Note that each entry created to hold
a new element of a list
representing the integer set is written only once after space is
reserved by the {\tt ALLOCATE} instruction in the insert code. The
absence of updates and the delaying of access until an entry is
filled combine to achieve the concurrency of operation without
departing from the interleaving semantics of critical sections.
