% -*- Mode: LaTeX -*-

\section{Mixed Eager and Lazy Evaluation}
\label{sec:alter}

In this section we present an alternate translation for barriers
based on a demand-driven identifier referencing mechanism within the
context of non-strict, eager evaluation. This translation overcomes
some of the semantic shortcomings of the data-driven barrier
translation presented above and is also sufficient for resource
management under an environment-based implementation.  We will
show the translation rules and discuss their properties, comparing
them with the data-driven translation.

The concept of a control region remains unchanged under this mixed
model of evaluation. We spawn all tasks within a control region
eagerly, but each computation fetches the values of its free (input)
identifiers as needed rather than being explicitly provided with them.
Similarly, the values of the bound (output) identifiers computed
within a region are not automatically sent to the computations that
may need them.  Instead, these values are stored in a known place from
where other computations may obtain them as needed.  Under this
execution model, the trigger and the signal of a control region (see
\fig{scope} (a)) take on a real meaning since these are the only
dependency arcs that actually enter and leave the control region. All
data-dependency arcs become implicit in storing and fetching computed
values.


\subsection{Barrier Translation based on Mixed Evaluation}

\begin{myfig*}{fig:dfbar2}{Barrier Translation Rules based on Mixed Evaluation.}
\centering
$\begin{array}{lcl}
\multicolumn{3}{c}{\cbx{Expressions}} \\
\bbx{TE} & :: & \bx{Expression} \rightarrow
\bx{Expression}\times\bx{Signal Expression}\\[.1in]

