Usage Counting Analysis for Lazy Functional Languages Export

@article{citeulike:336893, abstract = {If 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.}, author = {Hamilton, G. W.}, citeulike-article-id = {336893}, citeulike-linkout-0 = {http://dx.doi.org/10.1006/inco.1998.2735}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WGK-45J54KF-M/2/dc2f7bcb97d2e001bfbaf27e882cedc6}, day = {1}, doi = {10.1006/inco.1998.2735}, journal = {Information and Computation}, keywords = {call-by-name, call-by-need, denotational-semantics, functional-programming, laziness, lazy-evaluation, optimization, static-analysis}, month = {November}, number = {2}, pages = {100--137}, posted-at = {2005-09-30 13:49:47}, priority = {1}, title = {Usage Counting Analysis for Lazy Functional Languages}, url = {http://dx.doi.org/10.1006/inco.1998.2735}, volume = {146}, year = {1998} }

TY - JOUR ID - citeulike:336893 L3 - citeulike-article-id:336893 N2 - If 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. IS - 2 JF - Information and Computation EP - 137 TI - Usage Counting Analysis for Lazy Functional Languages VL - 146 SP - 100 KW - call-by-name KW - call-by-need KW - denotational-semantics KW - functional-programming KW - laziness KW - lazy-evaluation KW - optimization KW - static-analysis AU - Hamilton, GW PY - 1998/11/01/ UR - http://dx.doi.org/10.1006/inco.1998.2735 ER -