[plt-scheme] Behind the scenes, is everything running using continuation passing style?

On Nov 14, 2007, at 9:13 AM, Arthur Nunes-Harwit wrote:

>> If you *really* want to understand what's going on with CPS for
>> compilation, read also the paper on A-normalization:
>>
>>  PLDI 93 Flanagan, Sabry, Duba and Felleisen
>>  The Essence of Compiling with Continuations
>>  http://www.cs.rice.edu/CS/PLT/Publications/Scheme/pldi93-fsdf.ps.gz
>
>   An extension of this work is _A Reflection on Call-by-Value_ by  
> Sabry and Wadler.  One of the results is that the CPS language and  
> the ANF language are isomorphic.  (One might consider their CPS  
> language somewhat different in that continuations are not values.)   
> Thus I tend to take the (radical?) view these compilation  
> techniques as equivalent.  A linearization based on a  
> transformation to post-fix notation that subsequently becomes stack- 
> machine code (see Norvig's Paradigms of AI Programming) strikes me  
> as very different.
>
>   As others have said, my impression is that ANF has become a very  
> popular intermediate representation.  While it is not CPS, it is  
> surely a close cousin.


As the originator of ANF, let me add some advice here:

1. ANF came from work that Amr and I conducted in 92 on showing the  
Curry-style equivalence of CBV LC and CBN LC. There were rumors  
around that CPS added equational reasoning power. After all, the  
target language no longer cares whether you reduce by-name or by- 
value. We showed that by adding a set A of simple, strongly  
normalizing reductions on the SOURCE side, you got back this  
'isomorphism'. See LFP 1992.

2. We then recognized that the normal form induced by A was a good  
intermediate from and explained the step from SOURCE to TARGET and  
that this intermediate form exhibited the essential elements of CPS  
intermediate form. But it wasn't identical.

3. Sabry and Wadler added a wrinkle to the isomorphism of 1. I  
consider almost a detour in this story.

4. There is sufficient evidence that CPS still has one advantage,  
concerning join points of control flow. That is, it is easier to  
linearize from CPS than from ANF. The person who has articulated it  
best is Steve Weeks (a former PLT undergraduate) with postings and  
his MLton compiler. The one write-up of their work I know is "Fluet &  
Weeks, Contification using dominators, ICFP 2001." (Also see this  
year's ICFP for a follow-up on this from MSR @ Cambridge on compiling  
F#.)

5. There are people who prefer cps by knee-jerk. Don't pay attention.  
They don't understand the trade-offs.

;; ---

When you do implement call/cc with cps, you give up the "native"  
stack. Doable but a high cost for integrating with the rest of the  
world. As SK points out and I emphasize :-), the best synthesis is to  
map cps continuation manipulations into small "native" stack  
operations. Dybvig and Hieb's strategy of lazily copying the stack is  
by far the best. Clinger has an excellent survey paper on the topic,  
comparing different strategies, their [dis]advantages and benchmarks.

But of course, you really have to believe that call/cc and friends  
are essential to go through all this work.

Even though I spent over 10 years researching continuations and I  
consider it tremendous fun, I do not think that this is a bottleneck  
and see other issues as more important than a fast call/cc  
implementation.

-- Matthias