CPS Transformation of Flow Information, Part II: Administrative Reductions

Daniel Damian, Olivier Danvy


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.

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v9i36.21751
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library