I finished a preliminary version of the shift/reset control operator for
creating and using partial continuations: http://www.squeaksource.com/Control.html It's pretty easy to use: [ 1 + 2 ] reset => 3 [ 1 + [:k | 2 ] shift ] reset => 2 (because k's not used, that part of the stack's discarded) [ 1 + [:k | k value: 2 ] shift ] reset => 3 [ 1 + [:k | k value: (k value: 2) ] shift ] reset => 4 [ 1 + [:k | cont := k. k value: 0 ] shift ] reset => 1, and cont now holds the continuation, for later (re-)use. It probably has horrific bugs and will eat your machine. It does, however, have as full a test suite as I can imagine, the execution of which, at least, does not eat your machine! I wrote a reasonable walk-through of the library [1] that also mentions good starting points in the literature on the subject of partial/delimited/composable continuations. I wrote the library with two intentions - firstly, that I could understand partial continuations and, secondly, to try provide a common vocabulary for working with partial continuations. Comments welcome! frank [1] http://www.lshift.net/blog/2011/04/20/direct-implementation-of-shiftreset-in-smalltalk |
On Thu, Apr 21, 2011 at 12:50:50PM +0100, Frank Shearar wrote:
> I finished a preliminary version of the shift/reset control operator for > creating and using partial continuations: > > http://www.squeaksource.com/Control.html > > It's pretty easy to use: > > [ 1 + 2 ] reset => 3 > [ 1 + [:k | 2 ] shift ] reset => 2 (because k's not used, that part of > the stack's discarded) > [ 1 + [:k | k value: 2 ] shift ] reset => 3 > [ 1 + [:k | k value: (k value: 2) ] shift ] reset => 4 > [ 1 + [:k | cont := k. k value: 0 ] shift ] reset => 1, and cont now > holds the continuation, for later (re-)use. > > It probably has horrific bugs and will eat your machine. It does, > however, have as full a test suite as I can imagine, the execution of > which, at least, does not eat your machine! > > I wrote a reasonable walk-through of the library [1] that also mentions > good starting points in the literature on the subject of > partial/delimited/composable continuations. > > I wrote the library with two intentions - firstly, that I could > understand partial continuations and, secondly, to try provide a common > vocabulary for working with partial continuations. > > Comments welcome! > > frank > > [1] > http://www.lshift.net/blog/2011/04/20/direct-implementation-of-shiftreset-in-smalltalk > I never did understand the functional difference between continuations and suspended processes. Do you have any links to how partial continuations are useful? -- Matthew Fulmer (a.k.a. Tapple) |
On Thu, Apr 21, 2011 at 9:01 AM, Matthew Fulmer <[hidden email]> wrote:
> I never did understand the functional difference between > continuations and suspended processes. It's true, they are very similar in that the state they contain is exactly the same. However, suspended process can only be resumed once, where a continuation can be evaluated more than once. Evaluating a continuation boils down to creating a suspended process, replacing the current process with it, and resuming. > Do you have any links to how partial continuations are useful? I think it just boils down to memory consumption. Everything you can do with partial continuations you can also do by composing full continuations. Colin |
On 2011/04/21 18:03, Colin Putney wrote:
> On Thu, Apr 21, 2011 at 9:01 AM, Matthew Fulmer<[hidden email]> wrote: > >> I never did understand the functional difference between >> continuations and suspended processes. > > It's true, they are very similar in that the state they contain is > exactly the same. However, suspended process can only be resumed once, > where a continuation can be evaluated more than once. Evaluating a > continuation boils down to creating a suspended process, replacing the > current process with it, and resuming. > >> Do you have any links to how partial continuations are useful? > > I think it just boils down to memory consumption. Everything you can > do with partial continuations you can also do by composing full > continuations. Indeed. What's useful about partial continuations (as opposed to full ones) is precisely that they're _delimited_. That lets you divide your code into "kernel" and "user" spaces. With a full continuation, the captured call stack will capture part of the "kernel" calls, which is probably not desirable. Instead, when the user-space continuation makes a call to the kernel-space facilities, the kernel captures the delimited continuation, does its thing, and then resumes the continuation. Kiselyov's and Shan's "Delimited continuations in operating systems" [1] makes the case that operating systems implicitly use partial continuations all over the place, even if it's never stated. Kiselyov says "Explicitly recognizing these uses of delimited continuations helps us design a system of concurrent, isolated transactions where desirable features such as snapshots, undo, copy-on-write, reconciliation, and interposition fall out by default. It also lets us take advantage of efficient implementation techniques from programming-language research." As Colin mentions, partial continuations are also lighter weight than full ones, obviously, since they capture less. If you're doing heavy backtracking, that would quickly pay dividends, I suspect. Of course in Smalltalk we have full continuations at our fingertips all the time, in the form of thisContext sender. (This is what allows Generator to have such a trivial implementation.) But using thisContext willy-nilly sounds like a Bad Idea(tm). What my library provides is a more structured way of using continuations. (And I've already implemented delimited continuations in the form of zippers, so I had to balance things!) For more papers on continuations (and dynamic binding, and the interactions between the two) than you can shake a stick at: http://okmij.org/ftp/continuations/ frank [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.8610&rep=rep1&type=pdf |
In reply to this post by Frank Shearar
>>>>> "Frank" == Frank Shearar <[hidden email]> writes:
Frank> I finished a preliminary version of the shift/reset control operator for Frank> creating and using partial continuations: Frank> http://www.squeaksource.com/Control.html Frank> It's pretty easy to use: Frank> [ 1 + 2 ] reset => 3 Frank> [ 1 + [:k | 2 ] shift ] reset => 2 (because k's not used, that part of the Frank> stack's discarded) Frank> [ 1 + [:k | k value: 2 ] shift ] reset => 3 Frank> [ 1 + [:k | k value: (k value: 2) ] shift ] reset => 4 Frank> [ 1 + [:k | cont := k. k value: 0 ] shift ] reset => 1, and cont now holds the Frank> continuation, for later (re-)use. I have no clue what's going on here, and the "best paper" you link has greek characters in the second column on the first page. Can you explain what's happening in English? -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.posterous.com/ for Smalltalk discussion |
On 2011/04/21 19:56, Randal L. Schwartz wrote:
>>>>>> "Frank" == Frank Shearar<[hidden email]> writes: > > Frank> I finished a preliminary version of the shift/reset control operator for > Frank> creating and using partial continuations: > > Frank> http://www.squeaksource.com/Control.html > > > Frank> It's pretty easy to use: > > Frank> [ 1 + 2 ] reset => 3 > Frank> [ 1 + [:k | 2 ] shift ] reset => 2 (because k's not used, that part of the > Frank> stack's discarded) > Frank> [ 1 + [:k | k value: 2 ] shift ] reset => 3 > Frank> [ 1 + [:k | k value: (k value: 2) ] shift ] reset => 4 > Frank> [ 1 + [:k | cont := k. k value: 0 ] shift ] reset => 1, and cont now holds the > Frank> continuation, for later (re-)use. > > I have no clue what's going on here, and the "best paper" you link has > greek characters in the second column on the first page. They do like their Greek characters! (Which paper's throwing the Greek at you though?) > Can you explain what's happening in English? The idea's this: first, we mark the execution stack (with #reset, in this case). Later, we refer to that mark. In particular, as we send messages we push MethodContexts and BlockContexts onto the stack. At any point, we're executing within a particular context. For instance, when we send #abs to 3 in the below 1 + 2 * 3 abs we can say that the current context looks like this 1 + 2 * _ or, if you prefer, [:x | 1 + 2 * x ] What shift does is it cuts out part of the execution stack - everything from the current context down to the nearest mark made by reset - and turns that chunk of stack into a function. So if we have [ 1 + [:k | k value: 2 ] shift ] reset then shift creates a unary block that looks like this: [:x | 1 + x ] and passes that into the receiver of the shift. Or, to put it another way, the k in [:k | k value: 2 ] is the successor function, so the whole computation becomes [:k | k value: 2] value: [:x | 1 + x ] => [:x | 1 + x] value: 2 => 3 These examples are obviously very simple and "so what?"-ish. The Kiselyov and Shan paper I referenced gives a nice in-depth example of what continuations can do which should be readily recognisable to all of us: a userland process making system calls: we capture the userland portion of the stack, store it, hand control over to the system process which does something or other. When the system's done, it restores the userland chunk o' stack and the userland process continues computing. Another excellent intro is Chung Chieh Shan's "Shift to Control" (http://www.cs.rutgers.edu/~ccshan/recur/recur.pdf). Most of the paper's *cough* pretty hairy, especially if you're not familiar with the CPS transform (like me). However, the introduction to the paper is really great. This idea of "here we are, in some context" is the execution stack version of a zipper, only instead of walking over a list or a tree, we're walking over a stack of ContextParts. Hence "a zipper is a delimited continuation". Does that help? frank |
Hi,
You have a happy user already :) We are using your library to order a list of jobs. The jobs proceed up to a point where they need to access external resources, there they throw a notification, which we catch and put the job containing its partial continuation into a priority queue in order to access the resources in a balanced manner. Then we resume the continuations in this changed order. Balázs |
Can you post some snippets of your code that demonstrates how you use
it? I mostly understand what shift/resets does, but I'm not seeing how I would use it in practice or what kind of problems it's good for. rado On Fri, Apr 22, 2011 at 7:44 PM, Balázs Kósi <[hidden email]> wrote: > Hi, > > You have a happy user already :) We are using your library to order a > list of jobs. The jobs proceed up to a point where they need to access > external resources, there they throw a notification, which we catch > and put the job containing its partial continuation into a priority > queue in order to access the resources in a balanced manner. Then we > resume the continuations in this changed order. > > Balázs > > |
In reply to this post by Balázs Kósi
On 2011/04/22 18:44, Balázs Kósi wrote:
> Hi, > > You have a happy user already :) We are using your library to order a > list of jobs. The jobs proceed up to a point where they need to access > external resources, there they throw a notification, which we catch > and put the job containing its partial continuation into a priority > queue in order to access the resources in a balanced manner. Then we > resume the continuations in this changed order. I'm very happy to hear that, Balázs! frank |
Hi,
> I'm very happy to hear that, Balázs! Thanks for the code! > Can you post some snippets of your code that demonstrates how you use it? You find a little example attached. Here is some code to try it: CEResource start. " Start the resources. Now we have three of them a, b and c. Each of them produce a sequence of numbers. They need two seconds to produce the next number after a request. " [ Transcript show: [ :k | CEResource request: k from: #a ] shift; space ] reset. " With the snippet above you can write the next number on the Transcript. Press repeatedly, and watch as a number appears every two seconds. " CEJob new. " The Job makes ten requests to the resources, and collects their answers. Explore this expression. (Alt-Shift-i). And refresh the results collection by opening and closing it." CEResource stop. ControlExample.st (3K) Download Attachment |
In reply to this post by Frank Shearar
On Thu, 21 Apr 2011, Frank Shearar wrote:
> I finished a preliminary version of the shift/reset control operator for > creating and using partial continuations: > > http://www.squeaksource.com/Control.html > > It's pretty easy to use: > snip > Comments welcome! I thought it's a bit easier to use notifications instead of control operators. Here's an example: c := [ 3 + PartialContinuationNotification signal ] on: PartialContinuationNotification do: [ :not | not continuation ]. c value: 4. "==> 7" So I implemented it and uploaded it to http://leves.web.elte.hu/squeak/Control-ul.5.mcz . I also refactored the code a bit. Even though some Pharo folks always wanted to be able to use streams with OrderedCollection (which works in Squeak btw), it's kinda pointless thing to use #streamContents: with them, because OrderedCollections can grow by themselves, unlike Arrays or Strings. The code works, the tests are green, etc. But I wasn't happy with the results, because ContextPart already implements #copyTo: (which I think can also be simplified by removing BlockContext support), which can be used to serialize the stack. So I wrote the code, but it didn't work for some reason. The execution always ran into the error 'computation has been terminated' in MethodContext >> #cannotReturn: and the method context (which stitches the continuation onto the stack) was broken (nil in temporaries where should be non nil values). Finally I tried it in SqueakVM instead of Cog and it worked. The tests are green, the example code works, etc. The code with these changes is available at http://leves.web.elte.hu/squeak/Control-ul.6.mcz . I prepared an image to ease the debugging process, which is available at http://leves.web.elte.hu/squeak/ContextBug.zip . Levente P.S.: Feel free to add an issue to the Cog tracker. :) > > frank > > [1] > http://www.lshift.net/blog/2011/04/20/direct-implementation-of-shiftreset-in-smalltalk > > |
On Sun, 24 Apr 2011, Levente Uzonyi wrote:
snip > it didn't work for some reason. The execution always ran into the error > 'computation has been terminated' in MethodContext >> #cannotReturn: and the > method context (which stitches the continuation onto the stack) was broken > (nil in temporaries where should be non nil values). Finally I tried it in > SqueakVM instead of Cog and it worked. The tests are green, the example code I tracked down this issue a bit more. The cause of the problem is that with CogVM the pc of thisContext is being set to nil when the execution leaves the context. This means, that [thisContext copy] will not be able to copy the pc of the context: { thisContext pc. thisContext copy pc } "==> #(23 nil)" Levente |
On 2011/04/25 04:35, Levente Uzonyi wrote:
> On Sun, 24 Apr 2011, Levente Uzonyi wrote: > > snip > >> it didn't work for some reason. The execution always ran into the >> error 'computation has been terminated' in MethodContext >> >> #cannotReturn: and the method context (which stitches the continuation >> onto the stack) was broken (nil in temporaries where should be non nil >> values). Finally I tried it in SqueakVM instead of Cog and it worked. >> The tests are green, the example code > > I tracked down this issue a bit more. The cause of the problem is that > with CogVM the pc of thisContext is being set to nil when the execution > leaves the context. This means, that [thisContext copy] will not be able > to copy the pc of the context: > > { thisContext pc. thisContext copy pc } "==> #(23 nil)" That would explain why I didn't come across it: I wrote the library on the SqueakVM. frank |
In reply to this post by Levente Uzonyi-2
On 2011/04/24 21:08, Levente Uzonyi wrote:
> On Thu, 21 Apr 2011, Frank Shearar wrote: > >> I finished a preliminary version of the shift/reset control operator >> for creating and using partial continuations: >> >> http://www.squeaksource.com/Control.html >> >> It's pretty easy to use: >> > > snip > >> Comments welcome! > > I thought it's a bit easier to use notifications instead of control > operators. Here's an example: > > c := [ 3 + PartialContinuationNotification signal ] > on: PartialContinuationNotification > do: [ :not | not continuation ]. > c value: 4. "==> 7" This is much like shift/reset. Well, I mean, it's exactly the same thing expressed in a slightly different way: we're dividing the labours differently. I had thought of perhaps embedding shift more deeply into the image, and putting it on Object>>#shift: c := [ 3 + self shift ] reset. I didn't, for two reasons: 1. The literature uses the "pass the continuation as an argument" pattern, and I wanted to stick closely to that (at least at first), and 2. the "self" in the above has nothing at all to do with the computation. If you wanted to be _extra_ confusing you could say c := [ 3 + 4 shift ] reset. Your method avoids this issue, of course. It makes me wonder though. One could say this: c := [ 3 + CaptureContinuation here ] reset > So I implemented it and uploaded it to > http://leves.web.elte.hu/squeak/Control-ul.5.mcz . > > I also refactored the > code a bit. Even though some Pharo folks always wanted to be able to use > streams with OrderedCollection (which works in Squeak btw), it's kinda > pointless thing to use #streamContents: with them, because > OrderedCollections can grow by themselves, unlike Arrays or Strings. > The code works, the tests are green, etc. Thanks! Do you mind if I upload your changes to http://www.squeaksource.com/Control.html ? (Shall I add you as a developer to same?) > But I wasn't happy with the results, because ContextPart already > implements #copyTo: (which I think can also be simplified by removing > BlockContext support), which can be used to serialize the stack. So I > wrote the code, but it didn't work for some reason. <snip> How is it that I missed #copyTo:? I saw all the _other_ stack manipulating stuff! There is a LOT of seriously cool stuff in the image. frank |
In reply to this post by Frank Shearar
On Mon, 25 Apr 2011, Frank Shearar wrote:
> > On 2011/04/25 04:35, Levente Uzonyi wrote: >> On Sun, 24 Apr 2011, Levente Uzonyi wrote: >> >> snip >> >>> it didn't work for some reason. The execution always ran into the >>> error 'computation has been terminated' in MethodContext >> >>> #cannotReturn: and the method context (which stitches the continuation >>> onto the stack) was broken (nil in temporaries where should be non nil >>> values). Finally I tried it in SqueakVM instead of Cog and it worked. >>> The tests are green, the example code >> >> I tracked down this issue a bit more. The cause of the problem is that >> with CogVM the pc of thisContext is being set to nil when the execution >> leaves the context. This means, that [thisContext copy] will not be able >> to copy the pc of the context: >> >> { thisContext pc. thisContext copy pc } "==> #(23 nil)" > > That would explain why I didn't come across it: I wrote the library on the > SqueakVM. Not exactly. Your serialization method works with Cog, because the problem occurs when #copy is sent to thisContext. Since your method is serializing the contexts and all their variables separately to a collection, therefore it works. Levente > > frank > |
In reply to this post by Frank Shearar
On Mon, 25 Apr 2011, Frank Shearar wrote:
> On 2011/04/24 21:08, Levente Uzonyi wrote: snip >> I thought it's a bit easier to use notifications instead of control >> operators. Here's an example: >> >> c := [ 3 + PartialContinuationNotification signal ] >> on: PartialContinuationNotification >> do: [ :not | not continuation ]. >> c value: 4. "==> 7" > > This is much like shift/reset. Well, I mean, it's exactly the same thing > expressed in a slightly different way: we're dividing the labours > differently. Right. It's just feels more natural to use notifications. The above example is equivalent with: c := [ 3 + [ :k | k ] shift ] reset. I think the [ :k | k ] block just makes it harder to understand what the code actually does. > > I had thought of perhaps embedding shift more deeply into the image, and > putting it on Object>>#shift: > > c := [ 3 + self shift ] reset. > > I didn't, for two reasons: > 1. The literature uses the "pass the continuation as an argument" pattern, > and I wanted to stick closely to that (at least at first), and > 2. the "self" in the above has nothing at all to do with the computation. If > you wanted to be _extra_ confusing you could say > > c := [ 3 + 4 shift ] reset. > > Your method avoids this issue, of course. > > It makes me wonder though. One could say this: > > c := [ 3 + CaptureContinuation here ] reset That's a bit easier to understand, but I still consider the names #shift and #reset unrelated to continuations. > >> So I implemented it and uploaded it to >> http://leves.web.elte.hu/squeak/Control-ul.5.mcz . >> >> I also refactored the >> code a bit. Even though some Pharo folks always wanted to be able to use >> streams with OrderedCollection (which works in Squeak btw), it's kinda >> pointless thing to use #streamContents: with them, because >> OrderedCollections can grow by themselves, unlike Arrays or Strings. >> The code works, the tests are green, etc. > > Thanks! Do you mind if I upload your changes to > http://www.squeaksource.com/Control.html ? (Shall I add you as a developer to > same?) Both of them is ok for me. :) > >> But I wasn't happy with the results, because ContextPart already >> implements #copyTo: (which I think can also be simplified by removing >> BlockContext support), which can be used to serialize the stack. So I >> wrote the code, but it didn't work for some reason. > <snip> > > How is it that I missed #copyTo:? I saw all the _other_ stack manipulating > stuff! There is a LOT of seriously cool stuff in the image. Agreed, the code can be further simplified by using existing methods. Levente > > frank > > |
In reply to this post by Levente Uzonyi-2
On 2011/04/25 16:55, Levente Uzonyi wrote:
> > On Mon, 25 Apr 2011, Frank Shearar wrote: > >> >> On 2011/04/25 04:35, Levente Uzonyi wrote: >>> On Sun, 24 Apr 2011, Levente Uzonyi wrote: >>> >>> snip >>> >>>> it didn't work for some reason. The execution always ran into the >>>> error 'computation has been terminated' in MethodContext >> >>>> #cannotReturn: and the method context (which stitches the continuation >>>> onto the stack) was broken (nil in temporaries where should be non nil >>>> values). Finally I tried it in SqueakVM instead of Cog and it worked. >>>> The tests are green, the example code >>> >>> I tracked down this issue a bit more. The cause of the problem is that >>> with CogVM the pc of thisContext is being set to nil when the execution >>> leaves the context. This means, that [thisContext copy] will not be able >>> to copy the pc of the context: >>> >>> { thisContext pc. thisContext copy pc } "==> #(23 nil)" >> >> That would explain why I didn't come across it: I wrote the library on >> the SqueakVM. > > Not exactly. Your serialization method works with Cog, because the > problem occurs when #copy is sent to thisContext. Since your method is > serializing the contexts and all their variables separately to a > collection, therefore it works. Oh, right. I didn't see that distinction because, on the SqueakVM, your refactoring worked! frank |
In reply to this post by Levente Uzonyi-2
Hi Levente,
2011/4/26 Levente Uzonyi <[hidden email]>
Hmm... the above behavior is intentional and correct in that to speed up context-to-stack mapping Cog makes no guarantee to preserve the values of temporary values after a context has returned. You'll notice that the entire closure scheme is centered around this, in that temporaries that must outlive their dynamic extent for the correct working of blocks are either copied into blocks (as copied values) or stored into remote temp vectors, hence breaking any dependence on the temporaries in enclosing contexts.
If you can live with this restriction then instead of stating "Cog doesn't copy the temps properly, so copy them here."
in your reimplementation of copyTo: it would be more accurate to state "Cog doesn't preserve non-closed-over temps beyond their dynamic extent, so copy them here."
or some such. Note that Cog /does/ preserve arguments. However, I've clearly still got some bug because look at the following. In the copy the arguments ba1 & ba2 (1 & 2) are in the wrong place on the stack. Sigh...
[:ba1 :ba2| | context a b c d e | context := thisContext copy. a := b := c := d := e := context. { context. context copy } explore.
{ a. b. c. d. e } "This is here to avoid compiler complaints."] value: 1 value: 2
|
Hi Eliot,
On Tue, 26 Apr 2011, Eliot Miranda wrote: > Hmm... the above behavior is intentional and correct in that to speed up > context-to-stack mapping Cog makes no guarantee to preserve the values of > temporary values after a context has returned. You'll notice that the > entire closure scheme is centered around this, in that temporaries that must > outlive their dynamic extent for the correct working of blocks are either > copied into blocks (as copied values) or stored into remote temp vectors, > hence breaking any dependence on the temporaries in enclosing contexts. it's probably just the lack of my knowledge about VMs, but I don't see why an existing object's slots can't be copied by primitive 148. Here's an example: | context | context := MethodContext newForMethod: Object >> #yourself. context stackp: 3. 1 to: 3 do: [ :index | context at: index put: index ]. { context. context copy } explore The forged contexts in the above example never returned (because they weren't executed), but the copied context lacks the temps of the original. > > If you can live with this restriction then instead of stating > "Cog doesn't copy the temps properly, so copy them here." > in your reimplementation of copyTo: it would be more accurate to state > "Cog doesn't preserve non-closed-over temps beyond their dynamic extent, > so copy them here." > or some such. That's acceptable, but I think that loop is superfluous, see below. > > Note that Cog /does/ preserve arguments. However, I've clearly still got > some bug because look at the following. In the copy the arguments ba1 & ba2 > (1 & 2) are in the wrong place on the stack. Sigh... > > > > [:ba1 :ba2| | context a b c d e | > context := thisContext copy. > a := b := c := d := e := context. > { context. context copy } explore. > { a. b. c. d. e } "This is here to avoid compiler complaints."] value: 1 > value: 2 I think that this bug causes the problem with both #copyTo: and the above example. When this is fixed, then there will be no need to copy the temps slots in #copyTo:. The temp slots are copied in the next example, but they are off by 6 (the number of fixed slots): | context | context := MethodContext newForMethod: Object >> #yourself. context stackp: 16. 1 to: 3 do: [ :index | context at: index put: index ]. { context. context copy} explore Cheers, Levente > >> >> >> Levente >> >> >>> thanks! >>> >>> best, >>> Eliot >> >> >> > |
Free forum by Nabble | Edit this page |