[scala] [Continuations] multiple calls to shift within a reset?

[Ian Clarke]

Hi there.

I'm working on using the Scala continuations support to create a
framework where a framework user can write code which accesses a
key-value store using a get() method.

The interesting thing is that sometimes the value may be stored on a
remote computer.  In this case, I want to serialize the continuation,
move it to the remote computer, and restart it.  The basic idea is to
move the computation, not the data.

So I'm mucking around with 2.8's new continuation support, and I get this far:

  http://gist.github.com/172879

This code works exactly as I would hope, *however*, it all goes
horribly wrong if I add a second call to get() in the root() method
(ie. remove the comment on line 20).

When I do this, I get:

type mismatch;
found   : Unit @scala.continuations.uncps
@scala.continuations.cps[Unit,Option[((String) => Unit,
java.lang.String)]]
required: scala.continuations.ControlContext[?,?,Option[((String) =>
Unit, String)]]
ContTest.scala /SwarmProto/src line 20 Scala Problem

So it seems like trying to do an additional call to shift within a
reset changes the return type of the reset?

Does this mean that my framework cannot support an arbitrary number of
calls to get() within the root() method?  I'm sure that can't be the
case if delimited continuations are to be used for event-based
framework, since you can't predict how many calls to shift() a user of
the framework might have within their functions...

What am I not understanding?

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Tiark Rompf]

Hi,

of course you can have multiple shifts inside a reset block, but there  
are constraints on the types.

Consider a simplified get method:
        def get(k : String) = shift { c: (String => Unit) => Some("local") }

When called, it captures a delimited continuation, which is expected  
to return Unit, and instead of invoking the continuation, it returns  
an Option[String] to the caller of the enclosing reset. In other  
words, get must be called from an enclosing context of type Unit, but  
will change the context's type to Option[String]. Now, if you have  
multiple get()'s in a row it won't work, because after the first one,  
the context's type is no longer Unit but Option[String].

As a general rule of thumb, if you have shift { k: (A => B) => .....  
result }, it's always good if result is also of type B.
I'm attaching a file with two different ways to make your example  
work. The simplest approach is to do the remoting from within get and  
not from the outside.

- Tiark


On 22.08.2009, at 19:39, Ian Clarke wrote:

> Hi there.
>
> I'm working on using the Scala continuations support to create a
> framework where a framework user can write code which accesses a
> key-value store using a get() method.
>
> The interesting thing is that sometimes the value may be stored on a
> remote computer.  In this case, I want to serialize the continuation,
> move it to the remote computer, and restart it.  The basic idea is to
> move the computation, not the data.
>
> So I'm mucking around with 2.8's new continuation support, and I get  
> this far:
>
>  http://gist.github.com/172879
>
> This code works exactly as I would hope, *however*, it all goes
> horribly wrong if I add a second call to get() in the root() method
> (ie. remove the comment on line 20).
>
> When I do this, I get:
>
> type mismatch;
> found   : Unit @scala.continuations.uncps
> @scala.continuations.cps[Unit,Option[((String) => Unit,
> java.lang.String)]]
> required: scala.continuations.ControlContext[?,?,Option[((String) =>
> Unit, String)]]
> ContTest.scala /SwarmProto/src line 20 Scala Problem
>
> So it seems like trying to do an additional call to shift within a
> reset changes the return type of the reset?
>
> Does this mean that my framework cannot support an arbitrary number of
> calls to get() within the root() method?  I'm sure that can't be the
> case if delimited continuations are to be used for event-based
> framework, since you can't predict how many calls to shift() a user of
> the framework might have within their functions...
>
> What am I not understanding?
>
> Thanks,
>
> Ian.
>
> --
> Ian Clarke
> CEO, Uprizer Labs
> Email: [hidden email]
> Ph: [phone]
> Fax: [phone]

[Ian Clarke]

Thanks Tiark,

Thank you!

