[gambit-list] shift/reset with *correct* dynamic environment

Robby Findler robby at cs.uchicago.edu
Wed Oct 31 13:31:36 EDT 2007


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 at 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 at 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 at 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.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
> > > _______________________________________________
> > > Gambit-list mailing list
> > > Gambit-list at iro.umontreal.ca
> > > https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
> > >
> >
>
>
> --
> James Long
> Coptix, Inc.
> longster at gmail.com
>



More information about the Gambit-list mailing list