david@sbstaff2.cs.sunysb.edu (David Connelly) (01/26/91)
Would anyone have any pointers on how to implement continuations in a graph reduction interpreter based on Turner's combinator set? I see no difficulty in supporting continuations that are only passed inwards, but can find no easy solution to supporting continuations that are returned from the call/cc function. Is there better way to accomplish this other than to keep a history of all relevant node changes made after the continuation was created, and using the history to "undo" these changes after the continuation is invoked? Any hints would be appreciated. Thanks, David Connelly david@cs.sunysb.edu
acha@CS.CMU.EDU (Anurag Acharya) (01/27/91)
In article <1991Jan26.044605.3610@sbcs.sunysb.edu> david@sbstaff2.cs.sunysb.edu (David Connelly) writes:
Would anyone have any pointers on how to implement continuations
in a graph reduction interpreter based on Turner's combinator set?
I see no difficulty in supporting continuations that are only
passed inwards, but can find no easy solution to supporting continuations
that are returned from the call/cc function. Is there better way
to accomplish this other than to keep a history of all relevant
node changes made after the continuation was created, and using
the history to "undo" these changes after the continuation is invoked?
Any hints would be appreciated.
The obvious idea that comes to mind is to save a pointer to the root node
but that doesn't work since each reduction results in the redex node being
overwritten. This problem would go away if the reduction algorithm was modified
so that the redex node was *not* overwritten; instead was replaced by a new
result node. The obvious problem with this scheme is that it imposes a
computational penalty on every reduction even if call/cc is not used
(there might be other problems too -- I am not sure at this point).
Another possibility would be to copy the entire graph over during the call/cc
operation. This would make the call/cc operation pretty expensive - but the
expense would be incurred only if call/cc was used and the rest of the
operations proceed as they would without the call/cc operation. To invoke
the continuation, the current root node ptr would be replaced by the ptr
to the saved graph. This is kind of analogous to copying the stack over
to the heap that is used to implement call/cc in stack-based implementations --
it might be possible to carry over the incremental saving schemes used in these
cases for saving the graph.
anurag