From: Mikael Brockman <phubuh@...>
Date: 2004-07-20T01:15:21+09:00
Subject: Re: Compiling Ruby code

Kristof Bastiaensen <kristof@vleeuwen.org> writes:

> On Tue, 20 Jul 2004 00:00:22 +0900, Mikael Brockman wrote:
>
> Hi,
>
>> Kristof Bastiaensen <kristof@vleeuwen.org> writes:
>> 
>>> Well, I do think it is possible to compile Ruby, but it would be to hard.
>>> Firstly eval and module_eval should be thrown away, because they need to
>>> be able to parse code at runtime.
>>> Continuations make compiling very messy, since the stack needs to be
>>> copied.
>> 
>> That's not strictly true.  If you convert the code to
>> continuation-passing style, reifying continuations doesn't require
>> copying the stack.  CHICKEN and many other Scheme compilers choose this
>> approach.
>> 
>>   mikael
>
> That's interesting.  Could you explain how that works?
> My idea was that when a continuation is saved, it needs
> to keep the information, where it is going to (return
> adresses), and all local bindings.  I would think the best
> way is to save the stack, at least for compiled (machine)
> code.

In continuation-passing style, no expressions ever return.  When you
rewrite an expression into CPS, the value that it would return is
instead applied to a function that the expression receives as an
argument.  For example,

  f (g x)

is rewritten as

  (\k -> g x (\v -> f v k))

where \v -> e denotes the function from v to e.  Every program can be
converted to this style.  In this style, call/cc is a trivial operation,
since every expression receives its reified continuation as an argument.

You might want to read Danvy's ``Three Steps for the CPS
Transformation''[1] and Baker's ``CONS Should Not CONS Its Arguments,
Part II: Cheney on the MTA''[2].

[1] http://www.daimi.au.dk/~danvy/Papers/3steps.ps.gz
[2] http://home.pipeline.com/~hbaker1/CheneyMTA.html

  mikael