Mathematical Structures in Computer Science

Research Article

Representing Control: a Study of the CPS Transformation

Oliver Danvya1 and Andrzex Filinskia2

a1 Department of Computing and Information Sciences, Kansas State University, Manhattan Kansas 66506, USA. (danvy@cis.ksu.edu)

a2 School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA. (Andrzej.Filinski@cs.cmu.edu)

Abstract

This paper investigates the transformation of λν-terms into continuation-passing style (CPS). We show that by appropriate η-expansion of Fisher and Plotkin's two-pass equational specification of the CPS transform, we can obtain a static and context-free separation of the result terms into “essential” and “administrative” constructs. Interpreting the former as syntax builders and the latter as directly executable code, We obtain a simple and efficient one-pass transformation algorithm, easily extended to conditional expressions, recursive definitions, and similar constructs. This new transformation algorithm leads to a simpler proof of Plotkin's simulation and indifference results.

We go on to show how CPS-based control operators similar to, more general then, Scheme's call/cc can be naturally accommodated by the new transformation algorithm. To demonstrate the expressive power of these operators, we use them to present an equivalent but even more concise formulation of the efficient CPS transformation algorithm. Finally, we relate the fundamental ideas underlying this derivation to similar concepts from other work on program manipulation; we derive a one-pass CPS transformation of λn-terms; and we outline some promising areas for future research.

(Received February 00 1991)

(Revised June 00 1992)

Footnotes

This work was partly supported by NSF under grant CCR-9102625