# DCGs implemented with delimited continuations **URL:** \ **Category:** Help!\ **Created:** [February 26, 2020, 5:03am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921 "2020-02-26T05:03:12Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [February 26, 2020, 5:03am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/1 "2020-02-26T05:03:12Z")
I tried the DCG example in [https://www.swi-prolog.org/download/publications/iclp2013.pdf](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](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: ```prolog ?- listing(main). main :- reset(p, _, X), writeln(X), writeln(c). ?- listing(p). p :- writeln(a), shift(hello), writeln(b). ?- main. a call_continuation([$cont$((0x7fffdbfe62c0),9)]) c ``` but the talk says the output should be: ```prolog a hello c ``` Also, the DCG example in the paper fails when I try running it (I’m using `ph` because `phrase` is builtin): ```prolog 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], []). ``` ---
**Author:** ![CapelliC](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/capellic/32/17_2.png) [@CapelliC](https://swi-prolog.discourse.group/u/CapelliC)\ **Post date:** [February 26, 2020, 7:56am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/2 "2020-02-26T07:56:28Z")
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)`. ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [February 27, 2020, 7:18pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/3 "2020-02-27T19:18:48Z")
Just a side note, I don’t know what your use case is, but you may be able to use the new [intercept library](https://www.swi-prolog.org/pldoc/man?section=intercept) to achieve your goal. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [February 28, 2020, 6:53pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/4 "2020-02-28T18:53:02Z")
> [@CapelliC](#): > > Seems that 2nd and 3th arguments have been swapped 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.) ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [February 28, 2020, 7:18pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/5 "2020-02-28T19:18:06Z")
> [@peter.ludemann](#): > > 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.) When you get to “ah-ha!” you should write it up for others to read. 🙂 ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [March 5, 2020, 6:50pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/6 "2020-03-05T18:50:56Z")
> [@EricGT](#): > > When you get to “ah-ha!” you should write it up for others to read. 🙂 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. 🙂_ > [Continuation - Wikipedia](https://en.wikipedia.org/wiki/Continuation#First-class_continuations) ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [March 5, 2020, 7:03pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/7 "2020-03-05T19:03:24Z")
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. 🙂 ---
**Author:** ![jamesnvc](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jamesnvc/32/14_2.png) [@jamesnvc](https://swi-prolog.discourse.group/u/jamesnvc)\ **Post date:** [March 5, 2020, 9:53pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/8 "2020-03-05T21:53:03Z")
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… ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [March 6, 2020, 8:15am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/9 "2020-03-06T08:15:46Z")
> [@jamesnvc](#): > > a closure that represents “what was about to happen” 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](https://www.swi-prolog.org/pldoc/man?section=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. ---
**Author:** ![jamesnvc](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jamesnvc/32/14_2.png) [@jamesnvc](https://swi-prolog.discourse.group/u/jamesnvc)\ **Post date:** [March 6, 2020, 1:13pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/10 "2020-03-06T13:13:51Z")
Thanks Jan! I also tried [writing an explainer](https://occasionallycogent.com/continuations_in_prolog/index.html) after playing around with continuations a bit last night; hopefully that isn’t too incorrect/makes some sense. ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [March 6, 2020, 1:21pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/11 "2020-03-06T13:21:44Z")
[writing an explainer](https://occasionallycogent.com/continuations_in_prolog/index.html) 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. 🙂 Would also make for a nice exercise in an advance programming class. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [March 9, 2020, 11:32pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/12 "2020-03-09T23:32:57Z")
Does anyone know why the operations are called `shift` and `reset`? According to [Wikipedia](https://en.wikipedia.org/wiki/Delimited_continuation), these names come from the paper [Olivier Danvy; Andrzej Filinski (1990). “Abstracting Control”](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.960&rep=rep1&type=pdf), 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](https://www.swi-prolog.org/pldoc/doc_for?object=call/1) doesn’t mention continuations.) ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [March 10, 2020, 9:50am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/13 "2020-03-10T09:50:08Z")
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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [March 10, 2020, 10:51am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/14 "2020-03-10T10:51:16Z")
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: ```prolog :- 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: ```prolog 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. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [August 19, 2022, 7:39pm UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/15 "2022-08-19T19:39:34Z")
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: ```prolog %! 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. ```prolog %! 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: ```prolog %! 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”: ```prolog 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))`: ```prolog ?- 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. 😃 ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [August 23, 2022, 12:39am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/18 "2022-08-23T00:39:59Z")
The technical report CW631 ([https://www.cs.kuleuven.be/publicaties/rapporten/cw/CW631.pdf](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](https://github.com/kamahen/nerdle/blob/f31b1d7dd32bc8bd67decb891614e19b77ab49ed/cw631.pl) ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [August 23, 2022, 1:46am UTC](https://swi-prolog.discourse.group/t/dcgs-implemented-with-delimited-continuations/1921/20 "2022-08-23T01:46:18Z")
> [@anon95304481](#): > > Strictly speaking [SWI-Prolog](https://www.swi-prolog.org/pldoc/doc_for?object=manual) doesn’t implement the proposal of this paper, > since it has made a small modification. 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`