Home

Retrospective: The Essence of Compiling with Continuations

(link)

From 20 years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: 1979 - 1999. A Selection.

A one page retrospective of this highly important paper. Useful as a guide to the literature and related research.

By Ehud Lamm at 2004-07-05 09:29 | Theory | other blogs | 14964 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The original paper is one of

The original paper is one of the papers highlighted in the LtU papers page, by the way.

By Ehud Lamm at Mon, 2004-07-05 12:45 | login or register to post comments

Another retrospective seems to disagree

Olin Shivers in Higher-order
control-flow
analysis in retrospect:
Lessons learned, lessons abandoned:

In 2002, then, CPS would appear to be a lesson abandoned. I
would argue that the use of CPS remains a boon to program analysis.
Not only does CPS provide a uniform representation of control
structure, it also packages up evaluation context into a familiar
form: lambda. A functional-program analysis system already has
powerful machinery for reasoning about lambdas; the CPS transform
allows this machinery to be employed to reason about context,
as well. Without CPS, separate contextual analyses and transforms
must be also implemented—redundantly, in my view.
In the fourteen years that have passed since the publication of
“Control-flow analysis in Scheme,” I have seen many developments
of
k-CFA variants done in a direct-style setting. They are all, to
my eye, needlessly complicated by the profusion of control points
and control mechanisms made necessary by direct style—harder to
develop, harder to understand.

By Andris Birkmanis at Sun, 2005-01-23 17:19 | login or register to post comments

CPS, ANF, SSA

There was some discussion of CPS vs. A-normal form and the imperative-oriented alternative, Static Single Assignment, in the recent comp.lang.scheme thread Comparison of CPS, ANF, and SSA.

Functional compiler writers seem to mostly like ANF, but that doesn't necessarily negate Olin's perspective, since he seems focused on CFA and perhaps other program analyses which (I'll conjecture) may not be the only factor which matters to a compiler writer.

By Anton van Straaten at Sun, 2005-01-23 23:32 | login or register to post comments

reaction of mlton's stephen weeks

From a 2003 note to mlton-devel:

We completed the transition to SSA in December 2001, and have been
using SSA as our main IL for optimization since then. We are quite
happy with it[...]

So, to sum up, I see TECC as the first couple of steps on the path
from traditional CPS to SSA, which I view as a superior IL for
performing optimizations.

CPS -->
1. eliminate administrative redexes
2. eliminate redundant continuation arguments -- treat
the continuation as a global
3. name local blocks
4. eliminate scoping rules on block labels and variables and
replace with dominator condition on variables
--> SSA

Also check Matthias' response.

See also CPS vs SSA. His implementation of SSA is lovely, treating blocks as lambdas and phi functions as parameters. Note that his arguments seem to depend on an exhaustive whole-program closure conversion, such that the program is flattened to be first-order.

By Andy Wingo at Mon, 2011-07-11 18:06 | login or register to post comments

CWCC

Also, compiling with continuations, continued.

By Andy Wingo at Mon, 2011-07-11 18:08 | login or register to post comments