Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rutgers!rochester!pt.cs.cmu.edu!dravido.soar.cs.cmu.edu!acha From: acha@CS.CMU.EDU (Anurag Acharya) Newsgroups: comp.lang.functional Subject: Re: Continuations + Graph Reduction Message-ID: Date: 27 Jan 91 05:13:19 GMT References: <1991Jan26.044605.3610@sbcs.sunysb.edu> Sender: acha@dravido.soar.cs.cmu.edu Organization: Carnegie Mellon University Lines: 30 In-reply-to: david@sbstaff2.cs.sunysb.edu's message of 26 Jan 91 04:46:05 GMT 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