continuations for Groovy!?

classic Classic list List threaded Threaded
22 messages Options
123
Reply | Threaded
Open this post in threaded view
|

continuations for Groovy!?

Jochen Theodorou
Hi,

I thought a little about how to make continuations possible for groovy.
And then I thought it may be easy. As far as I understand continuations,
the neat thing is that the stack isn't polluted. I continue a method
call with another call. This emans we have to leave somehow the method.
In Java we can do this by return and by Exception.

Let us think we have an ContinuationObject that is returned whenver a
continuation call is made. That object would store all the data needed
for the next call. We don't have to return completly to the caller.
Instead we could, for exmaple in Invoker, test if such a object is
returned and then make a call to the method inside that object instead.
Problem here is, a method returning "int" may have problems with the
verifier if something different that "int" is returned.

Another possibility would be to use Exceptions for this. Again would the
Exception not go through to the original caller. For Exmaple Invoker
could catch it and handle it the way as above.

The effect would be that we would leave a method but don't return to the
caller. Instead we would continue the method call with another method.

To mark a continuation call as such I propose to use "returncc" instead
of "return". The implementation is really easy as no bytecode is needed
for this. The next release could have them

comments?

bye blackdrag
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Jochen Theodorou
I have to note, that my description is only covering the most simple
form of continuations and not the more advanced versions.

bye blackdrag
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Torsten Curdt
In reply to this post by Jochen Theodorou

> Hi,
>
> I thought a little about how to make continuations possible for  
> groovy. And then I thought it may be easy. As far as I understand  
> continuations, the neat thing is that the stack isn't polluted. I  
> continue a method call with another call. This emans we have to  
> leave somehow the method. In Java we can do this by return and by  
> Exception.

In theory javaflow [1] should also work for groovy ...we use bytecode  
instrumentation
to achieve the continuation behavior. I haven't tried it yet though.  
It's still on my
long todo list.

> To mark a continuation call as such I propose to use "returncc"  
> instead of "return". The implementation is really easy as no  
> bytecode is needed for this. The next release could have them

Hm... that sounds really interesting

cheers
--
Torsten


