Usage Counting Analysis for Lazy Functional Languages

AbstractIf it can be determined at compile-time how many times values will be used within lazy functional programs, a number of useful optimisations can be performed. For example, call-by-need parameter passing can be converted to call-by-name, and in-place updating and compile-time garbage collection can be performed. In this paper, it is shown how this usage counting information can be obtained by static analysis. This analysis is not itself a major contribution of this paper; similar analyses have been defined before. The major contributions of this paper are that it provides a framework against which this analysis can be proved correct for a lazy functional language, and the analysis is proved to be correct with respect to this framework. The framework for proving the correctness of the analysis is provided by defining a store semantics which counts the number of times values are used