Home > Archive > Functional > May 2007 > Not continuation passing style
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Not continuation passing style
|
|
| Jon Harrop 2007-05-04, 10:04 pm |
|
Compilers like SML/NJ transform function calls into CPS. This has the
advantage of avoiding stack overflows but incurs a performance cost.
I'm wondering if anyone has tried to do the opposite. Can you transform CPS
code back into stack-eating code to make it run faster? Maybe resort to CPS
when you're running low on stack?
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/produc...journal/?usenet
| |
| Marcin 'Qrczak' Kowalczyk 2007-05-05, 8:02 am |
| Dnia 05-05-2007, sob o godzinie 02:21 +0100, Jon Harrop napisa=C5=82(a):
> I'm wondering if anyone has tried to do the opposite. Can you transform C=
PS
> code back into stack-eating code to make it run faster?
It would require whole program analysis to be sure that the
continuations are only entered once, and in the reverse order
of their creation. I doubt it can be practical.
> Maybe resort to CPS when you're running low on stack?
The stack doesn't have to be limited to a fixed size. Some compilers
reallocate it on overflow.
--=20
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
| |
| Neelakantan Krishnaswami 2007-05-07, 7:04 pm |
| In article <463bdd7f$0$8758$ed2619ec@ptn-nntp-reader02.plus.net>, Jon Harrop
wrote:
>
> Compilers like SML/NJ transform function calls into CPS. This has
> the advantage of avoiding stack overflows but incurs a performance
> cost.
>
> I'm wondering if anyone has tried to do the opposite. Can you
> transform CPS code back into stack-eating code to make it run
> faster? Maybe resort to CPS when you're running low on stack?
CPS, as an intermediate representation, simply makes the control
context apparent in the source code. This does require you to have
have a heap-allocated continuation in your compiled code. For example,
the Moby compiler (whose runtime features a stack) will convert part
of a program into CPS in order to efficiently compile nested
recursions into nested loops.
But to answer your question, one cute way of representing a CPS-style
IR is to put it in a monadic style:
cps(x) == return x
cps(\x.e) == return (\x. cps(e))
cps(e e') == letv f = cps(e) in
letv v = cps(e') in
f(v)
As long as return and the monadic bind letv are interpreted in the
continuation monad, then this code is in CPS style. If you you never
use the explicit control context -- ie, you don't use call/cc -- you
can convert back to direct-style just by changing the monad you
interpret this program in from the continuation monad to the identity
monad.
--
Neel R. Krishnaswami
neelk@cs.cmu.edu
| |
| Jon Harrop 2007-05-07, 10:03 pm |
| Neelakantan Krishnaswami wrote:
> CPS, as an intermediate representation, simply makes the control
> context apparent in the source code. This does require you to have
> have a heap-allocated continuation in your compiled code. For example,
> the Moby compiler (whose runtime features a stack) will convert part
> of a program into CPS in order to efficiently compile nested
> recursions into nested loops.
Very interesting. Thanks.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/produc...journal/?usenet
| |
| Torben Ęgidius Mogensen 2007-05-08, 4:09 am |
| Jon Harrop <jon@ffconsultancy.com> writes:
> Compilers like SML/NJ transform function calls into CPS. This has the
> advantage of avoiding stack overflows but incurs a performance cost.
>
> I'm wondering if anyone has tried to do the opposite. Can you transform CPS
> code back into stack-eating code to make it run faster? Maybe resort to CPS
> when you're running low on stack?
There are two answers to this:
1. You can run the CPS program through an analysis that detects if
closures can be stack allocated. If you don't use control
operators etc., the continuations all can.
2. Olivier Danvy has written papers about converting CPS code into
direct-style code: http://citeseer.ist.psu.edu/danvy92back.html,
http://portal.acm.org/citation.cfm?id=141564 .
Torben
| |
| Ben Rudiak-Gould 2007-05-10, 10:04 pm |
| Jon Harrop wrote:
> Compilers like SML/NJ transform function calls into CPS. This has the
> advantage of avoiding stack overflows but incurs a performance cost.
I've never heard a lack of stack space mentioned as a reason for using CPS.
If that's a problem then you can just allocate a bigger stack. On the other
hand, putting your stack frames on the heap does make it a lot easier to
write a portable garbage collector, and I think many language implementors
do it for that reason. There's also the "Cheney on the M.T.A." technique,
which is an interesting hybrid.
-- Ben
| |
| Andrew Reilly 2007-05-10, 10:04 pm |
| On Thu, 10 May 2007 17:21:14 +0100, Ben Rudiak-Gould wrote:
> I've never heard a lack of stack space mentioned as a reason for using CPS.
> If that's a problem then you can just allocate a bigger stack.
It's been mentioned in the context of Java VMs for the case where you want
to support gazillions of threads (each with their own "stack") on a 32-bit
machine: there is conflict between running out of virtual memory or
unnecessarily constraining the per-thread stack size. CPS allows you to
smoosh all of the threads together into the one space, so that virtual
memory use tracks physical memory use more closely.
Of course, going to a 64-bit address space is also a way to avoid that
problem, and allows the continued use of the fairly efficient stack
structure. [As is a multi-process, rather than multi-thread, model.]
Cheers,
--
Andrew
| |
| Torben Ęgidius Mogensen 2007-05-11, 4:13 am |
| Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
> On Thu, 10 May 2007 17:21:14 +0100, Ben Rudiak-Gould wrote:
>
> It's been mentioned in the context of Java VMs for the case where you want
> to support gazillions of threads (each with their own "stack") on a 32-bit
> machine: there is conflict between running out of virtual memory or
> unnecessarily constraining the per-thread stack size. CPS allows you to
> smoosh all of the threads together into the one space, so that virtual
> memory use tracks physical memory use more closely.
That is not really an argument for CPS, but for using linked
heap-allocated frames as an implementation of the stack. CPS
conversion is one way of achieving this, but on JVM you need a bit
more as tailcalls (essential for CPS) are not directly supported.
Torben
|
|
|
|
|