% -*- Mode:TeX -*-

\documentstyle[11pt]{article}

\input tmacros
\input illhacks

\title{Supporting State-Sensitive Computation in a Dataflow System}

\author{Paul S. Barth\\Rishiyur S. Nikhil}

\begin{document}

\pagenumbering{arabic}

\maketitle

%\begin{abstract}

%\end{abstract}

\section{Introduction} 
Functional languages provide a solid foundation for programming
parallel computers.  Formal properties such as referential transparency
and determinacy make them good candidates for formal correctness proofs
(equational reasoning).  The treatment of functions as first class values,
the inclusion of higher-order functions, and function composition
simplifies programming.  The absence of state from the programming model
enables fine-grained, parallel execution.

However, many programs require non-functional behavior.
These programs fall into two classes: inherently indeterminate programs,
and determinate programs which employ state for efficiency.
Programs in these two classes have an explicit state that is
shared and updated by many processes.

An example of an indeterminate program is a printer queue in a
multiprogrammed operating system.
The output of the printer is determined by the order and priority
of print requests received, which cannot be known {\em a priori}.
Therefore, the operating system and its users comprise an indeterminate
system which cannot be expressed functionally.
This class of programs includes many operating system functions, such
as process scheduling, file management, and device handling.

As an example of a determinate program requiring state, consider a
parallel graph reduction algorithm.  
An expression is represented as a node, with incoming arcs from all
expressions referencing it, and outgoing arcs to all its subexpressions.
The evaluator demands the value of the topmost node, which demands the
value of its subexpressions, recursively and in parallel.
This algorithm is clearly exponential if an expression is reevaluated everytime it is referenced.  However, if the value of the expression is 
stored in the node after its first evaluation, and returned thereafter,
the algorithm is linear in the size of the graph.
This simple optimization is impossible to express in a functional language.
Even a functional language with determinate data structures (such as
I-structures\cite{I-structures} or streams\cite{KahnMacQueen}) is unable to
support this algorithm, since it is not known who will request the node
first, if ever.  Other examples from this class of programs include
databases, real-time systems, and artificial intelligence systems.  
The sheer number of programs in these two classes dictates that any realistic
functional programming language include support for non-functional programs.

Indeed, several language constructs have been proposed for supporting
state-sensitive behavior in a functional language.  These constructs
are of two types: nondeterministic primitives, and
state abstractions.  Nondeterministic primitives include
nondeterministic stream merge in its various forms.  State
abstractions include the {\em choice} operator for speculative
parallelism, and {\em managers} for handling shared resources.  The
two classes provide equivalent expressive power (i.e., either can
simulate the other), and both have shortcomings as vehicles for
supporting state-sensitive behavior.  Nondeterministic primitives
provide no method for clearly encapsulting the program's state and
the various functions which affect or respond to the state.
Abstractions, on the other hand, tend to support a specific style of
state-sensitive behavior, and are difficult to apply to a wide range
of problems efficiently.  


This paper describes a language construct for managing state-sensitive computation on
a dataflow computer.  Our approach has three broad goals:
\begin{enumerate}

\item {\bf Encapsulation:} The construct should clearly delineate
state-sensitive operations
from functions.  This construct should hide the details of request
processing and state updates, so that operations on the state can be
written functionally.  Scheduling policies should be easy to express
and independent from the state operations.

\item {\bf Expressiveness:} The construct should support recursive
state operations.   State should be a first-class
citizen, which can be dynamically created, passed between functions, and
stored in data structures.  

\item {\bf Efficiency:} The implementation of the construct should have
a low overhead and not unnecessarily restrict parallel access to
the state.
\end{enumerate}

The approach describe herein, called {\em managers}, attempts to satisfy
these goals in the context of the Id programming language\cite{Id}.  A
manager defines a state variable and a set of functions (called request
handlers) for updating and querying its contents.  Managers may be
dynamically created and used as first-class values, and request handlers
may be called from any function.  Managers provide mutual exclusion on
the state variable, allowing requests to be issued in parallel without
interference.  Furthermore, request handlers may be mutually or
self-recursive without deadlock.  Thus, managers as described here
provide an abstraction that encapsulates the state-sensitive aspects of
a program without compromising expressiveness or efficiency.

The next section describes the manager construct and gives a simple
example.  This is followed by a description of scheduling with managers, and
examples of the dining philosophers and a memory manager are given.
Section ???  describes efficient techniques for implementing managers.
Managers are then compared to other methods for supporting
state-sensitve computation.  The discussion section describes the impact
of managers on the formal properties of the language.  The last section
gives concluding remarks.



\section{Managers} 

The Id programming construct for state-sensitive
computation is the {\em manager}.  Conceptually, a manager is a
high-level interface to a state variable.  The state variable is
shared by an arbitrary number of processes, which invoke
state-sensitive computations through the manager interface.  The
computations invoked by a request compute two values: a response to
be sent to the requestor, and a new value for the state variable.
The manager synchronizes incoming requests, updates the state
variable, and returns responses.  Figure 1 illustrates this
view of managers.

\floatingfigure{manager}{1.69 true in}{System View of a Manager}

Specifically, each manager is an abstract data
type that defines a state variable, a set of query and 
update operations (called {\em request handlers}), and a constructor
for creating instances of the type.
In addition to defining the interface functions, the abstraction
provides the synchronization and updates on the state variable,
so that request handlers can be written functionally.
The program interface to managers is similar to other abstract datatypes:
manager instances are created (with some initial state) and
passed to functions who may make requests on the instance.

As an example, consider the implementation of a bank account program.
An account is created with an initial deposit, against which credits
and debits may be issued.  If a credit is issued, the balance is updated and
an acknowledgement of ``OK'' is the response.  If a debit is issued,
the balance is checked and updated if it is sufficient, and an ``OK''
response is returned.  If the balance is insufficient, it is not updated and
``NO'' is returned.  This example is given below:

\samepage{
\begin{center}
\begin{verbatim}
def_manager account balance =
     credit acct amount = "OK",balance+amount
  || debit  acct amount = if balance>=amount then
                            "OK",balance-amount
                           else "NO",balance
  || query acct = balance,balance;
\end{verbatim}
\end{center}
}

This defines the datatype {\tt account} with state variable {\tt balance}
and three request handlers, {\tt credit}, {\tt debit}, and {\tt query}.   
A constructor for accounts is also defined, called {\tt Account}, which
takes an initial balance and returns an account.
The debit and credit request handlers take two arguments
(the account instance and the amount of the transaction) and compute
a pair of values: the acknowledgement and the new account balance.
The query request handler returns the balance and leaves it unchanged.
The code template below illustrates the use of this manager:

\samepage{
\begin{center}
\begin{verbatim}
   {my_accout = Account init;
    ... (debit my_account 5) ...
    ... (credit my_account 7) ...
    ... (query my_account) ... }
\end{verbatim}
\end{center}
}

Here, the {\tt Account} constructor creates the instance {\tt
my\_account} with the balance initialized to {\tt init}.  Three requests
are made on the account, a debit of 5, a credit of 7, and a balance
query, which is returned.  Id is an implicitly parallel language, which
serializes requests based only on data dependencies.  Assuming there are
no data dependencies between these requests, they may execute in
parallel.  The order in which they are processed is indeterminate, but
the manager construct guarantees
serializability\cite{LamportSerializable}.  That is, the value of the
state variable following the processing of these two requests will be
the same as some serial order of these requests,.  In this example, the
result of the query request will be either 0, 7, or 2, which correspond
exactly to the possible balances.

\subsection{Types}


