Playing with Prolog - Continuations
Channel: Playing With Prolog
Date: 2017-02-27

This week we look at delimited continuations in SWI-Prolog.

Schrijvers, Demoen, Desouter, & Wielemaker, Delimited Continuations in Prolog  http://www.swi-prolog.org/download/publications/iclp2013.pdf

Very useful powerpoint by Tom Schrijvers on Delimited Continuations
http://www-ps.informatik.uni-kiel.de/kdpd2013/talks/schrijvers.pdf

A pack for playing with continuations:
http://www.swi-prolog.org/pack/file_details/cclab/README

The basic code
% example continuation that yields to caller

main :-
 farkle(foo).

farkle(Goal) :-
 writeln(Goal),
 reset(Goal, Ball, Continuation),
 writeln(Ball),
 (  Continuation = 0
 -+  true  % that plus sign is angle bracket (youtube rstriction)
 ;  farkle(Continuation)
 ).

foo :-
 between(1,5,N),
 shift(N),
 fail.
foo.

The backtrack code
back :-
 reset(p, _, Cont),
 writeln(c),
 call(Cont).
p :-
 shift(_),
 writeln(a).
p :-
 shift(_),
 writeln(b).

After we published this video, Sameer Abdallah posted this enlightening post on the SWI-Prolog mail list. Reproduced with his permission

Hi Anne and Sam,

Thanks for the video! It’s great that you are making efforts to introduce this very
powerful mechanism to more programmers. I would just like to add that the pack
‘cclab’  contains many examples of using delimited continuations in a
range of simple and complex ways. It especially shows how you can use nested
delimited contexts to combine computational effects (e.g. state, tabling, probabilistic
choice etc) — this relies on two predicates p_reset/3 and p_shift/2 which are built
on top of reset/3 and shift/1 and provide a concept of multiple prompts.
You note that capturing continuations is currently quite expensive - my hope is that
with more widespread use, there will be an incentive to improve the performance
of multi-prompt delimited control.

Another point of interest in your video is where Sam asks whether or not reset and
shift can be considered declarative. This is an interesting question - in functional
programming, delimited continuations allow you to implement computational effects
that don’t look purely functional, such as mutable state or nondeterminism. However,
the point is that the enclosing context (the reset) wraps and transforms the computation
inside into a pure functional value - for example, a stateful computation with set and
get is transformed into a pure value: a function mapping an input state to a result
and an output state. Similarly, a nondeterministic computation can be transformed
into a list or tree of results. The same is true of using delimited continuations to
implement state in Prolog (e.g. ccstate.pl in cclab) - the computation eventually appears
as a predicate relating input and output states in a pure declarative way. So I
think shift and reset can be used to implement computational effects in a way that
can be considered ‘declarative’. Compare this with the use of monads in Haskell:
monadic code ‘looks’ imperative, but the point is that it has a declarative reading:
it represents, is a pure functional value, and it can be reasoned about as such. With all
these mechanisms, the benefit is that the apparent ‘impurity’ is limited and carefully
controlled.

And then later pointed out that,  before calling a continuation multiple times, you should copy it:



If you want to call a continuation multiple times, the classic case being to implement
nondeterministic or probabilistic choice, then you have to copy it before calling it to
avoid binding any variables in the original. Otherwise, the although first call would
work, the second might not - it would find that things that were expected to be variables
have become ground values that might contradict the intended execution.

For example, suppose you want to model a probabilistic choice like this:

dist(Dist, X) :- shift(dist(Dist,X)).
flip :- dist([0.5-head, 0.5-tail], X), writeln(X).

The shift captures the continuation, along with its ‘interface’ variable X, so you
have a pair X-Cont. You then set X and call Cont:
    X=head, call(Cont).
You then want to see what happens if you call Cont with tails instead, but without
backtracking (eg to build a search tree) or a list of all possible results. You can’t do it -
    X=tail, call(Cont)
fails because X (which is also embedded in Cont) is alread bound to head.
Instead, you need to copy Cont and X like this:
    copy_term(X-Cont, X1-Cont1), X1=head, call(Cont1),
    copy_term(X-Cont, X2-Cont2), X2=tail, call(Cont2)
Luckily, lambda abstractions capture this pattern perfectly: using library(lambda),
    call(\X^Cont, head),
    call(\X^Cont, tail)
The lambda abstraction turns a raw continuation and its interface variables into
a bona-fide predicate that be handled as an immutable declarative value. The same
idea can be used to deal with variables in the continuation that represent an *output*
of the continuation.