TY - JOUR
AU - Damian, Daniel
AU - Danvy, Olivier
PY - 2002/08/05
Y2 - 2023/10/02
TI - CPS Transformation of Flow Information, Part II: Administrative Reductions
JF - BRICS Report Series
JA - BRICS
VL - 9
IS - 36
SE - Articles
DO - 10.7146/brics.v9i36.21751
UR - https://tidsskrift.dk/brics/article/view/21751
SP -
AB - 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.)<br /> <br />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.''<br /> <br />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.<br /><br />Supersedes BRICS-RS-01-40.
ER -