The {\tt def\_manager} construct defines an abstract type $T$, named by
its first argument.  The second argument names the state variable of
type $T_{S}$.  The constructor (denoted by the capitalized name of the
type) is of type $T_{S}\rightarrow T$, unless a user-defined constructor
is specified with {\tt constructor} keyword.  In this case, the
signature of the function is determined by the arguments and expression
following the keyword.  The expression must of course return an object
of type $T$.  
Each request handler has two type definitions, internal
and external, to allow the state variable to be hidden from requestors.
The internal definition is defined by the expressions associated with
each handler, and is of type 

\begin{equation}
T\rightarrow T_{1} \rightarrow ...\rightarrow T_{n}\rightarrow T_{r} \times T_{S}
\end{equation}

That is, the expression takes the handler arguments and returns a pair of the response
(of type $T_{r}$ and the new value for the state variable.  Note that the expression
also has implicit access to the state variable.

The external type of the handlers simply has the state
information stripped off, namely:

\begin{equation}
T\rightarrow T_{1} \rightarrow ...\rightarrow T_{n}\rightarrow T_{r} \times T_{S}
\end{equation}

Therefore, users see each handler as
a function call, taking the manager instance and other arguments and
returning a result.  The existence of an underlying state variable is
entirely transparent.

The manager construct provides encapsulation for both the state
variable and operations on it.  Functions for creating, accessing,
and updating the state variable are defined by a single construct.
The request handlers are defined by expressions which compute the
response and new state from the arguments and current state; the
the abstraction performs the exclusive access and update of the
state variable.  This allows the expressions to be written
functionally.  The external interface to a manager is clearly defined
by the request handlers, and the state variable is completely hidden.
In fact, if a constructor is included in the definition, even the
representation of the state can be hidden. This interface allows the
scope of the nondeterminism in the program to be clearly defined: any
function calling a request handler (or another nondeterministic
procedure) is potentially nondeterministic.

\subsection{Scheduling with Managers}

Managers defined thus far allow a wide range of state-sensitive
programs to be written, such as data bases and priority search
programs.  These programs channel information between computations
through the state variable.  However, some programs
require state-sensitive scheduling.

\subsubsection{Guards}

For example, consider a slight variation on the bank account.  In
this scenario, debits above the balance are deferred until sufficient
credits are made.  Incoming credits are applied against deferred
debits, and the satisfied debits are processed.  The following
manager implements this example:

\samepage{
\begin{center}
\begin{verbatim}
def_manager account balance =
     credit acct amount = ok,signal balance+amount;
   ||debit acct amount when (balance >= amount) =
                  ok,signal balance-amount;
   ||query account = balance,balance;
\end{verbatim}
\end{center}
}

This is identical to the previous definition of account, with the
addition of the {\tt when} and {\tt signal} constructs.
{\tt when p} is the request handler's guard\cite{DijkstraGuards}:
{\tt p} is a predicate on the state which must be true for the 
request handler to execute. If {\tt p} fails, the predicate is queued
and the result deferred.   {\tt signal s} indicates a state change,
where {\tt s} is the new state.  Signal checks the queue of deferred
requests and selects one whose predicate is now true, if any.
The new state is passed directly to this request handler which
begins execution.  Note that {\tt signal} is only used by request handlers
which might enable deferred requests.  For example, queries do not
update the balance, so a signal is not required.  However, there might
be remaining deferred debits after a credit, so debits issue a
signal.

The use of guards do not change the interface to
managers. For example, the {\tt sba} program defined earlier could use this
manager with no syntactic changes.  The only difference is a potentially
significant delay incurred when processing a debit request.  This is
significant from a correctness standpoint as well as convenience: a
debit may wait for a credit that will never arrive, and the program
will therefore not terminate.


\subsubsection{Schedulers}

Guards allow a request handler to define the conditions under which
will execute.
However, the description above does not define how a deferred request is selected
when a state change causes many conditions to become true.
In the example above, a single credit could enable many debits.
The specific debit picked depends on how guards store deferred requests
and {\tt signal} tests them.  The only constraint on these operations is that
they ensure ``fairness'' to avoid starvation.

Some programs, such as resource schedulers, require more explicit control
over the selection of enabled handlers.  For example, consider a print queue
in which short jobs are printed before long jobs.  
If the printer is free, a print request is serviced immediately.
If it is not, the request is classified as long or short and queued.
The {\tt signal} operation enables short jobs before long jobs.
If no jobs are waiting, it simply updates the state variable.
The manager below illustrates the print queue:

\samepage{
\begin{center}
\begin{verbatim}
def_manager printer free? (make_print_q,enq_print,deq_print) =
     print p job when free? = (do_print job p),false
   ||ack p = _,signal true;
\end{verbatim}
\pagebreak [0]
\begin{verbatim}
def make_print_q = ((make_empty_q),(make_empty_q));
def enq_print (fast_q,slow_q) entry = classify entry (fast_q,slow_q);
def deq_print (fast_q,slow_q) free? = 
   if (entries? fast_q) then
    (q_top fast_q),((rest fast_q),slow_q)
   else if (entries? slow_q) then
         (q_top slow_q),(fast_q,(rest slow_q))
        else _,(fast_q,slow_q);
\end{verbatim}
\end{center}
}
A scheduler is a triple of functions: initialization, enqueue, and
dequeue.  The initialization function returns a queue, and is called
whenever a manager instance is created.  The enqueue function takes a
queue and an entry and returns the queue with the entry inserted.  An
entry is a record with fields for the request's name,
arguments\footnote{Argument fields are referenced by position, rather
than name, since guards may create entries for several request
handlers.}, guard and return address of the deferred request, for
resumption by a signal operation.  The dequeue function takes a queue as
an argument and returns the next entry to run (if any\footnote{An
underscore (\_) is the null value, indicating there is no runnable
entry.}) and a new queue.

It is clear that scheduling could be incorporated directly into the
basic manager construct, by making the queue part of the state,
and providing a synchronization construct for results, such as 
I-structures\cite{I-structures} or futures\cite{futures}.
This is counter to our aims on several counts.  First,
it embeds the conditions of successful execution in the handler computation.
Second, it requires the explicit management of dynamic data dependencies
between request handlers, which is hard to write and even more difficult
to analyze.  Finally, it forces those computations not involved in
scheduling to include scheduling structures in its state update.

The scheduling constructs proposed here provide both encapsulation
and flexibility.  Guards are part of the
manager encapsulation, and can be included or omitted without
changing the interface.  Schedulers are defined as functions, even
though they are state-sensitive: the manager (implicitly) contains
the queue of deferred requests in its state.  Schedulers and managers
can be freely intermixed, allowing a single manager definition to
take on a variety of behaviors.  This also allows common scheduling
paradigms to be standardized and included in managers by reference.
These paradigms include:

\begin{itemize}
\item {\bf Fifo Test:} Enqueue in fifo order, dequeue first element whose
condition is satisfied.  The default.
\item {\bf Fifo:} Enqueue in fifo order, dequeue first element.  Useful
for simple mutual exclusion, where a signal operation implies that the
condition is true.
\item {\bf Priority:} Enqueue by inserting into a priority tree, dequeue
by taking top of tree and merging subtrees.
\end{itemize}


Note the expressiveness of the manager construct
when coupled with schedulers. Requests can arrive, be reordered,
and processed with the addition of simple queuing operations.  
Unlike stream-based scheduling, there are no constraints on the
scheduling function used.  Requests may be dynamically reordered or
priorities may be dynamically assigned.  

Non-strictness plays a key role in providing this expressiveness.
The request handlers compute two values, the response and the new
state.  Non-strictness allows the response to be deferred while the
state is returned (and therefore relinquished for other requests).
Naturally, this is critical to the type of managers described above,
where future requests satisfy a deferred request.  It is easy to see
how non-strictness also supports recursive manager requests.  A request
handler's response may be determined by another request of the same
manager.  Non-strictness allows the response to delay for the value
returned by the recursive call, while returning the new state
immediately.  Of course, request handlers must not use the manager
recursively while computing the new state.  The mutual exclusion
guarantee on the state variable would produce deadlock in this case.


\section{Dining Philosophers}

As an example, consider Dijkstra's  problem of the dining philosophers\cite{
DijkstraDining,ParlogDining}.  There are five philosophers who
share a dining table.  Each philosopher is assigned a seat, and requires the
forks on either side of it to eat the meal in the center.  There are
five forks, one between each pair of plates.  Each philosopher lives a dreary
existence of alternating between thinking and eating.  When a philosopher is ready to
eat, he contends with his neighbors for the forks on his left and right.
One problem with this contention is that it can lead to deadlock, where
each philosopher holds his left fork and is waiting for his right.
A simple solution is to only allow four philosophers at the table at a time.
In this model, there is a refectory which only admits four philosophers; the 
fifth philosopher must wait outside.  Once admitted, a philosopher picks up his left
and right forks and eats.   When finished, the philosopher leaves, potentially
enabling another philosopher to enter.  This solution is given below:

