\section{\label{transact}Critical Sections in Functional Programming}

In conventional programming environments,
a {\em critical section} is a portion of a program
that must be entered by only one process at a time
because each activation of it performs an update of shared
data. Considering that we are interested in critical sections
within the context of functional programs, we model a critical
section as function that takes a
value of type {\tt State} and a value of type {\tt Input}
and yields a new state and a value of type {\tt Output}
\begin{verbatim}
   function CritSect :: State -> Input ->
                                  [State, Output]
\end{verbatim}
as shown in Figure~\ref{crit-sect-function}.

\begin{figure}[tb]\small
\begin{center}

\illustrationx{crit-sect}{1.5in}

\end{center}
\caption{\label{crit-sect-function}A critical section
modelled as a state-modifying function.}
\end{figure}

Two or more processes may wish to invoke the critical section
at arbitrary points in the progress of their
respective computations. The desired effect is illustrated
in Figure~\ref{crit-sect-interleave}.
Note that the order in which instantiations of the critical section
are placed in the composition of critical section functions is
nondeterminate.

\begin{figure}[tb]\small
\begin{center}

\illustrationx{interleaved}{3.2in}

\end{center}
\caption{\label{crit-sect-interleave}The effect of
interleaved invocations of a critical section.}
\end{figure}

It is necessary that the critical section pass
through information that will allow each output value to
be directed to the correct process so it may continue its
activity. We accomplish this by letting each input value
be a record
\begin{verbatim}
   data Input :: (INPUT Value Continuation)
\end{verbatim}
where a value of type {\tt Continuation} represents the point
from which activity by the invoking process should be
continued with the output value from the critical section.
Similarly, each output value is a record
\begin{verbatim}
   data Output :: (OUTPUT Value Continuation)
\end{verbatim}
and we require that any critical section function preserve the
continuation from input to output.

We wish to be able to invoke the critical section code from
any point in a main program by writing something like
\begin{verbatim}
   output = Transact input crit_sect_funct
\end{verbatim}
at each point where a transaction may be needed. This would
mean that a position in the cascade composition of applications
of the function should be reserved for the {\tt input}
and the corresponding output value returned. This
form cannot work because, for one thing, the initial value of the
state has not been specified. In addition, our program might
require more than one series of transactions, each defining its
own private sequence of state values, but each series using the same
critical section function. What is needed is an entity that
uniquely represents the particular sequence of state values
of interest and associates some critical section function
with the series. We call this entity a {\em guardian}.

We will define two generic functions for creating and
utilizing guardians. The first is {\tt MakeGuardian} which
returns a guardian when given an initial state value and
the critical section function as arguments.
The second, {\tt Transact}, is not
really a function because, as we will show, it does the dirty work of
nondeterminately inserting an instance of the critical section
function into the cascade composition. Thus a main program for performing
a series of transaction using {\tt CritSect} as the critical
section function may be written as follows:

\begin{verbatim}
  Main = let
    guardian = MakeGuardian init-state CritSect
      ---
    output1 = Transact input1 guardian
      ---
    output2 = Transact input2 guardian
      ---
      ---
\end{verbatim}

The use of a guard location and the {\tt SWAP} operation are
the key to implementing these two generic modules. The
{\tt MakeGuardian} function may be coded as follows:
\begin{verbatim}
  MakeGuardian init-state CritSect = let
      queue = (ENTRY undefined undefined)
      guardian = guard queue;
      _ = Process  init_state queue CritSect
    in  
      guardian
\end{verbatim}
The special operation {\tt guard} creates a guard,
fills it with the initial value {\tt init-state},
and returns a reference to it (its address).
The {\tt MakeGuardian} function also starts the processing
of the (initially empty) queue by invoking the {\tt Process}
module.

In the code language of the abstract computer system discussed
in section~\ref{memory}, this would translate to:
\begin{verbatim}
  MakeGuardian init-state crit_sect_ptr;
    queue_ptr = ALLOCATE (2);
    WRITE queue_ptr + 0, UNDEF;
    WRITE queue_ptr + 1, UNDEF;

    guardian_ptr = ALLOCATE (1);
    () = SWAP guardian_ptr queue_ptr;

    fork
       Process init_state queue_ptr, crit_sect_ptr;

    return guardian_ptr;