Actually, before I saw your response I managed to make some progress
on my own, here is the approach I used:

  http://gist.github.com/173057

It seems to work right up to the end:

Attempting first get
Execute(IsCont(<function1>,remote location))
Continuation moved to remote location, executing
First get result: remote value
Execute(IsCont(<function1>,remote location))
Continuation moved to remote location, executing
Second get result: remote value
Exception in thread "main" java.lang.ClassCastException:
scala.runtime.BoxedUnit cannot be cast to Cont
        at ContTest$.execute(ContTest.scala:31)
        at ContTest$.main(ContTest.scala:23)
        at ContTest.main(ContTest.scala)

I don't know why its doing this since the shift should return NoCont()
per line 9, which I assume should then be returned by the reset, but
it looks like its returning a BoxedUnit instead.

I will review your code as I'm sure its better than mine, but I would
very much appreciate if you could let me know what I'm doing wrong in
my own attempt.

Thanks again,

Ian.

On Sat, Aug 22, 2009 at 3:30 PM, Tiark Rompf<[hidden email]> wrote:

> Hi,
>
> of course you can have multiple shifts inside a reset block, but there are
> constraints on the types.
>
> Consider a simplified get method:
>        def get(k : String) = shift { c: (String => Unit) => Some("local") }
>
> When called, it captures a delimited continuation, which is expected to
> return Unit, and instead of invoking the continuation, it returns an
> Option[String] to the caller of the enclosing reset. In other words, get
> must be called from an enclosing context of type Unit, but will change the
> context's type to Option[String]. Now, if you have multiple get()'s in a row
> it won't work, because after the first one, the context's type is no longer
> Unit but Option[String].
>
> As a general rule of thumb, if you have shift { k: (A => B) => ..... result
> }, it's always good if result is also of type B.
> I'm attaching a file with two different ways to make your example work. The
> simplest approach is to do the remoting from within get and not from the
> outside.
>
> - Tiark
>
>
> On 22.08.2009, at 19:39, Ian Clarke wrote:
>
>> Hi there.
>>
>> I'm working on using the Scala continuations support to create a
>> framework where a framework user can write code which accesses a
>> key-value store using a get() method.
>>
>> The interesting thing is that sometimes the value may be stored on a
>> remote computer.  In this case, I want to serialize the continuation,
>> move it to the remote computer, and restart it.  The basic idea is to
>> move the computation, not the data.
>>
>> So I'm mucking around with 2.8's new continuation support, and I get this
>> far:
>>
>>  http://gist.github.com/172879
>>
>> This code works exactly as I would hope, *however*, it all goes
>> horribly wrong if I add a second call to get() in the root() method
>> (ie. remove the comment on line 20).
>>
>> When I do this, I get:
>>
>> type mismatch;
>> found   : Unit @scala.continuations.uncps
>> @scala.continuations.cps[Unit,Option[((String) => Unit,
>> java.lang.String)]]
>> required: scala.continuations.ControlContext[?,?,Option[((String) =>
>> Unit, String)]]
>> ContTest.scala  /SwarmProto/src line 20 Scala Problem
>>
>> So it seems like trying to do an additional call to shift within a
>> reset changes the return type of the reset?
>>
>> Does this mean that my framework cannot support an arbitrary number of
>> calls to get() within the root() method?  I'm sure that can't be the
>> case if delimited continuations are to be used for event-based
>> framework, since you can't predict how many calls to shift() a user of
>> the framework might have within their functions...
>>
>> What am I not understanding?
>>
>> Thanks,
>>
>> Ian.
>>
>> --
>> Ian Clarke
>> CEO, Uprizer Labs
>> Email: [hidden email]
>> Ph: [phone]
>> Fax: [phone]
>

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Ian Clarke]

Ok, I seem to have persuaded my approach to work by inserting NoCont()
at line 20.  Its weird because I thought I'd tried this previously and
it didn't change the outcome.

Anyway, I'd still appreciate any feedback you have on my approach to this.

