Delimited continuations in Scala

[erdweg]

You can find some information on delimited continuations in Scala here: http://www.scala-lang.org/files/archive ... ns.package

Note especially the following:

The remainder of the reset block is wrapped into a closure that is passed as the parameter k to the shift function

Thus, the escaper only captures the code between the end of the shift and the end of the reset.

[errt]

This is still unclear to me. Slides e.g. said that the escaper in

Code: Alles auswählen

reset {
    1 + shift { k: (Int => Int) => { k(3) } }
}

was 1+k. Now, if

the escaper only captures the code between the end of the shift and the end of the reset

that would be nothing. So either the slides are wrong or the escaper does not only capture the code that is (lexically) between the end of the shift and the end of the reset, but at least all of the remaining calculation (which in this case includes the addition as that obviously can only be done once the second argument is fixed). Could you please provide some more clarification?

[Mr.B]

For my understanding, the "1+" is still in the continuation because it's one expression with the shift function. I'm not sure thats the correct reasoning but its true at least.
All expressions before the shift function are not contained in the continuation though.

Code: Alles auswählen

def foo() = {
  1 + shift(k => k(k(k(7))))
}
def bar() = {
  foo() * 2
}
def baz() = {
  reset(bar())
}
baz()  // result 70

source: http://www.scala-lang.org/old/node/2096

[errt]

Wasn't exactly that example in the slides accompanied by the explanation that this should be 16, as k is an Escaper and therefore can not be executed more than once in this context?

[Eichhorn]

The slides contain 4 examples which I'm not able to run on my local machine:

What will be printed on the console?

a)
def foo() = shift{k: (Int => Int) => k(7) + 1}
println(reset{2 * foo()})

b)
println(reset {shift { k: (Int=>Int) => k(k(k(7))) } + 1 } * 2)

c)
println(reset {shift { k: (Int=>Int) => k(k(k(7))); "done" } + 1})

d)
def foo() = { 1 + shift{k: (Int=>Int) => k(k(k(7)))}}
def bar() = {foo() * 2 }
def baz() = { reset{bar() + 10} }
println(baz())

Is anyone able to do so and might post the results?

[Meretrix]

a)
def foo() = shift{k: (Int => Int) => k(7) + 1}
println(reset{2 * foo()})

15

b)
println(reset {shift { k: (Int=>Int) => k(k(k(7))) } + 1 } * 2)

20

c)
println(reset {shift { k: (Int=>Int) => k(k(k(7))); "done" } + 1})

done

d)
def foo() = { 1 + shift{k: (Int=>Int) => k(k(k(7)))}}
def bar() = {foo() * 2 }
def baz() = { reset{bar() + 10} }
println(baz())

140

With these results I would think

For my understanding, the "1+" is still in the continuation because it's one expression with the shift function. I'm not sure thats the correct reasoning but its true at least.
All expressions before the shift function are not contained in the continuation though.

is correct

[Mr.B]

Wasn't exactly that example in the slides accompanied by the explanation that this should be 16, as k is an Escaper and therefore can not be executed more than once in this context?

The point is, k is the continuation and not the escaper.

If you take this example:

Code: Alles auswählen

def foo() = {
  1 + shift(k => k(k(k(7))))
}
def bar() = {
  foo() * 2
}
def baz() = {
  reset(bar())
}
baz()  // result 70

The continuation is k: x => (1 + x) * 2.
The escaper is the function in the shift block esc: k => k(k(k(7))).
So after the execution of the escaper function, the computation is halted.

[Eichhorn]

I'm trying to understand BindCC in our KCFWAE interpreter but don't understand why
eval(BindCC('k, Add(1, App('k, 3)))) evaluates to 3.

eval(BindCC('k, Add(1, App('k, 3))))
= interp(BindCC('k, Add(1, App('k, 3))), Map.empty, identity)
= interp(Add(1, App('k, 3)), Map.empty + ('k -> Continuation(identity)), identity)

Is there something wrong up to this point? Now I'd interp Add, which would make me interpret 1 and App('k, 3), which would give NumV(1) and NumV(3).
Since the result is 3 and not 4 there has to be an error in reasoning on my side. How is the addition "circumvented"?

[LordHoto]

I'm trying to understand BindCC in our KCFWAE interpreter but don't understand why
eval(BindCC('k, Add(1, App('k, 3)))) evaluates to 3.

eval(BindCC('k, Add(1, App('k, 3))))
= interp(BindCC('k, Add(1, App('k, 3))), Map.empty, identity)
= interp(Add(1, App('k, 3)), Map.empty + ('k -> Continuation(identity)), identity)

Is there something wrong up to this point? Now I'd interp Add, which would make me interpret 1 and App('k, 3), which would give NumV(1) and NumV(3).
Since the result is 3 and not 4 there has to be an error in reasoning on my side. How is the addition "circumvented"?

The interpreter call for App('k, 3) will only call the continuation saved in the "Continuation" value. It will not execute the continuation it gets called with. Thus, it will not apply the "Add" anymore and thus the result is 3. You should not forget our whole interpreter is in CPS.

[Eichhorn]

Thanks for clearing that up.