% -*- Mode: LaTeX -*-

\section{Placement of Barrier Translation within a Compiler}
\label{sec:frag}

The barrier translation presented above is a source to source
transformation of a Kernel Id program.  A natural question
is when should this translation be performed within the compiler.
Should we translate the barriers before or after other program
transformations such as $\lambda$-lifting, pattern-matching \etc are
performed?  Moreover, many reduction rules shown in \fig{rules} may be used
at compile-time as compiler optimizations \cite{Ariola91}.  We may
even want to postpone the barrier translation until after the
optimization phase because the translation increases the complexity of
the program.  Does it matter (semantically) when this
translation is performed?

\subsection{Canonicalization \vs Barrier Translation}
\label{sec:canon}

Unfortunately, the barrier translation shown in \fig{dfbar} is very
fragile even with respect to the simple canonicalization procedure
described in \sec{rules}. The termination semantics of a program may
be seriously altered when canonicalization is performed before the
barrier translation as opposed to after it.  Consider the example
given below.

\begin{myexample}{ex:canon1}
\{ ( x = a;
    --- 
    a = 1; ) 
  in a \}
\end{myexample} 

Without canonicalization, this program deadlocks under the barrier
translation because the value of \tbx{a} is required to discharge the
barrier. But the binding (\tbx{x = a}) can be eliminated \via
canonicalization which would make the above program terminate
normally.

If we do not perform canonicalization at all places before the barrier
translation, we may introduce spurious free identifiers within a
control region, as shown below.

\begin{myexample}{ex:canon2}
def f x = \{ y = a in x \}; 
( b = f 1; 
  --- 
 ... )
\end{myexample}

Inlining the function \tbx{f} into the pre-region of the barrier
introduces the redundant binding (\tbx{y = a}) within that region.
Suppose that this region is not canonicalized before barrier
translation, while the function \tbx{f} is canonicalized. This would
make the inlining appear incorrect, because the pre-region would
collect the free identifier \tbx{a} into its termination signal while
the function \tbx{f} would not.

\subsection{Compiler Optimizations \vs Barrier Translation}
\label{sec:trans}

\subsubsection*{The Role of Free Identifiers}

A similar discrepancy may be seen in the termination characteristics
of a program when traditional compiler optimizations are performed
before or after the barrier translation.  For instance, consider the
following program fragment:

\begin{myexample}{ex:elim}
def f x = 1; 
( y = f a;
  --- 
  ... )
\end{myexample}

If the user (or the compiler) decided to inline the function \tbx{f}
before performing barrier translation, it would eliminate the free
identifier \tbx{a} from the pre-region of the barrier. The computation
below the barrier would no longer wait for the value of the identifier
\tbx{a} to arrive, as it would have if the inlining had been performed
after barrier translation.

Most other reduction rules shown in \fig{rules} would also yield a
different termination behavior if used at compile-time before
performing barrier translation. For instance, applying \tbx{Cond}
rules would eliminate the free identifiers of one of the branches that
would otherwise be collected into the signal of the translated
conditional expression (see \fig{dfbar}).  Optimizing general
applications \tbx{Ap} to partial applications \tbx{Pap} would
introduce new free identifiers into a control region that would not be
present if the optimization had been performed after barrier
translation.

Another program transformation that changes the set of free
identifiers of a control region is $\lambda$-lifting
\cite{Johnsson85}.  $\lambda$-lifting converts free identifiers of a
function into additional parameters and then lifts them to the
top-level as combinators. All occurrences of the lifted function
identifier are replaced by partial applications of the transformed
function to its previous free identifiers. This transformation would
eliminate free identifiers from the region containing the lifted
$\lambda$-expression, and introduce free identifiers into regions
where the lifted function identifier occurs. Again, this would alter
the termination semantics of those regions.

\subsubsection*{The Role of Bound Identifiers}

The translation of a $\lambda$-expression in \fig{dfbar} shows that
the signal of the $\lambda$-body collects the weak head-normal forms
of all incoming bound identifiers of the function. This is essentially
a resource management requirement --- if an incoming argument is not
used within the body of the function then it must be collected into
its termination signal. This ensures that no dangling argument values
are left behind to be received
after the production of the termination signal has allowed
the function's activation
frame to be deallocated.

This data-driven compilation scheme creates some subtle problems for
transformations involving functions that do not use some of their
arguments. Consider the following example:

\begin{myexamplenocode}{ex:bound}
\begin{tabular}{lcl}
\begin{minipage}{1.2in}
\begin{code}
def f x y = y; 
\{ f' = f b;
 ( a = f' 1;
   --- 
   b = a; );
 in a \}
\end{code}
\end{minipage} & $\stackrel{\sibx{Inlining}}{\longrightarrow}$ &
\begin{minipage}{1.2in}
\begin{code}
def f x y = y;
\{ f' = f b; 
 ( a = 1;
   --- 
   b = a; ); 
 in a \}
\end{code}
\end{minipage}
\end{tabular}
\end{myexamplenocode}