PGP.sig (193 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Torsten Curdt
Ups!

[1] http://jakarta.apache.org/commons/sandbox/javaflow

>
>> Hi,
>>
>> I thought a little about how to make continuations possible for  
>> groovy. And then I thought it may be easy. As far as I understand  
>> continuations, the neat thing is that the stack isn't polluted. I  
>> continue a method call with another call. This emans we have to  
>> leave somehow the method. In Java we can do this by return and by  
>> Exception.
>
> In theory javaflow [1] should also work for groovy ...we use  
> bytecode instrumentation
> to achieve the continuation behavior. I haven't tried it yet  
> though. It's still on my
> long todo list.
>
>> To mark a continuation call as such I propose to use "returncc"  
>> instead of "return". The implementation is really easy as no  
>> bytecode is needed for this. The next release could have them
>
> Hm... that sounds really interesting
>
> cheers
> --
> Torsten
>


PGP.sig (193 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

tugwilson
In reply to this post by Jochen Theodorou

On 2 Dec 2005, at 09:29, Jochen Theodorou wrote:

> I have to note, that my description is only covering the most  
> simple form of continuations and not the more advanced versions.

Could you post a small example showing how this would be used?

Would this be something like the Python generator? See: http://
www.python.org/peps/pep-0255.html




John Wilson
The Wilson Partnership
http://www.wilson.co.uk


Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Jochen Theodorou
In reply to this post by Torsten Curdt
Torsten Curdt schrieb:

>> Hi,
>>
>> I thought a little about how to make continuations possible for  
>> groovy. And then I thought it may be easy. As far as I understand  
>> continuations, the neat thing is that the stack isn't polluted. I  
>> continue a method call with another call. This emans we have to  leave
>> somehow the method. In Java we can do this by return and by  Exception.
>
> In theory javaflow [1] should also work for groovy ...we use bytecode  
> instrumentation
> to achieve the continuation behavior. I haven't tried it yet though.  
> It's still on my long todo list.

the problem is to save the stack. My "solution" would destroy the stack.
It's more something like a explicit tail recursion call that throws away
the current stack element and continues the execution in another. You
can simulate some advanced continuations when you allow returncc to
usean additional  closures

def foo(x) {
   if (x>100000) return
   y=x+1
   foo(y)
   println y
}

would be transformed into

def foo(x) {
   if (x>100000) return
   y=x+1
   returncc foo(y),{println y}
}

the closure saves the value of y even if we leave foo. returncc would
leave the function foo and continue the call foo(y) saving the the
closure in a list. If there is no continuation call left, then we would
take the top element of the list and execute it. If more continuation
calls are done then the list would be expanded. But this too is not what
a real continuation is or am I wrong about that? Oh, and of course it is
not easy to continue a normal loop that way:

def foo(x) {
   if (x>100000) return
   y=x+1
   for (i in 1..4) { foo(y) }
   println y
}

closure are even more complicated as you don't wnat to leave the
closures call only, you want to leave the whole function.

>> To mark a continuation call as such I propose to use "returncc"  
>> instead of "return". The implementation is really easy as no  bytecode
>> is needed for this. The next release could have them
>
> Hm... that sounds really interesting

the use may be limited, but I think it is still usefull.

implementing our own version of javaflow would be another solution. The
mechanism I described does not return a continuation object. So you
can't control it like in javaflow.
Unlike javaflow's starting point we have full control about the things
we generate and don't need to transform method calls later. So we don't
really have to keep a complete Stackframe of our own, we could let the
compiler find out what is needed and what not. It's a mechanism like we
use for closures.


bye blackdrag

Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Torsten Curdt
> implementing our own version of javaflow would be another solution.

It always is ;) ...but be sure I'll be at least watching ;)

> The mechanism I described does not return a continuation object. So  
> you can't control it like in javaflow.
> Unlike javaflow's starting point we have full control about the  
> things we generate and don't need to transform method calls later.

Which is a much better starting point ...yepp!

> So we don't really have to keep a complete Stackframe of our own,  
> we could let the compiler find out what is needed and what not.

Well, we don't really keep a second copy of all stack
frames until you return the continuation.

...we analyse the bytecode to see what's on the stack
at a certain instruction and make sure we have the right
code in place to save and restore the call stack. So in
fact the resulting continuation is a copy of the call
stack with some information where to resume.

Given that the objects in the resulting stack frames
are serializable you can even write that continuation
to disk! ...and resume it later on of course

cheers
--
Torsten

PGP.sig (193 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Jochen Theodorou
In reply to this post by tugwilson
John Wilson schrieb:

>
> On 2 Dec 2005, at 09:29, Jochen Theodorou wrote:
>
>> I have to note, that my description is only covering the most  simple
>> form of continuations and not the more advanced versions.
>
> Could you post a small example showing how this would be used?
>
> Would this be something like the Python generator? See: http://
> www.python.org/peps/pep-0255.html


one simple usage:

def fib(n) {
   fibhelper(n,1G,1G)
}

def fibhelper(n,f1,f2) {
   if (n<=1) return f2
   returncc fibhelper(n-1,f2,f1+f2)
}

if you do that with a normal return you will get a stackoverflow for
n=300..400, that should be much less than java as the trace for java is
much smaller. But because retuncc does leave the function and make the
method call after that, the stack is not polluted and we can make n as
big as mour memory does it allow. Of course this is an example for tail
calls. So my "continuation" is a way to enforce a tail call. The benefit
is that the compiler doesn't need to know when he can transform
somethinf into a tail call and we can enforce tail calls where it
normally wouldn't be possible. But we don't have to give the control to
object's we know. Think of "returncc x.foo()" it doesn't matter what x
or foo are, all we knopw is that we can leave the current frame and give
the control to x.foo()

bye blackdrag
Reply | Threaded
Open this post in threaded view
|

Re: continuations for Groovy!?

Jochen Theodorou
In reply to this post by Torsten Curdt
Torsten Curdt schrieb:

>> implementing our own version of javaflow would be another solution.
>
> It always is ;) ...but be sure I'll be at least watching ;)

oh!... just saw that you are one of two members of javaflow ;)

[...]

>> So we don't really have to keep a complete Stackframe of our own,  we
>> could let the compiler find out what is needed and what not.
>
> Well, we don't really keep a second copy of all stack
> frames until you return the continuation.
>
> ...we analyse the bytecode to see what's on the stack
> at a certain instruction and make sure we have the right
> code in place to save and restore the call stack. So in
> fact the resulting continuation is a copy of the call
> stack with some information where to resume.
>
> Given that the objects in the resulting stack frames
> are serializable you can even write that continuation
> to disk! ...and resume it later on of course

hehe, nice idea... interested in adding that for groovy?

bye blackdrag
Reply | Threaded
Open this post in threaded view
|

RE: continuations for Groovy!?

Dierk König
In reply to this post by Jochen Theodorou
> def fib(n) {
>    fibhelper(n,1G,1G)
> }
>
> def fibhelper(n,f1,f2) {
>    if (n<=1) return f2
>    returncc fibhelper(n-1,f2,f1+f2)
> }

>  Of course this is an example for tail
> calls. So my "continuation" is a way to enforce a tail call.

How about calling it 'tail' instead of 'returncc', then?

Even if 'tail' refers do a non-recursive call this would make
a nice replacement...

cheers
Mittie
123