Delimited continuations in Scala

erdweg
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 28. Mär 2013 10:08

Delimited continuations in Scala

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 18. Okt 2012 19:12

Re: Delimited continuations in Scala

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 13. Dez 2009 17:04

Re: Delimited continuations in Scala

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 18. Okt 2012 19:12

Re: Delimited continuations in Scala

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 9. Mär 2012 18:11

Re: Delimited continuations in Scala

Beitrag von 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
Neuling
Neuling
Beiträge: 9
Registriert: 25. Apr 2012 22:43

Re: Delimited continuations in Scala

Beitrag von Meretrix »

Eichhorn hat geschrieben: a)
def foo() = shift{k: (Int => Int) => k(7) + 1}
println(reset{2 * foo()})
15
Eichhorn hat geschrieben: b)
println(reset {shift { k: (Int=>Int) => k(k(k(7))) } + 1 } * 2)
20
Eichhorn hat geschrieben: c)
println(reset {shift { k: (Int=>Int) => k(k(k(7))); "done" } + 1})
done
Eichhorn hat geschrieben: 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
Mr.B hat geschrieben: 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
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 13. Dez 2009 17:04

Re: Delimited continuations in Scala

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 9. Mär 2012 18:11

Re: Delimited continuations in Scala

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 14. Dez 2009 17:00

Re: Delimited continuations in Scala

Beitrag von LordHoto »

Eichhorn hat geschrieben: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.
Compiler 1 Tutor WS 12/13

Eichhorn
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 9. Mär 2012 18:11

Re: Delimited continuations in Scala

Beitrag von Eichhorn »

Thanks for clearing that up. :)

Antworten

Zurück zu „Archiv“