[gambit-list] Viewing CPS expansion?
feeley at iro.umontreal.ca
Sat May 23 07:47:13 EDT 2009
On 22-May-09, at 9:51 AM, Alex Queiroz wrote:
> 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
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.
More information about the Gambit-list