Fitness Conditions for fixed Point Iteration
DOI:
https://doi.org/10.7146/dpb.v21i384.6617Resumé
This paper provides a link between the formulation of static program analyses using the framework of abstract interpretation (popular for functional languages) and using the more classical framework of data flow analysis (popular for imperative languages). In particular we show how the classical notions of fastness, rapidity and k-boundedness carry over to the abstract interpretation framework and how this may be used to bound the number of times a functional should be unfolded in order to yield the fixed point. This is supplemented with a number of results on how to calculate the bounds for iterative forms (as for tail recursion), for linear forms (as for one nested recursive call), and for primitive recursive forms. In some cases this improves the ''worst case'' results of H.R. Nielson and F. Nielson: Bounded Fixed Point Iteration, but more importantly it gives much better ''average case'' results.Downloads
Publiceret
1992-02-01
Citation/Eksport
Nielson, F., & Nielson, H. R. (1992). Fitness Conditions for fixed Point Iteration. DAIMI Report Series, 21(384). https://doi.org/10.7146/dpb.v21i384.6617
Nummer
Sektion
Articles
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.