[squeak-dev] Scheme continuations vs Squeak continuations

hello list,

I realized yesterday that my scheme implementation in Squeak failed to
evaluate properly the so-called "mondo bizarro" code:

(let ((y (call-with-current-continuation (lambda (c) c))))
     (display 1)
     (call-with-current-continuation (lambda (c) (y c)))
     (display 2)
     (call-with-current-continuation (lambda (c) (y c)))
     (display 3)))

... which should display "11213"

instead, it writes "11" then goes on forever printing "2"

I wrote the equivalent code in Smalltalk:

y _ Continuation currentDo: [:c | c].
Transcript show: 1.
Continuation currentDo: [:c | y value: c].
Transcript show: 2.
Continuation currentDo: [:c | y value: c].
Transcript show: 3.

and it appears the (wrong) behavior is the same.

is anyone expert enough in continuations to help me fix this ?

(the Continuation class used here is from Seaside)


Stef

I'm assuming this is caused by Squeak's lack of full block closures.

Does it work if you make "y" an instance variable instead of a local?

Julian

On Fri, Jan 30, 2009 at 6:02 PM, Stéphane Rollandin
<[hidden email]> wrote:

Stéphane,

Julian Fitzell a écrit :
> I'm assuming this is caused by Squeak's lack of full block closures.
>
> Does it work if you make "y" an instance variable instead of a local?
>
> Julian

no, same behavior

Stef

Julian Fitzell a écrit :
> I'm assuming this is caused by Squeak's lack of full block closures.
>
> Does it work if you make "y" an instance variable instead of a local?
>
> Julian


actually, trying the following does work in a workspace or a method:

| y |
y _ Continuation currentDo: [:c | c].
Transcript show: 1.
Continuation currentDo: [:c | y value: c].
Transcript show: 2.
Continuation currentDo: [:c | y value: c].
Transcript show: 3.


so the problem occurs when y is an instance variable, while it works
fine with a local variable (although if you try the code above in a
workspace without declaring the | y | in the first line, it fails)


Stef

> so the problem occurs when y is an instance variable, while it works fine
> with a local variable (although if you try the code above in a workspace
> without declaring the | y | in the first line, it fails)

Of course this depends on the exact implementation of your
continuation. If this the one of Seaside, then it captures
temp-variables and arguments only.

If you want to translate your Scheme example in Smalltalk you need to
declare your let-variables as temps, otherwise they are not on the
execution stack and thus not captured and restored by the Seaside
continuation.

Cheers,
Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Lukas Renggli a écrit :
> Of course this depends on the exact implementation of your
> continuation. If this the one of Seaside, then it captures
> temp-variables and arguments only.

ok, thanks.

do you have any pointer about an alternate implementation which would
capture inst vars as well ?

Stef

> do you have any pointer about an alternate implementation which would
> capture inst vars as well ?

What about something like this?

Continuation>>initializeFromContext: aContext
        | valueStream context |
        valueStream := WriteStream on: (Array new: 20).
        context := aContext.
        [context notNil] whileTrue:
                [valueStream nextPut: context.
                1 to: context class instSize do: [:i | valueStream nextPut: (context
instVarAt: i)].
                1 to: context localSize do: [:i | valueStream nextPut: (context localAt: i)].
                valueStream nextPut: context receiver snapshotCopy. " <-- add this line "
                context := context sender].
        values := valueStream contents

Continuation>>restoreValues
        | valueStream context |
        valueStream := values readStream.
        [valueStream atEnd] whileFalse:
                [context := valueStream next.
                1 to: context class instSize do: [:i | context instVarAt: i put:
valueStream next].
                1 to: context localSize do: [:i | context localAt: i put: valueStream next].
                context receiver restoreFromSnapshot: valueStream next " <-- add this line " ]

Note that this does not solve the problem of the workspace variable
though. Workspace bindings are like global data and a continuation
cannot know what data outside its context you want to backtrack.
That's why there is a registration mechanism for objects in Seaside.

