Doc needs fix
"Prolog is described in Schrijvers et al., 2013 (preprint PDF)."
- The link for "Schrijvers et al., 2013" goes to the bibliography page where you are then stranded because there is no further link.
- The link for "(preprint PDF)" goes to a prerelease for the ISO Standard for the C language (surely a mistake)
Here is the correct link:
"Delimited continuations for Prolog": https://www.swi-prolog.org/download/publications/iclp2013.pdf - The PDF says it has been written in 2003, but it has really been written in 2013. It's a preprint.
It has been published in Theory and Practice of Logic Programming in 2013.
Call with Current Continuation Patterns, Darrel Ferguson, Dwight Deugo, August 24, 2001.
...this is meant to explore patterns in Scheme using call-with-current-continuation, not patterns in Prolog using reset/shift, but it eminently readable.
...which introduces shift and reset but it's a very technical paper (I don't get it yet)
"Shift" abstracts the current context as an ordinary, composable procedure and "reset" delimits the scope of such a context. Shift also differs from "escape" by not duplicating the current continuation. (...) While the effects of these operators are very similar to operators control and prompt of [Felleisen 88: The Theory and Practice of First-Class Prompts], there is a significant semantical difference between "shift/reset" and "control/prompt": the context abstracted by "shift" is determined statically by the program text, while "control" captures the context up to the nearest dynamically enclosing "prompt". In general, this leads to different behavior. Programming with continuations has appeared as an intriguing possibility offered by control operators such as Landin's "J", Reynolds's "escape", and "call-with-current-continuation" in Scheme. Such first-class continuations are more general than MacLisp's "catch/throw" mechanism and ML's "exceptions" since they allow a previous scope to be restored, just like applying a functional value reestablishes an earlier environment. First-class continuations have been investigated mainly as powerful, but unstructured devices requiring a deep intuition and operational skill [Friedman, Haynes, & Kohlbecker 84] [Haynes & Friedman 87]. However, some progress has been made towards a more declarative view of them, based on a category-theoretical duality between values and continuations [Filinski 89].
And as said in the main text this mechanism is excellent for implementing Coroutines.
Note the similarity between exception handling and delimited continuations
And this is not an accident:
- catch(:Goal, +Catcher, :Recover) (catch/3) and
- reset(:Goal, ?Ball, -Continuation) (reset/3)
Exception handling is a specialization of Delimited Continuations whereby the Recover goal is executed if Continuation is not 0, and the Continuation is thrown away.
This extends to the fact that if the call stack contains several calls to reset/3 (i.e. if you are in nested context) and you call shift/1 with a Term T, execution flow goes to the first reset/3 with a unifying Ball, in the same as as execution flow goes to the first catch/3 that unifies Catcher with Exception (I'm not sure how to think about this or how to use it.)
In Scheme (and others), there is the function call with current continuation, which calls a receiver function with the current continuation as single argument. The receiver then either use that continuation to get out of some inner computation if it has to.
The correspondence between call-cc to reset/3 is that
reset(Goal,Catcher,Cont) stores the the current continuation "behind the scenes" and makes it retrievable by a match with Catcher. A call to shift/1 corresponds to retrieval and call of the stored continuation, so that execution continues at the point of the matching reset/3 call. Additionally, the continuation of the shift/1 call point is generated, but one has not necessarily a need for that.
On this page:
Inspired "Schrijvers et al., 2013.":
- iterator: An implementation of "iterators" (which are apparently "generators", which are "semi-coroutines"] that generate output on behalf of a "master predicate" which then sends the output to a user-selectable destination (in this case, write/1).
- effect handler: An implementation of an "effect handler" keeping track of state on behalf of client code. Examples include: of a Markov Network visitor and a counter-to-zero.
producer_consumer_master.pl, a producer-consumer example with a central "master" that dishes out the reset/3 calls.
Shifting is not backtracking
:- debug(changee). changee :- debug(changee,"Changee says the variable is ~q",[N]), reset(call(changer,N),mine,_), debug(changee,"Changee now says the variable is ~q",[N]). changer(N) :- N = foo, shift(mine).
?- changee. % Changee says the variable is _9014 % Changee now says the variable is foo true.
Choice points are maintained
:- debug(multi). multi :- debug(multi,"Calling 'possible' through 'reset'",), reset(possible,mine,_), debug(multi,"Back in 'multi'",). possible :- debug(multi,"In 'possible'",), shift(mine). possible :- debug(multi,"In alternate 'possible'",), shift(mine).
?- multi. % Calling 'possible' through 'reset' % In 'possible' % Back in 'multi' true ; % In alternate 'possible' % Back in 'multi' true.
A simple loop example
Note the parameter passing to loopcontent/1 using an indirection through call/1.
:- debug(loop). loop(N) :- (N>0) -> ( debug(loop,"Calling 'loopcontent(~d)' through 'reset'",[N]), reset(call(loopcontent,N),mine,_), debug(loop,"Back in loop",), Nm is N-1, loop(Nm) ) ; debug(loop,"Loop is done",). loopcontent(N) :- debug(loop,"In 'loopcontent(~d)'",[N]), shift(mine).
Playing around with a booby-trapped "iterator" implementation
The predicate-to-call takes a list of stuff which are then generated one-by-one by an "iterator" coroutine and printed to stdout by the with_write/1 "manager" coroutine. The content of the list can elicit some occurrences of interest:
% === % The "master coroutine": It writes the values yielded by the "iterator" % represented by "Goal" to stdout. % === with_write(Goal) :- reset(Goal,yield(X),Cont), branch(Cont,yield(X)). branch(0,_) :- !, format("Iterator succeeded\n"). branch(Cont,yield(X)) :- format("Iterator yielded ~q\n",[X]), with_write(Cont). % === % The "iterator", generating successive values (read from a list in % this case) that are communicated to the master coroutine by a call % to shift/1. % However, the "iterator" behaves in peculiar ways depending on the % element encountered because we want to see what happens exactly. % == from_list([X|Xs]) :- ((X == fail; X == false) % elicit failure -> fail ; (X == throw) % elicit exception -> domain_error(this,that) ; (X == badshift) % elicit shift not unifiable by reset/3 call -> shift(bad(X)) ; (X == recur) % elicit matrioshka reset/3 call -> with_write(from_list([sub1,sub2,sub3])) ; shift(yield(X))), % bravely default from_list(Xs). % tail recursive loop from_list(). % == % Main predicate, call from toplevel % == run(L) :- must_be(list,L), with_write(from_list(L)).
?- run([a,b,c]). Iterator yielded a Iterator yielded b Iterator yielded c Iterator succeeded true. ?- run([a,fail,c]). Iterator yielded a false. ?- run([a,throw,c]). Iterator yielded a ERROR: Domain error: `this' expected, found `that' ?- run([a,badshift,c]). Iterator yielded a ERROR: reset/3 `bad(badshift)' does not exist ?- run([a,recur,c]). Iterator yielded a Iterator yielded sub1 Iterator yielded sub2 Iterator yielded sub3 Iterator succeeded Iterator yielded c Iterator succeeded true.
The "continuation" term is a compound term
At least in the current implementation, if you run:
compound_name_arity(Cont,Name,Arity), format("The continuation has name '~q' and ~d arguments ~q\n",[Name,Arity])
The continuation has name 'call_continuation' and 1 arguments
which is why a valid continuation is guaranteed distinguishable from 0.
It is actually an atomic goal: a call to call_continuation/1 with 1 argument prefilled.
There is nothing to do for the continuation of
?- reset(shift(mine),mine,C). C = call_continuation(). ?- reset(shift(mine),mine,C), call(C). C = call_continuation().
There is something to do if there is a true following the shift, namely, succeed:
?- reset((shift(mine),true),mine,C). C = call_continuation(['$cont$'(<clause>(0x23a5510), 15, '<inactive>', user, 125, '<inactive>', true)]). ?- reset((shift(mine),true),mine,C), call(C). C = call_continuation(['$cont$'(<clause>(0x23a5510), 15, '<inactive>', user, 125, '<inactive>', true)]).
There is something to do if there is a false following the shift, namely, fail:
?- reset((shift(mine),false),mine,C). C = call_continuation(['$cont$'(<clause>(0x23a5510), 15, '<inactive>', user, 125, '<inactive>', false)]). ?- reset((shift(mine),false),mine,C), call(C). false.