Regards,

Ian.

On Sat, Aug 22, 2009 at 7:03 PM, Ian Clarke<[hidden email]> wrote:

> Thanks Tiark,
>
> Thank you!
>
> Actually, before I saw your response I managed to make some progress
> on my own, here is the approach I used:
>
>  http://gist.github.com/173057
>
> It seems to work right up to the end:
>
> Attempting first get
> Execute(IsCont(<function1>,remote location))
> Continuation moved to remote location, executing
> First get result: remote value
> Execute(IsCont(<function1>,remote location))
> Continuation moved to remote location, executing
> Second get result: remote value
> Exception in thread "main" java.lang.ClassCastException:
> scala.runtime.BoxedUnit cannot be cast to Cont
>        at ContTest$.execute(ContTest.scala:31)
>        at ContTest$.main(ContTest.scala:23)
>        at ContTest.main(ContTest.scala)
>
> I don't know why its doing this since the shift should return NoCont()
> per line 9, which I assume should then be returned by the reset, but
> it looks like its returning a BoxedUnit instead.
>
> I will review your code as I'm sure its better than mine, but I would
> very much appreciate if you could let me know what I'm doing wrong in
> my own attempt.
>
> Thanks again,
>
> Ian.
>
> On Sat, Aug 22, 2009 at 3:30 PM, Tiark Rompf<[hidden email]> wrote:
>> Hi,
>>
>> of course you can have multiple shifts inside a reset block, but there are
>> constraints on the types.
>>
>> Consider a simplified get method:
>>        def get(k : String) = shift { c: (String => Unit) => Some("local") }
>>
>> When called, it captures a delimited continuation, which is expected to
>> return Unit, and instead of invoking the continuation, it returns an
>> Option[String] to the caller of the enclosing reset. In other words, get
>> must be called from an enclosing context of type Unit, but will change the
>> context's type to Option[String]. Now, if you have multiple get()'s in a row
>> it won't work, because after the first one, the context's type is no longer
>> Unit but Option[String].
>>
>> As a general rule of thumb, if you have shift { k: (A => B) => ..... result
>> }, it's always good if result is also of type B.
>> I'm attaching a file with two different ways to make your example work. The
>> simplest approach is to do the remoting from within get and not from the
>> outside.
>>
>> - Tiark
>>
>>
>> On 22.08.2009, at 19:39, Ian Clarke wrote:
>>
>>> Hi there.
>>>
>>> I'm working on using the Scala continuations support to create a
>>> framework where a framework user can write code which accesses a
>>> key-value store using a get() method.
>>>
>>> The interesting thing is that sometimes the value may be stored on a
>>> remote computer.  In this case, I want to serialize the continuation,
>>> move it to the remote computer, and restart it.  The basic idea is to
>>> move the computation, not the data.
>>>
>>> So I'm mucking around with 2.8's new continuation support, and I get this
>>> far:
>>>
>>>  http://gist.github.com/172879
>>>
>>> This code works exactly as I would hope, *however*, it all goes
>>> horribly wrong if I add a second call to get() in the root() method
>>> (ie. remove the comment on line 20).
>>>
>>> When I do this, I get:
>>>
>>> type mismatch;
>>> found   : Unit @scala.continuations.uncps
>>> @scala.continuations.cps[Unit,Option[((String) => Unit,
>>> java.lang.String)]]
>>> required: scala.continuations.ControlContext[?,?,Option[((String) =>
>>> Unit, String)]]
>>> ContTest.scala  /SwarmProto/src line 20 Scala Problem
>>>
>>> So it seems like trying to do an additional call to shift within a
>>> reset changes the return type of the reset?
>>>
>>> Does this mean that my framework cannot support an arbitrary number of
>>> calls to get() within the root() method?  I'm sure that can't be the
>>> case if delimited continuations are to be used for event-based
>>> framework, since you can't predict how many calls to shift() a user of
>>> the framework might have within their functions...
>>>
>>> What am I not understanding?
>>>
>>> Thanks,
>>>
>>> Ian.
>>>
>>> --
>>> Ian Clarke
>>> CEO, Uprizer Labs
>>> Email: [hidden email]
>>> Ph: [phone]
>>> Fax: [phone]
>>
>
>
>
> --
> Ian Clarke
> CEO, Uprizer Labs
> Email: [hidden email]
> Ph: [phone]
> Fax: [phone]
>

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Ian Clarke]

