Current continuation at procedure begin

Question

Creating a return procedure is apparently a common example of what one can create with continuations as in the following example:

(define (find-multiple factor)
  (let/cc return
    (for ([num (shuffle (range 2000))])
      (when (zero? (modulo num factor))
        (return num)))))

(find-multiple 43)

(from https://beautifulracket.com/explainer/continuations.html#what-are-they-good-for)

While I sort of understand, that the continuation at the beginning is to return to where the procedure was called from some value, I don't know what the continuation actually looks like. In the following example I can imagine what it looks like:

(define c #f)
(+ 1 (+ 2 (+ 3 (+ (let/cc here (set! c here) 4) 5)))) ; 15
(c 20) ; 31

The continuation is:

(lambda (something)
  (+ 1 (+ 2 (+ 3 (+ something 5))))

So the expression got wrapped into a lambda and the let/cc was replaced with the input parameter of the lambda.

But with the return procedure, I don't know what the right way to think about it is and what the continuation actually looks like.

Sylwester Sylwester · Accepted Answer · 2017-12-30T01:47:11

First off let/cc is just syntax sugar for call/cc. These are equal:

(let/cc here 
  (set! c here) 4)

(call/cc 
 (lambda (here) 
   (set! c here) 4))

All code no matter how you write it will be run in a particular way and each operation will do one step and then call the continuation of the rest of the program. This:

(define c #f)
(+ 1 (+ 2 (+ 3 (+ (let/cc here (set! c here) 4) 5)))) ; 15
(c 20) ; 31

Turns into something like this:

((lambda (c k)
   (call/cc&
    (lambda (here k)
      (set! c here)
      (k 4))
    (lambda (v)
      (+& v 5 (lambda (a1)
                (+& 3 a1 (lambda (a2)
                           (+& 2 a2 (lambda (a3)
                                      (+& 1 a3 (lambda (a4)
                                                 (c 20 k))))))))))))
 #f values)

Now notice that the order here now is explicit and surprise the deepest expression is handled first because all the other ones depend on its value being computed first. Also notice that the continuation includes the call to (c 20), every time.

Here are the CPS versions of the used procedures:

(define (+& a b k)
  (k (+ a b)))

(define (call/cc& f k)
  (f (lambda (v ign-k) (k v)) k))

That last one is perhaps the most clear implementation of call/cc you've ever seen. While the one in your code seems mysterious since the code isn't in continuation passing style, after a Scheme system makes it CPS call/cc wouldn't even be considered a primitive.

For (find-multiple 43) the continuation is just the REPL displaying the result. If you had used it somewhere like (+ 1 (find-multiple 43)) then the continuation would be (lambda (v) (+& 1 v halt))

EDIT

A simpler example:

(let ((x (read)))
  (display 
   (call/cc 
    (lambda (return)
      (- 4 (if (< x 4) x (return 10))))))))

Now When you run this and you enter a value below 4 the call/cc part isn't used, but if it isn't notice that this happens at a time where the next thing it is supposed to do is substract it from 4. In CPS it looks like this:

(read&
 (lambda (x)
   (call/cc& 
    (lambda (return& k)
      (define (k- v)
        (-& 4 v k))
      (<& x 4 (lambda (p)
                (if p
                    (k- x)
                    (return& 10 k-)))))                          
    (lambda (v)
      (display& v values)))))

And again here are the &-procedures. These are probably starting to become familiar and hopefully predictable:

(define (<& a b k) (k (< a b)))
(define (-& a b k) (k (- a b)))
(define (display& v k) (k (display v)))
(define (read& k) (k (read)))

Current continuation at procedure begin

1 Answers