% -*- Mode: LaTeX -*-

\section{Side-Effect Operations}
\label{sec:side}

Functional programming languages purposely do not permit assignment or
mutable storage.  Instead, such features are often offered through
various implementation tricks such as by using monadic programming
techniques.  Alternatively, side-effects may be introduced \via the
traditional assignment operator after specifying a precise sequential
ordering on all operations (\eg, Scheme and ML). Id, motivated by
concerns for parallelism, offers yet another alternative for
incorporating side-effects. In Id, it is possible to specify only a
partial order on side-effect operations and still retain an overall
consistent picture of the computation.

pH supports imperative operations on I-structure \cite{Arvind89} and
M-structure \cite{Barth91} objects. I-structures allow the creation of
a data structure to be separated from the definition of its
components: attempts to use the value of a component are automatically
delayed until that component is defined; attempts to redefine a
component lead to an error state.  M-structures, on the other
hand, are fully mutable data structures whose components can be
redefined repeatedly: an \tbx{mFetch} operation reads and empties a
full component; an \tbx{mStore} operation (re)defines it; two successive
\tbx{mStore} operations on the same component lead to an error
state unless separated by an \tbx{mFetch} operation.

For some programs in pH we need a way to sequentialize M-structure
operations in order to avoid race conditions implied by its parallel
evaluation order.  This is accomplished by the use of {\em control
regions\/} and \ibx{barriers} \cite{Aditya95}. A control region is
informally defined as a set of concurrent threads that are under the
same control dependence and therefore always execute together.
Threads within the same control region may execute in any order or in
an interleaved manner as long as the data dependencies among them are
respected.  Barriers provide a mechanism to detect the termination of
a set of parallel activities enclosed within a control region. A
barrier (\tbx{---}) creates two sub-regions within a given control
region --- one above the barrier called the \ibx{pre-region} and the
other below the barrier called the \ibx{post-region}.  Intuitively, no
computation within the post-region is allowed to proceed until all the
side-effect computations within the pre-region have terminated. This
semantics is different from those proposed in \cite{Aditya95} where a
barrier waits for the termination of \ibx{all} computations rather
than just those which cause side-effects.

In the rest of this section we describe the pH extensions to deal with
I-structure and M-structure operations. The semantics of barriers
is described in \sec{barrier}.

\subsection{Kernel Language Extensions}

\begin{myfig}{fig:lang-extn}{Kernel language extensions for
side-effect operations.}
\centering
$\begin{array}{lcl}
\bx{Constant} & ::= & \cdots \mid \wconst \\
\ibx{PF}^{1}  & ::= & \cdots \mid \tbx{iAlloc} \mid \tbx{mAlloc} \mid 
                      \tbx{iFetch} \mid \tbx{mFetch} \mid \tbx{W} \\
\ibx{PF}^{2}  & ::= & \cdots \mid \tbx{iStore} \mid \tbx{mStore} \mid \tand \\
S             & ::= & \cdots \mid (S_{1}\;\tbx{---}\;S_{2})
\end{array}$
\end{myfig}

We extend the kernel language to incorporate side-effect operations
and barriers as shown in \fig{lang-extn}.  We add primitives to
allocate, read, and write I-structures and M-structures.  The fetch
and store operations directly address store locations: indexed
addressing is handled separately in the kernel language.

We also extend the syntax for block bindings to allow barriers---two
sets of parallel block bindings may now be sequentialized by using a
barrier (\tbx{---}) between them.  Additional constants (\wconst),
primitive operators (\tbx{W} and \tbx{\&}) and strict function
application (\tbx{sap}) are used to translate barriers into an
ordinary set of bindings.

\subsection{Evaluation Rules for Side-Effect Operations}

In this section we describe additional evaluation rules for internal
primitive operators involving I-structures, M-structures, and
barriers.  All these operators are strict on all their inputs. 

\subsubsection*{I-structure Instructions}

