% Paper on M-structures for FPCA  % -*- Mode:TeX -*-
% Feb, 1991
% Barth, Nikhil and Arvind

\documentstyle{lncsconf}

% Standard Latex definitions.

% ----------------
% PARAGRAPH INDENTATION
\setlength{\parindent}{0in}
% SPACE BETWEEN PARAGRAPHS
\setlength{\parskip}{\medskipamount}
% ----------------
% STRUTS
% HORIZONTAL STRUT.  One argument (width).
\newcommand{\hstrut}[1]{\hspace*{#1}}
% VERTICAL STRUT. Two arguments (offset from baseline, height).
\newcommand{\vstrut}[2]{\rule[#1]{0in}{#2}}
% ----------------
% HORIZONTAL LINE ACROSS PAGE:
\newcommand{\hdivider}{\noindent\mbox{}\hrulefill\mbox{}} 
% ----------------
% EMPTY BOXES OF VARIOUS WIDTHS, FOR INDENTATION
\newcommand{\hm}{\hspace*{1em}}
\newcommand{\hmm}{\hspace*{2em}}
\newcommand{\hmmm}{\hspace*{3em}}
\newcommand{\hmmmm}{\hspace*{4em}}
% ----------------
% VARIOUS CONVENIENT WIDTHS RELATIVE TO THE TEXT WIDTH, FOR BOXES.
\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}
% ----------------
% ``TIGHTLIST'' ENVIRONMENT (no para space between items, small indent)
\newenvironment{tightlist}%
{\begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
}
}%
{\end{list}
}
% ----------------
% ITALICISE WORDS
\newcommand{\ie}{{\em i.e.,\/}}
\newcommand{\eg}{{\em e.g.,\/}}
\newcommand{\etc}{{\em etc.\/}}
\newcommand{\via}{{\em via\/}}
\newcommand{\vs}{{\em vs.\/}}
% ----------------
% CODE FONT (e.g. {\cf x := 0}).
\newcommand{\cf}{\small\tt}
% ----------------------------------------------------------------
% ID CODE DISPLAYS.
% Id code displays are enclosed between \bid and \eid.
% Most characters are taken verbatim, in typewriter font,
% Except:
%  Commands are still available (beginning with \)
%    but use ` and ' instead of { and }
%  Math mode is still available (beginning with $)
%    but use ~ and ! for ^ and _

\outer\def\beginid{%
  \begin{list}{$\bullet$}{%
%    \spacing{1}
    \medskip
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \catcode`\{=12
  \catcode`\}=12
  \catcode`\&=12
  \catcode`\#=12
  \catcode`\~=12
  \catcode`\%=12
  \catcode`\_=12
  \catcode`\^=12
%  \catcode`\!=8
%  \catcode`\'=2
%  \catcode`\`=1
  \obeyspaces
  \obeylines \small\tt}

\outer\def\endid{%
  \end{list}
  }

{\obeyspaces\gdef {\ }}

% ----------------
% ILLUSTRATIONS
% This command should specify a JJ directory for ps files for illustrations.
\def\psfileprefix{/jj/nikhil/docs/91-02-m-structures/}
\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}} 

% \illuswidth is used to set up boxes around illustrations.
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-10pt}

% ----------------------------------------------------------------

% HERE BEGINS THE DOCUMENT

\begin{document}

\title{M-Structures: Extending a Parallel, Non-strict, Functional Language with State}

\author{%
Paul S. Barth, Rishiyur S. Nikhil and Arvind \\
Massachusetts Institute of Technology \\
\\
{\small Laboratory for Computer Science} \\
{\small 545 Technology Square, Cambridge, MA 02139, USA} \\
{\cf \{barth,nikhil,arvind\}@au-bon-pain.lcs.mit.edu}
}


\maketitle

\begin{center}
{\bf Abstract}

\begin{minipage}{6.25in}
\setlength{\parskip}{\medskipamount}

Functional programs are widely appreciated for being ``declarative''
(algorithms are not {\em over-specified\/}) and implicitly parallel.
However, when modeling state, both properties are compromised because
the state variables must be ``threaded'' through most functions.
Further, state ``updates'' may require much copying.  A solution is to
introduce assignments, as in ML and Scheme; however, for meaningful
semantics, they resort to strict, sequential evaluation.

We present an alternative approach called {\em M-structures}, 
which are imperative data structures with
implicit synchronization.  M-structures are added to Id, a parallel
non-strict functional language.  We argue that some programs with
M-structures improve on their functional counterparts in three ways:
they are (1) more {\em declarative}; (2) more {\em parallel}; and (3)
more {\em storage efficient}.  Points (1) and (2) contradict
conventional wisdom.  We study two problems: histogramming a tree, and
graph traversal, comparing functional and M-structure solutions.

\end{minipage}

\end{center}

% ----------------------------------------------------------------

\section{Introduction}

Functional programming is widely appreciated for its declarative
nature.  By ``declarative'' we mean that one does not have to
{\em over-specify\/} the details of an algorithm.  This is sometimes
paraphrased as: ``Say {\em what\/} you want done, not {\em how\/} you
want it done''.

However, some programs cannot be expressed naturally in a purely
functional style.   For example, a program to assign unique
identifiers to the nodes in a tree must thread the supply of unique
identifiers through the traversal of the tree; this ``plumbing'' can
be quite messy.  Another weakness of functional languages
is that they are difficult to implement efficiently--- 
there is too much copying of data structures.

A common approach to addressing these weaknesses is to extend a
functional language with state.  Both ML and Scheme are examples of
this.  However, in order that these imperative features have a
meaningful semantics, the language is usually made into a strict,
call-by-value, sequential language.  For functional programs, this is
an over-specification of the order of evaluation, and may thus be
viewed as a loss of declarativeness.

Another issue is parallelism.  In pure functional languages,
parallelism is implicit.  Annotations for parallelism may be used, but
these can be viewed as hints and do not add to the intellectual burden
of the programmer.  However, in sequential functional languages with
imperative extensions, parallelism is usually re-introduced through
another layer of constructs such as threads, forks, semaphores,
futures, \etc\ These features usually make the language more complex.
% Further, there is some question whether this approach can yield the
% massive amounts of parallelism that one can obtain from pure
% functional languages, since it is it difficult to express massively
% parallel programs using explicit forks and synchronization.
Further, when two such parallel programs are composed, their parallelism does
not compose, because of the underlying strict semantics.  The
difference in resulting parallelism can be exponential, as
demonstrated in \cite{Nikhil90e}.  

Parallelism can also be curtailed by the threading alluded to above.
Threading ensures determinacy at the expense of serializing access to
the shared data structure.  For a large class of algorithms,
determinacy can be ensured in the presence of asynchronous updates to
a shared structure.  For example, accumulation and set operations can
use associative and commutative properties to produce determinate
results under any sequence of operations.  For such applications, only
the {\em atomicity\/} of each operation need be guaranteed to ensure
determinate results.  Again, the threading required by functional
programming over-specifies, by serializing, an inherently parallel
algorithm.

Let us call the traditional approaches A and B:
\begin{quote}
{\bf Approach A:} purely functional (strict or non-strict) with implicit
parallelism or annotations for parallelism.

{\bf Approach B:} strict functional + sequential evaluation + imperative
extensions + threads and semaphores for parallelism.
\end{quote}
In the literature, the landscape of functional programming techniques
is normally defined by these two approaches.  In this paper we would
like to open up an entirely new frontier:
\begin{quote}
{\bf Approach C:} non-strict functional + implicitly parallel evaluation +
M-structures + occasional sequentialization.
\end{quote}
M-structures are mutable data structures manipulated with
implicitly synchronized imperatives called {\em take\/} and {\em
put\/}, which are quite different from the traditional
assignment statement.

The main points we would like to demonstrate about Approach C are:
\begin{itemize}

\item[(1)]
Programs in Approach C are often more declarative than their
functional counterparts, because they are less specific about the
order in which things should be computed.  By omitting this level of
detail, programs in Approach C are often shorter and easier to read
than the pure functional versions.

\item[(2)]
Programs in Approach C often have much more parallelism than their
functional counterparts.

\item[(3)]
Programs in Approach C are often much more efficient than their
functional counterparts in terms of heap storage used and total number
of instructions executed.

\end{itemize}
The first two points come to us as a great surprise, because they
contradict our previous intuitions (and, we believe, conventional
wisdom)--- we always took it for granted that functional programs are
more declarative than programs with state, and that functional
programs always had more parallelism than programs with state.
See \cite{ArvindAssessing} for studies of implicit parallelism in functional Id
programs.

In fact, point (2) is a very curious reversal of conventional wisdom.
Whereas we always thought that programs with state needed powerful
analysis (\ie\ dependence analysis) in order to recover the
parallelism that is already evident in functional programs, we find
here that it is the functional programs that would need powerful
analysis to recover the parallelism that is evident in Approach C.
To our knowledge, no such analysis techniques exist yet.

The final point, storage efficiency, is also an issue in sequential
functional programs.  Many analysis techniques have been developed which
attempt to improve storage efficiency through reuse, such as abstract
reference counting\cite{Hudak87} and single-threadedness
analysis.  Unfortunately, most published techniques seem to be
based on an underlying sequential, strict semantics, sometimes restricted to
first-order languages and flat domains for data structures.  Thus,
non-strict, implicitly parallel languages are unlikely to benefit from these
techniques.

We hasten to add that Approach C is not without its problems!  As soon
as one adds state, one loses referential transparency (RT), and any
benefits that may go with it.  For example, RT provides a foundation for
equational reasoning, which may be used during compilation for common
subexpression elimination, proofs of invariants used in loop
optimization, \etc\
Equational reasoning may also be used to prove functional programs correct.
Our intent is not to challenge this work, but rather to demonstrate some
programs which benefit, in both declarativeness and efficiency, from violating
RT.  Such benefits have motivated other ``functional'' languages,  such as ML and Scheme, to
introduce imperative constructs.  These languages,
which comprise Approach B,  are still considered to be functional
languages because the style of programming in these languages is
``mostly functional''.  We suggest the same for Approach C---programs
are still written in a mostly functional style.  Further, we claim that
the non-strictness and implicit parallelism of Approach C yields
a more functional programming style than Approach B with explicit
parallelism constructs.  Regardless, Approaches B and C will require
the development of new foundations for proving correctness, such
as proposed by \cite{Burton}.

In this paper, we will demonstrate our claims by comparing Approach A
(functional programs) and Approach C (M-structures)
for two example applications:
computing a histogram of values, and performing a graph traversal.
The  declarativeness of these programs is critiqued, and
their performance measured on a parallel simulator.
The rest of this paper is organized as follows: Section
\ref{background} describes the core functional language, its
non-strict semantics and parallel execution model, the M-structure
extensions, and our parallel simulator.  Sections
\ref{example1}
and \ref{example2} explore the two example programs, respectively, in
some detail.  Section \ref{discussion} discusses our results, and
outlines a method for reasoning about M-structure programs.
We conclude in Section  \ref{conclusions}.

% ================================================================

\section{Background}

\label{background}

% ----------------------------------------------------------------

\subsection{The core functional language}

The core of Id is a non-strict functional language with implicit
parallelism\cite{Nikhil90c}.  It has the usual features of many modern
functional languages, including a Hindley/Milner type inference system,
algebraic types and definitions with clauses and pattern matching, and
list comprehensions.  An Id block, which has {\em  letrec} semantics,
consists of a set of bindings and a body expression following the 
keyword  {\cf In}, {\em e.g.}:

\beginid
{ x = 1:y ;
  y = 2:x ;
In
  x }
\endid
Here, ``{\cf :}'' is an infix list constructor, and the block
evaluates to a cyclic list whose infinite unfolding is {\cf 1:2:1:2:$\cdots$}
Note that non-strict evaluation allows this cycle to be created
with mutually recursive bindings; such bindings are meaningless under
strict evaluation.

In addition, Id has extensive facilities for arrays, including
array {\em comprehensions}  for the efficient construction
of functional arrays.  For example, the expression

\beginid
{array (1,5) of
 | [j] = 0 || j <- 1 to 5 }
\endid
creates an array with index range 1 to 5,
with every location containing 0.

One form of array comprehension useful for computing
histograms is the {\em accumulator}.
For example,  suppose we wish to build a histogram of numbers
ranging from 1 to 5 drawn from a list of numbers {\cf xs}.
The result is an array with index range 1 to 5, 
such that the $j$'th cell of the array
contains the number of occurrences of $j$ in {\cf xs}.  Here is the
program:

\beginid
{array (1,5) of
 | [j] = 0 || j <- 1 to 5
 accumulate (+)
 | [j] = 1 || j <- xs }
\endid
Before the {\cf accumulate} keyword is an array comprehension that
specifies the initial contents of the array (zeroes).  The rest of the
construct specifies that for each {\cf j} in {\cf xs}, we increment
element $j$ of the histogram by 1.

In array and accumulator comprehensions, no order is specified for the
array-filling computations.  However, note that array comprehensions
can be non-strict, whereas accumulator comprehensions must be strict.
In array comprehensions, each slot is assigned at most once, \ie\
there is a single transition from $\bot$ to non-$\bot$ (or
``unevaluated'' to ``evaluated'', in graph reduction terminology).
Thus, the array can be returned as soon as it has been allocated, with
consumers automatically blocking on $\bot$ if necessary.  However, in
accumulator comprehensions, each slot may go through several
intermediate non-$\bot$ states, and we cannot be sure that a slot has
reached its final value until all the accumulations have been
performed.  Thus, the array cannot be returned to a consumer until it
has been fully computed\footnote{ Array and accumulator comprehensions
in Haskell were influenced by these array notations in
Id\cite{Hudak90a}.  }.

% ----------------------------------------------------------------

\subsection{Non-strict, Implicitly Parallel Semantics}

We are interested in non-strict semantics, not only for its expressive
power, but also because it admits more parallelism than strict
semantics \cite{Nikhil90e}.  Many evaluation orders implement
non-strict semantics, with lazy evaluation being the most popular.
Id, on the other hand, implements non-strict semantics by {\em eager}
evaluation of most expressions.  A precise description of Id's
operational semantics using rewrite rules is given in
\cite{Ariola89a,Nikhil90a}.  The flavor of Id's semantics is given
here to illustrate its expressive power and implicit parallelism.
Briefly,
\begin{itemize}

\item
In a block:

\beginid
    { x1 = e1 ;
      ...
      xN = eN ; 
    In
      eBody }
\endid
all expressions ({\cf e1}, ..., {\cf eN} and {\cf eBody}) are
evaluated in parallel, and the value of {\cf eBody} may be returned as
soon as it is available (even if {\cf e1}, ..., {\cf eN} have not
finished evaluating).  Thus, the block has {\em letrec} semantics,
with no implicit ordering on the evaluation of expressions, except as
imposed by data dependencies.

\item
All expressions in an application \mbox{\cf (e0 e1 ... eN)} may be
evaluated in parallel.  Suppose {\cf e0} evaluates to a function {\cf
f} and we have a definition:
\beginid
def f x1 ... xN = eBody ;
\endid
then the application can immediately be rewritten to:
\beginid
    { x1 = e1 ; 
      ...
      xN = eN ;
    In
      eBody }
\endid
In other words, the function may be invoked as soon as {\cf e0} is
evaluated, and a result may be returned as soon as it is defined by
the function, even if the arguments {\cf e1}, ..., {\cf eN} have not
finished evaluating.

\item
In a conditional expression (\mbox{\cf IF e1 THEN e2 ELSE e3}), {\cf
e1} is evaluated to a boo\-lean value, after which {\em one\/} of the
expressions {\cf e2} or {\cf e3} is evaluated.

\end{itemize}

Id's rewrite rules also take a precise position on {\em sharing\/} of
computations and data structures, since this is
also crucial in a language with state.  Informally, an identifier such
as {\cf x1} above may not be substituted by {\cf e1} until {\cf e1}
has been reduced to a variable or constant;  this ensures that
expressions do not get duplicated.   Data structures are always
referred to \via\ labels, which may be regarded as abstract pointers.
Thus, a constructor produces a single data structure that is shared
among all its references.




Note that the operational semantics of Id are quite unique in that they are:
\begin{itemize}

\item
Non-strict, but not lazy (blocks, constructors, and function 
applications may return values before any of their inputs are
available), and

\item
Eager, but not call-by-value (evaluation of arguments is initiated
whether they are needed or not).

\end{itemize}
As an example of eager, non-strict evaluation, consider the 
following.  Given the function {\cf f}
\beginid
def f a b = (a+1,b+1) ;
\endid
we can evaluate the following block as sequence of rewrites:
\beginid
{ (x,y) = f 3 x ;
In
   y}
\endid
First, the function application reduces to a nested block:
\beginid
{(x,y) = { a = 3 ;
           b = x ;
         In
           (a+1,b+1) } ;
 In
   y}
\endid
In the rest of the sequence, nested block bindings are flattened into
a single block, and tuple bindings are rewritten into identifier
bindings.  The block returns a value when the body identifier
{\cf y} is bound to a constant:
\beginid
{ (x,y) = (a+1,b+1) ;  ==>  { x = a+1 ;  ==>  { x = 4 ;    ==>  5
  a     = 3 ;                 y = b+1 ;         y = b+1 ;
  b     = x ;                 a = 3 ;           a = 3 ;
In                            b = x ;           b = 4 ;
  y}                        In                In
                              y}                y}
\endid
This is perhaps an artificial example, but the cyclic binding
establishes the point that {\em this is a non-strict language even
though we do not use lazy evaluation\/}.  To emphasize this further,
we invite the reader to trace the evaluation of the function (due to
Traub \cite{Traub88a}):
\beginid
def f b x y = { xx = if b then x  else yy ;
                yy = if b then xx else y  ;
              In
                xx + yy } ;
\endid
under the calls \mbox{\cf (f True 10 20)} and \mbox{\cf (f False 10
20)}.  These expressions are undefined under strict semantics, but are
perfectly meaningful in Id and other non-strict languages.


% ----------------------------------------------------------------

\subsection{Non-strictness, yes, but why not lazy evaluation?}

Consider the following function:
\beginid
def f x = (e1, e2) ;
\endid
and suppose the expression {\cf e1} contains a side-effect.  In Id, we
can immediately conclude that whenever {\cf f} is called, the
side-effect will occur.

In a lazy evaluator, on the other hand, we have to look at each
application of {\cf f} separately--- the side-effect will occur only
if the application is actually examined in a strict context and,
further, that the first component of the resulting tuple is also
examined in a strict context.  For example, merely selecting the first
component of the tuple and storing it into another data structure will
not cause {\cf e1} to be evaluated, so the side-effect will not occur.
Thus, determining the conditions under which the side-effect will
occur is as hard a problem as strictness analysis, requiring
potentially global analysis.  The presence of higher order functions
only complicates matters further.

In Id, evaluation of an expression is controlled {\em only\/} by
conditionals.  Thus, determining the conditions under which a
side-effect in a function {\cf f} will occur requires only local
analysis; we do not have to look at the contexts in which {\cf f} is
applied.

We believe that having such a {\em local\/} model of whether or not
side-effects occur is essential in order to reason about programs with
side-effects.

% ----------------------------------------------------------------

\subsection{M-structures with {\em Take\/} and {\em Put\/} operations}

As described, Id is a determinate language with no provision for
side-effects.  Its eager, non-strict semantics allows the efficient,
parallel execution of functional programs.  However, functional Id programs
that share state suffer from the drawbacks alluded to earlier, \ie\
the loss of declarativeness and parallelism due to threading.

To support programs that share state, Id is extended with 
{\em M-structures}.  M-structures are implicitly synchronized 
data structures that support atomic updates.  We define two
M-structure operations, called {\em take} and {\em put\/},
for reading and writing the components of an M-structure.\footnote{
An analogous pair of operations, called
{\em E-fetch} and {\em E-store}, were developed independently by 
Milewski\cite{Estructures}.}

Take and put operations are {\em implicitly synchronized\/}, \ie\
there is no separate notion of locks or semaphores.  
Rather, a state bit is associated with every M-structure element
indicating whether it is {\em empty} or {\em full}.
The empty state means that the element is currently taken and
may not be read; the full state indicates that it is available.
A {\em take\/} operation on a full element atomically reads its value
and resets its state to empty, while a {\em take\/}
on an empty element suspends.
A {\em put\/} operation writes a new value to an
empty (\ie\ taken) element;\footnote{A version in which multiple {\em
put\/} operations are buffered has also been designed, allowing
M-structures to act as producer-consumer channels.  The examples in
this paper will not use this feature.} if there are suspended {\em
take\/} operations waiting for the element, one is resumed and the
value communicated to it, and the element remains in the empty state.
Otherwise, the value is written into the element and its state set to
full.

For example, consider the following statement\footnote{In Id,
statements are included among a block's bindings} that atomically
increments an element of an M-structure array:

\beginid
A![j] = A![j] + 1 ;
\endid
Here, the expression {\cf A![j]} on the right hand side denotes a {\em
take} operation on the $j$'th element of array {\cf A}.  This value is
incremented by one; the expression {\cf A![j]} on the left hand side
denotes a {\em put\/} operation on the same element.  Note that the
strictness of the addition operator ensures that the {\em take\/}
precedes the {\em put\/}.  In general, the expression computing the
value to be put into a cell should be strict in the value taken from
the cell.  Assuming this strictness, the M-structure synchronization
guarantees that the cell update is atomic.  For example, if $k$
parallel computations attempt to execute the statement above, their
access to the location will be properly serialized and the final value
of the cell will be its original value plus $k$.

\subsubsection{Explicit Sequencing}

When writing parallel programs that share state, it is sometimes
necessary to introduce explicit sequencing.  For example, suppose we
wish to reset an array location to 0 and return its old value, \eg\

\beginid
{ Aj = A![j] ;
  ---           % barrier
  A![j] = 0 ; 
In
  Aj }
\endid
The first statement takes the old value out, and the second one puts
the new value (0) back.  The horizontal line is read as a
sequentializing barrier, to ensure that the take occurs before the
put.  This is necessary since, by default, all components of a block
are evaluated in parallel, and so there would be nothing to prevent
the put occurring before the take.  The barrier makes the put
operation strict in the take.

A barrier in a block is more subtle than a simple sequencing form (the
classical semicolon).  It makes the statements following the barrier
(including the body of the block) {\em hyperstrict\/} in the
statements that precede the barrier.  That is, no expressions
following the barrier begin evaluation until all expressions before
the barrier are completely evaluated, including procedure calls and
all their expressions, recursively.  This hyperstrict evaluation
allows barriers to be used to sequence side-effects buried in
procedure calls.

Unlike synchronization barriers in other parallel languages, an Id
barrier is not a global barrier--- it is entirely {\em local\/} to the
block of bindings in which it appears, and it is reentrant,
\ie\ each instance of the block has its own barrier.  This not only
makes them relatively easy to use, but they are also implemented very
efficiently using ``synchronization trees'' (we do not have space to
go into details here).

\subsection{M-structures in Algebraic Types}
As another example of an M-structure, consider a polymorphic list
where each tail is updatable.  The following type declaration defines
such a list, where ``{\cf *0}'' is a type variable and ``{\cf !}''
denotes an updatable field (called an {\em m-field}):

\beginid
type mlist *0 = MNil | MCons *0 !(mlist *0) ;
\endid

Although Id has pattern-matching on algebraic types, one usually does
not use pattern-matching for types with m-fields, since
pattern-matching and imperatives do not mix well.  Thus, the fields of
an algebraic type may also be selected using record syntax, with field
names derived from the constructor and the field position.  Ordinary
fields, such as the head of the cons cell above, are selected using
``dot'' notation, \eg\ {\cf x.MCons\_1}.  M-fields are taken using
``bang'' notation in an expression, as in {\cf x!MCons\_2}.  A new
value {\cf v} may be put into an empty m-field using the statement:

\beginid
x!MCons_2 = v
\endid
Type-checking ensures that m-fields and ordinary fields are accessed
with the correct notation.

To compare the M-structure list with a functional list, consider the
problem of inserting an integer {\cf x} into a set {\cf ys}, taking
care not to insert duplicates.  In the following functional solution,
the set is represented as a list of integers and pattern matching is
used:
\newpage
\beginid
typeof insert_f = (list int) -> int -> (list int) ;
\null
def insert_f Nil    x = x:Nil
 |  insert_f (y:ys) x = if (x == y) then
                          ys
                        else
                          y:(insert_f ys x) ;
\endid
Using record syntax instead of pattern matching, {\cf insert\_f} is:

\beginid
def insert_f ys x = if (Nil? ys) then
                      Cons x Nil
                    else if (x == ys.Cons_1) then
                      ys
                    else
                      Cons ys.Cons_1 (insert_f ys.Cons_2 x) ;
\endid
For comparison, the following solution uses M-structure lists:

\beginid
typeof insert_m = (mlist int) -> int -> (mlist int) ;
\null
def insert_m ys x = if (MNil? ys) then
                      MCons x MNil
                    else if (x == ys.MCons_1) then
                      ys
                    else
                      { ys!MCons_2 = insert_m ys!MCons_2 x ; 
                      In
                         ys } ;
\endid
The first two conditional clauses of {\cf insert\_m} mimic the
functional solution.  In the third clause, we take the tail of the
list, insert {\cf x} into it and put it back, and we {\em return the
original list\/}.  Note that {\cf insert\_m} is strict in {\cf ys}
(due to the conditional), so the take and put are properly ordered.
The advantage of this program over the functional version is that it
takes $O(1)$ heap store per insertion, instead of $O(n)$, where $n$ is
the length of the list.

Under non-strict semantics, {\cf insert\_f} has the attractive
property that in the last line, the new cons cell can be returned even
while we are inserting {\cf x} into its tail.  Thus, multiple
insertions can be ``pipelined'', \ie\ a second insertion can run
closely behind the first, automatically synchronizing on empty slots.

Note that {\cf insert\_m} has the same kind of ``pipeline''
parallelism as {\cf insert\_f}.  In the last line, non-strictness
allows us to return {\cf ys} immediately.  If a second insertion is
attempted immediately, it can run closely behind the first, blocking
on empty fields (due to takes) in the same manner as {\cf insert\_f}
blocks on empty fields.

However, there is an interesting subtlety here.  Consider the
following two near-identical fragments:
\beginid
zs = insert_f ys x1 ;             zs = insert_m ys x1 ; 
ws = insert_f zs x2 ;             ws = insert_m zs x2 ;
\endid
and assume that neither {\cf x1} nor {\cf x2} is present in {\cf ys}.
In the functional case, despite the pipelined behavior, {\cf x2} is
guaranteed to be inserted behind {\cf x1}.  The second {\cf insert\_f}
can never ``overtake'' the first; if it tried to run faster, it would
block at some point, waiting for a result from the first {\cf
insert\_f}.

In {\cf insert\_m}, however, it is possible for the second insertion
to overtake the first, inserting {\cf x1} behind {\cf x2}.  The reason
is that in the parallel block in the last {\cf else} clause, the first
{\cf insert\_m} may return {\cf ys} before it takes the {\cf MCons\_2}
field.  Thus, when given {\cf ys}, the second {\cf insert\_m}
``races'' with the first traversal to take of this field, and may
potentially overtake it.  If we want to prevent this overtaking, we
have to delay returning {\cf ys} until the take completes.  This can
be accomplished with a barrier:

\beginid
def insert_m ys x = if ...
                      ...  
                    else ... 
                      ...
                    else
                      { ys' = ys!MCons_2 ;
                        --- 
                        ys!MCons_2 = insert_m ys' x ;
                      In
                        ys } ;
\endid
Note that this expression does not wait for the put to take place
before returning {\cf ys}--- that would make the insertion strict,
eliminating pipelined behavior completely.

This subtlety highlights important differences between M-structures
and their functional counterparts.  First, atomicity is clearly a
weaker property than determinacy.  In the above example, both the
M-structure and functional solutions are correct (neither make duplicate
entries); however, the M-structure solution admits more parallelism
through overtaking.  Second, the M-structure solution can be modified
to provide the sequencing property of the functional solution without
the additional storage overhead.  Finally, reasoning about the
interaction of several concurrent operations is more
difficult for M-structures than functional data structures.  We
address this issue in Section \ref{discussion}.




\bigskip

To conclude our discussion of the Id language and semantics, we make
the following observation.  In most approaches to parallel
computing, one starts with a sequential language and adds parallel
annotations.  This is true even amongst functional languages, \eg\ the
``future'' annotation \cite{Halstead85} and the ``spark'' annotation
\cite{Clack86a}.  In contrast, we go in the opposite direction:
we start with an implicitly parallel language and add
sequentialization only where necessary.  The degree to which we expose
and exploit parallelism is thus much more aggressive.

% ----------------------------------------------------------------

\subsection{Our Experiments}

To determine the validity of our claims, we compare several Id
programs written in a functional style (Approach A) against programs
using M-structures (Approach C).  These programs and our analysis are
presented in the next two sections.

We evaluate the programs in several ways.  First, 
we compare them subjectively in terms of declarativeness, \ie\
how well the structure of the program mirrors the structure of the
problem.   Second, we compare their efficiency in terms of storage
use and number of instructions executed.  Finally, their parallelism
is compared.  Since the parallelism exhibited by a program depends on
many factors, this last measurement deserves some explanation.

Id programs compile into dataflow
graphs, which constitute a parallel machine language (a partial order
on instructions).  The dataflow graphs respect the non-strict
semantics and parallel evaluation order describe earlier in this
section.  The performance of these programs is measured on GITA, which
is a dataflow simulator instrumented to take ``idealized'' performance
measurements.\footnote{GITA is part of the ``Id World'' programming
and simulation environment which has been in use at MIT and elsewhere
since 1986.}
The GITA simulator executes dataflow graphs under the following
idealized assumptions:
\begin{itemize}

\item
No limit on the number of instructions that can be executed in parallel.

\item
An instruction is executed as early as possible, \ie\ as soon as all
inputs are available.

\item
All instructions, including storage allocation ``instructions'', take 1 unit of time.

\item
No delay in communicating the output of one instruction to the input
of another.

\end{itemize}
The purpose of idealized simulation is to give an upper bound on
achievable performance, unconstrained by machine-specific
characteristics, such as the number of processors, available memory,
or scheduling policy.  One important measure of idealized performance
is the parallelism profile.  This profile charts the number of
parallel operations against time.  Given the above
assumptions, the parallelism profile
exhibited under GITA describes the  ``inherent'' parallelism of
a program, \ie\ the program's limit of achievable
parallelism.  In this paper, we summarize these profiles as the
average parallelism, which is the number of instructions divided by
the time to completion.

Note that a major idealization in GITA is that each heap allocation 
takes one instruction.  This hides the additional overhead of
heap management encountered
in a real system, such as garbage collection and initialization.  
In addition, storage management in a parallel system
may also perform the task of load balancing.
Thus, programs requiring more storage will, in
fact, require more instructions than indicated by idealized
performance measurements.  

% ================================================================

\section{Histogramming a tree of samples}

\label{example1}

% ----------------------------------------------------------------

Consider the problem of histogramming numbers in the leaves of a tree.
Given a tree $T$ of numbers, where each number is in
the range 1 to 5, the histogram $H$ is an array of 5 elements
such that $H_i =$ the number of leaves containing number $i$.

This problem statement is a highly abstracted account of MCNP, an
application program used by over 350 organizations in diverse
industries such as oil exploration, automobiles, medical imaging,
\etc\ \footnote{Los Alamos National Laboratory is developing a
comprehensive version of MCNP in Id under the direction of Olaf
Lubeck.} The program models the diffusion of subatomic particles from
a radioactive probe through the surrounding material, using Monte
Carlo simulation.  For each original particle, the program follows it
through events in its lifetime, such as motion in some direction,
collision with a material boundary or another particle,
\etc\ The tree structure arises because particles may split into two
(and recursively, those particles may split again), after which the
simulation follows each particle separately. 
When a particle finally dies, \ie\ reaches a leaf, some of its
properties are collected in various histograms, such as final position
and energy.  MCNP has eluded easy parallelization in all conventional
programming models, but is ``embarassingly parallel'', because the
tree may have thousands of branches, and the events in a particle's
life are decided purely locally, based on the toss of a coin.


In MCNP, no tree data structure is actually constructed.  Rather,
intermediate arguments and results are passed through the call/return
tree.  In our histogram example, the histogramming functions
traverse a previously constructed tree, with the following type
definition:

\beginid
type tree = Leaf int | Node tree tree ;
\endid

The cost of creating this tree is not included in the measurements.

% ----------------------------------------------------------------

\subsection{HA1: A Functional Solution}

This program builds an initial array H0 containing 0 everywhere, and
then performs a right-to-left traversal of the tree.  At each leaf,
the $i$'th element of the array is incremented by 1,
where $i$ is the number of the leaf. 
Since the functional solution may not use imperatives, incrementing
this element requires building a  new array, identical to the original,
except that the $i$'th location is incremented.  Here is
the code:

\beginid
typeof hist = tree -> (array int) ;
\null
def hist T = { H0 = {array (1,5) of
                     | [j] = 0 || j <- 1 to 5 }
             In
               traverse T H0 } ;
\null
typeof traverse = tree -> (array int) -> (array int) ;
\null
def traverse (Leaf i)   H = incr H i
 |  traverse (Node L R) H = traverse L (traverse R H) ;
\null
typeof incr = (array int) -> int -> (array int) ;
\null
def incr H i = {array (1,5) of
                | [j] = if (i==j) then H[j]+1 else H[j] || j <- 1 to 5 } ;
\endid

% ----------------

\subsubsection*{Critique}

In principle, the increments can be
done in any order.  However, since each increment creates a new array,
the array must be ``threaded'' sequentially through the traversal.
Threading requires that the recursive calls to {\cf traverse} be
composed, which imposes a particular order on the increment operations.  
In the original MCNP problem, threading is even worse, since many
arguments and results are passed through the call/return tree.
The threading required by functional programming obscures the
independent nature of the accumulations.

This program also suffers from storage overhead, since the histogram
array is copied at each leaf of the tree.  Each copy of the
array requires 5 loads and stores, while the problem requires only a
single load and store per increment.  Note that techniques for
eliminating copying in functional programs, such as
single-threadedness analysis and abstract reference counting, might
determine that all the updates could occur in place.  However, these
analyses assume a {\em sequential\/} order of execution, and so
preclude parallel execution.

% ----------------------------------------------------------------

\subsection{HA2: A Functional Solution using Accumulators}

In this example, we build an accumulator array with each element
initialized to zero.  The accumulation draws from a list produced by
{\cf traverse}, which collects all the numbers in the leaves of the
tree.  Here is the code:


\beginid
typeof hist = tree -> (array int) ;
\null
def hist T = {array (1,5) of
              | [j] = 0 || j <- 1 to 5
              accumulate (+)
              | i = 1 || i <- traverse T } ;
\null
typeof traverse = tree -> (list int) ;
\null
def traverse T = aux T Nil ;
\null
typeof aux = tree -> (list int) -> (list int) ;
\null
def aux (Leaf i)   is = i:is
 |  aux (Node L R) is = aux L (aux R is) ;
\endid

% ----------------

\subsubsection*{Critique}

The use of an accumulator for the histogram eliminates the need to
copy the array.  In fact, the accumulator is quite declarative and modular:	
for each $i$ drawn from the list of leaf numbers, 
the  $i$'th element is incremented by one.
The functions {\cf traverse} and {\cf aux} still require threading to
construct the list of leaf numbers.  However, non-strictness allows
this list to be constructed in parallel and 
``piped'' into the accumulator.

Although an improvement, the intermediate list read by the accumulator
incurs storage overhead and overspecifies the order of accumulations.
Accumulators use lists for modularity and composition; eliminating the
list through compiler analysis requires global analysis to thread the
accumulator through the generator function and its descendants.  

The use of accumulators in an early version of the MCNP program
corroborates these observations: the intermediate list complicated the
program and introduced inefficiencies.
The M-structure solution, presented next,
retains the declarativeness of accumulators
and eliminates the need for an intermediate list.


% ----------------------------------------------------------------

\subsection{HC: An M-structure Solution}

In this solution, the histogram $H$ is represented as an M-array
initialized to zero.  The
{\cf traverse} function recursively passes $H$ down to all leaves in
parallel.   Each leaf (containing $i$) atomically increments element
$H_i$ by taking the element, adding one, 
and putting it back.  A sequential barrier is used to ensure
that $H$ is not returned until {\cf traverse} completes.
(Recall that this  barrier is implicit in accumulators, since
they may not return until all accumulations have been performed.)
The M-structure program is below:

\beginid
typeof hist = tree -> (m_array int) ;
\null
def hist T = { H = {M_array (1,5) of
                    | [j] = 0 || j <- 1 to 5 } ;
                _ = traverse T H ;
               ---                                      % sequential barrier
             In
               H } ;
\null
typeof traverse = tree -> (m_array int) -> void ;
\null
def traverse (Leaf i)   H = { H![i] = H![i] + 1 }
 |  traverse (Node L R) H = { _ = traverse L H ;
                              _ = traverse R H } ;
\endid

Bindings of the form  ``{\cf \_ = e}'' are used to execute {\cf e} for
its side-effects and discard its result.   Let blocks with no body
expression return a meaningless value of type {\cf void}, and are
executed solely for side-effect.  

% ----------------

\subsubsection*{Critique}

This program requires no threading since the accumulation
is performed by side-effects.  Thus, the recursive calls to {\cf
traverse} are not composed, and the order of accumulations is  not
overspecified.  The atomicity of each accumulation is
is {\em locally\/} specified by the take and put operations and
their implicit synchronization.  In contrast to the functional
programs, only storage for the result histogram is required, and
each accumulation requires only a single 
load and store (take and put).

\subsection{Other Functional Solutions}
Several techniques for improving the performance of parallel
and functional programs have been developed, such as parallel
combining trees and tree-structured arrays.
These techniques were used in three other functional solutions,
which are summarized below:
\begin{description}

\item{\bf HA3: Tree Accumulation.}
The program recursively descends in parallel to every leaf. At a leaf
containing, say, 2, we produce the array {\cf [0 1 0 0 0]}.  At each
node, we add the arrays from the two subtrees and return the new
array. Thus, the top node produces the sum for the whole tree.
Although this eliminates threading, its storage requirements are
double that of HA1.

\item{\bf HA4: Parallel Traversal.} 
The entire tree is traversed five times in parallel (once for each
element in the histogram). The $i$'th traversal
uses parallel tree accumulation to sum the number
of leaves containing $i$.  Since this accumulation
computes an integer, it requires no additional storage.  
Finally, the histogram is
constructed by storing the five sums into an array, which is returned.
Although this has no threading and minimal storage, it executes a
large number of instructions, because the entire tree is traversed for
each element of the histogram.


\item{\bf HA5: Tree-Structured Histogram.}
The program is a modification of HA1, replacing the
histogram array by a balanced tree.  This reduces memory and
instruction overhead by copying a single path of the tree
($O(\log b)$ instead of $O(b)$, where $b$ is the number of elements in
the histogram).  Note that copying a path requires several memory
allocations rather than one, as well as conditionals to route each
increment to the appropriate leaf.  Therefore, this solution is less
efficient than HA1 for small histograms.  Even with large histograms, 
threading still obscures the code and
overspecifies the order of accumulations.

\end{description}



% ----------------------------------------------------------------

\subsection{Experimental results}

We ran the above programs on a full binary tree of depth 10, \ie\ 1024
leaves with an (almost) equal number of 1's, 2's, ... and 5's.  The
results are shown below:

\begin{center}

\begin{tabular}{|l|r|r|r|r|}
\hline
Program &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Avg.}         &
\multicolumn{1}{l|}{Heap}         \\
version                           &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  &
\multicolumn{1}{l|}{store}        \\

                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  &
\multicolumn{1}{l|}{used (words)} \\
\hline
HA1     &      199,757 &    1,452 &       138 &  9,250 \\
HA2     &       72,847 &    7,324 &        10 &  2,100 \\
HA3     &      325,472 &      238 &      1368 & 18,423 \\
HA4     &      266,223 &      195 &      1365 &      9 \\
HA5     &      253,370 &   28,833 &         9 & 11,301 \\
HC      &       60,496 &      589 &       103 &      9 \\
\hline
\end{tabular}

\end{center}

% \subsubsection*{Observations}
\subsubsection{Observations}

{\em Declarativeness:} We believe the M-structure solution HC is more
declarative than the functional solutions, since it does not
overspecify accumulation order by threading.

{\em Instruction count\/}: HC requires
the fewest number of instructions.  The instruction overhead of copying in
solutions HA1, HA3, and HA5 is significant when
compared to HA2 (accumulators) and HC.  The high instruction
count in HA4 is due to the duplicate traversals of the tree.

{\em Heap Store Used\/}: Copying intermediate data structures in the
functional solutions dominate their storage profiles.  Imperative
updates, as used in HC, allow storage use to be
reduced by three orders of magnitude.  

{\em Parallelism\/}: HA3 and HA4 have more parallelism
than the other programs, but this is mostly due to redundant
computation, such as copying arrays or multiple tree traversals.
The poor parallelism in HA2 and HA5 comes from overserialization:  the
intermediate list in the case of accumulators, and copying the path of
the tree in HA5.  The parallelism in HC is limited by synchronization
of take and put instructions.  Because they are atomic, the number of
parallel increment operations is bounded by the size of the histogram.
Parallelism in this example exceeds 5 because these increments are
overlapped with the tree traversal.


In summary, the M-structure solution to the histogramming problem
is highly declarative, and combines instruction efficiency and low
storage use with significant parallelism.

% ================================================================

\section{A Graph Traversal Problem}

\label{example2}

% ----------------------------------------------------------------
For a second comparison of functional and M-structure programs,
consider a simple graph traversal problem.
Suppose we are given a directed graph structure, \ie\ an
interconnection of nodes:
\beginid
type gnode = GNode int int (list gnode) ;
\endid
The first {\cf int} field contains a unique identifier for the node, the
second {\cf int} field contains some numeric information, and the list
of nodes represents the list of neighbors (possibly empty) of the
current node.

The problem is this: given a node $A$ in a graph, compute {\cf
rsum($A$)}, the sum of the integer information in all nodes reachable
from $A$.


The unique identifiers in the nodes highlight an important difference
between graphs and trees: graphs can have
can have shared substructures and cycles.  Graph
traversals need to take this into account to avoid repeated traversals
of nodes and subgraphs.  Therefore, traversal programs must be able to
test equality between nodes.  The notion of object equality differs between
functional and imperative languages, but is not central to the issues
in this paper.  For clarity, the unique ID field in the graph nodes
will be used to determine node equality.


% ----------------------------------------------------------------

Traditional graph traversal algorithms rely on ``marking'' visited
nodes to avoid repeated traversals.  For familiarity, we will begin this
section with two M-structure programs that use imperative operations to 
mark visited nodes.  This is followed by the functional solution and
experimental results.

\subsection{GC1: A Simple M-structure Solution}

The traditional imperative solution to this problem involves extending
the {\cf node} type to contain a {\em mark\/} field, which is used to
avoid repeated traversals of shared subgraphs.  We assume that the
mark field is initially set to {\cf False}.  The following program
expresses this solution:

\beginid
type gnode = GNode int int (list gnode) !bool ;
\null
def rsum nd = if (marked? nd) then
                0
              else
                nd.GNode_2 + sum (map rsum nd.GNode_3) ;
\null
def marked? nd = { m = nd!GNode_4 ;       % take the mark field
                  ---                     % sequentialize
                   nd!GNode_4 = True ;    % put True in mark field
                 In
                   m } ;
\endid
Note that in this solution, the unique ID field is not required.

% ----------------

\subsubsection*{Critique}

The solution is very clear. The only subtle point is the
atomicity of the {\cf marked?} predicate.  The value of the 
mark field is taken and returned, and set to {\cf True} regardless of
its previous value.  Since the mark field is set to {\cf True} the
first time the node is visited, the node will be counted only once.
As described earlier, the serialization barrier between the take and
put guarantee that they happen in the correct order.

While this solution corresponds to most textbook algorithms, it has
two drawbacks:

{\em Mark initialization\/}: We assumed that the marks in the graph
were initialized to {\cf False} before the traversal began.  But, how
do we achieve this?  Traditionally, we have some {\em independent\/}
access to all the nodes, such as an array or set of all nodes, and we
iterate through this collection, resetting all marks.  Note that
resetting the marks cannot be overlapped with the traversal
algorithm---this easily doubles the cost of the algorithm.  Further,
if the graph is large compared to the region traversed, resetting
all marks may be more expensive than the traversal.

{\em Multiple traversals\/}: Suppose we are given two nodes $A$ and
$B$ and want to compute the reachable sum from each of them, in
parallel.   GC1  cannot be used for this, since the marks from the $A$
and $B$ traversals may interfere, \ie\ nodes marked by 
$A$'s traversal will not be counted by the traversal from $B$, and
vice versa.

These drawbacks can be overcome by a  simple
extension of the ``mark field'' idea.  Here, each traversal
carries  an additional parameter, a unique {\em traversal
identifier\/}.   Rather than marking nodes with a boolean,
each node contains a list of traversal identifiers indicating who has
visited the node.  The {\cf marked?} predicate checks and updates this
list.  

This solution allows multiple traversals to occur in parallel, since they
have distinct traversal IDs and will not interfere.  Also, node marks
do not have to be reset, since a brand
new traversal ID is issued for each traversal.  
However, the performance of this solution worsens as
more and more traversals are performed, creating unused IDs that
slow the {\cf marked?} predicate and occupy storage.  Because of
this weakness, we will not pursue this idea any further.



% ----------------------------------------------------------------

\subsection{GC2: A Solution Allowing Multiple Traversals}

A better solution that allows multiple traversals uses a separate
{\cf visited} table to keep track of nodes already traversed.  
Rather than marking nodes directly, this table contains the unique IDs of
visited nodes, and is updated as each new node is encountered.
The original definition of graph nodes (without a mark field) is used:

\beginid
type gnode = GNode int int (list gnode) ;
\endid

Here is the code for the reachable sum:

\beginid
def rsum nd = { visited = mk_empty_table () ;
\null
                def aux (GNode x i nbs) =
                  if (member?_and_insert  visited  x) then
                    0
                  else
                    i + sum (map aux nbs) ;
              In
                aux  nd } ;
\endid
The {\cf member?\_and\_insert} function is analogous to the {\cf
marked?} function in GC1:  it returns a boolean indicating whether
{\cf x} is present in the {\cf visited} table, inserting {\cf x}
in the table if it is not.  

\subsubsection*{Critique}

The version of {\cf rsum} given in GC2 is quite similar to GC1.  There
is no threading, and marking code is localized.  The main difference
between the programs is the modularity supplied by the {\cf visited}
table.  It is shared by all calls to {\cf aux}, but does not require
threading or modification to the graphs.  Further, its storage can be
released after the traversal.

\subsubsection{A Parallel Hash Table}
We can implement the {\cf visited} table in a number of ways.  A
parallel hash table is a good candidate, since it allows $O(1)$ access
to the elements of a dynamically created set.  An
empty hash table of size $N$ (for some suitable constant $N$) is
constructed using an m-array comprehension:

\beginid
def mk_empty_table () = {M_array (1,N) of
                         | [j] = MNil || j <- 1 to N} ;
\endid
Each bucket of the array is initialized to an empty {\cf mlist}.

As with the {\cf marked?} function in the GC1 solution, the
{\cf member?\_and\_insert} function must execute atomically to avoid
duplicate traversals.  This function tests whether an integer {\cf x}
is in the hash table and, if not, inserts it:

\beginid
typeof member?_and_insert = (m_array (mlist int)) -> int -> bool ;
\null
def member?_and_insert  table  x =
  { (l,u) = bounds table ;
    j = hash l x u;
    (b,ys') = member?_and_insert_list table![j] x ;
    table![j] = ys' ;
  In
    b } ;
\endid
In the first line in the block we extract {\cf l} and {\cf u}, the
lower and upper index bounds of the table, and in the second line we
hash the given integer index {\cf x} into an index {\cf j} in the
range {\cf l} to {\cf u} (using some unspecified hash function). Then,
we take the set of integers at index {\cf j} and uses the
{\cf member?\_and\_insert\_list} function to  test if {\cf x} is in
that set and insert it if not.  
Finally, the (possibly) new set is  put back and the
boolean result returned.

Note that the list function that tests for membership, followed by
conditional insertion, is {\em not\/} a simple composition of the {\cf
member} and {\cf insert} functions on m-lists.
The elements of the list must be tested and inserted in a single
scan of the list to ensure atomicity.  Otherwise, a node may be seen as
unmarked by two processes, resulting in redundant traversals.

We modify our {\cf insert\_m} function from Section 2.5 to perform
this simultaneous test for membership and insertion:
\newpage
\beginid
typeof member?_and_insert_list = (mlist int) -> int -> (bool,(mlist int)) ;
\null
def member?_and_insert_list ys x =
  if (MNil? ys) then
    (False, MCons x MNil)
  else if (x == ys.MCons_1) then
    (True,ys)
  else
    { (b,ys') = member?_and_insert_list ys!MCons_2 x ;
      ys!MCons_2 = ys' ;   
    In      
      (b,ys) } ;

\endid

Note that the hash function can be applied to two integers {\cf x1}
and {\cf x2} in parallel.  If they hash to different indices, there is
absolutely no interference between the two calls.  Even if they hash
to the same index, they may ``pipeline'' as discussed earlier.

% ----------------

%
\subsubsection*{\bf GC2': A Mark Array} 
We can improve the implementation of the {\cf visited} table even
further if we know that the unique identifiers in the graph nodes are
in some contiguous range, say 1 to $N$.  In this case, the table can
be implemented as an array of booleans, instead of a hash table, \ie\

\beginid
def mk_empty_table () = {m_array (1,N) of
                         | [j] = False || j <- 1 to N} ;
\null
def member?_and_visited table x = { b = table![x] ; 
                                    --- 
                                    table![x] = True 
                                  In
                                     b } ;
\endid

Note that in the pure functional program described next, the $O(1)$
access time of the hash and mark tables cannot be exploited.
Implementing the {\cf visited} table as a balanced binary tree is the
best we can do.


\subsection{GA1: A Functional Solution}

Since nodes cannot be imperatively marked, the functional solution
also uses a {\cf visited} table to keep track
of nodes that have already been  traversed.  This table is
threaded through the traversal, as shown in the following 
program:
\newpage
\beginid
def rsum nd = { visited = TEmpty ;
\null
                def aux (s,visited) (GNode x i nbs) =
                    if (member? x visited) then
                      (s,visited)
                    else
                      {  visited' = insert visited x ;
                      In
                         foldl  aux  (s+i,visited')  nbs } ;
\null              
                (s,visited') = aux (0,visited) nd
              In
                s } ;
\null
\endid
The function {\cf foldl} is similar to {\cf map}, but passes partial
results (the partial sum and visited table) to each successive call of
{\cf aux}.   Here is the code for {\cf foldl}:
\beginid
def foldl f z Nil    = z
 |  foldl f z (x:xs) = foldl f (f z x) xs ;
\endid

The {\cf visited} table can be implemented as an ordered binary tree,
with $\log n$ time for the {\cf member?} and {\cf insert} functions,
assuming the tree is balanced:

\beginid
type tree = TEmpty | TNode int tree tree ;
\null
def member? TEmpty        x = False
 |  member? (TNode y L R) x = if (x == y) then
                               True
                              else if (x < y) then
                                member? L x
                              else
                                member? R x ;
\null
def insert TEmpty        x = TNode x TEmpty TEmpty
 |  insert (TNode y L R) x = if (x == y) then
                               (TNode y L R)
                             else if (x < y) then
                               (TNode y (insert L x) R)
                             else
                               (TNode y L (insert R x)) ;
\endid


% ----------------

\subsubsection*{Critique}

The {\cf rsum} program is obscured by the ``threading'' the {\cf
visited} table through the traversal.  Again, threading overspecifies
the order in which the traversal is made; here, the order of
insertions is determined by the function {\cf foldl}.  Conceptually,
one imagines all outward edges from a node being explored in parallel,
with a shared subnode being explored only by the first traversal that
happens to arrive there (we don't care which one).\footnote{ Readers
who are familiar with parallel graph reduction will recognize that
this is exactly what happens in a parallel graph reducer--- a shared
node is evaluated by the first process that arrives there, which also
marks it as ``in progress'', so that later-arriving processes will not
duplicate the work.}

Note that here, unlike the histogram example, sharing is critical
to ensure a polynomial time algorithm.  Therefore, threading is
unavoidable in purely functional solutions.
In more complex problems, the threading required by functional
programming further complicates the solution, adding extra parameters
and return values and imposing unnecessary serialization.


The functional solution also introduces storage overhead.
Each {\cf insert} rebuilds the {\cf visited} table along the
path from the newly inserted leaf back to the root, allocating new
tree nodes along the way.  The total storage cost for the table over
the complete graph traversal can therefore vary from $O(n \log n)$ to
$O(n^2)$, depending on how well the tree is balanced.
Including tree rebalancing operations introduces overhead that
may be recouped over many operations.

% ----------------------------------------------------------------


% ----------------

\subsection{Experimental Results}

We ran tests on our simulator, running four versions of {\cf rsum} on
four graphs.  The graphs each contained about 512 nodes, but differed
widely in their topologies (amount of sharing).  The four versions of
{\cf rsum} were:
\begin{quote}
\begin{tabular}{|l|p{4in}|}
\hline
GA1       & The functional program with a {\cf visited} table
                       implemented as an ordered binary tree. \\
\hline
GC2  & The M-structure program with a {\cf
                       visited} table implemented as a hash table of size 523. \\
\hline
GC2' & The M-structure program with a {\cf
                       visited} table, implemented as an array of booleans. \\
\hline
GC1 & The M-structure program using mark
                       fields in graph nodes. \\
\hline
\end{tabular}
\end{quote}
For the functional version, the unique identifiers in the graph nodes
were randomly generated so that the binary tree {\cf visited} table
would be roughly balanced, in order to show the numbers for the
functional program in the best possible light.  Random ID generation
was also used for the hash and marks version, though it does not
really matter for these versions.  For the ``array'' version, IDs
were integers in the range of 1 to $n$, the number of nodes in the
graph, and the array of marks had the same index range.

The fundamental difference in heap store use for the four programs is
in the {\cf visited} tables.  We modified the programs slightly from
the text of the paper in order to measure this, \ie\ to separate heap
usage for the {\cf visited} table from heap usage for closures in
higher order functions and tuples for multiple results.  These changes
do not affect the total instruction counts or parallelism very much.

The cost of originally building the graphs (storage and instructions)
is not included because the graphs were built in a separate invocation
before the application of {\cf rsum}.

Figures \ref{graph-g0} through \ref{graph-g3} show the four graphs and
the measurements for the four programs.

% ----------------

\begin{figure}[htbp]
\fbox{%
  \parbox%
   {\illuswidth}
   {\illustration{graph-g0}{1.6 true in}

\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
Program                           &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Avg.}         &
\multicolumn{1}{l|}{Heap}         \\
version                                  &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  &
\multicolumn{1}{l|}{store}        \\
                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  &
\multicolumn{1}{l|}{used (words)} \\
\hline
GA1       &      480,123 &   90,605 &         5.3 & 15,934 \\
GC2 &      102,244 &    4,280 &        23.9 &  2,072 \\
GC2' &       55,843 &    2,743 &        20.4 &    524 \\
GC1 &       48,002 &      412 &       116.5 &      0 \\
\hline
\end{tabular}
\end{center}

     \caption{%
        \label{graph-g0}
        {Reachable Sum on Graph0 (511 nodes).}
             }
    }}
\end{figure}

% ----------------

\begin{figure}[htbp]
\fbox{%
  \parbox%
    {\illuswidth}
    {\illustration{graph-g1}{2 true in}

\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
Program                           &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Avg.}         &
\multicolumn{1}{l|}{Heap}         \\
version                                  &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  &
\multicolumn{1}{l|}{store}        \\
                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  &
\multicolumn{1}{l|}{used (words)} \\
\hline
GA1       &      594,323 &  124,276 &        4.8  & 17,305 \\
GC2  &      177,062 &    9,271 &       19.1  &  2,959 \\
GC2' &       95,501 &    9,102 &       10.5  &    524 \\
GC1 &       84,078 &    3,728 &       22.6  &      0 \\
\hline
\end{tabular}
\end{center}

     \caption{%
        \label{graph-g1}
        {Reachable Sum on Graph1 (515 nodes).}
             }
    }}
\end{figure}

% ----------------

\begin{figure}[htbp]
\fbox{%
  \parbox%
    {\illuswidth}
    {\illustration{graph-g2}{1 true in}

\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
Program                           &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Avg.}         &
\multicolumn{1}{l|}{Heap}         \\
version                                  &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  &
\multicolumn{1}{l|}{store}        \\
                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  &
\multicolumn{1}{l|}{used (words)} \\
\hline
GA1       &      587,873 &  123,434 &        4.8  & 16,998 \\
GC2  &      130,188 &   22,527 &        5.8  &  2,068 \\
GC2' &       68,933 &   12,799 &        5.4  &    524 \\
GC1 &       59,902 &   11,596 &        5.2  &      0 \\
\hline
\end{tabular}
\end{center}

     \caption{%
        \label{graph-g2}
        {Reachable Sum on Graph2 (511 nodes).}
             }
    }}
\end{figure}

% ----------------

\begin{figure}[htbp]
\fbox{%
  \parbox%
    {\illuswidth}
    {\illustration{graph-g3}{1 true in}

\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
Program                           &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Avg.}         &
\multicolumn{1}{l|}{Heap}         \\
version                                  &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  &
\multicolumn{1}{l|}{store}        \\
                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  &
\multicolumn{1}{l|}{used (words)} \\
\hline
GA1       &      549,169 &  103,917 &         5.3 & 18,550 \\
GC2  &      103,456 &   28,844 &         3.6 &  2,076 \\
GC2' &       56,385 &   10,359 &         5.4 &    524 \\
GC1 &       48,518 &    8,808 &         5.5 &      0 \\
\hline
\end{tabular}
\end{center}

     \caption{%
        \label{graph-g3}
        {Reachable Sum on Graph3 (515 nodes).}
             }
    }}
\end{figure}

% ----------------

% \subsubsection*{Observations}
\subsubsection{Observations}

{\em Parallelism\/}: Graph0 and Graph1 have a high degree of
parallelism, \ie\ there is much branching without sharing;  Graph2 is
not very parallel (much branching, but also much sharing), and
Graph3 is also not very parallel (not much branching).  Nevertheless, the
functional program is unable to exploit the parallelism in Graph0 and Graph1,
because the threading of the {\cf visited} table forces it to be
practically sequential.  All the other programs, however, were able to
exploit the additional parallelism of those graphs.

{\em Instruction count\/}: The instruction counts for the functional
program GA1 is highest, by over a factor of 10 from the most efficient
version (marks).

{\em Heap Store Used\/}: The $O(n {\log}(n))$ heap store cost for the
{\cf visited} table in the functional program is apparent--- it uses
close to 10 times more heap store than its nearest rival (the hash
program GC2).  GC2 takes about 523 words for the hash array, plus 3
words (one cons cell) for each of the about 512 entries in the table,
making a total of a little over 2000 words.  The mark array GC2'
program takes exactly 524 words for the array of booleans.  GC1, which
marks the nodes directly, allocates no store, but we should remember
that we have already paid one word extra per graph node for the mark
field, \ie\ a total of about 512 words.

Again, we point out that the functional program is being presented in
it best possible light because (a) we are charging only one
instruction for each heap allocation, and (b) we have set up the IDs
to keep the {\cf visited} tree balanced.

% ================================================================

\section{Discussion}

\label{discussion}

In this section, our work on M-structures is put in the context of
other work.  First, we describe our preliminary experiences validating
our simulation results on a real multiprocessor.  Next, M-structures
are briefly compared to other non-deterministic extensions to
functional languages.  Finally, a method for reasoning about
M-structure programs is outlined.

\subsection{Validation}

In order to ensure that our simulations are reasonably accurate, we
have also run all the above programs on Monsoon, a parallel machine
with 64-bit, 10MIPS dataflow processors and 4 MWord I-structure memory
units\cite{Papadopoulos90a}.  These processors are being built in
partnership with Motorola, Inc.  Our programs ran on a two-node
prototype; a sixteen-node machine is expected to be available in June,
1991.  The major unaccounted cost in our simulation is that of heap
allocation, since the simulator counts each heap allocation as a
single instruction.  In Monsoon, therefore, instruction counts are
higher than in our simulations, but the overall trends are the same
(the Monsoon figures are too preliminary to publish at this time).

\subsection{Nondeterminism in Other Languages}

Since Approach C admits non-deterministic, parallel programs, it is
interesting to compare it to Approaches A and B extended to allow
non-determinacy. Several non-deterministic extensions have been
proposed for Approach A, such as amb\cite{Turner87a},
streams\cite{Stoye86}, and managers\cite{ArvindBrock,Arvind77a}.  To
retain the flavor of functional programming, these solutions are {\em
process-oriented}: many processes share information over an {\em
implicit} communication channel.  This channel merges updates and
synchronizes accesses.  Each process can then be viewed as a state
transformation function that maps successive values on the shared
channel.  Thus, each process can be analyzed as a function, with only
the aggregate behavior producing non-determinism.

Approach B allows imperative operations but ensures determinacy through
a sequential, strict control paradigm.  Extensions for parallelism, 
such as fork and join in Scheme and ML, require explicit synchronization
constructs to be used by the programmer.  Proving such programs correct
is difficult, and much of the original declarativeness of the program is
destroyed.

M-structures are a {\em data-oriented} approach to non-determinism, which
provides the efficiency of Approach B.  In addition, M-structures provide
the implicit synchronization, which  guarantees the atomicity of operations on 
individual elements of data structures. This fine-grained atomicity
allows for substantial parallelism in programs that share data
without additional synchronization complexity.  The result is highly
declarative, efficient programs.  

\subsection{Reasoning about M-structure Programs}

The attractiveness of an implicitly parallel, non-strict language
like Id is that programmers can write parallel, determinate programs
without annotations or explicit synchronization.  Reasoning about
determinate Id programs follows in the traditions of functional 
programming: functions map expressions to values, and correctness
proved by equational reasoning. 

M-structures introduce indeterminacy, and thus cannot use equational
reasoning. Instead, the correctness of an M-structure program is 
related to the notion of serializability in databases.  That is,
correctness is defined in terms of the history of values held in an
M-structure cell.  In a correct program, the sequence of cell values
is a member of an allowed set of sequences.  Serializability is one
notion of correctness, requiring that any parallel execution
corresponds to some interleaving of its update operations.
Serializability ensures that M-structure updates appear atomic and
sequential.

Determining the possible histories of an M-structure cell requires an
operational understanding of Id.  The set of M-structure histories is
determined by the possible orderings of take and put operations on the
cell.  Since Id is an implicitly parallel language, the order of
operations is a partial order, formed by a precedence relation $\prec$
between operations.  That is, given operations $a$ and $b$ in program
$P$, if $a\prec b$, then $a$ will execute before $b$ under any correct
execution of $P$.   Precedence between two operations is
determined by three things:
data dependence, control constructs, and data structures.

Data dependence defines precedence between
strict operators.  For example, 

\beginid
{i = a+b;
 In
   i*i};
\endid

yields {\cf +$\prec$*}, since the multiplication is strict in the
result of the addition. 

Control constructs define precedence between a predicate and the
selected expression.  For example,
in the following {\cf if} expression,

\beginid
 if i==0 then
   i+1
 else
   i+2
\endid

the equality test precedes the addition in both arms, \ie\
{\cf ==$\prec$+}. 

Finally, M-structures define a precedence relation, since a
take is always preceded by some put. 
A formal description of precedence has been developed by the authors,
based on operational semantics for Id given in \cite{Ariola89a}.

We now outline a correctness proof of the histogram program HC that
uses M-structures.
We wish to show that each cell in the histogram contains the sum
of the number of leaves in the tree with its index.  We can prove 
this by showing that the histogram is initialized to 0, that each
leaf is reached once, and that each update is atomic.  Since the
tree traversal is a simple recursion,  the second step
can be proved by traditional inductive means.

First, let us address the atomicity of the updates.  When a leaf
is reached, the expression {\cf H![i] = H![i]+1} is evaluated.
This corresponds to a take, an addition, and a put.  Put and addition
are strict in their arguments, therefore {\cf take$\prec$+$\prec$put}.
M-structure synchronization guarantees that exactly one take 
operation will get a value after a put.  This value will be 
incremented and put back, as defined above, potentially satisfying
another take.  This continues until all increments complete.
Thus, the precedence of this expression, and M-structure
synchronization yield some interleaving of atomic updates.

To show that M-structure cells are initialized correctly.  When an
M-structure is allocated, its elements are initially empty; the
constructor (the array comprehension) initializes these elements by
putting a value in each element.  In this case, the allocate is
followed by a put with the value 0.  Since any take must be preceded
by a put, no increment operation will begin until the cell has been
initialized.

Therefore, the history of
histogram cell $i$ is

{\cf
alloc$\prec$put 0$\prec$take$\prec$+$\prec$put$\prec$take$\prec$
+$\prec$put$\prec\cdots\prec$put}

which always corresponds to a serialization of the update operations.
Since addition is commutative and associative, serialization is
sufficient to determine that the cell has the correct count after the
last put, regardless of the order of the increments.  As expected,
eager evaluation allows this proof strategy to use local
assertions about initialization and update operations.

Note that M-structure synchronization enforces this precedence
relation even if a take operation is invoked before a put operation,
or several takes are issued simultaneously.  The implicit
synchronization provided by M-structures allows the set of all
possible interleavings to be reduced to only the set allowed by
the precedence relation.  Proving the correctness of this set
depends on the application.

Reasoning about  M-structure programs
involving more than a single cell is more complex, but follows the
same principles.  In this case, atomicity involves synchronizing
several M-structure operations to prevent processes from interfering
and to avoid deadlock.  To aid the development of such programs, the
authors are developing constructs for encapsulating M-structure operations
to ensure atomicity.  Such encapsulation has been shown
to be useful elsewhere \cite{Burton,Monitors} for reasoning about parallel
programs that share state.

\section{Conclusion}

\label{conclusions}

Although the results presented in this paper may be viewed as a
recommendation to use Approach C in programming, it may also be viewed
as a challenge for the functional programming community to come
up with new purely functional notations and optimization analyses that
match the declarativeness and efficiency of Approach C.  There is some
precedent for this kind of development.  Some years ago, we proposed a
non-functional construct called ``I-structures'', showing how they
cleanly overcame certain limitations in expressive power and
efficiency in functional languages \cite{Arvind89b}.  This stimulated
much debate and research, leading to 
the purely functional ``array comprehension'' notation in Id,
which eliminates much of the need for I-structures.  Perhaps this paper on
M-structures can serve a similar role and lead to new developments in
pure functional languages.

% * Discuss how our fine grain parallelism and synchronization is no
% more expensive than in the functional case (people may not realize how
% synchronization takes place due to non-strictness in parallel
% functional programs).

% * Discuss why many of the conventional analyses: abstract
% interpretation, single-thread analysis ... will not work here.

% * More comparison with Approach B (ML + threads, Scheme + futures).
% Discuss difficulty of writing parallel programs with explicit
% parallelism.

% * Compare with approaches to have non-determinism in functional
% programs (functional operating systems)?
% ================================================================

\vspace{1.5cm}

{\bf Acknowledgements}: This paper describes research performed at the
Laboratory for Computer Science of the Massachusetts Institute of
Technology.  Funding for the Laboratory is provided in part by the
Advanced Research Projects Agency of the Department of Defense under
the Office of Naval Research contract N00014-89-J-1988.
Paul Barth is supported by a fellowship from Schlumberger Technology
Corporation. 
\bibliographystyle{abbrv}
\bibliography{m-structures}

\newpage

\tableofcontents

\end{document}