It is easy to detect that the application (\tbx{f' 1}) before the
barrier is a full-arity application of the function \tbx{f}. If the
compiler decided to inline this function, then the resulting code
after canonicalization shown on the right would be able to discharge
the barrier immediately and the program would terminate normally. If
the compiler decided not to inline, then the data-driven
implementation of the function \tbx{f} would wait for its first
argument \tbx{b} at run-time before releasing the termination signal
which in turn is supposed to discharge the barrier and allow the
identifier \tbx{b} to become a value. Therefore, the program would
deadlock instead.

The above discrepancy arises because the data-driven implementation
deliberately waits for the unused bound identifiers of a function even
though at compile-time we eliminate such bindings \via
canonicalization. On the other hand, this problem would not arise if
the compiler was careful not to inline functions whose partial
applications spanned multiple control regions. Whether this condition
severely restricts the applicability of the inlining optimization is
a topic for further investigation.

\subsection{Currying Equivalence \vs Barrier Translation}
\label{sec:curry}

Functional languages such as Haskell (with lazy evaluation) or
functional Id without barriers (with eager evaluation) satisfy several
nice denotational properties based on $\lambda$-calculus that may be
used for equational reasoning among syntactic terms. For example, the
following equation expresses the \ibx{currying} equivalence:
\[\lambda xy.\;e \equiv \lambda x.\;\lambda y.\;e \]

When barriers are added to the language, we would still like to
preserve as many denotational equalities as possible because they
provide a useful intuitive model to the user and to the compiler for
reasoning about equivalence of program terms. Unfortunately, as far as
the currying equivalence goes, the termination semantics shown in
\fig{dfbar} differentiates between the two cases. This is
illustrated by the following example:

\begin{myexamplenocode}{ex:curry}
\begin{tabular}{lcl}
\begin{minipage}{1.2in}
\begin{code}
def f x y = y; 
\{ f' = f b;
 ( a = f' 1;
   --- 
   b = a; );
 in a \}
\end{code}
\end{minipage} & \vs &
\begin{minipage}{1.2in}
\begin{code}
def f x = g; 
def g y = y; 
\{ f' = f b; 
 ( a = f' 1;
   --- 
   b = a; ); 
 in a \}
\end{code}
\end{minipage}
\end{tabular}
\end{myexamplenocode}

The left-hand-side shows a function \tbx{f} with two arguments that is
curried over two applications. \tbx{f'} gets bound to a partial
application of the function \tbx{f} which behaves like the identity
function in value semantics but has a slightly more complex behavior
for termination semantics. The function application \tbx{(f' 1)} above
the barrier does not produce a signal until it also receives the first
argument of the function \tbx{f}. This is because the barrier
translation rules mandate that functions should collect their unused
arguments into signals.  But that can never happen, because the actual
value for that argument \tbx{b} cannot be produced until the
application itself terminates.  So the program deadlocks.

The right-hand-side shows an uncurried version of the same function.
Now \tbx{f'} gets bound to a pure identity function that does not
contain any free identifiers within its closure.  The application
above the barrier therefore successfully terminates, producing the
value for \tbx{b} which allows the binding for \tbx{f'} to terminate.
Thus the program successfully produces a value and terminates.

\subsection{Making Dataflow Barriers more Robust}
\label{sec:fix}

Judging by the above discussion, it seems that the simplest way to
guarantee that the source program semantics are kept intact is to
perform barrier translation before any other program transformation is
performed. This in itself is not problematic, and can be easily
done within the compiler, although it shows that the barrier
translation scheme presented in \fig{dfbar} is not sufficiently
robust. Below we outline some possible ways to improve its
robustness.

One simple way to ensure that elimination or introduction of free
identifiers into the pre-region of a barrier has no effect on its
termination semantics is to make a permanent record of its free identifiers
before any canonicalization or compiler transformations are attempted.
This set would be recorded at the barrier itself by inspecting the
original source program.\footnote{Identifier substitutions would still
need to be performed on this set of free identifiers.} These
identifiers would then be used to control the discharge of the barrier
at the time of translation irrespective of the actual set of free
identifiers of the pre-region obtained after canonicalization or
program transformations.  Note that this scheme would correctly handle
\ex{canon1} and \ex{elim} by permanently associating the free
identifier \tbx{a} with the region above the barrier and collecting it
within its termination signal during barrier translation.

The problem introduced by partial canonicalization may also be easily
overcome, by ensuring that we always canonicalize the whole program
before performing the barrier translation, thus ensuring that
redundant bindings are consistently eliminated from everywhere within
the program. This avoids the problem shown in \ex{canon2} and makes
canonicalization a robust operation.

Thus the overall barrier translation mechanism within the compiler
becomes the following:
\begin{enumerate}
\item Record the free identifiers of every pre-region of a barrier in
the source program.
\item Perform program transformations: $\lambda$-lifting, inlining, \etc.
\item Canonicalize the program eliminating all redundant bindings.
\item Translate the barriers in a manner similar to \fig{dfbar} using
the weak head-normal forms of previously saved free identifiers for
each pre-region. 
\end{enumerate}

The problem of preserving currying equivalence is a little more
difficult to overcome. This show that the data-driven termination
semantics are fundamentally at odds with desirable semantic properties
enjoyed by the value semantics. In the next section we explore a
different approach to this problem, mixing eager evaluation with a
demand-driven identifier referencing mechanism.
