- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Delimited Continuations
Tue, 2010-02-02, 23:25
I'll be talking about DC at the next Bay Area Scala Enthusiasts meeting. So, Question, Observation, Question.
Question: why use a monad of continuation instead of a straight CPS transform? Somebody is bound to ask me and I want to answer more than "um..."
Observation: code written using manual CPS style tends to have more types inferred than code written with shift/reset. Scala's local type inference likes it when things are tied together into big expressions with lambdas. It's not so happy with DC.
compare
List(1,2,3) map {x => x + 1}
vs
reset{shift(List(1,2,3).map[Int, List[Int]]) + 1}
While that's a silly example the same thing really hurts the ability to use DC to make clean DSLs. For instance, if the "using" resource management function gets some DC based sugar to make it more direct, the result seems in some ways less pleasant than the original.
Compare a pair of imperative programs
// standard using block definition
def using[X <: {def close()}, A](resource : X)(f : X => A) = {
try {
f(resource)
} finally {
resource.close()
}
}
def copyFileCPS = using(new BufferedReader(new FileReader("test.txt"))) {
reader => {
using(new BufferedWriter(new FileWriter("test_copy.txt"))) {
writer => {
var line = reader.readLine
var count = 0
while (line != null) {
count += 1
writer.write(line)
writer.newLine
line = reader.readLine
}
count
}
}
}
}
vs
// A DC version of 'using'
def resource[X <: {def close()}, B](res : X) = shift(using[X, B](res))
// some sugar for reset
def withResources[A, C](x : => A @cps[A, C]) = reset{x}
// and now use our new lib
def copyFileDC = withResources {
val reader = resource[BufferedReader,Int](new BufferedReader(new FileReader("test.txt")))
val writer = resource[BufferedWriter,Int](new BufferedWriter(new FileWriter("test_copy.txt")))
var line = reader.readLine
var count = 0
while(line != null) {
count += 1
writer write line
writer.newLine
line = reader.readLine
}
count
}
The DC version is nicely "flatter" but the need to put type annotations on each call to resource() is annoying and arguably negates the pleasantness of direct style code.
Which leads to:
Question: any thoughts on ways to cut down on the type annotations? Both as a possible change in how the plugin behaves and as how I should use the plugin?
Question: why use a monad of continuation instead of a straight CPS transform? Somebody is bound to ask me and I want to answer more than "um..."
Observation: code written using manual CPS style tends to have more types inferred than code written with shift/reset. Scala's local type inference likes it when things are tied together into big expressions with lambdas. It's not so happy with DC.
compare
List(1,2,3) map {x => x + 1}
vs
reset{shift(List(1,2,3).map[Int, List[Int]]) + 1}
While that's a silly example the same thing really hurts the ability to use DC to make clean DSLs. For instance, if the "using" resource management function gets some DC based sugar to make it more direct, the result seems in some ways less pleasant than the original.
Compare a pair of imperative programs
// standard using block definition
def using[X <: {def close()}, A](resource : X)(f : X => A) = {
try {
f(resource)
} finally {
resource.close()
}
}
def copyFileCPS = using(new BufferedReader(new FileReader("test.txt"))) {
reader => {
using(new BufferedWriter(new FileWriter("test_copy.txt"))) {
writer => {
var line = reader.readLine
var count = 0
while (line != null) {
count += 1
writer.write(line)
writer.newLine
line = reader.readLine
}
count
}
}
}
}
vs
// A DC version of 'using'
def resource[X <: {def close()}, B](res : X) = shift(using[X, B](res))
// some sugar for reset
def withResources[A, C](x : => A @cps[A, C]) = reset{x}
// and now use our new lib
def copyFileDC = withResources {
val reader = resource[BufferedReader,Int](new BufferedReader(new FileReader("test.txt")))
val writer = resource[BufferedWriter,Int](new BufferedWriter(new FileWriter("test_copy.txt")))
var line = reader.readLine
var count = 0
while(line != null) {
count += 1
writer write line
writer.newLine
line = reader.readLine
}
count
}
The DC version is nicely "flatter" but the need to put type annotations on each call to resource() is annoying and arguably negates the pleasantness of direct style code.
Which leads to:
Question: any thoughts on ways to cut down on the type annotations? Both as a possible change in how the plugin behaves and as how I should use the plugin?
Wed, 2010-02-03, 16:47
#2
Re: Delimited Continuations
On Wed, Feb 3, 2010 at 3:30 AM, Tiark Rompf <tiark.rompf@epfl.ch> wrote:
cool! If there is going to be another BASE meeting on Feb 16 we might actually have the chance to chat face to face.
I think something will happen on the 16th whether it's BASE or not. Looking forward to it!
Mostly for reasons of flexibility. In some cases, one would like to leave the direct-style world and actually access the underlying ControlContext object, pass it around, use map/flatMap to compose it, etc. This comes into play, for example, if you want to reach past the first enclosing reset.
Great, you just tied my brain in a knot! :-)
Another point is possible future performance enhancements. Although this is not done currently, one could represent trivial ControlContexts (i.e. shift (k => k(3)) just as TrivialContext(3). TrivialContext could then be a subclass of ControlContext with more efficient map and flatMap implementations.
That makes a lot of sense. I've done it with other monads and it's a handy trick.
However, you can simplify your code by introducing an implicit which provides the missing bit of context-dependent information:
That's pretty clever. Thanks!
Wed, 2010-02-03, 17:17
#3
Re: Delimited Continuations
Any of you (or both of you...) ever want to write a book about CPS tricks in Scala, I assure you all there will be at least one guaranteed sale. :-)
On Wed, Feb 3, 2010 at 1:38 PM, James Iry <jamesiry@gmail.com> wrote:
--
Daniel C. Sobral
I travel to the future all the time.
On Wed, Feb 3, 2010 at 1:38 PM, James Iry <jamesiry@gmail.com> wrote:
On Wed, Feb 3, 2010 at 3:30 AM, Tiark Rompf <tiark.rompf@epfl.ch> wrote:
cool! If there is going to be another BASE meeting on Feb 16 we might actually have the chance to chat face to face.
I think something will happen on the 16th whether it's BASE or not. Looking forward to it!
Mostly for reasons of flexibility. In some cases, one would like to leave the direct-style world and actually access the underlying ControlContext object, pass it around, use map/flatMap to compose it, etc. This comes into play, for example, if you want to reach past the first enclosing reset.
Great, you just tied my brain in a knot! :-)
Another point is possible future performance enhancements. Although this is not done currently, one could represent trivial ControlContexts (i.e. shift (k => k(3)) just as TrivialContext(3). TrivialContext could then be a subclass of ControlContext with more efficient map and flatMap implementations.
That makes a lot of sense. I've done it with other monads and it's a handy trick.
However, you can simplify your code by introducing an implicit which provides the missing bit of context-dependent information:
That's pretty clever. Thanks!
--
Daniel C. Sobral
I travel to the future all the time.
Wed, 2010-02-03, 18:17
#4
Re: Delimited Continuations
> I'll be talking about DC at the next Bay Area Scala Enthusiasts meeting.
cool! If there is going to be another BASE meeting on Feb 16 we might actually have the chance to chat face to face.
LinkedIn will be hosting an extraordinary session of BASE on February 16. Glad to hear you'll be there, Tiark!
--j
Wed, 2010-02-03, 19:57
#5
Re: Delimited Continuations
On Wed, Feb 3, 2010 at 6:13 PM, Jorge Ortiz wrote:
>
>> > I'll be talking about DC at the next Bay Area Scala Enthusiasts meeting.
>> cool! If there is going to be another BASE meeting on Feb 16 we might
>> actually have the chance to chat face to face.
>
> LinkedIn will be hosting an extraordinary session of BASE on February 16.
> Glad to hear you'll be there, Tiark!
Excellent! Looking forward to meeting you there. Cheers -- Martin
Wed, 2010-02-03, 21:47
#6
Re: Delimited Continuations
On 03.02.2010, at 19:22, martin odersky wrote:
> On Wed, Feb 3, 2010 at 6:13 PM, Jorge Ortiz wrote:
>>
>>>> I'll be talking about DC at the next Bay Area Scala Enthusiasts meeting.
>>> cool! If there is going to be another BASE meeting on Feb 16 we might
>>> actually have the chance to chat face to face.
>>
>> LinkedIn will be hosting an extraordinary session of BASE on February 16.
>> Glad to hear you'll be there, Tiark!
>
> Excellent! Looking forward to meeting you there. Cheers -- Martin
me too ;-) Looking forward to it!
- Tiark
> I'll be talking about DC at the next Bay Area Scala Enthusiasts meeting.
cool! If there is going to be another BASE meeting on Feb 16 we might actually have the chance to chat face to face.
> Question: why use a monad of continuation instead of a straight CPS transform? Somebody is bound to ask me and I want to answer more than "um..."
Mostly for reasons of flexibility. In some cases, one would like to leave the direct-style world and actually access the underlying ControlContext object, pass it around, use map/flatMap to compose it, etc. This comes into play, for example, if you want to reach past the first enclosing reset. Another point is possible future performance enhancements. Although this is not done currently, one could represent trivial ControlContexts (i.e. shift (k => k(3)) just as TrivialContext(3). TrivialContext could then be a subclass of ControlContext with more efficient map and flatMap implementations.
> Observation: code written using manual CPS style tends to have more types inferred than code written with shift/reset. Scala's local type inference likes it when things are tied together into big expressions with lambdas. It's not so happy with DC.
> For instance, if the "using" resource management function gets some DC based sugar to make it more direct, the result seems in some ways less pleasant than the original.
Your observation is correct and this is precisely one of the things I would like to improve before shipping continuations as part of an official 2.8 release. The problem is that the current hooks in the type checker provide compiler plugings only with limited access to the internal state of the type checker. Making a connection between the *context type (in your case, Int) and the type parameter B of resource[X,B], which would need to be instantiated with Int, will most likely need additional infrastructure. And since we want to avoid too much special-casing and rather come up with something that is useful for other plugins as well this requires a fair amount of head scratching.
However, you can simplify your code by introducing an implicit which provides the missing bit of context-dependent information:
trait ContextType[B]
def forceContextType[B]: ContextType[B] = null
// A DC version of 'using'
def resource[X <: {def close()}, B: ContextType](res : X): X @cps[B,B] = shift(using[X, B](res))
// some sugar for reset
def withResources[A](x : => A @cps[A, A]) = reset{x}
// and now use our new lib
def copyFileDC = withResources {
implicit val _ = forceContextType[Int]
val reader = resource(new BufferedReader(new FileReader("test.txt")))
val writer = resource(new BufferedWriter(new FileWriter("test_copy.txt")))
var line = reader.readLine
var count = 0
while(line != null) {
count += 1
writer write line
writer.newLine
line = reader.readLine
}
count
}
So it boils down to one extra line, which, although not ideal, should be tenable for the time being.
Note also that I dropped the second type parameter from withResources. In most practical cases one can restrict oneself to @cps[A,A] and in upcoming releases we might even make it the default (i.e. have one annotation @cps[A] for the common case and another one, @cpsPoly[A,B], for the less common cases).
Cheers,
- Tiark