\section{Conclusions and Extensions}
\label{section:conclusion}
In this paper, we have presented new algorithms for partitioning
non-strict functional languages. We have presented two new
algorithms for basic block partitioning and characterized the
complexity of the problem. We have extended the basic block
algorithms to propagate information globally.
Our inter-procedural algorithm
is based on abstract interpretation and handles recursive functions
in a natural manner. We have also defined partitioning as a program
transformation enabling us to prove the correctness of our algorithms
using denotational semantics.

Several straightforward extensions follow from the techniques
presented in this paper. We can extend our algorithms
to incorporate higher-order functions and
data-structures that are not present in our kernel language.
The basic technique is to be conservative when dealing with
blocks that contain higher-order functions or data-structures.
Though path analysis extends naturally to higher-order functions,
it is computationally more efficient to make approximations when dealing with
them \cite{Bloss88}. On the partitioning side, one can disconnect
nodes that call perform calls to unknown functions and then
partition the block using algorithm 3. A similar approach can be used to deal
with data-structures. However, it is interesting
to extend the algorithms to deal with data-structures like
lists and arrays making use of their dependence information. 
Research done in analyzing strictness properties 
of lists \cite{Wadler87} and Fortran style array subscript analysis 
would probably be of relevance here.

A nontrivial extension of the partitioning algorithm is to incorporate
{\em context} information during partitioning. The idea behind this is
simple: in many cases, one can deduce that a function is always being
used in a strict manner and this information can be used to generate
better partitions for the the function. An extension to the partitioning
algorithm that achieves this is presented in \cite{Coorg94}. 

We plan to implement these algorithms in a compiler for Id. This
would shed light on the quantitative benefits of the various parts
of our partitioning algorithms. 

\section{Acknowledgments}
Many thanks to Shail Aditya, Arvind, and Boon Ang for their
helpful comments and suggestions.