\te{c}          & = & c,\hm 0 \\
\te{x}          & = & x,\hm 0 \\
\te{\ibx{PF}^{n}(X_{1},\ldots,X_{n})} & = &
\ibx{PF}^{n}(X_{1},\ldots,X_{n}),\hm 0 \\
\te{\tbx{Cond} \;(X, E_{1}, E_{2})} & = & 
\tbx{Cond} \;(X, \te{E_{1}}, \te{E_{2}}) \\
\te{\lambda x_{1} \cdots x_{n}.\; E} & = & 
\lambda x_{1} \cdots x_{n}.\; \te{E},\hm 0 \\
\te{\tbx{Ap}(F,X)} & = & \tbx{Ap}(F,X) \\
\te{\{\;S^{\sibx{par}}\;\tbx{in}\;(X_{1},\ldots,X_{n})\;\}} & = &
\{\;S'^{\sibx{par}}\;\tbx{in}\;(X_{1},\ldots,X_{n},s)\;\} \\
\multicolumn{3}{l}{\bx{where}\hm S'^{\sibx{par}},s = \ts{S^{\sibx{par}}}} \\[.1in]
\multicolumn{3}{c}{\cbx{Statements}} \\
\ts{} & :: & \bx{Statement} \rightarrow \bx{Statement}\times\bx{Signal Identifier}\\[.1in]
\ts{x_{1},\ldots,x_{n} = E} & = & (x_{1},\ldots,x_{n},s_{1} = \te{E}; \\
& & s = s_{1}+\whnf{x_{1}}+\cdots+\whnf{x_{n}}),\hm s \\
\ts{\epsilon} & = & (s=0),\hm s \\
\ts{S_{1};\ldots;S_{n}} & = & (S'_{1};\ldots;S'_{n}; s=s_{1}+\cdots+s_{n}),\hm s \\
\multicolumn{3}{l}{\bx{where}\hm S'_{i},s_{i} = \ts{S_{i}} \hm 1\leq{}i\leq{}n} \\
\ts{S^{\sibx{par}}_{1} \;\tbx{---}\; S^{\sibx{par}}_{2}} & = & 
(S'^{\sibx{par}}_{1}; \\ 
& & F = \lambda s.\{\;S'^{\sibx{par}}_{2}
\;\tbx{in}\; y_{1},\ldots,y_{m},s_{2} \;\}; \\ 
& & y_{1},\ldots,y_{m},s'_{2} =
\tbx{Sap}(F,s_{1})),\hm s'_{2} \\
\multicolumn{3}{l}{\bx{where}\hm \begin{array}[t]{lcl}
S'^{\sibx{par}}_{i}, s_{i} & = & \ts{S^{\sibx{par}}} \hm
1\leq{}i\leq{}2 \\ y_{1},\ldots,y_{m} & = &
\fn{BV}{S^{\sibx{par}}_{2}} \end{array}} \\
\ts{\tbx{I-store}(X_{0},X_{1},X_{2})} & = & 
(\tbx{I-store}(X_{0},X_{1},X_{2}); \\ & & s =
\whnf{X_{0}}+\whnf{X_{1}}+\whnf{X_{2}}),\hm s \\
\ts{\tbx{M-store}(X_{0},X_{1},X_{2})} & = & 
(\tbx{M-store}(X_{0},X_{1},X_{2}); \\ & & s =
\whnf{X_{0}}+\whnf{X_{1}}+\whnf{X_{2}}),\hm s
\end{array}$
\end{myfig*}

\fig{dfbar2} shows the new barrier translation rules under the mixed
execution model. We no longer collect weak head-normal forms of the free
identifiers of every sub-expression into its signal.
Nevertheless, we still need to collect the weak head-normal forms of
the bound identifiers of a computation into its signal, identifying
the termination of that computation.  Similarly, the weak head-normal
forms of the identifiers participating in side-effect operations
\tbx{I-store} and \tbx{M-store} signify the completion of those
operations. Within expressions, identifiers are expected to be fetched
on demand and therefore do not need any separate termination signal.

Another interesting difference between this translation and that of
\fig{dfbar} is the rule for $\lambda$-expressions. Note that the rule
presented in \fig{dfbar} collects all $\lambda$-bound identifiers into
its termination signal in order to capture the identifiers that are
left unused. On the other hand, the rule presented in \fig{dfbar2}
does not collect any such identifiers.  This is because unused
identifiers are never fetched under mixed evaluation. This property
allows the currying equivalence to be preserved as shown in
\ex{curry}.  Under the new translation rule, the signal from the body
of the function \tbx{f} on the left-hand-side would no longer depend
on its unused bound identifier \tbx{x}; so the left-hand-side
would also produce a value and terminate properly.

\subsection{Properties of Mixed Barrier Semantics}

The translation shown in \fig{dfbar2} is automatically robust with
respect to compiler optimizations and program transformations, since
termination of a computation depends only upon the values of
identifiers that are actually required during that computation. No
artificial data-dependencies may be introduced or eliminated by
program transformations. It also satisfies the currying equivalence,
and is therefore a semantically cleaner alternative to purely eager,
data-driven barrier translation.

As expected, the mixed evaluation model is much more relaxed in terms
of the condition governing the discharge of a barrier. The termination
of the pre-region of a barrier now solely depends upon the termination
of the actual computation spawned within it and not on the arrival of
unused values.  This may cause some programs to terminate properly
under this semantics that would have deadlocked under dataflow barrier
semantics as shown below:

\begin{myexample}{ex:mixed1}
\{ ( def f x = x + a ;
    ---
    a = 1; )
  in f 3 \}
\end{myexample}

Under dataflow barrier semantics, the value of \tbx{a} is still
required to discharge the barrier since it is a free identifier of the
pre-region, but since \tbx{a} is bound in the post-region, the value
never arrives and the program deadlocks.  Under mixed barrier
semantics, function definitions always terminate immediately; so the
barrier discharges, allowing the overall expression to produce a value
and terminate properly.

Both dataflow and mixed termination semantics provide the power to
control the termination of actual computations including those
involving side-effects. The major difference between them shows up
while using them for resource management.  Dataflow termination
semantics automatically provide a full resource management capability,
by ensuring that even unused values have been received by the time a
termination signal is produced from a control region.  We may need to
move to an environment-based implementation in order to provide a
similar capability under the mixed termination semantics.