\samepage{
\begin{center}
\begin{verbatim}
def phil j ref forks =
    {while true do
      {seq
         cogitate ;
         call enter ref;
         l_fork = pick_up forks[j]
       | r_fork = pick_up forks[j+1 mod 5] ;
         burp = ingest l_fork r_fork;
         call put_down forks[j]
       | call put_down forks[j+1 mod 5]
       | call leave ref }} ;
\end{verbatim}
\pagebreak[0]
\begin{verbatim}
def_manager refectory n fifo_test =
      enter r when (n>0) = ok,(n-1)
   || leave r            = ok,signal (n+1);

def_manager fork free? fifo =
    pick_up f when free? = ack,false
  ||put_down f = _,signal true;
\end{verbatim}
\end{center}
}

Each philosopher is an infinite process that requests entry to the refectory and
access to his forks.  After eating, the forks are relinquished and the philosopher
leaves and returns to thinking.  The {\tt seq} Id construct serializes these actions,
except where a vertical bar ({\tt |}) indicates parallel execution.
The processes are initialized with the following expression:

\samepage{
\begin{center}
\begin{verbatim}
 { forks = {array (1,5)
                 | [j] = Fork true || j <- 1 to 5} 
   refectory =  Refectory 4;
   In
     {for j <- 1 to 5 do
        call phil j ref forks }};
\end{verbatim}
\end{center}
}


