A framework for strictness analysis based on type inference

Lazy evaluation has several advantages in semantic power over its eager counterpart. However, eager evaluation often provides a more efficient implementation. Strictness has been identified as the condition for safely altering the evaluation order in lazy evaluation while preserving the semantics. Strictness analysis is intended to provide some information at compile-time for code-optimization; and hence reduce the drawbacks of lazy evaluation. Traditionally, the strictness analysis problem has been approached using abstract interpretation. In this work, we analyze the strictness analysis problem in great detail to identify the essential factors involved and hence exclude other irrelevant factors such as the type discipline of the base language. Based on our analysis of the problem, we provide a new perspective and develop a framework which can lead to a clearer and simpler description of the problem and also to a more flexible solution. Our framework defines the strictness analysis problem from a perspective of viewing strictness properties as types possessed by programs and performs strictness analysis using type inference techniques. The problem is defined utilizing the classical notion of reduction and elementary set-theory, in contrast to the denotational semantics and domain theory used in the abstract interpretation approach. This provides a more simple and direct definition for strictness analysis, and thus leads to a simpler framework. We develop a new syntactic representation for strictness properties of a program and a new computational technique for strictness analysis. The syntactic representation takes the form of a type language. The computational technique is based on well-understood type inference techniques and improves on previous works as it does not require fixed-point iteration. Our framework is parameterized with respect to the type language describing strictness properties and to the type inference techniques. As improvements in type theory and type inference methods become available, both of them can be extended toward a more complex and more powerful strictness analysis.