CPS Update

CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1076 bytes --]

Hello,

The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now
includes support for toplevel references and sets, thanks mostly to Andy's
work on supporting them in RTL. (Although you shouldn't kick that part of
it too hard just yet; I think I know where it will break.) Other highlights
include using the top-level variable support to evaluate "(+ 3 4)"
correctly.

Overall, I think it's coming along well. The parts of Tree-IL that are left
to implement are local mutable variables (should be easy after toplevel
ones), module references and sets (very similar to top-level ones),
closures, and the dynamic environment stuff. Local mutable variables are my
next project, and then I think closures.

One question I've had is, can we assume that the variables in the (guile)
module are immutable? I think the current compiler does this. Otherwise
there's no correct way to inline primitive procedures like + unless we have
a way to invalidate our compiled code and recompile it (which I would like
to have anyway, but that's a different story).

Best,
Noah

[-- Attachment #2: Type: text/html, Size: 1318 bytes --]

Re: CPS Update

[Stefan Israelsson Tampe]

Hey Noha,

Great work indeed.

Isn't the primitiveness decided by tree-il? you wil get a (<primcall>
...) tree il element and then should know how to emit a
corresponding primitive instruction(s). Anyway I think that your
conclusion is right, it would not make sense to support overwriting
these primitives dynamically, but

scheme@(guile-user)> (set! + (lambda x (apply * x)))
scheme@(guile-user)> (+ 2 3)
$1 = 6
scheme@(guile-user)> (define (f x y) (+ x y))
scheme@(guile-user)> ,x f
Disassembly of #<procedure f (x y)>:

   0    (assert-nargs-ee/locals 2)      ;; 2 args, 0 locals
   2    (local-ref 0)                   ;; `x'
   4    (local-ref 1)                   ;; `y'
   6    (add)
   7    (return)

So things are not consistent!

BTW
If you like I could work on getting define* and lambda* to work, I
have that code in my branch and should be able
to make it work on your branch as well. WDYT?

/Stefan

On Sat, Feb 16, 2013 at 1:53 AM, Noah Lavine <noah.b.lavine@gmail.com> wrote:
> Hello,
>
> The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now
> includes support for toplevel references and sets, thanks mostly to Andy's
> work on supporting them in RTL. (Although you shouldn't kick that part of it
> too hard just yet; I think I know where it will break.) Other highlights
> include using the top-level variable support to evaluate "(+ 3 4)"
> correctly.
>
> Overall, I think it's coming along well. The parts of Tree-IL that are left
> to implement are local mutable variables (should be easy after toplevel
> ones), module references and sets (very similar to top-level ones),
> closures, and the dynamic environment stuff. Local mutable variables are my
> next project, and then I think closures.
>
> One question I've had is, can we assume that the variables in the (guile)
> module are immutable? I think the current compiler does this. Otherwise
> there's no correct way to inline primitive procedures like + unless we have
> a way to invalidate our compiled code and recompile it (which I would like
> to have anyway, but that's a different story).
>
> Best,
> Noah
>

Re: CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 3191 bytes --]

Hello,


On Sat, Feb 16, 2013 at 2:39 AM, Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:
>
> Isn't the primitiveness decided by tree-il? you wil get a (<primcall>
> ...) tree il element and then should know how to emit a
> corresponding primitive instruction(s).


Oh, you're right. I was thinking about that because I don't run the Tree-IL
optimizers when I test it, so I don't get any Tree-IL primitives.
Eventually maybe the primitive generation should happen in CPS, but I don't
think it has to happen all at once.


> Anyway I think that your
> conclusion is right, it would not make sense to support overwriting
> these primitives dynamically, but
>
> scheme@(guile-user)> (set! + (lambda x (apply * x)))
> scheme@(guile-user)> (+ 2 3)
> $1 = 6
> scheme@(guile-user)> (define (f x y) (+ x y))
> scheme@(guile-user)> ,x f
> Disassembly of #<procedure f (x y)>:
>
>    0    (assert-nargs-ee/locals 2)      ;; 2 args, 0 locals
>    2    (local-ref 0)                   ;; `x'
>    4    (local-ref 1)                   ;; `y'
>    6    (add)
>    7    (return)
>
> So things are not consistent!
>

