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