This example illustrates the effectiveness of the
manager construct.  The managers for the computation state are
modular, compact, and efficient. 


\section{Implementation Issues}

Efficiency is typically critical to state-sensitive computation.
Such computations are often implemented as a network of processes
communicating through the shared state.  If these processes are
running in parallel, the shared state (with its attendent property of
mutual exclusion) may become a bottleneck during execution.
Therefore, any undue overhead or unnecessary serialization introduced
by managers may seriously compromise the efficiency of the entire
program.

\subsection{Locked Storage}

The Id programming language is compiled for a dataflow machine
with I-structure storage \cite{ Traub,Monsoon}.  This storage
provides hardware synchronization on individual storage cells.
In particular, the storage unit supports locked storage cells \cite{ patent?}.
Locked storage provides mutual exclusion on
mutable storage cells through two operations:
{\em read-and-lock}, and {\em write-and-unlock}.
Associated with each cell is a bit indicating whether the
cell is locked or unlocked.  If the cell is unlocked, a read-and-lock
operation atomically locks the cell and returns its value.  If
the cell is locked, read-and-lock defers until it is unlocked.
Write-and-unlock takes a cell and a value as arguments.
If there are any deferred read-and-lock operations, the value is
passed to one and the cell remains locked.  Otherwise, the value
is placed in the cell and it is unlocked.  Attempts to write-and-unlock
an unlocked cell is an error.

