In "non-strict" functional languages, a data structure may be read before all its components are written, and a function may return a value before finishing all its computation or even before all its arguments have been evaluated. Such flexibility gives expressive power to the programmer, but makes life difficult for the compiler because it may not be possible to totally order instructions at compile time; the correct order can vary dramatically with the input data. Presently, compilers for non-strict languages rely on "lazy evaluation", in which a subexpression is not evaluated until known (at run time) to contribute to the final answer. By scheduling each subexpression separately, lazy evaluation automatically deals with the varying orderings required by non-strictness, but at the same time incurs a great deal of overhead. Recent research has employed strictness analysis and/or annotations to make more scheduling decisions at compile time, and thereby reduce the overhead, but because these techniques seek to retain laziness, they are limited in effectiveness. This work presents an alternative compilation strategy which deals with non-strictness independent of laziness, through the analysis of data dependence. The analysis determines which instructions can be ordered at compile time and which must be scheduled at run time in order to implement non-strictness properly. The option is then presented of imposing laziness or ignoring it - and it is found that choosing the latter path can lead to significantly reduced overhead. Abandoning laziness means certain programs (those which use "infinite objects") may fail to terminate properly. It is suspected that non-strictness and not the ability to handle infinite objects is the more important feature for the programmer; nevertheless, annotations are provided for the programmer to achieve termination in the presence of infinite objects. Even with annotations, this approach entails less overhead. The strategy is discussed in the context of both sequential implementations and parallel implementations where the object code is partially sequentialized. It also show how lazy code can be generated from this framework.

Table of Contents:
Part 1 Introduction: notation - functional programs; notation - sets, relations and graphs. Part 2 Background - functional language compilers: strict compilers; lazy compilers - force-and-delay; lazy compilers - graph reduction; lazy compilers - abstract machines; strictness analysis. Part 3 Lenient evaluation: expressive power from non-strictness; expressive power from laziness; lenience - non-strictness without laziness; semantics or implementation techniques?; compilation as orders - sequential threads; code generation options; a footnote - non-sequentiality. Part 4 Functional quads: syntax; semantics; from a functional language to functional quads; functional quads vs sequential quads; mathematical properties of reduction; termination, weak normal forms, and lazy evaluation; denotational semantics; appendix - the structure of the set "identifier". Part 5 The analysis framework: required reductions; program requirement graphs; function requirement graphs; constraint computation; partitioning; complexity and approximations; appendix - NP-completeness of CCo. Part 6 Dependence analysis: approximate requirement graphs; outline of dependence analysis; arithmetic expressions; conditionals; interlude - dependence analysis vs strictness analysis; first-order functions; non-flat domains; higher-order functions; feedback dependences; appendix - proof of the "collapsing" lemma. Part 7 Constraint computation and partitioning: an approximation to constraint graphs; improving the approximation; improving the running time; avoiding new cycles. Part 8 Code generation: code generation concepts; basic code generation; optimizations; implementing tagged locations; partitioning for uniprocessor demand-driven execution; lazy evaluation; partitioning heuristics. Part 9 Conclusion: relationship to other work; directions for future research; concluding remarks.