Sorry for bombarding but I'm on a relatively tight deadline :-)

What about "for" loops within a reset which call a shift?  ie.
       
        def root2() : Cont = reset {
                val num = List(1,2,3,4,5);
                for (n <- num) {
                        println("get "+n+" "+get("remote"));
                }
        }

This gives me a:

cannot cps-transform expression {   val num: List[Int] =
immutable.this.List.apply[Int](1, 2, 3, 4, 5);
num.foreach[Unit](((n: Int) => scala.this.Predef.println("get
".+(n).+(" ").+(ContTest.this.get("remote"))))) }: type arguments
[Unit,Unit,Nothing] do not conform to method shiftUnit's type
parameter bounds [A,B,C >: B] ContTest.scala /SwarmProto/src line
23 Scala Problem

I think I have a vague understanding of why, but no idea what to do
about it!  Is there a special version of "for" that must be used
within reset?

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Tiark Rompf]

On 23.08.2009, at 03:58, Ian Clarke wrote:

> What about "for" loops within a reset which call a shift?  ie.
>
> def root2() : Cont = reset {
> val num = List(1,2,3,4,5);
> for (n <- num) {
> println("get "+n+" "+get("remote"));
> }
> }

> I think I have a vague understanding of why, but no idea what to do
> about it!  Is there a special version of "for" that must be used
> within reset?

I've just committed some changes to allow that. You can use it as  
follows:

     import scala.continuations._
     import scala.continuations.ControlContext._
     import scala.continuations.Loops._

     reset {
       val num = List(1,2,3,4,5)
       for (x <- num.suspendable) {

         shift { k: (Unit => Unit) =>
           println(x)
           if (x < 3) k()
           else println("enough is enough")
         }

       }
     }


> Ok, I seem to have persuaded my approach to work by inserting NoCont()
> at line 20.  Its weird because I thought I'd tried this previously and
> it didn't change the outcome.


That's indeed the way to make it work. The code shouldn't even have  
compiled without it (I fixed the error handling, too).

- Tiark

[Ian Clarke]

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <[hidden email]> wrote:

I've just committed some changes to allow that. You can use it as follows:

Cool, but can you give a general explanation of what can and cannot be done inside a reset{}?

The thing is that I want to create a framework where people can implement their own code to be called from a reset{}, and they aren't going to understand if there are limitations on what they can do, unless I can remove them, or at least enumerate them.

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Tiark Rompf]

In a reset block you can do anything, but shifts are not allowed everywhere. The limitation is that everything on the call path between a shift and its enclosing reset must be "shift-aware". That rules out the regular foreach, map and filter methods because they know nothing about continuations, so they can't call closures containing shift. 

- Tiark

On 24.08.2009, at 01:23, Ian Clarke wrote:

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <[hidden email]> wrote:

I've just committed some changes to allow that. You can use it as follows:

Cool, but can you give a general explanation of what can and cannot be done inside a reset{}?

The thing is that I want to create a framework where people can implement their own code to be called from a reset{}, and they aren't going to understand if there are limitations on what they can do, unless I can remove them, or at least enumerate them.

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Ian Clarke]

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <[hidden email]> wrote:

I think I have a vague understanding of why, but no idea what to do
about it!  Is there a special version of "for" that must be used
within reset?

I've just committed some changes to allow that. You can use it as follows:

I've taken a look at the new Loops class, a few comments/questions:

I notice that your implementation of loopWhile is recursive.  Will Scala's compiler do tail-call optimization on this, or is there a danger of stack overflows if looping over large lists?

Wouldn't it be preferable to have a SuspendableIterableView rather than a SuspendableListView since Iterable  is where foreach, map, flatMap, and filter are originally defined in the class hierarchy?

Filter isn't implemented yet.

I'm not sure about what implications this might have, but is there any way that SuspendableIterableView could or should extend or mix in Iterable?

Is there any way that implicit conversions could be used to avoid the need to manually convert the List/Iterable to a Suspendable view using the .suspendable method?

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Tiark Rompf]

