[gambit-list] shift/reset with *correct* dynamic environment
James Long
longster at gmail.com
Tue Oct 30 20:29:19 EDT 2007
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.gz
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
More information about the Gambit-list
mailing list