Re: basic question about cps (Torben Ęgidius Mogensen)
Wed, 14 Nov 2012 11:25:37 +0100

          From comp.compilers

Related articles
basic question about cps (2012-11-12)
Re: basic question about cps (2012-11-14)
Re: basic question about cps (Stefan Monnier) (2012-11-14)
Re: basic question about cps (2012-11-21)
| List of all articles for this month |

From: (Torben Ęgidius Mogensen)
Newsgroups: comp.compilers
Date: Wed, 14 Nov 2012 11:25:37 +0100
Organization: - Supporting Open source
References: 12-11-004
Keywords: analysis
Posted-Date: 15 Nov 2012 00:04:43 EST writes:

> Hi, I have a basic question about writing a compiler using
> continuation-passing style as an intermediate language.
> It seems to me that if one performs the cps transformation one is left
> with many 'computed' calls (that is call to variables holding
> procedure values, namely, the continuation). It seems that compiling
> such 'computed' calls would be much slower than compiling 'direct'
> calls to known procedures.
> Question:
> 1. Is this assumption valid?
> 2. If it is, then it seems that cps is not very useful without some
> non-trivial control flow analysis...??

There are indeed a lot of calls when you do CPS transformation, but
the majority of these are tail-calls, so if you do tail-call
optimisation, you are not so bad off. Also, while closures in general
need to be heap allocated, continuation closures can be stack
allocated (unless they are captured with call/cc or similar

Depending on which formulation of CPS transformation you use, you may
also end up with a lot of so-called "administrative redexes", which
you can reduce at compile time.

With the above "optimisations", the code you get is very similar to
"normal" compiled code that uses a stack of activation records. The
advantage of using CPS is that inlining and other transformations are
simpler on the CPS form than in traditional intermediate code. You
also get some of the dataflow-analysis advantages that SSA form gives

A good place to get in-depth coverage of CPS as an intermediate form
is Andrew Appel's book "Compiling with Continuations". I don't think
it is in print anymore, but you can probably get it at most CS


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.