Cheers,
Lukas


>
> Stef
>
>
>



--
Lukas Renggli
http://www.lukas-renggli.ch

Lukas Renggli a écrit :
> What about something like this?

... this does not seem to work as is for the mondo bizarro problem; I
will explore a little bit further (if I can). thanks !

Stef

Stéphane,

First, Squeak continuations are indeed not equivalent to what you find
in Scheme. You can read about the difference in the post I wrote many
moons ago (Seaside didn't exist then):

http://lists.squeakfoundation.org/pipermail/squeak-dev/1998-October/016038.html

But this is not why this particular example doesn't work as expected.

The real problem is that the Smalltalk example only seems to do what
the Scheme one does. Since it's up to you to find what's wrong with
your Scheme implementation, you need to understand why exactly Mondo
Bizarro works the way it does. The key here is that "let" is not an
assignment, it's a function call (!).

Consider that

    (let ((x v)) ...)

is equivalent to

    ((lambda (x) ...) v)

With this in mind, it's easy to see that at the start, "y" in the
original invocation is bound to

    (lambda (y) (display 1) ...)

Invoking that "y" after "(display 1)" creates a new invocation *with
its own binding of y*. That separate "y" is bound to "(lambda (x)
(display 2) ...)" in the context of the first invocation.

So, the setup is a group of three coroutines, with the execution
threaded through them. The original invocation prints 1 and creates
the second one. The second one prints 1 and switches back to the
first. The first prints 2 and creates a third invocation, which prints
1 and jumps back to the first. The first prints 3 and completes. This
is how "11213" is produced.

For this to work as intended, "y" should have a separate binding in
each invocation. Smalltalk assignment behaves this way for temps
because with Seaside continuations you assign to "y" in separate
contexts. For workspace and instance variables it doesn't work (and
can't).

Cheers,

--Vassili

Waow, thanks for the thorough explanation, it is very helpful !
now I have to dig in my scheme and see what I can do about it...

thanks again,


Stef

Stéphane Rollandin wrote:
Indeed in GNU Smalltalk I get Squeak's behavior if y is a global, while
I get the correct behavior if y is a local.  You get the latter with

 Eval [
  |y|
  y _ Continuation currentDo: [:c | c].
  1 printNl.
  Continuation currentDo: [:c | y value: c].
  2 printNl.
  Continuation currentDo: [:c | y value: c].
  3 printNl.
 ]

and the former by removing "|y|" (which makes y work across multiple
Evals) in GNU Smalltalk's REPL.

> So, the setup is a group of three coroutines, with the execution
> threaded through them. The original invocation prints 1 and creates
> the second one. The second one prints 1 and switches back to the
> first. The first prints 2 and creates a third invocation, which prints
> 1 and jumps back to the first. The first prints 3 and completes. This
> is how "11213" is produced.

this made my day :) I just had to swap two statements in the
implementation of 'let for my scheme to comply with the Mondo Bizarro
puzzle.

now I wonder how many similar traps are still open in my code... looks
like I can expect 'call/cc to to behave badly again some time, since I
don't see a way to get a systematic overview of these subtle issues and
fix them all.

what I can do is implement a call/cc stress test for my scheme. if
people have little nasty piece of scheme code to submit, I would gladly
include them in the test suite.

for those interested, the scheme for Squeak is available here:
http://www.zogotounga.net/comp/squeak/lispkit.htm

and the current tests are the #testCallCC serie in ULispWithLibTest.
obviously I need more or them.


regards,

Stef

Stephane
the book of friedman on the art of scheme is cool to un.derstand  
continuations with escaper and others

Stef

On Feb 1, 2009, at 1:12 PM, Stéphane Rollandin wrote:

> Waow, thanks for the thorough explanation, it is very helpful !
> now I have to dig in my scheme and see what I can do about it...
>
> thanks again,
>
>
> Stef
>
>