Good example! This looks like a bug to me. I think I read that loading
GOOPS turns things like '+ into generic operations - that might be a case
where this matters a lot.

I have thought a bit about how to fix this. The module system already
allows us to be notified whenever a variable changes, so it would be easy
to watch all of the variables in (guile) and recompile procedures when they
change. I might take a look at this soon.


> BTW
> If you like I could work on getting define* and lambda* to work, I
> have that code in my branch and should be able
> to make it work on your branch as well. WDYT?


Thanks, but I haven't even gotten far enough to think about this. I'm still
working on getting all of the basic features going. After that I would
definitely like define* and lambda*.

Noah


>
> /Stefan
>
> On Sat, Feb 16, 2013 at 1:53 AM, Noah Lavine <noah.b.lavine@gmail.com>
> wrote:
> > Hello,
> >
> > The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now
> > includes support for toplevel references and sets, thanks mostly to
> Andy's
> > work on supporting them in RTL. (Although you shouldn't kick that part
> of it
> > too hard just yet; I think I know where it will break.) Other highlights
> > include using the top-level variable support to evaluate "(+ 3 4)"
> > correctly.
> >
> > Overall, I think it's coming along well. The parts of Tree-IL that are
> left
> > to implement are local mutable variables (should be easy after toplevel
> > ones), module references and sets (very similar to top-level ones),
> > closures, and the dynamic environment stuff. Local mutable variables are
> my
> > next project, and then I think closures.
> >
> > One question I've had is, can we assume that the variables in the (guile)
> > module are immutable? I think the current compiler does this. Otherwise
> > there's no correct way to inline primitive procedures like + unless we
> have
> > a way to invalidate our compiled code and recompile it (which I would
> like
> > to have anyway, but that's a different story).
> >
> > Best,
> > Noah
> >
>

[-- Attachment #2: Type: text/html, Size: 4494 bytes --]

Re: CPS Update

[Mark H Weaver]

Noah Lavine <noah.b.lavine@gmail.com> writes:
> Oh, you're right. I was thinking about that because I don't run the
> Tree-IL optimizers when I test it, so I don't get any Tree-IL
> primitives.

I think you should be running the existing tree-il passes before you
convert to CPS.  As I pointed out earlier, many optimizers will not be
able to work well after conversion to CPS, fundamentally because CPS
loses information about where order of evaluation is unspecified.

Furthermore, some of the existing passes make important simplifications
to the resulting tree-il.  For example, the code in fix-letrec.scm
eliminates all <letrec> nodes, so that's one less thing for you to have
to implement.  Primitives.scm marks primitives explicitly using
<primcall> tree-il nodes, so that later code doesn't have to make thorny
assumptions about what variables should be considered primitives.

> I think I read that loading GOOPS turns things like '+ into generic
> operations - that might be a case where this matters a lot.

No, because GOOPS has a special mechanism for cases like '+': they are
called "primitive generics".  When numerical operations are unable to
handle the argument types provided, they calls 'scm_wta_dispatch_*'.
Therefore, adding new methods to numerical operations does not involve
changing their bindings.  This is good because it means that you can
extend numerical operations without slowing them down at all for
built-in numbers.

> I have thought a bit about how to fix this. The module system already
> allows us to be notified whenever a variable changes, so it would be
> easy to watch all of the variables in (guile) and recompile procedures
> when they change. I might take a look at this soon.

This would be nice too, of course, but I warn you that it's a can of
worms.  In the general case, it involves on-stack replacement, because
you might need to recompile a procedure that's currently in the middle
of being run, and thus currently has activation records on the stack(s).

Thanks for you work on this, Noah!

      Mark

Re: CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 2990 bytes --]

Hello,

On Sat, Feb 16, 2013 at 2:14 PM, Mark H Weaver <mhw@netris.org> wrote:

> Noah Lavine <noah.b.lavine@gmail.com> writes:
> > Oh, you're right. I was thinking about that because I don't run the
> > Tree-IL optimizers when I test it, so I don't get any Tree-IL
> > primitives.
>
> I think you should be running the existing tree-il passes before you
> convert to CPS.  As I pointed out earlier, many optimizers will not be
> able to work well after conversion to CPS, fundamentally because CPS
> loses information about where order of evaluation is unspecified.
>
> Furthermore, some of the existing passes make important simplifications
> to the resulting tree-il.  For example, the code in fix-letrec.scm
> eliminates all <letrec> nodes, so that's one less thing for you to have
> to implement.  Primitives.scm marks primitives explicitly using
> <primcall> tree-il nodes, so that later code doesn't have to make thorny
> assumptions about what variables should be considered primitives.


Interesting points. I think you're right that Tree-IL should be optimized
first. For the specific issue of order of evaluation, I'm hoping to add
something (either a special function or a special node type) to CPS to
represent continuations that can be evaluated in any order. It seems like
evaluation order is a decision that should be made in either the code
generator or the register allocator, and those operate on CPS. I also
dislike losing information.


> > I think I read that loading GOOPS turns things like '+ into generic
> > operations - that might be a case where this matters a lot.
>
> No, because GOOPS has a special mechanism for cases like '+': they are
> called "primitive generics".  When numerical operations are unable to
> handle the argument types provided, they calls 'scm_wta_dispatch_*'.
> Therefore, adding new methods to numerical operations does not involve
> changing their bindings.  This is good because it means that you can
> extend numerical operations without slowing them down at all for
> built-in numbers.
>

I see. That's very cool.


>
> > I have thought a bit about how to fix this. The module system already
> > allows us to be notified whenever a variable changes, so it would be
> > easy to watch all of the variables in (guile) and recompile procedures
> > when they change. I might take a look at this soon.
>
> This would be nice too, of course, but I warn you that it's a can of
> worms.  In the general case, it involves on-stack replacement, because
> you might need to recompile a procedure that's currently in the middle
> of being run, and thus currently has activation records on the stack(s).
>

You mean if a function modifies another function that called it. Yes, that
seems complicated. It's not very important to me to fix it in general,
because I don't know of a case where it's useful. I think fixing it without
the on-stack replacement would be a reasonable compromise.


> Thanks for you work on this, Noah!
>

Thank you!

Noah

[-- Attachment #2: Type: text/html, Size: 4157 bytes --]

Re: CPS Update

[Mark H Weaver]

Hi Noah,

> On Sat, Feb 16, 2013 at 2:14 PM, Mark H Weaver <mhw@netris.org> wrote:
[...]
>     Noah Lavine <noah.b.lavine@gmail.com> writes:
[...]
>     > I have thought a bit about how to fix this. The module system already
>     > allows us to be notified whenever a variable changes, so it would be
>     > easy to watch all of the variables in (guile) and recompile procedures
>     > when they change. I might take a look at this soon.
>     
>     
>     This would be nice too, of course, but I warn you that it's a can of
>     worms.  In the general case, it involves on-stack replacement, because
>     you might need to recompile a procedure that's currently in the middle
>     of being run, and thus currently has activation records on the
>     stack(s).
>     
>
> You mean if a function modifies another function that called it.

There are many other cases.  Think multiple threads, coroutines, logic
programming systems, etc.  That's why I wrote "stack(s)".  Actually, I
should have written "(partial) continuation(s)".  There are any number
of ways that an activation record for some procedure you modify could
still be alive somewhere in the heap.  The issue can arise even with
simple lazy data structures.  I don't think it's something we should
punt on.  IMO anyway.

What do you think?

    Mark

Re: CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1899 bytes --]

Hello,

On Sat, Feb 16, 2013 at 4:18 PM, Mark H Weaver <mhw@netris.org> wrote:

> Hi Noah,
>
> > On Sat, Feb 16, 2013 at 2:14 PM, Mark H Weaver <mhw@netris.org> wrote:
> [...]
> >     Noah Lavine <noah.b.lavine@gmail.com> writes:
> >
> > You mean if a function modifies another function that called it.
>
> There are many other cases.  Think multiple threads, coroutines, logic
> programming systems, etc.  That's why I wrote "stack(s)".  Actually, I
> should have written "(partial) continuation(s)".  There are any number
> of ways that an activation record for some procedure you modify could
> still be alive somewhere in the heap.  The issue can arise even with
> simple lazy data structures.  I don't think it's something we should
> punt on.  IMO anyway.
>
> What do you think?
>

Yes, you're right. I hadn't thought about those cases. This is a tricky
question.

But before we continue, are you sure that the right semantics is to modify
all of the continuations? In particular, let's say you have a function like
this:

(define (func x)
  (+ x 2 (my-special-function x)))

And my-special-function captures its continuation, k. Later on, you modify
func to be this:

(define (func x)
  (+ x 2))

Now what is the continuation k supposed to do? That continuation doesn't
exist in the latest version of func. I think in this case you have to treat
it like a closure that is still holding on to the continuation that it was
passed (conceptually, at least) when it was called. So it would return to
the old version of func.

On the other hand, take the same example, but this time redefine "+"
instead of "func". Now, does the continuation k call the new definition of
+, or the old one?

These really are questions for me. I don't know what the correct behavior
here is, but I think that if we can answer both of these questions, then we
know more or less what the correct thing to do is.

Noah

[-- Attachment #2: Type: text/html, Size: 2811 bytes --]

Re: CPS Update

[Mark H Weaver]

Noah Lavine <noah.b.lavine@gmail.com> writes:
> But before we continue, are you sure that the right semantics is to
> modify all of the continuations? In particular, let's say you have a
> function like this:
>
> (define (func x)
>   (+ x 2 (my-special-function x)))
>
> And my-special-function captures its continuation, k. Later on, you
> modify func to be this:
>
> (define (func x)
>   (+ x 2))
>
> Now what is the continuation k supposed to do? That continuation
> doesn't exist in the latest version of func. I think in this case you
> have to treat it like a closure that is still holding on to the
> continuation that it was passed (conceptually, at least) when it was
> called. So it would return to the old version of func.

Yes.  If you redefine 'func', that only affects future calls to func,
not existing calls.

> On the other hand, take the same example, but this time redefine "+"
> instead of "func". Now, does the continuation k call the new
> definition of +, or the old one?

In your example above, it's unspecified, because the operator and
operands of a procedure call are evaluated in unspecified order.
Therefore, an implementation is allowed to evaluate '+' either before or
after it evaluates (my-special-function x).

However, consider this slightly different example:

(define (func x)
  (let ((r (my-special-function x)))
    (+ x 2 r)))

Here, (my-special-function x) must be evaluated before evaluating '+'.
Evaluating '+' means to fetch the value stored in the location denoted
by '+'.  Therefore, if '+' is rebound during the call to
'my-special-function', then the new binding for '+' must be used.

This is a case where on-stack-replacement is needed to implement the
correct semantics.

To summarize, when you rebind a function 'foo', it is not the existing
activation records for 'foo' that you need to worry about.  Instead, you
need to worry about existing activation records for all compiled
procedures 'bar' that incorporated assumptions about 'foo'.

Thanks for working on this,

     Mark

Re: CPS Update

[Stefan Israelsson Tampe]

Hi,

1. Does any other system recompile stuff that set! a + operation
2. Isn't the least we should do to warn when a user set! + as I did in
the last email
3. Wouldn't it be a good idea to allow a user to specify which basic
vm op's would be translated
   to a macine instruction or not. So say that I would like to count
the number of scheme + guile uses at
   startup, then I could specify in a configuration that + should not
be comiled to a vm-op and then recompile guile and then use set!

On Sat, Feb 16, 2013 at 5:29 PM, Noah Lavine <noah.b.lavine@gmail.com> wrote:
> Hello,
>
>
> On Sat, Feb 16, 2013 at 2:39 AM, Stefan Israelsson Tampe
> <stefan.itampe@gmail.com> wrote:
>>
>> Isn't the primitiveness decided by tree-il? you wil get a (<primcall>
>> ...) tree il element and then should know how to emit a
>> corresponding primitive instruction(s).
>
>
> Oh, you're right. I was thinking about that because I don't run the Tree-IL
> optimizers when I test it, so I don't get any Tree-IL primitives. Eventually
> maybe the primitive generation should happen in CPS, but I don't think it
> has to happen all at once.
>
>>
>> Anyway I think that your
>> conclusion is right, it would not make sense to support overwriting
>> these primitives dynamically, but
>>
>> scheme@(guile-user)> (set! + (lambda x (apply * x)))
>> scheme@(guile-user)> (+ 2 3)
>> $1 = 6
>> scheme@(guile-user)> (define (f x y) (+ x y))
>> scheme@(guile-user)> ,x f
>> Disassembly of #<procedure f (x y)>:
>>
>>    0    (assert-nargs-ee/locals 2)      ;; 2 args, 0 locals
>>    2    (local-ref 0)                   ;; `x'
>>    4    (local-ref 1)                   ;; `y'
>>    6    (add)
>>    7    (return)
>>
>> So things are not consistent!
>
>
> Good example! This looks like a bug to me. I think I read that loading GOOPS
> turns things like '+ into generic operations - that might be a case where
> this matters a lot.
>
> I have thought a bit about how to fix this. The module system already allows
> us to be notified whenever a variable changes, so it would be easy to watch
> all of the variables in (guile) and recompile procedures when they change. I
> might take a look at this soon.
>
>>
>> BTW
>> If you like I could work on getting define* and lambda* to work, I
>> have that code in my branch and should be able
>> to make it work on your branch as well. WDYT?
>
>
> Thanks, but I haven't even gotten far enough to think about this. I'm still
> working on getting all of the basic features going. After that I would
> definitely like define* and lambda*.
>
> Noah
>
>>
>>
>> /Stefan
>>
>> On Sat, Feb 16, 2013 at 1:53 AM, Noah Lavine <noah.b.lavine@gmail.com>
>> wrote:
>> > Hello,
>> >
>> > The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It
>> > now
>> > includes support for toplevel references and sets, thanks mostly to
>> > Andy's
>> > work on supporting them in RTL. (Although you shouldn't kick that part
>> > of it
>> > too hard just yet; I think I know where it will break.) Other highlights
>> > include using the top-level variable support to evaluate "(+ 3 4)"
>> > correctly.
>> >
>> > Overall, I think it's coming along well. The parts of Tree-IL that are
>> > left
>> > to implement are local mutable variables (should be easy after toplevel
>> > ones), module references and sets (very similar to top-level ones),
>> > closures, and the dynamic environment stuff. Local mutable variables are
>> > my
>> > next project, and then I think closures.
>> >
>> > One question I've had is, can we assume that the variables in the
>> > (guile)
>> > module are immutable? I think the current compiler does this. Otherwise
>> > there's no correct way to inline primitive procedures like + unless we
>> > have
>> > a way to invalidate our compiled code and recompile it (which I would
>> > like
>> > to have anyway, but that's a different story).
>> >
>> > Best,
>> > Noah
>> >
>
>

Re: CPS Update

[William ML Leslie]

On 20 February 2013 03:21, Mark H Weaver <mhw@netris.org> wrote:
> (define (func x)
>   (let ((r (my-special-function x)))
>     (+ x 2 r)))
>
> Here, (my-special-function x) must be evaluated before evaluating '+'.
> Evaluating '+' means to fetch the value stored in the location denoted
> by '+'.  Therefore, if '+' is rebound during the call to
> 'my-special-function', then the new binding for '+' must be used.
>
> This is a case where on-stack-replacement is needed to implement the
> correct semantics.
>
> To summarize, when you rebind a function 'foo', it is not the existing
> activation records for 'foo' that you need to worry about.  Instead, you
> need to worry about existing activation records for all compiled
> procedures 'bar' that incorporated assumptions about 'foo'.

Recompiling every procedure that uses + when somebody binds it means
compiling a lot of code that probably isn't going to be used.  More
likely, if + has been inlined here, the compiler will have to emit a
guard that checks inlining assumptions as the start of the let body.
This is how those sort of semantics are preserved where OSR is not
implemented.

Regarding rebinding (+): A few people have expressed opinions about
scheme becoming less fluid, and I think most would probably agree that
even if certain bindings are assumed constant or types are declared in
module APIs and specialised code generated, the most-general code
still wants to be available, and ideally from within the .so .

-- 
William Leslie

Re: CPS Update

[Mark H Weaver]

William ML Leslie <william.leslie.ttg@gmail.com> writes:

> On 20 February 2013 03:21, Mark H Weaver <mhw@netris.org> wrote:
>> (define (func x)
>>   (let ((r (my-special-function x)))
>>     (+ x 2 r)))
>>
>> Here, (my-special-function x) must be evaluated before evaluating '+'.
>> Evaluating '+' means to fetch the value stored in the location denoted
>> by '+'.  Therefore, if '+' is rebound during the call to
>> 'my-special-function', then the new binding for '+' must be used.
>>
>> This is a case where on-stack-replacement is needed to implement the
>> correct semantics.
>>
>> To summarize, when you rebind a function 'foo', it is not the existing
>> activation records for 'foo' that you need to worry about.  Instead, you
>> need to worry about existing activation records for all compiled
>> procedures 'bar' that incorporated assumptions about 'foo'.
>
> Recompiling every procedure that uses + when somebody binds it means
> compiling a lot of code that probably isn't going to be used.  More
> likely, if + has been inlined here, the compiler will have to emit a
> guard that checks inlining assumptions as the start of the let body.

I'm afraid this isn't good enough.  Even if one ignores the possibility
of multiple threads, checks would have to be added not just at the start
of each let body, but also upon return from every procedure that might
rebind '+' or capture its continuation.  This includes all procedures
accessed through toplevel/module bindings.

Therefore, I repeat my initial assertion that this is a can of worms.
I'd like to see it implemented in Guile some day, but it's a big job.

     Regards,
       Mark

Re: CPS Update

[William ML Leslie]

On 23 February 2013 18:49, Mark H Weaver <mhw@netris.org> wrote:
> William ML Leslie <william.leslie.ttg@gmail.com> writes:
>> Recompiling every procedure that uses + when somebody binds it means
>> compiling a lot of code that probably isn't going to be used.  More
>> likely, if + has been inlined here, the compiler will have to emit a
>> guard that checks inlining assumptions as the start of the let body.
>
> I'm afraid this isn't good enough.  Even if one ignores the possibility
> of multiple threads, checks would have to be added not just at the start
> of each let body, but also upon return from every procedure that might
> rebind '+' or capture its continuation.  This includes all procedures
> accessed through toplevel/module bindings.

Not each let body, the let body in the example code.  Specifically, a
guard needs to be placed whenever code with undetermined effect
happens-before a 'call' to an inlined function.  That we are talking
about happens-before means the possibility of runtime invalidation of
code is limited not only by calls to functions of unknown effect, but
also by usages of the variable.

> Therefore, I repeat my initial assertion that this is a can of worms.

Except that most dynamic compilers for imperative languages already do
this (because it's a pretty common thing to need to do).

--
William Leslie

Re: CPS Update

[Mark H Weaver]

Hi William,

William ML Leslie <william.leslie.ttg@gmail.com> writes:
> On 23 February 2013 18:49, Mark H Weaver <mhw@netris.org> wrote:
>> William ML Leslie <william.leslie.ttg@gmail.com> writes:
>>> Recompiling every procedure that uses + when somebody binds it means
>>> compiling a lot of code that probably isn't going to be used.  More
>>> likely, if + has been inlined here, the compiler will have to emit a
>>> guard that checks inlining assumptions as the start of the let body.
>>
>> I'm afraid this isn't good enough.  Even if one ignores the possibility
>> of multiple threads, checks would have to be added not just at the start
>> of each let body, but also upon return from every procedure that might
>> rebind '+' or capture its continuation.  This includes all procedures
>> accessed through toplevel/module bindings.
>
> Not each let body, the let body in the example code.

Ah, sorry, I misunderstood you.

> Specifically, a guard needs to be placed whenever code with
> undetermined effect happens-before a 'call' to an inlined function.

Yes.  Thank you for expressing it much more clearly than I had.  I would
further refine it to "a guard needs to be placed whenever code that
might mutate an inlined variable happens-before the inlined variable
would have been referenced."

> That we are talking about happens-before means the possibility of
> runtime invalidation of code is limited not only by calls to functions
> of unknown effect, but also by usages of the variable.

You bring up an important point: that a happens-before relation can be
composed of an arbitrarily long chain of other relations.  This requires
more careful study.

>> Therefore, I repeat my initial assertion that this is a can of worms.
>
> Except that most dynamic compilers for imperative languages already do
> this (because it's a pretty common thing to need to do).

I didn't realize that this technique was so commonly implemented.
Nonetheless, I worry that this technique may not perform as well for
Scheme as for other languages.  The reason is that in Scheme, calls to
procedures of unknown effect are vastly more common than in other
languages, at least for Schemes that allow arbitrary variables such as
'+' to be mutated.

Thanks for your insights.

     Regards,
       Mark

Re: CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 2578 bytes --]

Hello,

Another quick update on CPS. I just pushed patches that implement closure
conversion and use it to compile closures correctly. I think this is a big
step forward for the CPS compiler. Since the last email, I've also
implemented local mutable variables, and sequences (as part of that).

Somewhat shockingly, I think that's almost every language feature. The
other things (dynamic environment, prompts) can actually be done by making
closures and calling the functions that implement them - it's just faster
to use the RTL instructions. However, I think the primitive procedure
generation is robust enough to handle those without too much trouble.

The bigger task now is a combination of finding and eliminating bugs and
slowly removing the ugly hacks I put in there. I don't think there are too
many, but the way the closure conversion handles letrecs and the big case
statement in the  primitive instruction generator are notable examples.
There are also some arbitrary limitations in the code - things like only
allowing one argument to a procedure, or one procedure in a letrec. I put
those in because I knew I could remove them without fundamentally changing
things, and I wanted to sketch out the whole compiler first to get the
organization right. Now I need to go through and fix all of that.

But overall, I think the CPS compiler is going well.

Best,
Noah



On Fri, Feb 15, 2013 at 7:53 PM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> Hello,
>
> The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now
> includes support for toplevel references and sets, thanks mostly to Andy's
> work on supporting them in RTL. (Although you shouldn't kick that part of
> it too hard just yet; I think I know where it will break.) Other highlights
> include using the top-level variable support to evaluate "(+ 3 4)"
> correctly.
>
> Overall, I think it's coming along well. The parts of Tree-IL that are
> left to implement are local mutable variables (should be easy after
> toplevel ones), module references and sets (very similar to top-level
> ones), closures, and the dynamic environment stuff. Local mutable variables
> are my next project, and then I think closures.
>
> One question I've had is, can we assume that the variables in the (guile)
> module are immutable? I think the current compiler does this. Otherwise
> there's no correct way to inline primitive procedures like + unless we have
> a way to invalidate our compiled code and recompile it (which I would like
> to have anyway, but that's a different story).
>
> Best,
> Noah
>
>

[-- Attachment #2: Type: text/html, Size: 3161 bytes --]

Re: CPS Update

[Andy Wingo]

On Fri 08 Mar 2013 23:57, Noah Lavine <noah.b.lavine@gmail.com> writes:

> Somewhat shockingly, I think that's almost every language feature.

Wow, nice work :-))

Sounds like great stuff.  I hope to join you in this work once 2.0.8 is
out.  It's really great that you're working on this!

Cheers,

Andy
-- 
http://wingolog.org/

Re: CPS Update

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 525 bytes --]

On Sat, Mar 9, 2013 at 3:31 AM, Andy Wingo <wingo@pobox.com> wrote:

> On Fri 08 Mar 2013 23:57, Noah Lavine <noah.b.lavine@gmail.com> writes:
>
> > Somewhat shockingly, I think that's almost every language feature.
>
> Wow, nice work :-))
>
> Sounds like great stuff.  I hope to join you in this work once 2.0.8 is
> out.  It's really great that you're working on this!
>

Thanks a lot. I am not an expert by any means, and it would be great to
have someone like you who really knows what they're doing hacking at it.

Noah

[-- Attachment #2: Type: text/html, Size: 1009 bytes --]