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

\documentstyle{article}

\input{laktex}
\input{latex-defs}

% HERE BEGINS THE DOCUMENT
\smartspacing{1.6}

\begin{document}

\begin{center}
{\Large\bf M-Structures: Extending a Parallel, Non-strict, Functional Language with State\footnote{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, Rishiyur S. Nikhil and Arvind

\spacing{1}
MIT Laboratory for Computer Science\\
545 Technology Square\\
Cambridge, MA 02139\\
USA\\
barth@abp.lcs.mit.edu


\today


{\bf Abstract} \\
\begin{minipage}{5.5in}
\medskip
\spacing{1}
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.
In addition, functional programs have {\em implicit} parallelism:
simple compiler analysis can identify expressions that may evaluate in parallel
without additional programmer annotations.
However, when functional programs use shared data structures,
both their declarativeness and parallelism can be compromised.  This
is because the shared data must be ``threaded'' through the 
function call tree, in order to ensure determinacy.
Further, updates to the structure may require copying it.
One way to reduce threading and copying is to introduce imperative
operations, as in ML and Scheme.  To provide a meaningful semantics 
in the presence of side-effects, these languages require strict, sequential
evaluation---thus eliminating the benefit of parallelism.

In this paper we present M-structures, which are imperative data structures with
implicit synchronization.  M-structures have been added to Id, an implicitly parallel,
declarative language with non-strict semantics.  We argue that Id programs
that use M-structures to share state improve on their functional counterparts in
three ways: M-structure programs are (1)  more {\em declarative}; (2) more
{\em parallel}; and (3) more {\em storage efficient}.  Points (1) and (2) are
surprising, in that they contradict the conventional wisdom about functional 
programs stated above.  We demonstrate our claims by studying two algorithms
that share state: computing the histogram of a tree of samples, 
and traversing a  graph.  These programs are written both functionally and with
M-structures, and evaluated for declarativeness, parallelism, and efficiency.
Performance analysis is given from both idealized simulation and execution on
Monsoon, a 10MIPS dataflow processor.
\end{minipage}

\end{center}
% ----------------------------------------------------------------
\end{document}