\section{Introduction}
\label{section:introduction}
Functional programming languages can be divided into two classes:
{\em strict} and {\em non-strict}. 
In a non-strict language, functions may return values before all
their arguments are available, and data structures may be defined 
before all their components are defined. 
Many modern functional languages are non-strict; examples
include Haskell \cite{Haskell90} and Id \cite{Nikhil90}.
Such languages give greater
expressive power to the programmer than a strict language. 
Some of the languages provide non-strictness because of its cleaner
semantics. Others, like Id, also use non-strictness to generate
parallelism in a program.

Compiling non-strict languages to conventional microprocessors has been
the focus of many recent papers \cite{Traub92,Schauser91,Schauser94a}. 
Some features in the 
design of commercial microprocessors make it difficult to execute non-strict
programs directly. These processors are highly
tuned to execute a sequence of instructions efficiently by 
providing features like a large register set and deep pipelining. 
Unfortunately, this also implies
that there is a high penalty for dynamic scheduling of instructions.
As serial execution is interrupted,
registers have to be saved and restored, there
may be bubbles in the instruction pipeline etc. Synchronization
is also expensive in these processors since it 
has to be explicitly performed (in software) using instructions.

For programs in a non-strict language, it is not always possible 
at compile-time 
to specify an exact ordering of instructions. This is illustrated
in the following example written in Id.\\
Example 1:
\begin{verbatim}
def f a b = 
 {x = a + 1;
  y = b * 2
 in
   (x,y)};

{...                {...
 (c,d) = f 2 c       (c,d) = f d 1
...}                ...}
\end{verbatim}
The function {\tt f} takes two arguments {\tt a},{\tt b} and returns
two results {\tt x},{\tt y}. The set of statements enclosed by \{\ldots\}
form a recursive {\em let} block definition. There is no syntactic ordering
of the statements of the block. Also shown are calls to the function
{\tt f} in some other parts of the program (these are referred to
as {\em contexts} of {\tt f}). In both the contexts,
a result of {\tt f} is fed back into one of the function's arguments.

Consider the execution of the first context in a language
with strict semantics. The function {\tt f} is not called until
both of its arguments are available. In this case, it is not going
to be called until the variable {\tt c} gets a value. As
the value of {\tt c} depends on the call itself, this leads to a 
{\em deadlock} in the program; the variables {\tt c} and {\tt d}
never get defined.

In a non-strict execution, it is possible to call a function
even though not all of its arguments are available. Also, it is 
possible to return some results
even though not all of the function's results are available.
So, the function {\tt f} is called with the first argument
2 and the second argument $\bot$ (an {\em undefined} value). Then,
the value of {\tt x} can be computed to be 3. Now, the variable {\tt c}
gets defined to be the value 3, and the computation of {\tt y} and
{\tt d} can proceed. Hence, the non-strict execution produces
meaningful values for the variables {\tt c} and {\tt d}. Note that
in this execution, the $+$ instruction {\em must} have executed
before the $*$ instruction -- there is no other order that could
produce the correct results for {\tt f}.

Similarly, the second context produces a deadlock in a
strict execution, but produces valid results in a non-strict 
execution. However, this context requires that the $*$ instruction
execute before the $+$. Thus, depending upon the context, the 
instructions in {\tt f} can execute in either order. 
We have no choice but to compile these programs
 such that the two instructions execute independently,
when their data becomes available. Compiling {\tt f} in
this manner entails performing
dynamic scheduling/synchronization at each instruction -- leading
to an inefficient execution  on microprocessors.

Traub \cite{Traub88} 
made the significant observation that dependence analysis
could enable efficient compilation of some functions.
A simple example of such a function is given below.\\
Example 2:
\begin{verbatim}
def f a b =
 {x = a + b;
  y = a * b
 in
  (x,y)}
\end{verbatim}
In this function, we can infer that the dependence behavior
of both the $*$ and $+$ instruction is very similar: they 
both depend on the values of {\tt a} and {\tt b}. For this 
function, any context that feeds results back to arguments always
deadlocks, even in a non-strict execution. Thus, it is {\em safe}
to compile the function such that the two instruction execute
together, in some order.

Thus, the goal {\em partitioning} \cite{Traub88} is to infer
the possible dependencies in a program and use that information
to {\em sequentialize} parts of a program. This is achieved
by compiling each function into a set of {\em threads} while preserving
the function's non-strict semantics. Each
thread is a sequence of instructions and once a thread begins
execution, it does not need any dynamic scheduling/synchronization
during its execution. 
Threads of this form yield efficient implementation on conventional
architectures using an abstract machine such as TAM \cite{Culler93}.
They can also be implemented on parallel multi-threaded
hardware (\eg, *T \cite{Nikhil92}). 

Combining instructions into threads enables
more efficient use of registers and amortizes the overheard
of dynamic scheduling/synchronization over many instructions.
Partitioning attempts to make threads
as large as possible, to enable efficient execution of non-strict
programs on microprocessors. 


The strategy used to implement non-strictness 
(that is, functions
accepting {\em undefined} arguments and returning {\em partial} results) 
is called the {\em lenient} strategy \cite{Traub88}. 
This strategy gives flexibility 
to the programmer in using the recursive {\em let} block. It enables
circular dependencies to be resolved at run-time, instead of being 
statically resolved. Non-strictness in data-structures
also gives the programmer ability to create circular data-structures
functionally \cite{Traub88}.

Another 
strategy that provides non-strictness is the {\em lazy evaluation}
strategy, where the evaluation of an expression is delayed until
the execution cannot proceed without the value of that expression.
Unlike lenient evaluation, 
lazy evaluation also gives the user the ability to manipulate
infinite data structures \cite{Henderson80}. In this paper,
we are primarily interested in implementing a non-strict language
with the lenient strategy (though we do remark on the applicability
of the techniques developed here to implement lazy evaluation).

The contributions of this paper are:
\begin{itemize}
\item The definition of partitioning as a program transformation. 
\item Design of new basic block partitioning algorithms. Also, a
precise characterization of the complexity of the partitioning problem.
\item A new inter-procedural partitioning algorithm based on
abstract interpretation.
\item The proof of correctness of the partitioning
 algorithms using denotational semantics.
\end{itemize}

The rest of the paper is organized as follows. Section~\ref{section:syntax}
defines a simple non-strict kernel language and its semantics. Section~\ref{section:partitioning}
formally defines the partitioning problem and the notion of correctness 
of a partitioning. 
Section~\ref{section:basic} deals with the problem of partitioning 
basic blocks. 
Section~\ref{section:global} uses abstract interpretation techniques
to extend the basic block partitioning algorithm
to partition arbitrary blocks. 
Section~\ref{section:related} compares this paper with 
related work and section~\ref{section:conclusion}
concludes. In the appendix,
we present proof sketches of some of the theorems stated in this paper.



