[pypy-dev] continuations

[Erik Gorset]

On Sep 17, 2007, at 4:02 PM, Carl Friedrich Bolz wrote:
> Christian Tismer wrote:
>> Ok, no problem, PyPy is the platform with the most chances
>> to do this right, so why not discuss it here.
>>
>> I'd just prefer to change the topic then, since this is about a
>> stackless sprint to finish and clean up things which are waiting.
>> These things are going to be folded back into CPython stackless,
>> where the re-incarnation of continuations is pretty unlikely.
>
> Oh, absolutely. A change of topic (or even a new thread) would have  
> been
> good.

Ok, thanks. I hope I'm not stepping on anyones toes by discussing
continuations here. I'm a big fan of pypy project and find the work
you're doing very interesting. I was just curious if there was any
plans for supporting my favorite language feature :-)

I'll insert my answer to Armin here:

On Sep 17, 2007, at 12:31 PM, Armin Rigo wrote:
> On Mon, Sep 17, 2007 at 03:00:51AM +0200, Erik Gorset wrote:
>> Btw, it's possible to simulate some of call/cc's behavior using
>> _stackless.fork() (I have a play-implementation lying around here
>> somewhere). But it has several issues. The biggest one is that fork()
>> actually copies some of the objects found on the stack. It's been
>> a while since I've played around with cloneable and fork, so maybe
>> this has been fixed.
>
> A deep issue with continuations in a language like Python is that  
> there
> is no single best definition of what it should capture and what it
> should not.  If you think about what you would like to occur when you
> capture a continuation or fork a coroutine, then you'll notice that  
> you
> actually want some objects on the stack to be duplicated, and others
> not.

Actually, continuation should never copy objects. It's only about the
non-local returns. For example the return statement makes it possible
to jump back to the caller. If return instead was a function which
you could save and call again, you would have the equivalent of
call/cc. The big point here is that you don't have a stack anymore,
but a tree of continuations.

> For example, in:
>
>     def f(n):
>         return [x*x for x in range(n)]
>
> which, remember, is equivalent to:
>
>     def f(n):
>         lst = []
>         for x in range(n):
>             lst.append(x*x)
>         return lst
>
> if we pause this function in the middle of the loop and fork it,  
> then it
> feels "right" to duplicate the list -- otherwise both the original and
> the copy will append the remaining items into the same list, resulting
> in a single list with more than n elements.

This is similar to problems with some implementation of map in scheme,
not all are safe to use with call/cc. Some care must be taken to make
sure different control flows are compatible with each other. With great
power comes great responsibility ;-) The thing is, with call/cc it's
possible to embed different paradigms in python like constraint,  
logic and
dataflow programming. I find this very interesting :-)

> In essence, it seems to me that both forking and full continuations
> should not be part of the core of a language, for the same reasons as
> pickling -- in my own experience at least, more than half of the time
> "pickle" doesn't capture enough or capture too much.  There is no  
> single
> best solution.

I think I will have to disagree here. Several uses of continuations  
already
exists in the language like generators/coroutines, the return statement,
loops and exceptions. True continuations unifies this into one concept
with simple semantics. The option for a virtual machine implementation
is then to either implement all the normal flow controls as special  
cases,
or use true continuations as the fundamental building block for the  
rest.

-- 
Erik Gorset
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 1962 bytes
Desc: not available
Url : http://codespeak.net/pipermail/pypy-dev/attachments/20070918/85561e7f/attachment-0001.bin