Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #780

Re: basic question about cps

Show all headers | View raw

n.oje.bar@gmail.com 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
constructs).

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
you.

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
libraries.

	Torben

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

basic question about cps n.oje.bar@gmail.com - 2012-11-12 11:05 -0800
  Re: basic question about cps torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-11-14 11:25 +0100
  Re: basic question about cps Stefan Monnier <monnier@iro.umontreal.ca> - 2012-11-14 11:13 -0500
    Re: basic question about cps n.oje.bar@gmail.com - 2012-11-21 09:27 -0800

csiph-web