CPS Transformation of Flow Information, Part II: Administrative Reductions

D. Damian, Olivier Danvy

    Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

    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.
    Original languageEnglish
    JournalJournal of Functional Programming
    Volume13
    Issue5
    Pages (from-to)925-933
    Number of pages9
    ISSN0956-7968
    DOIs
    Publication statusPublished - 2003

    Fingerprint

    Dive into the research topics of 'CPS Transformation of Flow Information, Part II: Administrative Reductions'. Together they form a unique fingerprint.

    Cite this