[gambit-list] Viewing CPS expansion?

Marc Feeley feeley at iro.umontreal.ca
Sat May 23 07:47:13 EDT 2009


On 22-May-09, at 9:51 AM, Alex Queiroz wrote:

> Hallo,
>
> On 5/22/09, Marc Feeley <feeley at iro.umontreal.ca> wrote:
>>
>> On 21-May-09, at 4:54 PM, James Long wrote:
>>
>>> `gsc' supports -expansion, but it seems to show the basic expansion
>>> into normalized gambit code.  Is there any way to show the fully
>>> CPS-transformed forms of the code?
>>
>>
>> Nope.  Gambit does not transform code to CPS style.
>>
>
>     Also more of a curiosity, why? Is CPS irremediably slower? I've
> been reading a lot about compiling lately...

In the context of a full implementation of Scheme (with first class  
continuations), the use of CPS as an intermediate representation:

1) Simplifies writing a simple non-optimizing compiler (see the 90  
minutes Scheme compiler).  Why?  Because first-class continuations  
come "for free".

2) Make it more difficult (but not impossible) to write an optimizing  
compiler.  Why?  Because an advanced static analysis is needed to  
determine which closures can be managed in a "stack like" manner.

In a multithreaded Scheme like Gambit which implements threads using  
first class continuations, this static analysis would end up  
determining that none of the continuation closures can be managed in a  
"stack like" manner (they would be allocated on the heap, which would  
put more pressure on the garbage collector, and likely decrease  
overall performance).

But in practice, very frequently continuation frames are not captured,  
and could be managed on a stack.  Gambit uses this fact to implement a  
dynamic conservative frame lifetime analysis.  Basically, when a  
continuation is captured due to a call to call/cc or a thread context  
switch, the current content of the stack is logically transferred to  
the heap (this requires a few simple pointer updates, and no copying).

It would still be possible to do this with a CPS intermediate  
representation as long as the closures corresponding to continuations  
would be marked specially.

Marc




More information about the Gambit-list mailing list