CPS Transformation of Flow Information, Part II: Administrative Reductions
DOI:
https://doi.org/10.7146/brics.v8i40.21700Resumé
We characterize the impact of a linear beta-reduction on the result of a control-flow analysis. (By ``a linear beta-reduction'' we mean the beta-reduction of a linear lambda-abstraction, i.e., of a lambda-abstraction whose parameter occurs exactly once in its body.)As a corollary, we consider the administrative reductions of a Plotkin-style transformation into continuation-passing style (CPS), and how they affect the result of a constraint-based control-flow analysis and in particular the least element in the space of solutions. We show that administrative reductions preserve the least solution. Since we know how to construct least solutions, preservation of least solutions solves a problem that was left open in Palsberg and Wand's paper ``CPS Transformation of Flow Information.''
Therefore, together, Palsberg and Wand's article ``CPS Transformation of Flow Information'' and the present article show how to map, in linear time, the least solution of the flow constraints of a program into the least solution of the flow constraints of the CPS counterpart of this program, after administrative reductions. Furthermore, we show how to CPS transform control-flow information in one pass.
Superseded by BRICS-RS-02-36.
Downloads
Publiceret
2001-10-04
Citation/Eksport
Damian, D., & Danvy, O. (2001). CPS Transformation of Flow Information, Part II: Administrative Reductions. BRICS Report Series, 8(40). https://doi.org/10.7146/brics.v8i40.21700
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).