Direct implementation of shift/reset in Smalltalk

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

Direct implementation of shift/reset in Smalltalk

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Tapple Gao
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)

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Colin Putney-3
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Randal L. Schwartz
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Balázs Kósi
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

radoslav hodnicak
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
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: Direct implementation of shift/reset in Smalltalk

Balázs Kósi
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
Reply | Threaded
Open this post in threaded view
|

A possible Cog bug (was: Re: [squeak-dev] Direct implementation of shift/reset in Smalltalk)

Levente Uzonyi-2
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
>
>

Reply | Threaded
Open this post in threaded view
|

Re: A possible Cog bug (was: Re: [squeak-dev] Direct implementation of shift/reset in Smalltalk)

Levente Uzonyi-2
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

Reply | Threaded
Open this post in threaded view
|

Re: A possible Cog bug

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: A possible Cog bug

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: [Vm-dev] Re: A possible Cog bug

Levente Uzonyi-2
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
>

Reply | Threaded
Open this post in threaded view
|

Re: A possible Cog bug

Levente Uzonyi-2
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
>
>

Reply | Threaded
Open this post in threaded view
|

Re: [Vm-dev] Re: A possible Cog bug

Frank Shearar
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

Reply | Threaded
Open this post in threaded view
|

Re: [Vm-dev] Re: A possible Cog bug (was: Re: [squeak-dev] Direct implementation of shift/reset in Smalltalk)

Eliot Miranda-2
In reply to this post by Levente Uzonyi-2
Hi Levente,

2011/4/26 Levente Uzonyi <[hidden email]>
 
Hi Eliot,

On Tue, 26 Apr 2011, Eliot Miranda wrote:

Hi Levente,
    try out the latest VMs.  They don't fix the bugs, but do change the symptoms.  e.g. in

c := [ 3 + PartialContinuationNotification signal ]
        on: PartialContinuationNotification
        do: [ :not | not continuation ].
c value: 4. "==> 7"

there is now an MNU of #+ since 3 has been replaced by a MethodContext.

So if I could ask you could dig in again, that would help.

the symptoms are much better now. The cause of the MNU seems to be that the copied contexts have some "junk" at their indexable slots. Implementing ContextPart >> #copyTo: as below solves (hides) the problem.

ContextPart >> copyTo: aContext
       "Copy self and my sender chain down to, but not including, aContext.  End of copied chain will have nil sender."

       | copy |
       self == aContext ifTrue: [ ^nil ].
       copy := self copy.
       "Cog doesn't copy the temps properly, so copy them here."
       1 to: self size do: [ :i | copy at: i put: (self at: i) ].
       sender ifNotNil: [ copy privSender: (sender copyTo: aContext) ].
       ^copy

To reproduce the "junk" copying bug, evaluate the following:

| context |
context := thisContext copy.
{ context. context copy } explore

The first context's first slot will be nil, while the second context's first slot will point to the sender context. Actually the indexable slots are filled with the values of the fixed slots, that's why the sender context is at the first indexable slot of the second context. Here's an example with more indexable slots:

| 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."

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


Levente


thanks!

best,
Eliot




Reply | Threaded
Open this post in threaded view
|

Re: [Vm-dev] Re: A possible Cog bug (was: Re: [squeak-dev] Direct implementation of shift/reset in Smalltalk)

Levente Uzonyi-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
>>
>>
>>
>