DCGs implemented with delimited continuations

Help!
1

I tried the DCG example in https://www.swi-prolog.org/download/publications/iclp2013.pdf … and it doesn’t work. Also, the simple examples in https://www-ps.informatik.uni-kiel.de/kdpd2013/talks/schrijvers.pdf work a bit differently.

How are the semantics of SWI-Prolog different from the delimited continuation paper? This is the example from slide 17 of the talk:

?- listing(main).
main :-
    reset(p, _, X),
    writeln(X),
    writeln(c).

?- listing(p).
p :-
    writeln(a),
    shift(hello),
    writeln(b).

?- main.
a
call_continuation([$cont$(<clause>(0x7fffdbfe62c0),9)])
c

but the talk says the output should be:

a
hello
c

Also, the DCG example in the paper fails when I try running it (I’m using ph because phrase is builtin):

c(E) :- shift(c(E)).

ph(Goal, Lin, Lout) :-
    reset(Goal, Cont, Term),
    (   Cont==0
    ->  Lin=Lout
    ;   Term=c(E)
    ->  Lin=[E|Lmid],
        ph(Cont, Lmid, Lout)
    ).
                                                                                 
ab(0).
ab(N) :- c(a), c(b), ab(M), N is M + 1.

test(N) :- ph(ab(N), [a,b,a,b], []).
2

Seems that 2nd and 3th arguments have been swapped, probably for consistency with the usual ‘output come last’ style, from reset(Goal,Continuation,Term) to reset(:Goal, ?Ball, -Continuation).

3 Likes
3

Just a side note, I don’t know what your use case is, but you may be able to use the new intercept library to achieve your goal.

2 Likes
4

Thank-you, that fixed it. The examples work and I’m slowly getting an intuitive feeling of what delimited continuations do and how to use them. (It feels a bit like when I first learned Prolog, except I haven’t had the “ah-ha!” moment yet.)

5

When you get to “ah-ha!” you should write it up for others to read. :slightly_smiling_face:

6

Not an “ah-ha!” yet, but this quote helped (unfortunately, most of the explanations are for functional programming and/or monads, and seem to be unnecessarily complicated, especially if they mention destructive operations such as setq … I’m still working on getting a level of intuition for delimited continuations that’s as good as my intuition for unification):

Say you’re in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there’s a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :slight_smile:
Continuation - Wikipedia

2 Likes
7

Yes I have seen that one before and while it is memorable, it still doesn’t resonate to help me understand them.

I’ll keep an eye out for further post. :slightly_smiling_face:

8

I thought I understood continuations in Scheme (where it gives you a closure that represents “what was about to happen”, so you can kind of jump back to that place in the code, where the arguments you pass to that closure are “what happens”), but in Prolog, with logic variables, I find it much harder to follow…

9

Also the Prolog version is exactly that. Shift/1 captures the forward continuation up to the matching reset/3 and causes reset/3 to succeed. There is no backtracking in this process and the continuation (a term on the stack) thus shares all (logical) variables with the environment at the point where we aborted the execution (shift). You can do something else and continue where you were by calling the continuation. That is what happens in the DCG story, but what you can also achieve using the intercept interface, which is typically faster and doesn’t suffer from some subtle interaction with cuts of delimited continuations.

Tabling uses them differently. Here the continuations are copied in permanent memory (say assert, though it uses internal alternatives). Now you can execute the continuation any time later and as many times as you want. The copy looses the variable bindings and thus you must make the copy together with a term representing the variables that must be shared with the environment. Now we can copy the continuation+vars back to the stacks, unify the vars and call the continuation.

3 Likes
10

Thanks Jan! I also tried writing an explainer after playing around with continuations a bit last night; hopefully that isn’t too incorrect/makes some sense.

2 Likes
11

writing an explainer

Nice job!

Something I am working on currently might be able to use this and is a practical use. The code is working as DCGs with several accumulators working in parallel on the same data, so I am converting it to EDCGs to see how that plays out, but will give this a try also.

EDIT

Thought of a different practical example that this might be of use, creating a spreadsheet.

For cells that have equations based on other cells that may have equations or data, when updating a cell it needs to check if the cells it depends on have had their data updated and recalculate.

While I don’t have the time to do this variation of a practical example, someone else might. :slightly_smiling_face:

Would also make for a nice exercise in an advance programming class.

12

Does anyone know why the operations are called shift and reset? According to Wikipedia, these names come from the paper Olivier Danvy; Andrzej Filinski (1990). “Abstracting Control”, but that paper doesn’t seem to have explanation for the choice of names.