Locked storage provides mutual exclusion on state variables.
Recall that each request handler may reference the state variable in its
body.  When a request is made, a read-and-lock operation is performed
on the state variable.  The result of this is passed into the body of
the request handler.  The new state returned by the request handler
is passed to a write-and-unlock operation which updates the cell.
Figure ??? below illustrates this activity:

\samepage{
\begin{center}
{\tt
\begin{tabbing}
def \=handlern m arg1 arg2 ... argn = \\
    \>\{\=state = read\_and\_lock m; \\
    \>\> result,new\_state = {\em handler expression}; \\
    \>\> write\_and\_unlock m new\_state; \\
    \>\> In \= \\
    \>\>\>  result\};
\end{tabbing}}
\end{center}
}


The efficiency of this implementation comes from two sources: low overhead
and parallelism.  The locking operations described here correspond to
a few dataflow instructions.  The Monsoon implementation of locks is
non-blocking; therefore, no machine cycles are wasted spin-locking.
The only overhead remaining is function call overhead, which can be
eliminated by compiler macro substitution.  The resulting overhead
for manager requests is approximately a half dozen instructions.

This implementation also gains efficiency through parallelism.
Multiple requests can run in parallel, including multiple versions
of the same request handler.  Locks provide the mutual exclusion
necessary to avoid interference, but do not serialize state-independent
portions of the handlers.  For example, credits to the bank account
can be acknowledged before the balance is actually available.
(??? how does the balance get updated in a fully lazy implementation???)

This implementation is also space efficient.  By storing the
state variable in a locked cell rather than a stream, state
updates do not require memory allocation.  This approach is
also more efficient than one that employs a request stream.
If the state variable is unlocked, no memory is allocated to
hold the request: the state variable is simply passed into the
request handler.

\subsection{Scheduling}

The scheduling constructs interact closely with the state access and
update operations.  Request handlers with guards obtain the lock
on the state variable and evaluate their condition.  If it succeeds,
the handler is processed as outlined above.  If it fails,  the handler
is suspended and an entry is sent to the enqueue function.  The enqueue
function adds the entry to the deferred queue and unlocks the state.
A signal operation calls the dequeue function
while still holding the lock on the state variable.  If the function returns
an entry, the new state is passed into the suspended request.
Note that the lock is not relinquished throughout this process, so that
no intervening requests can invalidate the condition of the deferred
request.

Although scheduling is abstracted from the request handlers, in some
instances scheduling can be integrated with mutual exclusion on the
state variable.  Certain default scheduling policies, such as fifo (with
no test), can be implemented directly as a locked cell.  If the guard
simply tests a boolean, the lock bit on the state variable can provide
the necessary queuing and synchronization.  In this case, scheduling can
be completely subsumed by mutual exclusion.


\section{Relation to Previous Work}

There have been several proposals for extending functional languages
with constructs for state-sensitive behavior.  These typically
introduce a non-deterministic stream merge operator, allowing state
operations to be interleaved.  In this model, state-sensitive
behavior is implemented as a network of stream functions.  The state
of the system is described by the contents of the streams and the
internal state of the functions (if any).  Henderson \cite{
interleave} introduces nondeterministic merge at the language level,
while Stoye \cite{ stoye86} embeds the merge operator in the
operating system.  Neither technique distinguishes between
state-sensitive functions and ordinary stream functions.


Resource managers for Id were first proposed in 1977 \cite{
ArvindMonitors} and later refined by Arvind and Brock\cite{
ArvindBrock}.  These managers also employ nondeterministic merge to
interleave requests and use stream functions to describe
state-dependent behavior.  However, the language construct
encapsulates the request handler and the state variable, and hides
the merge operator.  The construct allows state-dependent
computations to be distinguished from other stream operators, thereby
delineating the nondeterminism present in a program.

Managers described herein retain this encapsulation but have
with several salient differences.  In our approach, request handlers
are scalar rather than stream functions.  These functions are
provided with the state of the resource and other arguments pertinent
to the request, and return both a response to the requestor and a new
state value.  Rather than a nondeterministic stream merge, multiple
requests execute concurrently, with the manager construct providing
mutual exclusion on the state variable.  Finally, instead of a single
function processing all manager requests, this approach allows the
definition of different functions for each type of request.

