[Continuations] multiple calls to shift within a reset?

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

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(,remote location))
Continuation moved to remote location, executing
First get result: remote value
Execute(IsCont(,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 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: ian@uprizer.com
>> Ph: +1 512 422 3588
>> Fax: +1 512 276 6674
>

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 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(,remote location))
> Continuation moved to remote location, executing
> First get result: remote value
> Execute(IsCont(,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 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: ian@uprizer.com
>>> Ph: +1 512 422 3588
>>> Fax: +1 512 276 6674
>>
>
>
>
> --
> Ian Clarke
> CEO, Uprizer Labs
> Email: ian@uprizer.com
> Ph: +1 512 422 3588
> Fax: +1 512 276 6674
>

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.

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

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <tiark.rompf@epfl.ch> 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: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674

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 <tiark.rompf@epfl.ch> 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: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <tiark.rompf@epfl.ch> 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: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674

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

On Sun, Aug 23, 2009 at 5:17 PM, Tiark Rompf <tiark.rompf@epfl.ch> 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

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: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674

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 <ian.clarke@gmail.com> 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: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674

--
Ian Clarke
CEO, Uprizer Labs
Email: ian@uprizer.com
Ph: +1 512 422 3588
Fax: +1 512 276 6674