\section{Comparison with previous work}

\label{comparison}

Languages like Scheme \cite{Rees86} and ML \cite{Harper88} are, of course,
capable of state-sensitive computation because they have explicit imperative
constructs.  However, these are sequential languages, and our emphasis here
is on highly parallel languages, where {\em synchronization\/} is essential
to control access to shared state.

In \cite{Henderson82}, Henderson describes an {\cf interleave} ``function''
that nondeterministically merges two input streams into a single output
stream in the temporal order in which the objects of the input stream become
available.  Using this, a simple bank account for two users can be written as
follows:
\beginid
resps1,resps2 = untag (process_reqs init_bal
                                    (interleave (tag 1 reqs1)
                                                (tag 2 reqs2)))
\endid
 The {\cf tag} function attaches a name (an integer) to each request so that
its source is known even after it is merged with other requests.  {\cf
Interleave} merges all requests nondeterministically into a single stream.
\mbox{\cf (Process\_reqs bal)} is a simple stream mapping function from
tagged-requests to tagged-responses that carries along a current balance (the
state), and implements the state transition rule.  {\cf Untag} strips the
tags off the stream of tagged responses, returning a pair of response
streams. 

The method can be elegant when the topology is simple and known statically,
as in the above example.  When the topology changes dynamically, then $n$-ary
tagging, $n$-ary interleaving, $n$-ary untagging, etc., all become rapidly
unmanageable.  Programming in this style is often referred to as ``spaghetti
programming''.

In \cite{Stoye86}, Stoye embeds the merge operation in the operating system.
Thus, each ``process'' is a pure function from an input request stream to an
output response stream, and has a unique name (an integer, say).  When
process P1 wishes to send a message to process P2, it places a request tagged
with ``2'' in its output stream.  The operating system picks it up and places
it in the input stream for P2.  P2, in turn, places a response tagged with
``1'' in its input stream, which is again transmitted by the operating system
into the input stream for P1.  Thus the nondeterministic merge is embedded in
the operating system which serves as a giant dispatching mechanism, picking
up requests from all the processes' output streams and, based on the tags,
moving them into the corresponding processes' input streams.

The main problem with this approach it that it does not appear to be very
modular, since {\em all\/} messages in the system are routed through a
single, giant, nondeterministic switch.

Resource managers for Id were first proposed in 1977 \cite{Arvind77a} and
later refined by Arvind and Brock \cite{Arvind84}.  Here, the external view
of a manager was a request-to-response procedure.  The internal view, on the
other hand, was a stream-to-stream function.  The tagging and
nondeterministic merging of the requests and the untagging and separation of
the responses was done implicitly in the implementation.

A problem with Arvind-Brock managers seems to be that they do not compose
well.  In their paper, they discuss the priority printer scheduler where in
addition to the manager construct they also had to use a nondeterministic
{\cf merge} operator explicitly.

There are some general criticisms of all stream-based approaches.  The first
is that multiple arguments to a request must be packaged into a data
structure in order that they can be inserted into the request stream.  These
arguments are subsequently retrieved from this data structure inside the
manager.  In contrast, in our managers, multiple arguments are ordinary
function arguments, and are typically handled much more efficiently than a
heap-based data structure (in conventional terminology, they are passed ``on
the stack'').

A second general criticism of all stream-based approaches is a question of
types and type-checking.  Since all requests are merged into a single stream,
they must all be of the same type (the same is true for responses).  To
accommodate this, it is usually necessary to define a new algebraic type
containing one disjunct for each kind of request, and a new algebraic type
containing one disjunct for each kind of response.  Each request then has to
be packed into an request-type object before the interleave and unpacked
inside the request processor; the response then has to be packed into a
response-type object and subsequently unpacked after untagging.  This can
involve a substantial overhead.

In Stoye's approach, the problem of type-checking appears to be even more
serious.  As in Henderson's system, all requests to a process must be of the
same type (and, similarly, all responses from a process). But it is worse
than that.  P1 may wish to send requests to two unrelated managers P2 and P3.
But since all these requests must be channeled through a single stream (P1's
output stream), this implies that the types of the input streams of P2 and P3
must be the same.  Similarly, all responses from P2 and P3 to P1 are
channeled through P1's input stream, which implies that the types of the
output streams of P2 and P3 must be the same.

In our manager construct, on the other hand, each kind of request is handled
by its own, distinct handler; thus, each handler can have its own type,
unrelated to the types of other handlers.

A third general criticism of stream-based approaches is this.  Since all
requests arrive on the same stream, it necessitates a run-time case analysis
and dispatch to different handlers after examining the type of a request.  In
our manager construct, this dispatch is done at compile time, since the
programmer directly calls the appropriate handler function for different
types of requests.  Because this dispatch is done at compile time, calls to
our managers are also amenable to compile-time optimization, the most
important one being inlining.

In our manager construct, the ``tagging'' and ``untagging'' operations are
done implicitly using the underlying continuations (dataflow tags) that must
exist already in any implementation (whether dataflow or not).  Thus, the
programmer never has to worry about explicitly managing a separate namespace
for processes.  This makes it much easier to deal with managers as first
class objects, i.e., they are named and manipulated like any other object in
the language.

For simple managers (responding in the order of requests), when requests are
sufficiently infrequent, there is no stream construction at all, either
implicitly or explicitly.  Requests are queued only when they contend for the
state variable.  It is not clear what compiler prowess would be needed to
optimize stream-based managers to reach this level of efficiency.  For
scheduling managers, we explicitly build a queue of deferred requests in the
handler bodies and embed it in the state of the manager;  however, this is
inevitable in any manager that does scheduling, stream-based or otherwise.
