Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.misty.com!news.iecc.com!.POSTED!nerds-end
From: torbenm@diku.dk (Torben Ægidius Mogensen)
Newsgroups: comp.compilers
Subject: Re: basic question about cps
Date: Wed, 14 Nov 2012 11:25:37 +0100
Organization: SunSITE.dk - Supporting Open source
Lines: 41
Sender: johnl@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <12-11-009@comp.compilers>
References: <12-11-004@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: leila.iecc.com 1352955883 99306 64.57.183.58 (15 Nov 2012 05:04:43 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Thu, 15 Nov 2012 05:04:43 +0000 (UTC)
Keywords: analysis
Posted-Date: 15 Nov 2012 00:04:43 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:780

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