Open AccessCPS Transformation of Flow Information, Part II: Administrative Reductions
Author(s) -
Daniel Damian,
Olivier Danvy
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i36.21751
Subject(s) - mathematics , reduction (mathematics) , corollary , linear map , transformation (genetics) , flow (mathematics) , information flow , constraint (computer aided design) , abstraction , algebra over a field , discrete mathematics , pure mathematics , geometry , chemistry , biochemistry , linguistics , philosophy , epistemology , gene
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. Preservation of least solutions solves a problem that was left open in Palsberg and Wand's article "CPS Transformation of Flow Information.'' Together, Palsberg and Wand's article 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. Supersedes BRICS-RS-01-40.