Delimited continuations and forall

Help!
1

I’m bit surprised by the behaviour of delimited continuations when used together with forall/2.

Let’s start with a simple example which doesn’t use forall:

shift_all([]):-!.
shift_all([X|Xs]):-shift(X), shift_all(Xs).

Querying reset(shift_all([1,2,3]), X, Cont), reset(Cont, X2, Cont2) returns X=1, X2=2 as expected.

Now when I try:

reset(forall(member(M, [1,2,3]),shift(M)), X, Cont), reset(Cont, X2, Cont2) I get:

ERROR: Type error: `callable' expected, found `0' (an integer)
ERROR: In:
ERROR: [11] reset(user:0,_7526,_7528)

Can someone help explain what’s going on?

Is this because forall uses backtracking to drive the Generator and the first continuation “loses” knowledge of choice points, that is, it doesn’t backtrack to find next solution?

1 Like
2

I’ve read the original paper at https://www.swi-prolog.org/download/publications/iclp2013.pdf and there’s even a small example with backtracking.

The problem is that, contrary to what I assumed, choice points are not “converted” into continuations but are propagated to wherever reset was called.

3

Yes. Delimited continuations do not play with commit, forall/2 is implemented using \+/1, which commits.

4

What do you mean by “commit”? Is this simply removing the choicepoint (that is, some kind of “cut”)?

forall/2 is actually a double negation:

forall(Cond, Action) :-
    \+ (Cond, \+ Action).

PS:

The cut probably isn’t needed. But that doesn’t change the error you get.

5

The usual idea of continuations is that you can abort (using shift/1) any computation and make it continue using call/1, just as if nothing happened. That is not always the case for Prolog’s continuations. The case that typically goes wrong is where you shift before a commit (!/0 or ->) Let us consider this

 p, shift(Ball), q -> r ; s

Running this, the ;/2 choicepoint was created before the shift and thus remains part of the computation. If we resume after the shift, the link between the commit implied by → and the choice point of the ;/2 is lost and the → thus no longer has any effect. That is the original work. SWI-Prolog’s implementation can in some cases deal with the commit if the continuation is immediately restarted. Use cases such as tabling store the continuation for later reused though. In this case it doesn’t matter as tabling has the same limitations when dealing with commits.

Thus, shift only captures the current forward continuation, not the choice points.

1 Like