Naming clarification about delimited continuation (reset/3 and shift/1)

SWI-Prolog provides two predicates reset/3 and shift/1 to implement delimited continuations. These two predicates are described in Schrijvers et al., 2013 (preprint PDF), which is a very nice paper. However, the names seems a bit confused. I will explain below.

The reset and shift operators originally come from Danvy; Filinski,1990. “Abstracting Control”. In that paper, the authors claim that

Shift abstracts the current context as an ordinary, composable procedure and reset delimits the scope of such a context.

This means that the continuation captured by shift is like a “total function”, i.e. it always returns normally. But this is not the case in SWI-Prolog.

For example,

?- reset((
          format("111~n"),
          shift(1),
          format("222~n"),
          shift(2),
          format("333~n") 
         ),
         Term1, Cont1),
   format("444~n"),
   call(Cont1),
   format("555~n").
111
444
222
ERROR: reset `2' does not exist (No matching reset/3 call)

The ERROR tells us that Cont1 is not “total”, because there is no reset/3 as a delimiter inside Cont1. A workaround is manually wrapping a reset/3 around the continuation applications:

?- reset((
          format("111~n"),
          shift(1),
          format("222~n"),
          shift(2),
          format("333~n") 
         ),
         Term1, Cont1),
   format("444~n"),
   reset(call(Cont1), Term2, Cont2), % wrap a reset/3
   format("555~n").
111
444
222
555

This works. To obtain the original semantics of reset/shift, we can always do this, but still be careful with the semantics differences. In fact, the reset/3 and shift/1 in SWI-Prolog is more like the prompt and control in Felleisen,1988. The Theory and Practice of First-Class Prompts. The Racket reference demonstrates the differences.

(reset val) => val
(reset E[(shift k expr)]) => (reset ((lambda (k) expr)
                                     (lambda (v) (reset E[v]))))
  ; where E has no reset

vs.

(prompt val) => val
(prompt E[(control k expr)]) => (prompt ((lambda (k) expr)
                                         (lambda (v) E[v])))
  ; where E has no prompt

Note that, in the reset/shift case, there is a reset in the captured continuation (but SWI-Prolog no this stuff).

Below is a more complicated example to compare the differences:

  1. Prompt and control semantics:

    SWI-Prolog version:

    P.s. SWI-Prolog’s reset/3 and shift/1 is exactly prompt and control in Racket.

    :- dynamic save1/1.
    
    ?- reset((
              format("111~n"),
              shift(1),
              format("222~n"),
              shift(2),
              format("333~n") 
             ),
             Term1,Cont1),
       format("444~n"),
       assertz(save1(Cont1)).
    111
    444
    
    ?- save1(Cont1),
       reset((
              format("555~n"),
              call(Cont1),
              format("666~n")
             ),
             Term2, Cont2),
       format("777~n").
    555
    222
    777
    

    Note that the format("666~n") is not called, so Cont1 is not “total”.

    Racket version:

    > (define save1 null)
    
    > (match-let ([(cons v cont) (prompt (begin
                         (printf "111\n")
                         (control k (cons 1 k))
                         (printf "222\n")
                         (control k (cons 2 k))
                         (printf "333\n")
                         (cons '_ 0)
                         ))])
        (printf "444\n")
        (set! save1 cont))
    111
    444
    
    > (match-let ([(cons v cont) (prompt (begin
                         (printf "555\n")
                         (save1 '_)
                         (printf "666\n")
                         (cons '_ 0)
                         ))])
        (printf "777\n"))
    555
    222
    777
    
  2. Reset and shift semantics:

    SWI-Prolog version:

    P.s. Must wrap a reset/3 around the call(Cont1).

    ?- reset((
              format("111~n"),
              shift(1),
              format("222~n"),
              shift(2),
              format("333~n") 
             ),
             Term1,Cont1),
       format("444~n"),
       assertz(save1(Cont1)).
    111
    444
    
    ?- save1(Cont1),
       reset((
              format("555~n"),
              reset(call(Cont1), _, _),
              format("666~n")
             ),
             Term2, Cont2),
       format("777~n").
    555
    222
    666
    777
    

    Now the format("666~n") is called.

    Racket version:

    > (define save1 null)
    
    > (match-let ([(cons v cont) (reset (begin
                           (printf "111\n")
                           (shift k (cons 1 k))
                           (printf "222\n")
                           (shift k (cons 2 k))
                           (printf "333\n")
                           (cons '_ 0)
                           ))])
        (printf "444\n")
        (set! save1 cont))
    111
    444
    
    > (match-let ([(cons v cont) (reset (begin
                           (printf "555\n")
                           (save1 '_)
                           (printf "666\n")
                           (cons '_ 0)
                           ))])
        (printf "777\n"))
    555
    222
    666
    777
    

Therefore, the conclusion is that the reset/3 and shift/1 in SWI-Prolog is exactly prompt and control of Felleisen,1988.

Some useful quotes from Abstracting Control:

While the effects of these operators are very similar to operators control and prompt of [Felleisen 88], there is a significant semantical difference between shift/reset and control/prompt: the context abstracted by shift is determined statically by the program text, while control captures the context up to the nearest dynamically enclosing prompt. In general, this leads to different behavior.

The operator control is often referred to as Felleisen & Friedman’s Ƒ operator. Its operational definition leaves some room for variation, and one restricted form, also known as Ƒ-, is characterized by wrapping a prompt around all continuation applications. The effect is to close the extent of a context at the point of abstraction, instead of joining it to the context at the point of application. This is very much like building an explicit closure with FUNCTION around a LAMBDA in Lisp 1.5, which experience has shown to be preferable in general for both theoretical and practical reasons, leading to lexically scoped procedures in Scheme. In fact, Ƒ- coincides operationally with shift_1 for the simple case of one delimited context, just like static and dynamic scoping agree when the latter is used in a controlled way.

It seems that prompt and control can always simulate reset and shift, but not vice versa. SWI-Prolog’s delimited continuation is essentially prompt and control, that is nice. Perhaps prompt/3 and control/1 are more suitable names for delimited continuations in SWI-Prolog? Just for discussion.

2 Likes

Although I use reset/shift in my zdd library only as useful primitives for DCG like programming to hide computation states, I have little backgounds knowledge on the reset/shift, which is I feel shameful. Such said, I have some question and request on the current shift/reset of SWI-Prolog.

The swi reset may return 0 as the third argument, but
0 is not callable.

?- reset(true, A, X), reset(X, B, Y).
ERROR: Type error: callable' expected, found 0’ (an integer)
ERROR: In:
ERROR: [11] reset(user:0,_12328,_12330)
ERROR: [9] toplevel_call(user:user: …) at

So I needed a small interpreter to treat such 0 as true to continue. I could not find a reason why that 0 is replaced with true, which programming is easier including debugging.

My small experience might not be related to your post, but I am interested in reset/shift-like controls for programming to hide complex computation state like monad, though I am not familiar with monad so much.

Yes, reset/3 returns 0 as the third argument means that the Goal exit normally without calling shift/1.

I think it is reasonable, because it expresses there is no continuation instead of there is the continuation that includes a simple goal true. I always do some if-the-else test the Cont argument after calling reset/3.

Schrijvers et al., 2013:

Shift-less resets and reset-less shifts In hProlog, we have chosen to unify the Cont and Term arguments of reset/3 with zero in the absence of shift, and to have the toplevel catch shifts outside of a reset. Alternative semantics are easy to implement as a variation on the basic schema.

1 Like

My usage of reset/shift might be no more than a substitution of b_setval/b_getval, which may be only one of the aspects of original shift/reset. Thanks for the information.

Dear @chansey97, I am sorry for the confusion. You are right that the operators do not correspond to the traditional shift and reset operators in the literature.

I was not aware of the range of different operators at the time of choosing the names. Later, in my PPDP 2014 paper Heuristics Entwined with Handlers Combined I did indicate that the interface is closer to the fcontrol and run operators of Sitaram as presented in

D. Sitaram. Handling control. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, PLDI ’93, pages 147–155, New York, NY, USA, 1993. ACM. ISBN 0-89791-598-4. . URL http://doi.acm.org/10.1145/155090.155104.

Which do you think is closer to SWI-Prolog’s interface: prompt/control or fcontrol/run?

Best,

Tom

3 Likes

Dear @TomSchrijvers, I didn’t know fcontrol/run before, thanks for telling me this operator. I just found that Racket has its implementation, which is called % and fcontrol.

The essential reduction rules are:

(% val proc) => val
(% E[(fcontrol val)] proc) => (proc val (lambda (x) E[x]))
; where E has no %

Yes. I think the %/fcontrol is closer to the current SWI-Prolog’s interface than prompt/control, because (fcontrol v #:tag prompt-tag) only requires one argument, ignore #:tag for now, which is more like shift/1 in SWI-Prolog, whereas (control id expr ...+) requires id.

In addition, % requires handler-expr, which can avoid Cont==0 and make the code shape more like catch/throw, but I have no idea if it would make the programs more readable…

P.s. I haven’t read that paper yet, so this is just a quick answer.