Scala continuations: many shifts in sequence

Question

I have been trying to wrap my head around the complex typing issues with scala continuations. I've been reading all the material I can find on it, including the reference docs on the continuations package. I think I have it figured out to some degree and it makes SOME sense when you think about it.

I think my understanding of it (and some of my question) can be best summed up by this program:

package com.whatever;
import scala.util.continuations._;

object methods {

  /* The method takes an Int as its parameter.  Theoretically, at some point in the future,
   * it will return a Float to the remainder of the continuation.  This example does it
   * immediately but doesn't have to (for example it could be calling a network service
   * to do the transformation)
   * 
   * Float @cpsParam[Unit,Float] means that whatever part of the reset{} that is captured
   * as a closure should receive a Float and needn't return anything (would it be meaningful
   * if Unit were something else?)
   * 
   * The reason I have to return 0.toFloat is so the compiler can properly type the
   * method.  That zero will never go anywhere.  Is this a sign I'm doing it wrong?
   */
  def method1(param:Int): Float @cpsParam[Unit,Float] = shift { cb:(Float=>Unit) =>
    cb(param.toFloat); 
    0.toFloat;
  }

  /* This method is basically identical but returns a String instead of a Float (Again,
   * theoretically this would be done by a network service and cb would be called at some
   * point in the future.
   */
  def method2(param:Int): String @cpsParam[Unit,String] = shift { cb:(String=>Unit) =>
    cb(param.toString);
    ""
  }
}

object Main {
  def main(args:Array[String]):Unit = {
    reset {
      val f = methods.method1(5);
      println(f);
    }
  }
}

Incidentally, it's criminal that StackOverflow doesn't highlight scala! (I stand corrected; it actually does a pretty good job but just not in the live preview)

My questions are as follows:

1. Judging from the comments in the program above, what is missing from my understanding of scala's CPS? Is there ever a situation where you would NOT want Unit as B in @cpsParam[B,C]?
2. The above program compiles and works (it prints out "5.0"). But, the issue I'm running into now that's causing my confusion is when I change the reset block to try to call method2 after method1:

(Apparently you can't have a code block right after a list)

reset {
  val f = methods.method1(5);
  println(f);
  val s = methods.method2(42);
  println(s);
}

When I do this (which seems like a pretty simple thing), I get the following compiler error at the reset (this is scala 2.10 Milestone 2):

illegal answer type modification: scala.util.continuations.cpsParam[Unit,Float] andThen scala.util.continuations.cpsParam[Unit,String]

I interpret this to mean "Your first shift returns a Float and your second shift returns a String and you can't do that." Is this accurate? Does that mean you cannot use CPS to do two (or more) things in sequence unless they have the same return type? Because that seems like kind of a serious limitation. I'm guessing I'm either 1) Missing something that allows you to do this, or B) Missing some obvious reason why it's impossible for that to happen with CPS. But which one is it?

I'm starting to feel less like you need to be a post-doc student in order to understand scala's CPS. But I'm certainly not quite there yet.

Answer 1

After I asked this question I did a whole lot more research and I think I am able to answer my own question now (I hope this isn't a faux pas).

There are three things I did that helped me understand the problem and I think anyone who is having trouble with scala's continuations would do well to follow these steps:

1. Read the original academic paper about scala's continuations. It is very dry and I suspect that it's mostly the gibberish ravings of a group of lunatics, but it is also very helpful in that it gives you some insight into how the compiler transforms your continuation-driven code and the typing and purity issues that it faces in doing so.
2. Rewrite your code in callback-passing style. This is the single most important thing you can do to really get a handle on what's going on with the flow of continuations and their types.
3. Examine, and I mean really examine the type signature of shift and pay attention to what it's doing. This will drive you to the epiphany that I had.

In my case, I was typing the @cpsParams and the cb parameter to shift all wrong. I am going to explain how I figured out what I was doing wrong, so that anyone else who is as dumb as me can follow the same steps and hopefully gain some insight when the continuations compiler is driving them mad.

Step 1

I read the above paper. About a dozen times. I still understand very little of it. But what I do understand is very helpful.

Step 2

I rewrote my reset block in callback passing style, pretending that instead of being a shift, each of the methods had a second parameter called cb that would take a function to do the rest of the block. Here's what the reset block would look like after this:

  methods.method1(5, {f: Int => {
    println(f);
    methods.method2(42, {s: String => {
        println(s);
    });
  });

See what's going on? So now instead of writing code that appears to be blocking, I am explicitly delimiting the continuations myself and passing them as functions to each method. So for each of these situations, it becomes clear that each of my anonymous callback functions needn't return anything and, in fact, they should both return Unit or they will contaminate the return type of the method that they are being passed into. I think this is what the compiler was trying to tell me (though I could be wrong).

Here's what method1 would have to look like for my callback-style program

   def method1(param:Int, cb:(Float=>Unit)):Unit = {
     cb(param.toFloat);
   }

method2 is similar but takes a (String=>Unit). Now it becomes clear that my methods should also return Unit or they could contaminate the return type of the callback functions.

Step 2 Conclusion

I think a lot of my confusion stemmed from the fact that for some reason, the picture in my head was that each shift only captured up to the next shift as a continuation. Of course this isn't the case; each shift must capture the whole rest of the reset block including all the following shifts so that it forms a big nested callback-in-a-callback situation. Furthermore, all the callbacks and all the CPS-called methods should always (as far as I can tell) return Unit, because not only will their result never do anything, but it could contaminate the return type of the function that calls them, and so on up the chain of callbacks.

Step 3

Now I looked at the signature of shift. It was right there in front of me:

def shift[A,B,C](fun: (A => B) => C)): A @cpsParam[B,C]

As I looked at this, I realized that combined with my callback-style exercise, there was enough information here for me (even without fully understanding what shift does behind the scenes) to turn this into basically an exercise in dimensional analysis.

I know that the result of method1 is going to be a Float. Therefore the continuation callback (denoted as (A => B) above) needs to accept a Float as its parameter. This fixes A as Float. Therefore method1 is now looking like this:

def method1(param:Int): Float @cpsParam[B,C] = shift { cb: (Float => B) => {
    ...
    C
  }
}

In other words, the function I pass to shift must take a function from Float to B, and return C. Well I know from my exercise that the callback should return Unit or things get messy. I also know that in my callback exercise, the methods themselves should obviously return Unit because they were passing their actual result as a parameter to the continuation. That is analogous to C also being Unit. So this means method1 must look like this:

def method1(param:Int): Float @cpsParam[Unit,Unit] = shift { cb: (Float => Unit) => {
    cb(param);
  }
}

And method2 will be the same except the callback will take a String.

What I Learned

It now seems to me that instead of getting confused by all the type parameters being thrown around, you can simply remember that if you were writing a callback-driven program, pretty much all the functions involved would return Unit because any results are getting passed as parameters instead of being returned.

What this means is that, as far as I can tell, there won't be much of a purpose for B and C in the shift to be anything other than Unit. Which makes perfect sense because there is an annotation @suspendable that is a shortcut for @cps[Unit] which is a shortcut for @cpsParam[Unit,Unit].

I don't know why the examples on scala-lang.org are such crap. But really all they needed to say was, "if you need to use anything other than MyReturnType @suspendable then you are probably doing it wrong, and by the way the function parameter that shift takes should also probably return Unit." Then I would still have the last few precious days of my life.

Happy Ending

The program with the changes I noted above totally compiles and runs with both methods in sequence. So that leads me to believe I finally have it right. If you are a Ph.D with a deep understanding of CPS then please correct any inaccuracies in my ramblings.