Continuations in Prolog
One of the concepts in programming that I found most challenging to learn is the “continuation”.
I was first introduced to the idea in Scheme, which features “first-class continuations”. These allow one to capture “what’s going to happen next” as a closure that can then be passed around. For purposes of example, we’ll look at delimited continuations, where we explicitly scope our continuation (both to be closer to Prolog and to hopefully make our examples a little easier to follow).
Here’s a somewhat silly example of using continuations to jump back into the middle of a function.
(use-modules (ice-9 control)) ;; for delimited continuations (define test-continuation #f) (define (test) (display "inside (test)\n") (reset ;; this establishes the bounds of the continuation (display "entering reset\n") (display (list "In test" (+ 1 (* 2 (shift ;; this grabs the "what's next" to do inside this reset ;; (i.e. finish computing (+ 1 (* 2 <something>)) ;; and then output the newline and "done") cont ;; and binds it to this variable ;; ...so here, `cont` is a closure that is essentially ;; (lambda (x) (display (+ 1 (* 2 x))) (newline) (display "done\n")) (begin (set! test-continuation cont) 0)))))) (newline) (display "done\n"))) (display "calling (test)\n") (test) (display "calling (test-continuation 2))\n") (test-continuation 2) (display "calling (test-continuation 4))\n") (test-continuation 4)
calling (test) inside (test) entering reset calling (test-continuation 2)) (In test 5) done calling (test-continuation 4)) (In test 9) done
Essentially, the continuation lets us do non-local control flow, somewhat like C’s setjmp
and longjmp
or Common Lisp’s condition system.
We can think of it as freezing the state of everything inside the reset
that hasn’t yet finished and saving it for later, in a way that lets us “fill in” the call to shift
with whatever we want and continue from there.
Prolog’s delimited continuations work very much the same way, except with logic variables as maybe an extra little wrinkle.
Let’s first try to emulate the Scheme example in Prolog:
test(Cont, Term) :- writeln("Inside test"), reset(test_, Term, Cont), writeln("After reset"). test_ :- writeln("Entering reset"), shift(Y), X is 1 + (2 * Y), format("In test X = ~w; done~n", [X]). ?- test(Cont, Term), % using double-negation so we can bind Term more than once \+ \+ ( writeln("calling Cont(2)"), Term = 2, call(Cont)), \+ \+ ( writeln("calling Cont(4)"), Term = 4, call(Cont)).
Inside test Entering reset After reset calling Cont(2) In test X = 5; done calling Cont(4) In test X = 9; done
Things are a little different in Prolog, since we’re dealing with predicates and binding logic variables instead of functions with return values, but in the same way reset
calls a goal, binding Cont
to a continuation that represents “everything after the call to shift
” and Term
to the argument passed to shift
.
Let’s look at a more realistic example of continuations, which actually inspired the writing of this post: Using continuations to implement DCGs:
% our version of =phrase=, implemented with continuations phrase_cc(Goal, Lin, Lout) :- reset(Goal, E, Cont), ( Cont == 0 % Cont = 0 mean no call to shift/1 inside =Goal= % .. so we're done; remaining input should equal output -> Lin = Lout % otherwise, whatever was shifted should match the % head of the input list... ; Lin = [E|Lmid], % ...and the rest of the "DCG" we're evaluating by % recursively calling =Cont=, which will continue the goal % where the last shift occured phrase_cc(Cont, Lmid, Lout) ). % "DCG" that matches =N= consecutive =[a, b]='s ab(0). ab(N) :- shift(a), shift(b), ab(M), N is M + 1. % equivalent to the above as a normal dcg ab_dcg(0) --> []. ab_dcg(N) --> [a], [b], ab_d(M), { N is M + 1 }. test(N) :- phrase_cc(ab(N), [a,b,a,b], []). ?- test(N), format("N = ~w~n", [N]).
N = 2
Here, we’re using continuations to make something like a generator, where the shift
is filling the role of yield
.
The phrase_cc
predicate uses reset
to call the passed-in Goal,
but pausing whenever it calls shift
and checking that whatever value was “yielded” through the shift matches the current input state.
I encourage the reader to grab the above code & try sprinkling some more format/2
’s in to get a good sense of what’s happening and hopefully get a better intuitive sense of how continuations work.
So, what is a continuation?
The way I usually think of them is as a closure that represents some code that’s paused at a certain point, waiting for a value.
The call to reset
delimits the area of the function that we want to capture and shift
pokes a hole in the function that we can “fill in” by passing in a value to the continuation.
In Prolog, since we’re using predicates instead of Scheme-like functions, we just separate calling the continuation and passing the value to shift; e.g., where in Scheme we’d write:
(use-modules (ice-9 control)) (define cont #f) (reset (display (list "number" (shift k (set! cont k)))) (newline)) (cont 1) (cont 2)
(number 1) (number 2)
in Prolog, we’d have to separate “passing the value in” (by unifying the variable that is passed to shift/1
) and resuming the continuation (by call/1
-ing the Cont
):
test :- shift(X), format("number ~w~n", [X]). ?- reset(test, Term, Cont), \+ \+ ( Term = 1, call(Cont) ), \+ \+ ( Term = 2, call(Cont) ).
number 1 number 2
Hopefully this makes continuations a little less mysterious; if something is still unclear, please let me know!