I find the names shift and reset unhelpful and other names in the article (Ƒ, #, prompt, control, cupto, fcontrol) aren’t an improvement. … sadly catch and throw are already taken, but perhaps catch_continuation and yield would be more mnemonic?

@jan – as far as I can tell, call/1 works the same with delimited continuations as with regular terms … is this a correct understanding? (The documentation for call/1 doesn’t mention continuations.)

13

I never liked the names much either. On the other hand, you use these primitives only for writing libraries that provide new high level control structures and very rarely just locally in your code, so why care (much)?.

The mechanism is transparent to call/1. Why would it not be? There is a little technical issue in the sense that a continuation is basically a list of frames, each frame storing the variables, a reference to the clause and a program pointer into this clause. Call/1 using control structures however compiles the control structure to a volatile clause on the stack. We cannot reference that. The system has a hack that call/1 below reset/3 interprets the control structure in Prolog. This provides the necessary stable clauses. The performance impact varies. Notably if the control structure is a failure driven loop, the compiled version may be significantly faster. If there is no internal backtracking and especially if the control structure is a conjunction that fails early, the interpreted version may actually be faster.

The interpreted version is also not ISO compliant in the sense that call((fail,0)) is supposed to raise a type error. As the fail stops the interpretation though, no error is raised.

1 Like
14

Still note that the signal/intercept interface is a sensible alternative for those cases where after reset/3 you do something and call the continuation. This is more or less an interrupt that can also be handled using library(intercept). Here is an example:

:- use_module(library(intercept)).

iphrase(Goal, List, Tail) :-
    State = list(List),
    intercept(Goal, iphrase(What), iphrase_handler(What), State),
    arg(1, State, Tail).

iphrase_handler(Literal, State) :-
    arg(1, State, List),
    append(Literal, Tail, List),
    setarg(1, State, Tail).

literal(List) :-
    send_signal(iphrase(List)).

And a use case:

test(X) :-
    iphrase(t(X), `hello world`, []).

t(World) :-
    literal(`hello `),
    literal(Rest),
    atom_codes(World, Rest).

And finally

?- test(X).
X = world ;
false.

At the time I was working with Tom and Benoit on delimited continuations there was not yet library(intercept) so I hacked something that resembled using library(intercept) to compare. Real DCGs are clearly the fastest, but using the intercept alternative was faster than delimited continuation and doesn’t suffer from some of the nasty corner cases related to cuts and if->then;else that cause problems with delimited continuations.

2 Likes
15

I’ve had a bit of an “ah-ha!” with delimited continuations, so here’s my attempt to explain them. I think that the “get/put” example (the “state monad”[*]) is a bit better for explaining than the DCG example (but if my explanation doesn’t help, I can try again with DCGs).

The trick (for me) was to not think about the specific semantics of reset/3 and shift/1 but rather how they’re used – reset/3 is used by a “server” and shift/1 is used by a “client”. The “server” is just a loop over a Goal that can send a “command” to the server (using shift/1), with each iteration passing the “state” and receiving a Command from the “client”. When there are no more commands to the server, the loop terminates:

%! run_state(:Goal, +StateIn, -StateOut) is det.
run_state(Goal, StateIn, StateOut) :-
    reset(Goal, Command, Cont),
    (   Cont == 0  % no more commands from Goal?
    ->  StateOut = StateIn
    ;   run_state_(Command, Cont, StateIn, StateOut)
    ).

The “server” interprets the Command. There are two commands: “get” the current state’s value and “put” (or set) the state’s value. The Cmd argument contains a new value with put_cmd(Value); get_cmd(Value) receives (unifies) the current value. Note that the run_state_/4 predicate recursively tail-calls run_state/3 with a new continuation as the Goal – this continuation resumes execution immediately after the command to the server.

%! run_state(?Cmd, +Cont, +StateIn, -StateOut) is det.
run_state_(get_cmd(S), Cont, StateIn, StateOut) =>
    S = StateIn,
    run_state(Cont, StateIn, StateOut).
run_state_(put_cmd(S), Cont, _StateIn, StateOut) =>
    run_state(Cont, S, StateOut).

We now define wrappers for the client:

%! get(-S) is det.
get(S) :- shift(get_cmd(S)).

%! put(+S) is det.
put(S) :- shift(put_cmd(S)).

Now, let’s put it together. We first define an inc(I) predicate that increments the “state”:

inc(I) :-
    get(S0),
    S is S0 + I,
    format('~w + ~w => ~w~n', [S0, I, S]), % for debugging
    put(S).

and let’s run it with the goal (inc(1), inc(2), inc(4)):

?- run_state((inc(1), inc(2), inc(4)), 0, S).
0 + 1 => 1
1 + 2 => 3
3 + 4 => 7
S = 7.

This style of client/server reminds me of Erlang, except that the full power of Prolog is available, including backtracking.

Of course, there are other uses of reset/3 and shift/1, but the client-server paradigm helped me understand the “state monad” and DCGs using delimited continuations.

[*] Don’t worry about the term “monad”. After all, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor. :smiley:

1 Like
18

The technical report CW631 (https://www.cs.kuleuven.be/publicaties/rapporten/cw/CW631.pdf) has a number of examples (interators, generators, coroutines, transducers); I’ve updated them in this file:
nerdle/cw631.pl at f31b1d7dd32bc8bd67decb891614e19b77ab49ed · kamahen/nerdle · GitHub

20

There’s a comment at the beginning of my cw631.pl file that mentions these changes because of the change in delimited continuations since the CW631 was written:

  • reset/3 has different order of parameters and only sets Cont=0 (not Term)
  • call_continuation/1 not needed (call/1 can be used instead and in some cases it can be completely removed because the Cont can be given to reset/3 (previously call_continuation(Cont) was needed).

These have required changes to the code in the paper, which is why I’m publishing it – for example, in some cases, the original code implicitly checked for Term=0 and that needed to be changed to explicitly check for Cont==0