Hello everyone,
I have been studying delimited continuations recently. After being blissfully enlightened, I really wanted to have them in Gambit (with a *correct* dynamic environment). I wasn't sure if this was possible non-natively though (at least safely), because Gambit's dynamic environment is somewhat complex, and I have to be able to destructively manipulate the dynamic environment to make sure the delimited continuation truly has its own dynamic environment "slice".
However, I figured out how to (hopefully safely) manipulate Gambit's dynamic environment, and I have a full implementation of shift/reset running in Gambit. This implementation is based off Oleg Kiselyov's work; his paper is here:
http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding
I am not sure of the performance implications of the Gambit version of shift/reset. I am unhappy with how much has to happen per reset or shift, but such is the cost of a non-native implementation. Unfortunately it goes against the grain of Gambit; after looking at some of Gambit's internals, Marc obviously has fine-tuned the code to be very efficient, and each reset or shift call is quite heavy compared to call/cc. Marc... what are thoughts on a native implementation of shift/reset?
I included some tests which show that the dynamic environment does act the way we expect.
If you are a zipped tar kind of guy: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-gambit.tar...
Or you just want the files: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-fixed.scm http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-broken.scm http://james.tech.coptix.com/files/shift-reset-gambit/tests.scm
"shift-reset-fixed.scm" contains the full shift/reset implementation. "shift-reset-broken.scm" contains a naive implementation with a broken dynamic environment. "tests.scm" has some tests to show how the dynamic env is fixed. Note that at the top you can include "shift-reset-broken.scm" instead of the fixed version to see how the dynamic env would normally be broken.
James
--
; tests.scm
(include "shift-reset-fixed.scm")
(define var (make-parameter 5))
(define (displine) (disp "--------------------"))
(define (disp . rest) (apply print (append rest '("\n"))))
(define (dispv . rest) (print rest) (print "\n" (var) "\n"))
(define (test f) (let ((k (f))) (k disp)))
(define (test-parameterize f v1 v2) (parameterize ((var v1)) (let ((k (f v2))) (k dispv))))
(define (parameterize-no-shift v) (reset (parameterize ((var v)) (print "v: " (var)))) (disp ", v: " (var)))
(define (parameterize-it-outside v) (parameterize ((var v)) (reset (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (parameterize-it-inside v) (reset (parameterize ((var v)) (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (wind-outside) (call/cc (lambda (k) (dynamic-wind (lambda () (disp "in winding")) (lambda () (k (reset ((shift f f) "in reset")))) (lambda () (disp "in unwinding"))))))
(define (wind-inside) (reset (dynamic-wind (lambda () (disp "winding")) (lambda () ((shift f f) "inside dynamic-wind")) (lambda () (disp "unwinding")))))
(disp "Testing RAW RESET...") (parameterize-no-shift 20)
(displine)
(disp "Testing OUTSIDE PARAMETERIZE...") (test-parameterize parameterize-it-outside 10 11)
(displine)
(disp "Testing INSIDE PARAMETERIZE...") (test-parameterize parameterize-it-inside 10 11)
(displine)
(disp "Testing OUTSIDE WINDING...") (test wind-outside)
(displine)
(disp "Testing INSIDE WINDING...") (test wind-inside)
; The previous tests output what we expect:
Testing RAW RESET... v: 20, v: 5 -------------------- Testing OUTSIDE PARAMETERIZE... inside reset 11 outside of reset 11 inside reset again 10 last time in reset 10 -------------------- Testing INSIDE PARAMETERIZE... inside reset 11 outside of reset 10 inside reset again 11 last time in reset 11 -------------------- Testing OUTSIDE WINDING... in winding in unwinding in reset -------------------- Testing INSIDE WINDING... winding unwinding winding inside dynamic-wind unwinding
Afficher les réponses par date
Hi --
In case you're not aware, PLT Scheme has delimited continuations that work properly with the dynamic environment, threads, exceptions, etc. Even though I'm sure you probably still want to stick with Gambit, I hope that you'd still find our writeup useful (it explains the semantic issues that we encountered and how we dealt with them):
http://people.cs.uchicago.edu/~robby/pubs/papers/icfp2007-fyff.pdf
Robby
On 10/30/07, James Long longster@gmail.com wrote:
Hello everyone,
I have been studying delimited continuations recently. After being blissfully enlightened, I really wanted to have them in Gambit (with a *correct* dynamic environment). I wasn't sure if this was possible non-natively though (at least safely), because Gambit's dynamic environment is somewhat complex, and I have to be able to destructively manipulate the dynamic environment to make sure the delimited continuation truly has its own dynamic environment "slice".
However, I figured out how to (hopefully safely) manipulate Gambit's dynamic environment, and I have a full implementation of shift/reset running in Gambit. This implementation is based off Oleg Kiselyov's work; his paper is here:
http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding
I am not sure of the performance implications of the Gambit version of shift/reset. I am unhappy with how much has to happen per reset or shift, but such is the cost of a non-native implementation. Unfortunately it goes against the grain of Gambit; after looking at some of Gambit's internals, Marc obviously has fine-tuned the code to be very efficient, and each reset or shift call is quite heavy compared to call/cc. Marc... what are thoughts on a native implementation of shift/reset?
I included some tests which show that the dynamic environment does act the way we expect.
If you are a zipped tar kind of guy: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-gambit.tar...
Or you just want the files: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-fixed.scm http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-broken.scm http://james.tech.coptix.com/files/shift-reset-gambit/tests.scm
"shift-reset-fixed.scm" contains the full shift/reset implementation. "shift-reset-broken.scm" contains a naive implementation with a broken dynamic environment. "tests.scm" has some tests to show how the dynamic env is fixed. Note that at the top you can include "shift-reset-broken.scm" instead of the fixed version to see how the dynamic env would normally be broken.
James
--
; tests.scm
(include "shift-reset-fixed.scm")
(define var (make-parameter 5))
(define (displine) (disp "--------------------"))
(define (disp . rest) (apply print (append rest '("\n"))))
(define (dispv . rest) (print rest) (print "\n" (var) "\n"))
(define (test f) (let ((k (f))) (k disp)))
(define (test-parameterize f v1 v2) (parameterize ((var v1)) (let ((k (f v2))) (k dispv))))
(define (parameterize-no-shift v) (reset (parameterize ((var v)) (print "v: " (var)))) (disp ", v: " (var)))
(define (parameterize-it-outside v) (parameterize ((var v)) (reset (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (parameterize-it-inside v) (reset (parameterize ((var v)) (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (wind-outside) (call/cc (lambda (k) (dynamic-wind (lambda () (disp "in winding")) (lambda () (k (reset ((shift f f) "in reset")))) (lambda () (disp "in unwinding"))))))
(define (wind-inside) (reset (dynamic-wind (lambda () (disp "winding")) (lambda () ((shift f f) "inside dynamic-wind")) (lambda () (disp "unwinding")))))
(disp "Testing RAW RESET...") (parameterize-no-shift 20)
(displine)
(disp "Testing OUTSIDE PARAMETERIZE...") (test-parameterize parameterize-it-outside 10 11)
(displine)
(disp "Testing INSIDE PARAMETERIZE...") (test-parameterize parameterize-it-inside 10 11)
(displine)
(disp "Testing OUTSIDE WINDING...") (test wind-outside)
(displine)
(disp "Testing INSIDE WINDING...") (test wind-inside)
; The previous tests output what we expect:
Testing RAW RESET... v: 20, v: 5
Testing OUTSIDE PARAMETERIZE... inside reset 11 outside of reset 11 inside reset again 10 last time in reset 10
Testing INSIDE PARAMETERIZE... inside reset 11 outside of reset 10 inside reset again 11 last time in reset 11
Testing OUTSIDE WINDING... in winding in unwinding in reset
Testing INSIDE WINDING... winding unwinding winding inside dynamic-wind unwinding _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
I was not aware of it, thanks for the reference. I do want to stick with Gambit, but the more implementations which have a working shift/reset, the more I can test my code on.
I should say that my current version is not full shift/reset (I may have mistakenly said so). It's not. You still can't serialize them because the input/output ports are still captured. I also need to take care of other fields in Gambit dynamic environment vector; right now all I watch out for is the local parameters, input/output ports, exception handler, and dynamic wind. Other parts of the dynamic environment such as the interrupt mask, debugging settings, and repl context, I'm assuming, still suffer the capturing problem. I'm not exactly sure what the debugging settings (maybe traced functions?) and repl context are though, and they require more research.
James
On 10/31/07, Robby Findler robby@cs.uchicago.edu wrote:
Hi --
In case you're not aware, PLT Scheme has delimited continuations that work properly with the dynamic environment, threads, exceptions, etc. Even though I'm sure you probably still want to stick with Gambit, I hope that you'd still find our writeup useful (it explains the semantic issues that we encountered and how we dealt with them):
http://people.cs.uchicago.edu/~robby/pubs/papers/icfp2007-fyff.pdf
Robby
On 10/30/07, James Long longster@gmail.com wrote:
Hello everyone,
I have been studying delimited continuations recently. After being blissfully enlightened, I really wanted to have them in Gambit (with a *correct* dynamic environment). I wasn't sure if this was possible non-natively though (at least safely), because Gambit's dynamic environment is somewhat complex, and I have to be able to destructively manipulate the dynamic environment to make sure the delimited continuation truly has its own dynamic environment "slice".
However, I figured out how to (hopefully safely) manipulate Gambit's dynamic environment, and I have a full implementation of shift/reset running in Gambit. This implementation is based off Oleg Kiselyov's work; his paper is here:
http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding
I am not sure of the performance implications of the Gambit version of shift/reset. I am unhappy with how much has to happen per reset or shift, but such is the cost of a non-native implementation. Unfortunately it goes against the grain of Gambit; after looking at some of Gambit's internals, Marc obviously has fine-tuned the code to be very efficient, and each reset or shift call is quite heavy compared to call/cc. Marc... what are thoughts on a native implementation of shift/reset?
I included some tests which show that the dynamic environment does act the way we expect.
If you are a zipped tar kind of guy: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-gambit.tar...
Or you just want the files: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-fixed.scm http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-broken.scm http://james.tech.coptix.com/files/shift-reset-gambit/tests.scm
"shift-reset-fixed.scm" contains the full shift/reset implementation. "shift-reset-broken.scm" contains a naive implementation with a broken dynamic environment. "tests.scm" has some tests to show how the dynamic env is fixed. Note that at the top you can include "shift-reset-broken.scm" instead of the fixed version to see how the dynamic env would normally be broken.
James
--
; tests.scm
(include "shift-reset-fixed.scm")
(define var (make-parameter 5))
(define (displine) (disp "--------------------"))
(define (disp . rest) (apply print (append rest '("\n"))))
(define (dispv . rest) (print rest) (print "\n" (var) "\n"))
(define (test f) (let ((k (f))) (k disp)))
(define (test-parameterize f v1 v2) (parameterize ((var v1)) (let ((k (f v2))) (k dispv))))
(define (parameterize-no-shift v) (reset (parameterize ((var v)) (print "v: " (var)))) (disp ", v: " (var)))
(define (parameterize-it-outside v) (parameterize ((var v)) (reset (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (parameterize-it-inside v) (reset (parameterize ((var v)) (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (wind-outside) (call/cc (lambda (k) (dynamic-wind (lambda () (disp "in winding")) (lambda () (k (reset ((shift f f) "in reset")))) (lambda () (disp "in unwinding"))))))
(define (wind-inside) (reset (dynamic-wind (lambda () (disp "winding")) (lambda () ((shift f f) "inside dynamic-wind")) (lambda () (disp "unwinding")))))
(disp "Testing RAW RESET...") (parameterize-no-shift 20)
(displine)
(disp "Testing OUTSIDE PARAMETERIZE...") (test-parameterize parameterize-it-outside 10 11)
(displine)
(disp "Testing INSIDE PARAMETERIZE...") (test-parameterize parameterize-it-inside 10 11)
(displine)
(disp "Testing OUTSIDE WINDING...") (test wind-outside)
(displine)
(disp "Testing INSIDE WINDING...") (test wind-inside)
; The previous tests output what we expect:
Testing RAW RESET... v: 20, v: 5
Testing OUTSIDE PARAMETERIZE... inside reset 11 outside of reset 11 inside reset again 10 last time in reset 10
Testing INSIDE PARAMETERIZE... inside reset 11 outside of reset 10 inside reset again 11 last time in reset 11
Testing OUTSIDE WINDING... in winding in unwinding in reset
Testing INSIDE WINDING... winding unwinding winding inside dynamic-wind unwinding _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Yes, all these details are what make for an interesting read in our paper. It may be that you want to look at our design in general, since all of our dynamic context boils down to just a few constructs, making it easier to keep track of everything.
Robby
On 10/31/07, James Long longster@gmail.com wrote:
I was not aware of it, thanks for the reference. I do want to stick with Gambit, but the more implementations which have a working shift/reset, the more I can test my code on.
I should say that my current version is not full shift/reset (I may have mistakenly said so). It's not. You still can't serialize them because the input/output ports are still captured. I also need to take care of other fields in Gambit dynamic environment vector; right now all I watch out for is the local parameters, input/output ports, exception handler, and dynamic wind. Other parts of the dynamic environment such as the interrupt mask, debugging settings, and repl context, I'm assuming, still suffer the capturing problem. I'm not exactly sure what the debugging settings (maybe traced functions?) and repl context are though, and they require more research.
James
On 10/31/07, Robby Findler robby@cs.uchicago.edu wrote:
Hi --
In case you're not aware, PLT Scheme has delimited continuations that work properly with the dynamic environment, threads, exceptions, etc. Even though I'm sure you probably still want to stick with Gambit, I hope that you'd still find our writeup useful (it explains the semantic issues that we encountered and how we dealt with them):
http://people.cs.uchicago.edu/~robby/pubs/papers/icfp2007-fyff.pdf
Robby
On 10/30/07, James Long longster@gmail.com wrote:
Hello everyone,
I have been studying delimited continuations recently. After being blissfully enlightened, I really wanted to have them in Gambit (with a *correct* dynamic environment). I wasn't sure if this was possible non-natively though (at least safely), because Gambit's dynamic environment is somewhat complex, and I have to be able to destructively manipulate the dynamic environment to make sure the delimited continuation truly has its own dynamic environment "slice".
However, I figured out how to (hopefully safely) manipulate Gambit's dynamic environment, and I have a full implementation of shift/reset running in Gambit. This implementation is based off Oleg Kiselyov's work; his paper is here:
http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding
I am not sure of the performance implications of the Gambit version of shift/reset. I am unhappy with how much has to happen per reset or shift, but such is the cost of a non-native implementation. Unfortunately it goes against the grain of Gambit; after looking at some of Gambit's internals, Marc obviously has fine-tuned the code to be very efficient, and each reset or shift call is quite heavy compared to call/cc. Marc... what are thoughts on a native implementation of shift/reset?
I included some tests which show that the dynamic environment does act the way we expect.
If you are a zipped tar kind of guy: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-gambit.tar...
Or you just want the files: http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-fixed.scm http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-broken.scm http://james.tech.coptix.com/files/shift-reset-gambit/tests.scm
"shift-reset-fixed.scm" contains the full shift/reset implementation. "shift-reset-broken.scm" contains a naive implementation with a broken dynamic environment. "tests.scm" has some tests to show how the dynamic env is fixed. Note that at the top you can include "shift-reset-broken.scm" instead of the fixed version to see how the dynamic env would normally be broken.
James
--
; tests.scm
(include "shift-reset-fixed.scm")
(define var (make-parameter 5))
(define (displine) (disp "--------------------"))
(define (disp . rest) (apply print (append rest '("\n"))))
(define (dispv . rest) (print rest) (print "\n" (var) "\n"))
(define (test f) (let ((k (f))) (k disp)))
(define (test-parameterize f v1 v2) (parameterize ((var v1)) (let ((k (f v2))) (k dispv))))
(define (parameterize-no-shift v) (reset (parameterize ((var v)) (print "v: " (var)))) (disp ", v: " (var)))
(define (parameterize-it-outside v) (parameterize ((var v)) (reset (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (parameterize-it-inside v) (reset (parameterize ((var v)) (dispv "inside reset") ((shift f (dispv "outside of reset") f) "inside reset again") (dispv "last time in reset"))))
(define (wind-outside) (call/cc (lambda (k) (dynamic-wind (lambda () (disp "in winding")) (lambda () (k (reset ((shift f f) "in reset")))) (lambda () (disp "in unwinding"))))))
(define (wind-inside) (reset (dynamic-wind (lambda () (disp "winding")) (lambda () ((shift f f) "inside dynamic-wind")) (lambda () (disp "unwinding")))))
(disp "Testing RAW RESET...") (parameterize-no-shift 20)
(displine)
(disp "Testing OUTSIDE PARAMETERIZE...") (test-parameterize parameterize-it-outside 10 11)
(displine)
(disp "Testing INSIDE PARAMETERIZE...") (test-parameterize parameterize-it-inside 10 11)
(displine)
(disp "Testing OUTSIDE WINDING...") (test wind-outside)
(displine)
(disp "Testing INSIDE WINDING...") (test wind-inside)
; The previous tests output what we expect:
Testing RAW RESET... v: 20, v: 5
Testing OUTSIDE PARAMETERIZE... inside reset 11 outside of reset 11 inside reset again 10 last time in reset 10
Testing INSIDE PARAMETERIZE... inside reset 11 outside of reset 10 inside reset again 11 last time in reset 11
Testing OUTSIDE WINDING... in winding in unwinding in reset
Testing INSIDE WINDING... winding unwinding winding inside dynamic-wind unwinding _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
-- James Long Coptix, Inc. longster@gmail.com
On 30-Oct-07, at 8:29 PM, James Long wrote:
Marc... what are thoughts on a native implementation of shift/reset?
It is on my TODO (it was the first thing I added to the Gambit wish list page!). I think a correct implementation of shift/reset is necessary to properly serialize continuations and do distributed parallel computation. The hard part in all of this is to find a good representation for the dynamic environment. The problem I see with the PLT Scheme implementation is that the dynamic wind stack must be copied (in O(n)) when a delimited continuation is invoked. I think I have found a solution, but it is only by going through the details that I can confirm that it works.
Marc
Hey Marc -- it should be possible to explore such alternatives in Redex, without having to actually implement it first. There is a redex model of what appears in the paper to start from, too.
Robby
On 10/31/07, Marc Feeley feeley@iro.umontreal.ca wrote:
On 30-Oct-07, at 8:29 PM, James Long wrote:
Marc... what are thoughts on a native implementation of shift/reset?
It is on my TODO (it was the first thing I added to the Gambit wish list page!). I think a correct implementation of shift/reset is necessary to properly serialize continuations and do distributed parallel computation. The hard part in all of this is to find a good representation for the dynamic environment. The problem I see with the PLT Scheme implementation is that the dynamic wind stack must be copied (in O(n)) when a delimited continuation is invoked. I think I have found a solution, but it is only by going through the details that I can confirm that it works.
Marc
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
-
James Long -
Marc Feeley -
Robby Findler