Continuation, as its name implies, means what follows from the current state. In the general case, a continuation could be influenced by the current state, so in order to model such “influence”, a continuation accepts an input, which denotes the explicit dependency. I will use two examples to illustrate how continuation is used in Racket.

§Component wise division

Given two equal-length lists, a and b, implement dot-divide-or-error, which calculates a./b or return the passed err-val if any component in b is 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
(trace-define (dot-divide-or-error numerators denominators err-val)
  (match `(,numerators . ,denominators)
    [`(() . ,_) '()]
    [`((,x . ,xs) . (,y . ,ys))
      (if (= 0 y)
        err-val
        (let ([ret (dot-divide-or-error xs ys err-val)])
          (begin
            (if (equal? ret err-val)
              err-val
              (cons (/ x y) ret))
            )))]
    [_ err-val]
    ))

(define (dot-divide-or-error-jump numerators denominators err-val)
  (let/ec k
          (trace-let dot-divide-or-error-jump#
            ([numerators numerators] [denominators denominators])
            (match `(,numerators . ,denominators)
              [`(() . ,_) '()]
              [`((,x . ,xs) . (,y . ,ys))
                (if (= 0 y)
                  (k err-val)
                  (cons (/ x y) (dot-divide-or-error-jump# xs ys)))]))))

(define (dot-divide-or-error-tail numerators denominators err-val)
  (trace-let dot-divide-or-error-tail#
    ([numerators numerators] [denominators denominators] [acc '()])
    (match `(,numerators . ,denominators)
      [`(() . ,_) (reverse acc)]
      [`((,x . ,xs) . (,y . ,ys))
        (if (= 0 y)
          err-val
          (dot-divide-or-error-tail# xs ys (cons (/ x y) acc)))])))

; example code
(displayln 'err-val)
(dot-divide-or-error (range 1 5) (append (range 1 4) '(0)) #f)
(dot-divide-or-error-jump (range 1 5) (append (range 1 4) '(0)) #f)
(dot-divide-or-error-tail (range 1 5) (append (range 1 4) '(0)) #f)

(displayln 'success)
(dot-divide-or-error (range 1 5) (append (range 2 6)) #f)
(dot-divide-or-error-jump (range 1 5) (append (range 2 6)) #f)
(dot-divide-or-error-tail (range 1 5) (append (range 2 6)) #f)

In the output, we can see that *-jump (continuation) and *-tail (tail call) versions immediately return on error, without going through the call stack. When no error occurs, the tail call version can still avoid going though the call stack on return.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
$ racket ex1.rkt
err-val
>(dot-divide-or-error '(1 2 3 4) '(1 2 3 0) #f)
> (dot-divide-or-error '(2 3 4) '(2 3 0) #f)
> >(dot-divide-or-error '(3 4) '(3 0) #f)
> > (dot-divide-or-error '(4) '(0) #f)
< < #f
< <#f
< #f
<#f
#f
>(dot-divide-or-error-jump# '(1 2 3 4) '(1 2 3 0))
> (dot-divide-or-error-jump# '(2 3 4) '(2 3 0))
> >(dot-divide-or-error-jump# '(3 4) '(3 0))
> > (dot-divide-or-error-jump# '(4) '(0))
#f
>(dot-divide-or-error-tail# '(1 2 3 4) '(1 2 3 0) '())
>(dot-divide-or-error-tail# '(2 3 4) '(2 3 0) '(1))
>(dot-divide-or-error-tail# '(3 4) '(3 0) '(1 1))
>(dot-divide-or-error-tail# '(4) '(0) '(1 1 1))
<#f
#f
success
>(dot-divide-or-error '(1 2 3 4) '(2 3 4 5) #f)
> (dot-divide-or-error '(2 3 4) '(3 4 5) #f)
> >(dot-divide-or-error '(3 4) '(4 5) #f)
> > (dot-divide-or-error '(4) '(5) #f)
> > >(dot-divide-or-error '() '() #f)
< < <'()
< < '(4/5)
< <'(3/4 4/5)
< '(2/3 3/4 4/5)
<'(1/2 2/3 3/4 4/5)
'(1/2 2/3 3/4 4/5)
>(dot-divide-or-error-jump# '(1 2 3 4) '(2 3 4 5))
> (dot-divide-or-error-jump# '(2 3 4) '(3 4 5))
> >(dot-divide-or-error-jump# '(3 4) '(4 5))
> > (dot-divide-or-error-jump# '(4) '(5))
> > >(dot-divide-or-error-jump# '() '())
< < <'()
< < '(4/5)
< <'(3/4 4/5)
< '(2/3 3/4 4/5)
<'(1/2 2/3 3/4 4/5)
'(1/2 2/3 3/4 4/5)
>(dot-divide-or-error-tail# '(1 2 3 4) '(2 3 4 5) '())
>(dot-divide-or-error-tail# '(2 3 4) '(3 4 5) '(1/2))
>(dot-divide-or-error-tail# '(3 4) '(4 5) '(2/3 1/2))
>(dot-divide-or-error-tail# '(4) '(5) '(3/4 2/3 1/2))
>(dot-divide-or-error-tail# '() '() '(4/5 3/4 2/3 1/2))
<'(1/2 2/3 3/4 4/5)
'(1/2 2/3 3/4 4/5)

§Iterating a list

Find the first element that satisfies a predicate in a list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
(define (my-pred x) (> x 3))

(define (find-rec pred l)
  (match l
    [`() #f]
    [`(,x . ,xs) (if (pred x)
                   x
                   (find-rec pred xs))]))

(define (find-rec-jump pred l)
  (let/ec k
          (let find-jump# ([l l])
            (match l
              [`() #f]
              [`(,x . ,xs) (if (pred x)
                             (k x)
                             (find-jump# xs))]))))

(define (my-foldl f acc l)
  (match l
    [`() acc]
    [`(,x . ,xs) (my-foldl f (f x acc) xs)]))

(define (find-via-fold pred l)
  (define found #f)
  (my-foldl (lambda (x acc)
              (cond
                [found acc]
                [(pred x) (begin
                            (set! found #t)
                            x)]
                [else acc]))
            #f
            l))

(define (find-via-fold-jump pred l)
  (let/ec k
          (my-foldl (lambda (x _)
                      (if (pred x)
                        (k x)
                        #f))
                    #f
                    l)))

; benchmarking code
(for ([high (map (lambda (x) (* 2 x)) (range 1 3))])
  (let* ([len (* high 1000 1000)]
         [list (range 1 len)])
    (begin
      (printf "list-len = ~a~n" len)
      (time (find-rec my-pred list))
      (time (find-rec-jump my-pred list))
      (time (find-via-fold my-pred list))
      (time (find-via-fold-jump my-pred list))
      )))

In the output, we can see that continuation provides a way for “early return” inside a fold.

1
2
3
4
5
6
7
8
9
10
11
$ racket ex2.rkt
list-len = 2000000
cpu time: 0 real time: 1 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 32 real time: 32 gc time: 0
cpu time: 0 real time: 0 gc time: 0
list-len = 4000000
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 61 real time: 61 gc time: 0
cpu time: 0 real time: 0 gc time: 0