CPS Transformation of Flow Information, Part II: Administrative Reductions

Daniel Damian
Olivier Danvy

August 2002

Abstract:

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

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.