The \fbx{iAlloc} instruction allocates an empty I-structure array. The
\fbx{iFetch} and \fbx{iStore} instructions address an I-structure
location directly; all address arithmetic must be done separately. The
\fbx{iFetch} instruction is similar to \fbx{loadi\_$k$}. The
\fbx{iStore} instruction updates an empty location with a value and
reactivates any suspended continuations. Storing to an already
\fbx{full} location is considered to be an error.

\begin{evalrule}{\fbx{iAlloc}:}
\inference{\state{\_}{\primapp{\fbx{iAlloc}}{\loc_{x}}:\insts}%
                 {\envs}{\works}{\store[\loc_{x}\mapsto\ftag{\ul{n}}]}{}}%
          {\state{\loc}{\insts}{\envs}{\works}{\store'}{}} \\
\multicolumn{1}{l}{where $\store'=\store+\{\;\loc\mapsto\dtag{[\;]},
\ldots,(\loc+n-1)\mapsto\dtag{[\;]}\;\}$}
\end{evalrule}

\begin{evalrule}{\fbx{iFetch}:}
\inference{\state{\_}{\primapp{\fbx{iFetch}}{\loc_{x}}:\insts}{\envs}%
                 {\works}{\store[\loc_{x}\mapsto\ftag{\loc}]}{}}%
          {\state{\_}{\touch{\loc}:\lda{\loc}:\insts}{\envs}{\works}{\store}{}}
\end{evalrule}

%% \ibx{Discuss Atomicity !!}

\begin{evalrule}{\fbx{iStore}:}
\inference{\state{\_}{\primapp{\fbx{iStore}}{\loc_{x},\loc_{z}}:\insts}{\envs}{\works}%
                 {\store[\loc_{x}\mapsto\ftag{\loc}]}{}}%
          {\state{\_}{\fn{atomic}{[\fullerr{\loc},\lda{\loc_{z}},\sta{\loc}]}:\insts}%
                 {\envs}{\works}{\store}{}}
\end{evalrule}

\subsubsection*{M-structure Instructions}

The \fbx{mAlloc} and \fbx{mStore} instructions are identical to the
corresponding instructions for I-structures. The \fbx{mFetch}
instruction is similar to the \fbx{iFetch} except that it empties the
location being accessed and has to be retried if the location is
already empty. 

\begin{evalrule}{\fbx{mAlloc}:}
\inference{\state{\_}{\primapp{\fbx{mAlloc}}{\loc_{x}}:\insts}%
                 {\envs}{\works}{\store[\loc_{x}\mapsto\ftag{\ul{n}}]}{}}%
          {\state{\loc}{\insts}{\envs}{\works}{\store'}{}} \\
\multicolumn{1}{l}{where $\store'=\store+\{\;\loc\mapsto\dtag{[\;]},
\ldots,(\loc+n-1)\mapsto\dtag{[\;]}\;\}$}
\end{evalrule}

\begin{evalrule}{\fbx{mFetch}:}
\inference{\state{\_}{\primapp{\fbx{mFetch}}{\loc_{x}}:\insts}{\envs}%
                 {\works}{\store[\loc_{x}\mapsto\ftag{\loc}]}{}}%
          {\state{\_}{\fn{atomic}{[\rtouch{\loc},\tka{\loc}]}:\insts}{\envs}{\works}{\store}{}}
\end{evalrule}

%% \ibx{Discuss Atomicity !!}

\begin{evalrule}{\fbx{mStore}:}
\inference{\state{\_}{\primapp{\fbx{mStore}}{\loc_{x},\loc_{z}}:\insts}{\envs}{\works}%
                 {\store[\loc_{x}\mapsto\ftag{\loc}]}{}}%
          {\state{\_}{\fn{atomic}{[\fullerr{\loc},\lda{\loc_{z}},\sta{\loc}]}:\insts}%
                 {\envs}{\works}{\store}{}}
\end{evalrule}
