Continuations + Graph Reduction

Thread View: comp.lang.functional

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by David Connelly Sat, 26 Jan 1991 04:46

#769

Author: David Connelly
Date: Sat, 26 Jan 1991 04:46

14 lines
1077 bytes

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

Re: Continuations + Graph Reduction

#772

Author: Anurag Acharya
Date: Sun, 27 Jan 1991 05:13

30 lines
2433 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads