Shift vs Control difference - an example

Show & Tell
1

Hello,

I don’t know if this is well known or not, but after some reasoning I found an interesting example about the difference between shift and control.

I asked the AI to make an example about delimited continuations and the result is this:

#lang racket

(require racket/control)

(define (amb choices)
  (control cont
    (for-each (lambda (x) 
                (prompt (cont x)))
              choices)))

;; A helper to force backtracking
(define (backtrack) (abort 'fail))

(define (find-pair sum-target)
  (reset
   (let ([x (amb '(1 2 3 4 5 6))]
         [y (amb '(1 2 3 4 5 6))])
     (if (and (= (+ x y) sum-target))
         (display (list x y))
         (backtrack))))) ; Try the next combination

(find-pair 7)

=> (1 6)(2 5)(3 4)(4 3)(5 2)(6 1)

It uses control and abort to develop a backtrack algorithm.

Now let’s change control with shift (I didn’t change prompt with reset because they are interchangeable):

#lang racket

(require racket/control)

(define (amb choices)
  (shift cont
    (for-each (lambda (x) 
                (prompt (cont x)))
              choices)))

;; A helper to force backtracking
(define (backtrack) (abort 'fail))

(define (find-pair sum-target)
  (reset
   (let ([x (amb '(1 2 3 4 5 6))]
         [y (amb '(1 2 3 4 5 6))])
     (if (and (= (+ x y) sum-target))
         (display (list x y))
         (backtrack))))) ; Try the next combination

(find-pair 7)

=> (1 6)(2 5)(3 4)(4 3)(5 2)(6 1)

The result is the same, but what if I remove prompt?

Here I removed prompt from the control version:

#lang racket

(require racket/control)

(define (amb choices)
  (control cont
    (for-each (lambda (x) 
                (cont x))
              choices)))

;; A helper to force backtracking
(define (backtrack) (abort 'fail))

(define (find-pair sum-target)
  ...)

(find-pair 7)

=> 'fail

The result is a failure.

But if I remove prompt from the shift version:

#lang racket

(require racket/control)

(define (amb choices)
  (shift cont
    (for-each (lambda (x) 
                (cont x))
              choices)))

;; A helper to force backtracking
(define (backtrack) (abort 'fail))

(define (find-pair sum-target)
  ...)

(find-pair 7)

=> (1 6)(2 5)(3 4)(4 3)(5 2)(6 1)

It works, because shift adds a prompt when calls the continuation.

I managed to find a concise example:

#lang racket

(require racket/control)

(prompt (shift cont
          (+ (cont '())
             (cont '())
             (cont '())))
        (abort 1))

(prompt (control cont
                 (+ (cont '())
                    (cont '())
                    (cont '())))
        (abort 1))
          
(prompt (control cont
                 (+ (prompt (cont '()))
                    (prompt (cont '()))
                    (prompt (cont '()))))
        (abort 1))

=> 3
   1
   3

It's possible to use control and shift instead of abort:

#lang racket

(require racket/control)

(prompt (shift cont
          (+ (cont '())
             (cont '())
             (cont '())))
        (shift c 1))

(prompt (control cont
                 (+ (cont '())
                    (cont '())
                    (cont '())))
        (control c 1))
          
(prompt (control cont
                 (+ (prompt (cont '()))
                    (prompt (cont '()))
                    (prompt (cont '()))))
        (control c 1))

=> 3
   1
   3

But I think abort is clearer.

Shift is more elegant and concise, but perhaps control is more explicit and clear. It’s possible to use both, they work properly, It’s a matter of taste.

Matteo

1 Like
2

As you point out, shift sets up an internal prompt when it reifies the delimited continuation. Ergo it's not a matter of taste -- the two constructs have a different semantics.

One way to understand this is that control turns the delimited continuation into a plain function, assuming the language itself is functional. By contrast, shift adds the delimiter and hence its reified continuation is inherently effectful i.e. has an effect on continuation manipulations.

But yes, the two are close when it comes to pragmatics ("use in context") and you can often exchange one for the other.