Furthermore, stream-based paradigms yield no more expressive power than
managers.  Managers can easily and efficiently implement
nondeterministic stream merge by storing a stream in the state variable.
Arvind-Brock style managers can be implemented by passing this
stream directly to their manager functions when it is created.
The example below illustrates this:

\samepage{
\begin{center}
\begin{verbatim}
def_manager ab_manager (req_stream,res_stream) =
    use m req = (hd res_stream),
                ((enqueue req req_stream),(tl res_stream));
   constructor f = {req_s = (make_empty_queue)p;
                    res_s = f req_s;
                    In
                      (req_s,res_s)};
\end{verbatim}
\end{center}
}
 
Arvind and Brock \cite{ ArvindBrock} showed how some forms of
scheduling can be done with a network of stream functions and the
nondeterministic merge primitive.  Their strategy evaluated the
priority of each request and copied it into a stream associated with
this priority.  The resource was allocated to the top stream element
in the highest priority stream.  In effect, streams were used to
implement a fixed number of priority queues.  Nonstrict cons allowed
the output stream to correspond to the input stream, even though the
stream elements were filled at different times.

The scheduling constructs described here provide more flexibility
and better abstraction than the stream-based approach.  A variety
of schedulers can be defined, including priority queues with unbounded
priorities. The when and signal abstractions remove the scheduling
from the state operations, without compromising efficiency.
This abstraction should provide a better foundation for reasoning
about state-sensitive computation.


\section{Discussion}

Adding state-sensitive computation to a functional language profoundly
impacts the language.  Although the extensions add power critical to 
a wide class of computer programs, they compromise important formal
properties of the language, and introduce the need for state-sensitive
control of the program's execution.  

\subsection{Indeterminacy}
The most important formal property lost is the Church-Rosser
property, determinacy.  Formally, this means that an expression can
reduce to different values, dependent on the evaluation strategy
used.  Operationally, this means program results can vary with
respect to processor load, processor configuration, network
latency--in short, aspects of the system typically invisible in a
determinate language.  However, the formal implications are far more
drastic than the pragmatic ones because, in practice,
state-sensitive computations fall into the two classes alluded to in
the introduction: inherently indeterminate computations, and
deterministic programs employing state-sensitive computations
for efficiency.  Although these classes differ in the program
properties they hope to preserve, the manager construct provides a 
solid foundation for both.

Inherently indeterminite programs {\em expect} their results to
differ with the dynamics of program execution--such
programs are designed to control or respond to system state.
For example, some parallel heuristic search programs control execution
by pursuing the best candidates for a solution at a given point in
time. Alternatively, a real-time program may respond to a disjunction of
inputs and respond to the first arriving.  The goal of a programming construct
for this class of programs is to simplify the description of the
state-sensitive behavior, and to allow detection of anomolies in
program behavior, such as starvation or deadlock.  Managers encapsulate
state variables and their attendant operations, and provide an
abstraction for scheduling separate from state operations.
This should be instrumental in reaching the goals of this class
of programs.


The second class consists of programs such as the memory allocator
whose nondeterminism is entirely transparent to its users.  This is
because values returned by the manager (memory blocks) are entirely
indistiguishable with the interface provided (read and write to a
cell).  Another set of programs in this class are accumulators\cite{
accumulators}, in which a memory cell is updated by operations that
are commutative and associative.  A set of updates to an accumulator
yields the same value regardless of the order of the updates.  These
programs are clearly determinite, even though a central component of
the program is state-sensitive.  For this class of programs, the goal
is to prove that a program with managers is determinate.  Again,
encapsulation should simplify this task by deliniating program
regions that are potentially indeterminate.  The guards associated
with request handlers make the conditions of execution explicit.  The
treatment of managers as abstract datatypes puts this task properly
in the realm of type checking.  We believe that these properties
will make the manager construct invaluable in our analysis.

