Delimited Continuations vs. For-Comprehensions

Quicksearch

Login

Delimited Continuations vs. For-Comprehensions

Sunday, May 1. 2011

Yesterday's article about Monadic Test Data Generators inspired me to think again about delimited continuations, perhaps even to understand them. I think I managed with the help of this helpful stack-overflow question. Concerning the actual use case at hand, I would say that I was partly successful.

The goal of this exercise is to see whether this example can be improved concerning conciseness and readability:

```
case class A(x : Int, b : Boolean)
```
```
 
```
```
val genA = for {
```
```
  x <- genInt
```
```
  b <- genBool
```
```
} yield A(x, b)
```

The goal can be translated into: how to hide the flatMap calls even better than in a for-comprehension. Well, I took my inspiration from Derek William's great work on Akka Futures. Basically, it was very simple: make flatMap available wrapped in a shift block and provide a factory method which provides the delimiting reset. My first try looked something like this:

```
class Generator[+T](f : () => T) {
```

    def apply[TT]() : T @cps[Generator[TT]] = shift { this flatMap _ }

    def generate(n : Int) : IndexedSeq[T] = 0 to n map (x => get)

```
    def get = f()
```

    def flatMap[TT](ff : T => Generator[TT]) = new Generator( () => ff(get).get )

    def map[TT](ff : T => TT) = new Generator( () => ff(get) )

