How is Prolog `shift`/`reset` like other languages?

user_257418 0
Viewed 202

I found an example of shift-reset delimited continuations in Haskell here:

resetT $ do
    alfa
    bravo
    x <- shiftT $ \esc -> do
       charlie
       lift $ esc 1
       delta
       lift $ esc 2
       return 0
    zulu x

This will:

  1. Perform alfa

  2. Perform bravo

  3. Perform charlie

  4. Bind x to 1, and thus perform zulu 1

  5. Fall off the end of resetT, and jump back to just after esc 1

  6. Perform delta

  7. Bind x to 2, and thus perform zulu 2

  8. Fall off the end of resetT, and jump back to just after esc 2

  9. Escape from the resetT, causing it to yield 0

I can't figure out how to write the equivalent code using SWI-Prolog's shift/1 and reset/3.

The code below is my attempt. The output is the same, but it seems messy and backwards, and I feel like I'm misusing Ball to get something similar to the esc 1 and esc 2 in the Haskell example. Also, I am not sure what to do with return 0.

% not sure about this...
example :-
  reset(step, ball(X), Cont),
  ( writeln("charlie"), X=1, call(Cont), fail
  ; writeln("delta"), X=2, call(Cont)).

step :-
  writeln("alfa"),
  writeln("bravo"),
  shift(ball(X)),
  format("zulu ~w~n", X).

I'm rather confused: Scheme/Haskell/ML-style shift-reset and Prolog shift-reset seem almost like entirely different things! For example, you pass a lambda into Haskell's shiftT but you do not pass a goal into Prolog's shift/1.

Where is the Prolog equivalent of Haskell's \esc -> ... esc 1 or return 0? And where is the Haskell equivalent of Prolog's Ball or call(Cont)?

I feel that a "proper" port of the Haskell example above would answer these questions.

delimited-continuations swi-prolog prolog continuations haskell
2 Answers

  1. The reset and shift operators originally come from Danvy; Filinski,1990. “Abstracting Control”. The corresponding interfaces in Haskell Control.Monad.Trans.Cont conform to the original semantics, except for some type restrictions. The delimited continuation interfaces in SWI-Prolog are not exactly the original reset and shift. They are more closely related to Felleisen,1988's prompt and control or Sitaram’s fcontrol and run operators.

  2. Usually, it is not difficult to translate delimited continuation programs from Haskell to Prolog. The difficulty in your example is that it calls the same continuation esc twice with different values. For example,

    example :-
  reset(step, ball(X), Cont),
  X=1, call(Cont),
  X=2, call(Cont).

    After the first call(Cont), X is already bound to 1, you cannot rebind it to 2.

    TomSchrijvers' advice is to create copies of the continuation with fresh unification variables using copy_term/2 (yes, continuations are also terms in SWI-Prolog!), so the Prolog equivalent of your example is

    example(X) :-
  reset(step, Ball, Cont),
  copy_term(Cont+Ball, Cont1+Ball1),
  copy_term(Cont+Ball, Cont2+Ball2),
  writeln("charlie"),
  ball(X1) = Ball1,
  X1=1, reset(Cont1, _, _),
  writeln("delta"),
  ball(X2) = Ball2,
  X2=2, reset(Cont2, _, _),
  X=0.  

step :-
  writeln("alfa"),
  writeln("bravo"),
  shift(ball(X)),
  format("zulu ~w~n", X),
  shift(ball(X)).

?- example(X).
alfa
bravo
charlie
zulu 1
delta
zulu 2
X = 0.

More detail discussion, see https://swi-prolog.discourse.group/t/naming-clarification-about-delimited-continuation-reset-3-and-shift-1

user_45184820

Pitty the CW631 paper here:
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW631.pdf

doesn’t show Felleisen prompt/control implemented with difference list rules:

/* Vanilla conjunction list solve/1 extended to control/3 */
control([], none, []).
control([prompt(A)|B], A, B).
control([control(L, P, Q)|B], X, Y) :- control(L, P, Q), control(B, X, Y).
control([A|B], X, Y) :- rule(A,C,B), control(C, X, Y).

Its quite fast, since it does nothing with the continuation, just takes it as is, which I suppose is the spirit of Felleisen. Here the good ole shift/reset:

/* SWI-Prolog 8.5.14 */
?- time(run_state(fib(25), 0, S)).
% 2,306,455 inferences, 0.453 CPU in 0.499 seconds (91% CPU, 5090108 Lips)
S = 121393 .

And here the prompt/control:

/* SWI-Prolog 8.5.14 */
?- time(control([run_state([fib(25)],0,S)],_,_)).
% 3,641,788 inferences, 0.891 CPU in 0.980 seconds (91% CPU, 4089025 Lips)
S = 121393 .

/* Jekejeke Prolog 1.5.4, only 512 MB allocated, JDK 16 */
?- time(control([run_state([fib(25)],0,S)],_,_)).
% Threads 1,656 ms, GC 404 ms, Up 2,086 ms (Current 08/23/22 04:19:56)
S = 121393

The test case is here:
http://www.rubycap.ch/gist/felleisen2.txt

user_175247900
Related