Annotation--annotation

LogicalCaptain said (2020-06-29T16:19:51):

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.

"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)
throw(+Exception) (throw/1) and
shift(+Ball) (shift/1)

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.

Examples

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).
- iterator.pl
- Illustration
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.

And also:

producer_consumer_master.pl, a producer-consumer example with a central "master" that dishes out the reset/3 calls.

Shifting is not backtracking

Variables bound by a procedure called via reset/3 stay bound after shift/1

:- 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).

And so:

?- 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).

And so:

?- 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:

trial.pl:

% ===
% 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)).

And so:

?- 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])

you get:

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.

This is also why reset/3 can take both an atomic goal on the first round and a continuation returned by a previous reset/3.

Edge cases

There is nothing to do for the continuation of shift() itself:

?- 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.

Doc needs fix

Further reading

Note the similarity between exception handling and delimited continuations

Examples

Shifting is not backtracking

Choice points are maintained

A simple loop example

Playing around with a booby-trapped "iterator" implementation

The "continuation" term is a compound term

Edge cases