```
}
```
```
 
```
```
object Generator {
```

    def apply[T](body : => T @cps[Generator[T]]) : Generator[T] = reset {

```
        new Generator[T]( () => body )
```
```
    }
```

    // Generator.scala:11: error: type mismatch;

    // found   : T @util.continuations.package.cps[generator.Generator[T]]

```
    // required: T
```

    //        new Generator[T]( () => body )

```
    //                                ^
```
```
}
```

This, however, does not work because the function passed into the constructor from the make method is of type T @cps[Generator[T]] instead of plain T. It took me a while to figure out that the work-around is to store it into a field for cleansing the type:

def apply[T](body : => T @cps[Generator[T]]) : Generator[T] = reset {

```
    val x = body
```
```
    new Generator[T]( () => x )
```
```
}
```

At first I had a hard time accepting that this would work, fearing that this shiny new Generator would only repeat the same value over and over again. But wait! The body argument will be the formal parameter of this function which will then fabricate a new Generator based on that input, and the input is none other than the output of the nested Generator. Or, to look at it another way: as the Generator.apply method always flatMaps (as opposed to map), the factory method needs to supply the final flatten by hand, which is not necessary in the for-comprehension case, because the final for-clause is translated to map (now I am beginning to see the rationale behind that, too).

Now that the library is working let's have a look at the use case:

```
object Tester {
```

    val genInt = new Generator( () => Random.nextInt )

    val genBool = new Generator( () => Random.nextBoolean )

```
 
```
```
    case class A(x : Int, b : Boolean)
```

    val genA = Generator( A(genInt[A](), genBool[A]()) )

```
 
```
```
    def main(args : Array[String]) {
```

        genA generate 10 foreach println

```
    }
```
```
}
```

genA is a Generator[A] and everything is type-safe (as far as I can tell), so have a close look at the crucial line 6: this single line now does the job of the four lines shown at the top of the article. The first feature which meets the eye are those type annotations [A] on both nested generators. These are unfortunately necessary as Scala otherwise infers [Nothing] (Derek got away in Akka by sacrificing type safety and returning a Future[Any]). I will try to ask the powers that be whether this situation can be improved, but until then I see this as the ugly spot on an otherwise very nice solution:

The factory method makes it visually clear that a generator is created, which is not immediately obvious with the for-comprehension
No need for inventing parameter names and binding them in a multi-line statement, just call your code and replace some parts by the generators.
One practical aspect is that Generator(…) is an expression which may be followed e.g. by generate 10, alleviating the need for enclosing it in parentheses as is necessary with the for-comprehension.

A closing remark on type-safety: giving the wrong type leads to an interesting new error message. Out of curiosity I partily changed line 6 to genBool[B] (with some B in scope which is incompatible with A), and received the following in return:

illegal answer type modification: util.continuations.package.cps[generator.Generator[generator.Tester.A]] andThen \
util.continuations.package.cps[generator.Generator[generator.Tester.B]]
    val genA = Generator.make( A(genInt[A](), genBool[B]()) )
                                ^
one error found

Posted by Dr. Roland Kuhn in Scala at 21:49 | Comments (8) | Trackbacks (0)

Trackbacks

Trackback specific URI for this entry

No Trackbacks

Comments

Display comments as (Linear | Threaded)

I'm actually not convinced that I do give up type safety with the way I did it. The 'reset' method I have returns the correct type, not a Future[Any]. My first implementation used the '@suspendable' annotation which is the same as @cps[Unit], and I wasn't returning 'Unit'. I only had to change it to get exceptions returned properly.

That being said, making an implementation for a Future is different then something like this so it may not work the same. It might be worth trying it with Generator[Any] and seeing if it does break type safety. You might have to make Generator covariant for that to work.

Good information in there though, I'll have to play around with your code when I get a chance.

#1 Derek Williams on 2011-05-02 05:56 (Reply)

I tried, but simply changing it to Generator[Any] did not work and I didn't invest much time in it. What was the exact problem with @suspendable? Making the cps-annotations simpler looks desirable Anyway, will try out more tonight.

#1.1 rk on 2011-05-02 09:16 (Reply)

This works for me: https://gist.github.com/951681

#1.1.1 Derek Williams on 2011-05-02 16:34 (Reply)

Nevermind, checked to make sure the right type was infered and it wasn't. Not sure why it works properly in Akka. Maybe I need to test it more, perhaps it isn't doing what I think it is.

#1.1.1.1 Derek Williams on 2011-05-02 16:41 (Reply)

Checked again. I did all my testing of type safety within the reset, not with the result. I ignored the value of the reset as it wasn't part of the original spec, just a side effect of the way I implemented it. Values were originally supposed to be returned by assigning values to futures, which is type safe. So it's not really applicable to what you are trying to do here.

#1.1.1.1.1 Derek Williams on 2011-05-02 16:57 (Reply)

Fixed now in Akka. I knew I had compile time type safety with this before, I accidently removed it during a refactoring. Added a test for it now too. If it wasn't for this blog post I wouldn't have tested for it, thanks!

#1.1.1.1.1.1 Derek Williams on 2011-05-02 22:46 (Reply)

The thing is: A generator like you have created here with CPS is much easier created without any CPS at all:

https://gist.github.com/951254

So the question is what the value of using CPS is here. The only line where you are using CPS is here:

Generator( A(genIntA, genBoolA) )

CPS is essentially making the control flow explicit so what you could do behind the scenes here is changing the order in which genInt/genBool are called to produce an A, but why would you want to make use of that here?

#2 Johannes Rudolph on 2011-05-02 09:21 (Reply)

Yes, you are right. It seems I was too much caught up in that flatMap scheme to see the easier alternative (and that one can be composed, too). At least it made me research and understand how the continuations plugin can be used, now I can confidently ambush any opportunity for using it

Seriously, though, CPS would for example allow me to keep track of the generators used within one expression. What I also have in my real use case (though based solely on flatMap) is to calculate an estimate of the size of the value set in order to be able to adapt the number of samples taken.

#2.1 Dr. Roland Kuhn on 2011-05-02 09:32 (Reply)

Add Comment

Name
Email
Homepage
In reply to
Comment	You can use [geshi lang=lang_name [,ln={y\|n}]][/geshi] tags to embed source code snippets. Markdown format allowed Standard emoticons like :-) and ;-) are converted to images. E-Mail addresses will not be displayed and will only be used for E-Mail notifications. To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly. Enter the string from the spam-prevention image above:
	Remember Information? Subscribe to this entry