[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