\section{Dataflow Signal Graphs}

We illustrate dataflow signal graphs using an example.
Figure~\ref{insert-haskell} shows a
function expressed in Haskell \cite{HudakEtAl91} that
inserts an integer into an ordered list.
Figure~\ref{insert-dfg} shows  the {\tt Insert} function
represented as a {\em dataflow program signal graph}.
Each actor (denoted by a box) specifies an {\em action} that occurs after all
predecessor boxes (or the {\em start} node) have completed their
actions. A directed arc ({\tt u},{\tt v}) between
two actors {\tt u} and {\tt v}
in the graph denotes that when {\tt u} finishes its action,
a signal is to be sent to node {\tt v} to signal its completion.
Therefore, these arcs are called  {\em signal arcs}.

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

  Insert :: Set -> Int -> Set  

  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)
\end{verbatim}
\caption{\label{insert-haskell}The {\tt Insert}
  function written in Haskell.}
\end{figure}


An action is an operation that
reads values of input variables, performs computation, and
possibly assigns results to an output variable. Some
boxes, drawn as oblongs, perform tests on input variables
and signal successor boxes depending on
outcomes of the tests. Application of a function
causes: new instances of the function's variables to be created
and initialized with the undefined value; argument
values to be made available to the new activation; and the {\em start}
node of the called function graph to be enabled. When the application
terminates, the result value is	assigned
to a specified variable of the caller. Each variable must be
assigned a unique and unambiguous value (or not be assigned or
referenced) in any instantiation
of the program graph. So that this is true, all data dependences
between variables in a program graph must be represented
by the partial order defined by the signal arcs of the graph. 

Incremental arrays are implemented using I-structure operations
~\cite{ArvindNikPin89}.
The {\tt CREATE~n} operation creates (as a heap node) an array of $n$
elements indexed by integers $0, ... , n-1$ in which each element
has the value {\tt UNDEF}, meaning undefined. The {\tt CREATE} operation
yields a {\em pointer} to the heap node that may be held by a variable, stored
as an array element, and used to store and access elements
of the array. An action {\tt A[i]:v}
defines element {\tt i} of array {\tt A} to have the value {\tt v}.
Any reference {\tt A[i]} to an array element completes (yielding
the element value) only when the element has become defined.

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

\illustrationx{insert-graph}{5in}

\end{center}
\caption{\label{insert-dfg}Dataflow program graph for
   the {\tt Insert} function.}
\end{figure*}

Such Haskell programs and the dataflow signal graphs derived from
them are {\em determinate}---the result of any function evaluation is
independent of the order in which enabled nodes of the graphs
are chosen for execution. In the next section we describe
an {\em abstract computer system} capable of performing
computations specified by dataflow signal graphs. Then we show
how the system may be augmented and programmed to implement
nondeterminate transaction processing computations.