\subsection{Synchronization}
A complication introduced by state-sensitive computation is the need for
additional synchronization constructs.  This need is present both
within a single manager, and among a group of managers.  Within a
manager, requests should not lock the state variable until
all the arguments to the request have arrived.  Otherwise, the 
variable will be unavailable to ready requests, creating a bottleneck.
In the case of multiple managers, some programs may require a rendezvous
of their responses to signal an aggregate action.  Linguistic extensions
for supporting this type of synchronization have been proposed and
are currently being tested. 

\section{Conclusion}
Support for state-sensitive computation is critical to the success and
widespread use of functional languages. Managers are a construct for
writing such programs that
provide encapsulation, expressiveness, and efficiency. They allow
for the succinct expression of state-sensitive computations, yet provide
control and flexibility in their use.  They have been used for
a variety of applications, and will provide the foundation for
analysis of programs incorporating state-sensitive computation.

\section{Acknowledgements}

\end{document}

% The second example of a memory
% manager demonstrate that non-trivial managers can be written, and
% that the implementation is efficient enough to support systems
% programming.  It also demonstrates the importance of explicit 
% scheduling functions.

% \subsubsection{Memory Allocation}
% A more complex example is a buddy-system memory allocator.  In a
% buddy system, memory is divided into blocks of size $2^{k}$,
% for $k$ from  1 to $m$, the log of the size of memory.
% Each block lies on a $2^{k}$ memory boundary.   Blocks of
% memory are allocated and deallocated, and split and
% coelesced to avoid waste yet maintain blocks  large enough
% for arrays.

% The manager implementation of this fairly straightforward.
% A manager is defined that handles allocation and deallocation
% requests for blocks of size $2^{k}$.  $m$ instances of this manager
% are created, one for each block size from 1 to $m$.  These managers are
% placed in the array $B$, with the index indicating the exponenent of the
% block size being managed.  The manager definition for each manager is below:


% \begin{verbatim}
% % B,m are globals
% def_manager buddy mem_q (make_alloc_q,enq_alloc,deq_alloc) =
%      alloc b k when entries? = (top_of_q mem_q),signal (rest mem_q)
%   || dealloc b mem = {k = logsize mem;
%                       my_buddy = get_buddy mem;
%                       In
%                         if (free? my_buddy) then
%                           (dealloc B[k+1] (coalesce mem my_buddy)),mem_q
%                         else _,signal (enqueue mem mem_q)};

% def make_alloc_q = make_fifo_q;
% def make_alloc_deq q = make_alloc_deq q;
% def enq_alloc q entry = 
%    {k = (entry_arg entry 2);
%     b = alloc B[k+1] k+1;
%     b1,b2 = split b;
%     call dealloc B[k] b1;
%     call dealloc B[k] b2;
%     In
%       cons entry q};

% \end{verbatim}

% Low level details of the support functions are omitted for simplicity.
% The state variable is a queue of memory blocks of size $2^{k}$.  The
% {\tt alloc} request handler has a guard that checks the queue for
% entries.  If there are entries, the top of the queue is returned and the
% rest of the queue becomes the new state.  If the queue is empty, control
% passes to the enqueue function, which attempts to allocate the next larger
% size block. This recurs until a block is
% found, or we fail with the largest block size ($2^{m})$.  When a larger
% block is found, it is split and the two halves are put on the next
% smaller queue via a dealloc request.  The {\tt dealloc} request handler
% checks to see if the incoming memory can be coelesced with its
% ``buddy'', i.e., the other block of memory originally produced by the
% split.  If so, they are coelesced and dealloc is recursively called on
% the manager for $2^{k+1}$ size blocks.  Otherwise the block is simply
% enqueued.  Note that the direct call from the signal to any waiting
% alloc requests prevents blocks from being coelesced when there are
% outstanding allof.

\bye