On 24.08.2009, at 15:40, Ian Clarke wrote:

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <[hidden email]> wrote:

I think I have a vague understanding of why, but no idea what to do
about it!  Is there a special version of "for" that must be used
within reset?

I've just committed some changes to allow that. You can use it as follows:

I've taken a look at the new Loops class, a few comments/questions:

I notice that your implementation of loopWhile is recursive.  Will Scala's compiler do tail-call optimization on this, or is there a danger of stack overflows if looping over large lists?

No, tail-call optimization is not possible in this case, and for long lists, you will get stack overflows. But you can counter this by using a task runner to do transparent trampolining (see examples/Test4.scala for an example).

Wouldn't it be preferable to have a SuspendableIterableView rather than a SuspendableListView since Iterable  is where foreach, map, flatMap, and filter are originally defined in the class hierarchy?

Yes, this would be the proper way to do it and for the release version we'll do it that way. I just haven't had the time yet.

I'm not sure about what implications this might have, but is there any way that SuspendableIterableView could or should extend or mix in Iterable?

I'm not sure, because the method signatures need to be different. I'm also not too convinced of the utility suspendable views would have as general collection data types (besides enabling comprehensions).

Is there any way that implicit conversions could be used to avoid the need to manually convert the List/Iterable to a Suspendable view using the .suspendable method?

I don't think this would work, because type inference is currently not precise enough to disambiguate all uses. There are a lot of situations where it wouldn't be clear which foreach method should be used (the cps or no-cps version).

- Tiark

[Ian Clarke]

Hi again,

So I've tried to use num.suspendable per your suggestion, but now I'm getting this error on the method that contains the for loop:

Description Resource Path Location Type

type mismatch;  found   : Unit @scala.continuations.docps @scala.continuations.cps[Product with us.locut.swarm.Cont,Product with us.locut.swarm.Cont]  required: Unit @scala.continuations.cps[Unit,Product with us.locut.swarm.Cont] ContTest.scala /SwarmProto/src/us/locut/swarm line 26 Scala Problem

My code is:

def root2() : Cont = reset {

val num = List(1,2,3,4,5);

for (n <- num.suspendable) {

println("get "+get("remote"));

}

}

Any ideas?

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

[Ian Clarke]

Ak, never mind, fixed it (forgot the NoCont() at the end of root2().

Ian.

On Mon, Aug 24, 2009 at 8:30 PM, Ian Clarke <[hidden email]> wrote:

Hi again,

So I've tried to use num.suspendable per your suggestion, but now I'm getting this error on the method that contains the for loop:

Description Resource Path Location Type

type mismatch;  found   : Unit @scala.continuations.docps @scala.continuations.cps[Product with us.locut.swarm.Cont,Product with us.locut.swarm.Cont]  required: Unit @scala.continuations.cps[Unit,Product with us.locut.swarm.Cont] ContTest.scala /SwarmProto/src/us/locut/swarm line 26 Scala Problem

My code is:

def root2() : Cont = reset {

val num = List(1,2,3,4,5);

for (n <- num.suspendable) {

println("get "+get("remote"));

}

}

Any ideas?

Thanks,

Ian.

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]

--
Ian Clarke
CEO, Uprizer Labs
Email: [hidden email]
Ph: [phone]
Fax: [phone]