\end{verbatim}
In this code the {\tt SWAP} operation is used just to put
an initial value in the guard location. The previous
value in the guard location is garbage and is thrown away.

The guard location holds a pointer to the final (unfilled)
entry of a queue of entries of the form
\begin{verbatim}
   data Queue =
      (ENTRY Input Queue) |
      (EMPTY)
\end{verbatim}
The generic {\tt Process} function applies the critical
section function to input values provided
by the queue entries, returning the result values as
specified by the given continuation in each instance.
Figure~\ref{process-haskell} shows the coding
of the {\tt Process} function. (Its normal
return value is empty because the effect of executing
{\tt Process} is to provide return values to each caller
of {\tt Transact} by means of the continuations saved in
the entries of the queue.)

\begin{figure}\small
\begin{verbatim}
Process :: State -> Queue ->
       (Input -> State (Output, State) -> _

data Queue = (ENTRY Input Queue)

data Input = (INPUT Value Continuation)
data Output = (OUTPUT Value Continuation)

Process state queue crit_sect_funct =
      (ENTRY input queue') = queue;
      (output, state') = crit_sect_funct input state;
      (OUTPUT result cont) = output;
            _ = continue cont result
   in
      Process state' queue crit_sect_funct
\end{verbatim}
\caption{\label{process-haskell}The {\tt Process} function.}
\end{figure}


The special module {\tt Transact} processes each call
making a new entry in the queue for processing by
the {\tt Process} function.
Its code is given in Figure~\ref{transact-haskell}.
The new queue entry consists of the argument and the return
continuation and becomes the final entry of the
queue. This is done by the {\tt update}
operator which is implemented using the {\tt SWAP}
memory operation as shown in Figure~\ref{transact-code}.

\begin{figure}\small
\begin{verbatim}
Transact argument guardian = let

    cont = return_continuation;
        -- obtain the contiuation for this call
        -- of Transact
    new = (ENTRY undefined undefined);
        -- make a new unfilled queue entry
    current = update guardian new; 
        -- set the guard so future requests use
        -- the new queue entry
    input = (INPUT argument cont);
        -- construct the new queue entry
    define current (ENTRY input new)  
        -- fill the current queue entrye
  in _
\end{verbatim}
\caption{\label{transact-haskell}The special module {\tt Transact}.}
\end{figure}

\begin{figure}[tb]\small
\begin{verbatim}
  Transact argument guard_ptr return_continuation

    cont = return_continuation;
    new_ptr = Allocate (2);
    WRITE new_ptr + 0, UNDEF;
    WRITE new_ptr + 1, UNDEF;
    current_ptr = SWAP guard_ptr, new_ptr;
    input_ptr = Allocate (2);
    WRITE input_ptr + 0, argument;
    WRITE input_ptr + 1, cont;
    WRITE current_ptr + 0, input_ptr;
    WRITE current_ptr + 1, new_ptr;
    QUIT;                   

  end Transact
\end{verbatim}
\caption{\label{transact-code}Abstract machine code for the
   {\tt Transact} module.}
\end{figure}

The way this code appends entries to the queue for
the {\tt Process} function is illustrated by
the succession of snapshots in Figure~\ref{snapshots}.
In Figure~\ref{snapshots}(A) the guard holds a reference
to current (and final) entry {\tt b}
of the queue. The {\tt Process} function is following the
chain of entries from the top and pauses when it attempts to access (with
a {\tt READ} operation) entry {\tt b} which is yet to be filled in.
In Figure~\ref{snapshots}(B), a new (empty) entry {\tt c} has been
created and a {\tt SWAP} operation performed to substitute
{\tt c} for {\tt b} in the guard. The new empty entry is now
referenced by the guard. In Figure~\ref{snapshots}(C)
the pointer to {\tt c} has been installed (by
a {\tt WRITE} operation) in the current entry {\tt b}, allowing the
{\tt Process} function to proceed.

\begin{figure*}
\begin{center}

\illustrationx{snapshots}{4.5in}

\end{center}
\caption{\label{snapshots}Snapshots showing formation of the stream
of {\tt Entries} at the guard.}
\end{figure*}
