% -*- Mode: LaTeX -*-

\section{Non-Strict, Eager Evaluation}
\label{sec:eager}

The Haskell language prescribes a {\em lazy\/} evaluation strategy for
non-strict computation: only those tasks are evaluated which are
required to produce the result. This strategy imposes a
strong sequential constraint on the overall computation, although the
exact ordering of tasks is decided dynamically. On the other hand, Id
and pH languages follow an {\em eager\/} evaluation strategy for the
same non-strict computation: all tasks execute in
parallel, restricted only by the data-dependencies among them. This
strategy automatically exposes large amounts of parallelism both
within and across procedures. We describe this evaluation model below.

\subsection{The Fully Parallel Execution Model}

A program in Id consists of an expression to be evaluated within the
scope of a set of top-level function and type declarations.  Each
function is broken up into several threads of computation (the length
of the threads is determined in part by the compiler's ability to
identify strict regions and in part by the ability of the run-time
system and the hardware to exploit the exposed parallelism
efficiently).

The parallel execution model of Id and pH is shown pictorially in
\fig{model}. Each function application allocates an {\em activation
frame\/} which records function arguments and keeps temporary, local
values. Threads belonging to a function share its activation frame and
may be active concurrently. The activation frame is deallocated when
the function terminates. Executing threads may enable other threads by
sending data or synchronization information to their associated
activation frame: this characterizes the ``data-driven'' nature of
this execution model.

The program starts by allocating a root activation frame to evaluate
the top-level expression. Parallel threads containing function
applications give rise to parallel child activations, while loop
invocations give rise to multiple parallel iterations.  At
any time the overall computation is represented by a
tree of activation frames as shown in \fig{model}, exploiting both
intra-procedural and inter-procedural parallelism.

\begin{myfig}{fig:model}{The Fully Parallel Execution Model of Id and pH.}
\illustration{model}[\hsize]
\end{myfig}

In contrast, under lazy evaluation computation is spawned in parallel
only if it is already known to contribute towards the final result.
Otherwise, every potentially concurrent task is suspended in a {\em
thunk\/} immediately upon creation. A ``demand-driven'' evaluation of
the suspended thunks exposes only a small part of the parallel
execution tree at any given time. Of course, some of the thunks may
never get evaluated under demand-driven evaluation.  

All threads participating in the parallel computation share a
globally addressable heap.  Data structures allocated on the heap may
continue to exist even after the function that allocated them has
terminated. Such data structures either have to be explicitly
deallocated or are garbage-collected when no more references to them
remain.

\subsection{Result \vs Termination}

An important aspect of non-strict, eager evaluation is that the
production of the result of a computation and its termination may not
always coincide. For instance, the resulting \tbx{Cons}-cell in the
following example\footnote{All our examples use the Id syntax
\cite{Id90.1}. In Id, functions are introduced using the {\em def\/}
keyword and colon (:) is the infix list constructor.} may be allocated
and returned without waiting for the termination of the computation
that fills it. I-Structure synchronization on the \tbx{Cons}-cell
automatically blocks any attempt to read its contents until it is
filled.

\begin{myexample}{ex:term}
def enlist f x = (f x) : nil;
\end{myexample}

Under lazy evaluation, a computation proceeds only as far as necessary
to produce the requested result, so we never have to worry
about the termination of the computation aside from the production of
its result. On the other hand, under eager evaluation, several
activities may be spawned eagerly that do not immediately contribute
towards the result. Therefore, it is semantically important to
separate the production of the result of a computation from its
overall termination. From now on, we will use the term {\em Value
Semantics\/} to refer to the result of a computation, and {\em
Termination Semantics\/} to identify its termination.\footnote{These
correspond to what were called non-strict and strict semantics,
respectively, in \cite{Stoy94}.} Semantically, a given computation may
give rise to one of the following possible outcomes \cite{Ariola89}:
\begin{enumerate}
\item {\bf Result with proper Termination} --- The computation
produces a result and terminates. 
\item {\bf Result with improper Termination} --- The computation
produces a result but does not terminate. The non-termination could be
either due to an infinite computation or due to a deadlocked
computation.
\item {\bf No Result or Termination} --- The computation does not
produce a result and does not terminate. Again, the non-termination
could be due to infinite computation or deadlock.\footnote{The fourth
possibility, of proper termination but without producing a result, is
not considered to be meaningful and is lumped with the third outcome.
Some graph-reduction based semantic definitions \cite{Ariola94} do,
however, distinguish between these two cases.}
\end{enumerate}

For example, the function \tbx{f1} below produces an infinite list
of \tbx{x}'s as the result and terminates properly, \tbx{f2}
produces the same result but does not terminate because of infinite
computation, while \tbx{f3} does not produce a result and deadlocks
because the \tbx{+} operator is strict in its arguments. 

\begin{myexample}{ex:inf}
def f1 x = \{ a = x:a in a \};
\vsp
def f2 x = \{ a = x:(f2 x) in a \};
\vsp
def f3 x = \{ a = a+x in a \};
\end{myexample}

\subsection{Control Regions}
\label{sec:cr}

\begin{myfig}{fig:scope}{Control Regions and Barriers.} 
\illustration{scope}[\hsize]
\end{myfig}

\noindent Another important aspect of eager evaluation is the notion
of {\em control regions}. In a sequential language, the control
``flows'' through a chain of primitive tasks each of which has a well
defined initiation and termination point. Under the fully parallel
model of Id, a group of tasks may be initiated in parallel,
constituting a {\em control region\/} as shown in \fig{scope}
(a).  A control region is informally defined as a set of parallel
tasks that always execute together (respecting data-dependencies), and
their combined termination may be used as a synchronization event to
initiate other control regions. A control region containing a set of
parallel tasks requires the values of its free identifiers as input
and produces one or more values as output.  It also
takes in a trigger input and signals the termination of all the tasks
contained within it.

As an example, the body of an Id function constitutes a control region
which is initiated when the function is applied to all its arguments.
The termination of the entire body is determined by the joint
termination of each of its sub-computations. Control regions are
always properly nested within one another and therefore form a
``tree'' of parallel activities rather than a sequence.  The
activation tree in \fig{model} shows the dynamic nesting of procedure
control regions.  Similarly, each of the branches of a conditional
expression forms a control region that is statically nested inside the
enclosing region.  In this case, only one of the branches is initiated
when the predicate is resolved and the termination of the entire
expression is determined by the termination of that branch.

