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!