CS 2500 Honors Lab 12: Control

Goal: Abstracting Control

The purpose of this lab is to introduce you to the control operator call-with-current-continuation, or call/cc for short. Control operators allow the programmer to manipulate the evaluation of a program as it executes—many consider them difficult to understand and tricky to use! To try to overcome this difficulty, we will spend the majority of the lab discussing the notion of "control" and getting comfortable with the control operators abort and call/cc. At the end of the lab we will apply call/cc to implement exception handling in Racket.

1. What is Control?

Consider the following dumb computation:

  (product (list 5 8 1 0 2 9 3))
= (* 5 (product (list 8 1 0 2 9 3)))
= (* 5 (* 8 (product (list 1 0 2 9 3))))
= (* 5 (* 8 (* 1 (product (list 0 2 9 3)))))
= (* 5 (* 8 (* 1 (* 0 (product (list 2 9 3))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 (product (list 9 3)))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 (product (list 3))))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 (* 3 (product empty))))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 (* 3 1)))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 3))))))
= (* 5 (* 8 (* 1 (* 0 (* 2 27)))))
= (* 5 (* 8 (* 1 (* 0 54))))
= (* 5 (* 8 (* 1 0)))
= (* 5 (* 8 0))
= (* 5 0)
= 0

After product sees 0 it continues to compute (product (list 2 9 3)), even though it could predict the result of this part of the computation:

(* 0 (product (list 2 9 3))) = 0

We could avoid some work in this case by skipping the rest of the computation if an element in the list is 0. To do this, we could refine the implementation from this…

(define (product ns)
  (cond
    [(empty? ns) 1]
    [else        (* (first ns) (product (rest ns)))]))

…to this:

(define (product ns)
  (cond
    [(empty? ns)      1]
    [(= 0 (first ns)) 0]
    [else             (* (first ns) (product (rest ns)))]))

Now the computation is less dumb since it avoids computing (product (list 2 9 3)):

  (product (list 5 8 1 0 2 9 3))
= (* 5 (product (list 8 1 0 2 9 3)))
= (* 5 (* 8 (product (list 1 0 2 9 3))))
= (* 5 (* 8 (* 1 (product (list 0 2 9 3)))))
= (* 5 (* 8 (* 1 0)))
= (* 5 (* 8 0))
= (* 5 0)
= 0

But wouldn't it be nice if it also avoided computing every step of (* 5 (* 8 (* 1 0))) and instead replaced the whole thing with 0?

  (product (list 5 8 1 0 2 9 3))
= (* 5 (product (list 8 1 0 2 9 3)))
= (* 5 (* 8 (product (list 1 0 2 9 3))))
= (* 5 (* 8 (* 1 (product (list 0 2 9 3)))))
= (* 5 (* 8 (* 1 (STOP!-THE-ANSWER-IS 0))))
= 0

If we had an operator like STOP!-THE-ANSWER-IS then we could refine our implementation of product once more to avoid computing any of the multiplications by 0:

(define (product ns)
  (cond
    [(empty? ns)      1]
    [(= 0 (first ns)) (STOP!-THE-ANSWER-IS 0)]
    [else             (* (first ns) (product (rest ns)))]))

But how can we get an operator like STOP!-THE-ANSWER-IS? The closest thing we have is error, but it signals an error to the user whereas we just want to return a normal value.

The problem is that Racket has a strict idea about how a program is evaluated, which prevents us from defining an operator like STOP!-THE-ANSWER-IS. That is, Racket has a strict notion of the control of a program. What we lack is a way to influence this control.

2. Aborting Control

Here's an easy way out of our problem: I will simply give you STOP!-THE-ANSWER-IS, and I will call it abort. Since it manipulates the control of the remainder of the program's evaluation we'll call it a control operator.

The operator abort behaves just as we wanted above: Racket will evaluate your program as normal, except if it ever needs to evaluate a part that says (abort val), then Racket will replace the whole program with val. Consider some examples:

1. Plan to do some arithmetic but decide partway through that you're finished:

   
     (* 2 (+ 1 (abort (* 5 (- 6 2)))))
   = (* 2 (+ 1 (abort (* 5 4))))
   = (* 2 (+ 1 (abort 20)))
   = 20
   

   Notice that abort has no effect until its argument evaluates to a value.

2. Choose one of two functions to apply while building a string:

   
     (string-append "Your total is: $"
                    ((first (list (λ (n) (abort "Hi Mom!"))
                                  number->string))
                     80))
   = (string-append "Your total is: $"
                    ((λ (n) (abort "Hi Mom!"))
                     80))
   = (string-append "Your total is: $"
                    (abort "Hi Mom!"))
   = "Hi Mom!"
   

   Even if abort's argument doesn't need to evaluate, it still has no effect until control reaches it.

3. Choose the other function instead:

   
     (string-append "Your total is: $"
                    ((second (list (λ (n) (abort "Hi Mom!"))
                                   number->string))
                     80))
   = (string-append "Your total is: $"
                    (number->string
                     80))
   = (string-append "Your total is: $"
                    "80")
   = "Your total is: $80"
   

   Since we never needed to evaluate (abort "Hi Mom!"), control of the program proceeded normally.

4. Apply each function in a list to the number 3:

   
     (map (λ (f) (f 3)) (list add1 sqr number->string abort odd?))
   = (cons (add1 3)
           (map (λ (f) (f 3)) (list sqr number->string abort odd?)))
   = (cons 4
           (map (λ (f) (f 3)) (list sqr number->string abort odd?)))
   = (cons 4 (cons (sqr 3)
                   (map (λ (f) (f 3)) (list number->string abort odd?))))
   = (cons 4 (cons 9
                   (map (λ (f) (f 3)) (list number->string abort odd?))))
   = (cons 4 (cons 9 (cons (number->string 3)
                           (map (λ (f) (f 3)) (list abort odd?)))))
   = (cons 4 (cons 9 (cons "3"
                           (map (λ (f) (f 3)) (list abort odd?)))))
   = (cons 4 (cons 9 (cons "3" (cons (abort 3)
                                     (map (λ (f) (f 3)) (list odd?))))))
   = 3
   

   Here we see that we can pass abort around just like any other function.

(+ 1 (abort 2))

(+ 1 (abort ((λ (x y) (+ (add1 x) (sub1 y))) 2 3)))

(+ 1 (abort (λ (x y) (+ (add1 x) (sub1 y)))))

(local [(define (loop x)
          (loop x))]
  (loop (abort "Hello, World!")))

(local [(define (loop x)
          (loop x))]
  (abort (loop "Hello, World!")))

abort

(abort abort)

(map abort (list 1 2 3))

(map (λ (x) x) (list add1 abort (λ (x) (+ x x))))

Recall our original problem: we wanted to implement product so that it short-circuited if it encountered a 0. Using abort, now we can:

(define (product ns)
  (cond
    [(empty? ns)      1]
    [(= 0 (first ns)) (abort 0)]
    [else             (* (first ns) (product (rest ns)))]))

This appears to solve our problem, but what if product is part of some larger computation?

  (+ 1 (product (list 5 8 1 0 2 9 3)))
= (+ 1 (* 5 (* 8 (* 1 (abort 0)))))
= 0

The computation waiting for product to finish is lost and replaced with 0… What if this computation is computing the new balance in my bank account and product is only supposed to compute the amount to withdraw?

  (- old-balance (product (list 5 8 1 0 2 9 3)))
= (- old-balance (* 5 (* 8 (* 1 (abort 0)))))
= 0

You might be impressed with your faster implementation of product, but I certainly won't be impressed with my new balance…

3. Controlling Control

Aborting a computation is somewhat handy, but it's too global—it affects the entire computation. What we want is something that enables us to manipulate control more locally so that we can grab control at one point in the program and then jump back to it sometime later.

In our example

(- old-balance (product (list 5 8 1 0 2 9 3)))

what we want is a way to grab the remainder of the computation, (- old-balance •), before we start to compute (product (list 5 8 1 0 2 9 3)). This way, when we see the 0 we don't abort the whole computation with 0, but instead we only abort the computation between 0 and (- old-balance •).

  (- old-balance (product (list 5 8 1 0 2 9 3)))
= (- old-balance (WHERE-AM-I? (λ (GO-BACK) (product-helper GO-BACK (list 5 8 1 0 2 9 3)))))
  ; GO-BACK = (λ (x) (abort (- old-balance x)))
= (- old-balance (product-helper GO-BACK (list 5 8 1 0 2 9 3)))
= (- old-balance (* 5 (product-helper GO-BACK (list 8 1 0 2 9 3))))
= (- old-balance (* 5 (* 8 (product-helper GO-BACK (list 1 0 2 9 3)))))
= (- old-balance (* 5 (* 8 (* 1 (product-helper GO-BACK (list 0 2 9 3))))))
= (- old-balance (* 5 (* 8 (* 1 (GO-BACK 0)))))
= (- old-balance (* 5 (* 8 (* 1 ((λ (x) (abort (- old-balance x))) 0)))))
= (- old-balance (* 5 (* 8 (* 1 (abort (- old-balance 0))))))
= (- old-balance 0)
= old-balance

Here we're pretending that we have an operator WHERE-AM-I? that grabs the rest of the computation (- old-balance •), adds an abort, turns it into a λ, and then passes it into our own function so that GO-BACK = (λ (x) (abort (- old-balance x))). We then carry GO-BACK along as we compute the product so that when we encounter 0 we can call (GO-BACK 0) to locally abort the product computation and jump straight to (- old-balance 0).

Enough pretending—I'll give you this control operator too.

How does it behave? It grabs the rest of the computation, turns it into an aborting λ, and hands it to the function you supply. Your function can then do whatever it wants with it. If it calls it with argument val, the computation will jump back to the captured point, filling the hole with val. If it doesn't call it, life proceeds as usual.

If we call the rest of the computation at some point in the program the current continuation, then a good name for this operator is call-with-current-continuation. That's a mouthful, so let's also abbreviate it as call/cc. Since we're about to start carrying around lots of continuations we should pick a good name for them: k is conventional, just like n for integers or s for strings.

(+ 1 (call/cc (λ (k) (k 3))))

(+ 1 (call/cc (λ (k) (* 2 (k 3)))))

(+ 1 (call/cc (λ (k) (* 2 3))))

(call/cc (λ (k) (* 2 (k 3))))

((call/cc (λ (k) +)) 2 3)

((call/cc (λ (k) (k +))) 2 3)

((call/cc (λ (k) (+ 1 (k +)))) 2 3)

4. Laws of Control

Now that you have a feel for call/cc and abort, let me show you a very concise and very precise way to describe their behavior. Think of these like laws of physics—very small, very dense, and containing all the information you need. Much staring required.

To illustrate what a law looks like in Racket, let's first look at a law that describes behavior we're already comfortable with: the law of λ. It says that if you apply a λ to a value then it plugs that value into its body:

((λ (x) exp) val) = replace x with val in exp

It's important that val is a value: if we apply (λ (x) exp) to some expression exp2 that isn't yet evaluated, then ((λ (x) exp) exp2) must first evaluate exp2 to a value val before it can apply the above law.

So a law is just an equation between two expressions that we read left to right: when you see the thing on the left, replace it with the thing on the right. What then should be the laws for call/cc and abort?

(abort val) = …
(call/cc val) = …

Whereas the law of λ didn't care where in the program the application occurred, laws for control operators need to know their context because it determines their current continuation. What we want is something like

C[(abort val)] = …
C[(call/cc val)] = …

where the context C represents a program with a hole in it, and C[exp] is the same with exp plugged in the hole. Given this, the law for abort now seems clear: throw away the context and replace the whole program with the given value.

C[(abort val)] = val

But this law gets us in trouble. It says that this computation should happen:

  (if (even? 0) 42 (+ 1 (abort -1)))
= -1

What happened? C = (if (even? 0) 42 (+ 1 •)) is certainly a legal context… The problem is that our law evaluates (abort val) anywhere in the program at any time, but we meant for it to evaluate (abort val) only when it's the current expression being evaluated. What we wanted was:

  (if (even? 0) 42 (+ 1 (abort -1)))
= (if true 42 (+ 1 (abort -1)))
= 42

We want the above law to apply only when (abort val) is the current expression to evaluate. So let's only talk about contexts where the hole is the current expression. We will call these the evaluation contexts and write them as E. Our laws now look like this:

E[(abort val)] = val
E[(call/cc val)] = …

This properly captures the behavior of abort: if you encounter (abort val) while evaluating a program, throw away the rest of the program and replace all of E[(abort val)] with just val. This rules out the bad computation above and enables the good one.

What about the law for call/cc?

E[(call/cc val)] = …

Above we said that (call/cc val) grabs its current continuation, wraps it in an aborting λ, and hands it to val. Since the current continuation is exactly the evaluation context E, this is now straightforward:

E[(call/cc val)] = E[(val (λ (x) (abort E[x])))]

That's it—that's the crux of the lab in two laws of Racket:

E[(abort val)]   = val
E[(call/cc val)] = E[(val (λ (x) (abort E[x])))]

All we lacked before was the notion of an evaluation context.

(+ 1 (call/cc (λ (k) (* 2 (list (k 3) (k 4) (k 5))))))

(+ 1 (call/cc (λ (k) (* 2 (map k (list 3 4 5))))))

(cons 1 (list (call/cc (λ (k) (* 2 (k 3))))
              (call/cc (λ (k) (* 4 (k 5))))))

(cons 1 (map call/cc
             (list (λ (k) (* 2 (k 3)))
                   (λ (k) (* 3 (k 5))))))

(local [(define l (call/cc (λ (k) (list k 0 1))))]
  (local [(define f (first l))
          (define a (second l))
          (define b (third l))]
    (if (< a 7)
      (f (list f (+ 1 a) (* 2 b)))
      b)))

(call/cc (λ (k) k))

(call/cc abort)

(call/cc call/cc)

((call/cc call/cc) (call/cc call/cc))

5. Applying Control

Besides creating puzzling programs, what are control operators good for? If you've programmed in other languages, you might have seen "control-like" constructs such as:

• break statements in loops
• continue statements in loops
• return statements in procedures
• try/catch blocks for handling exceptions

Or maybe:

• concurrency, where multiple threads run simultaneously

And I should mention a couple of useful constructs that most programmers probably haven't seen since most languages don't provide support for them:

• coroutines, where control alternates between a consumer as it requires data and a producer as it creates it
• non-chronological backtracking, where a search algorithm can quickly jump between points it has visited in the past

Whereas most languages provide these kinds of features for you (or not), if you have a control operator like call/cc you can build them yourself. Let's finish up the lab by using call/cc to build a try-catch operator to handle exceptions in Racket.

Recall the error operator:

> (cons step (error "I'm a doctor, not an escalator!"))
I'm a doctor, not an escalator!

Calling error lets you signal errors to the user. A useful variant would be a try-catch operator that lets you signal errors to other parts of the program:

(try-catch
  (λ () (sqrt (safe-/ 2 (safe-first l))))
  (λ (err)
    (cond
      [(symbol=? err 'div-0)      ...]
      [(symbol=? err 'empty-list) ...])))

(define (safe-/ a b)
  (if (= b 0)
    (throw 'div-0)
    (/ a b)))

(define (safe-first l)
  (if (empty? l)
    (throw 'empty-list)
    (first l)))

Here's how we would like this to work. To evaluate the program (try-catch thunk handle), the thunk—a function with no arguments—is invoked, (thunk), and if any part of the program calls throw while (thunk) is evaluating, then the evaluation of (thunk) is abandoned and (handle err) is evaluated instead, where err is the argument supplied to throw. Calling throw is often called throwing or raising an exception, and the argument handle is often called the exception handler. If no exception is raised, then (try-catch thunk handle) evaluates to the result of (thunk); if the exception err is raised, then it evaluates to the result of (handle err).

(+ 1 (try-catch (λ () (* 2 (throw 3)))
                (λ (err) (- err))))

(+ 1 (try-catch (λ () (* 2 3))
                (λ (err) (- err))))

(+ 1 (try-catch (λ () (* 2 (throw 3)))
                (λ (err) (throw (- err)))))

(+ (try-catch (λ () (* 2 (throw 3)))
              (λ (err) (- err)))
   (try-catch (λ () (string-append (throw "fish") "cows"))
              (λ (err) (string-length err))))

(throw "foo")

(+ (try-catch (λ () 1)
              (λ (err) err))
   (throw "foo"))

Now let's implement try-catch and throw. For throw to abort the evaluation of (thunk) and jump to the handler, try-catch will have to do some fancy footwork with call/cc. But in addition to that, notice that (throw err) has no idea which handler it should call!—we need some way for try-catch to communicate the current handler to throw. A good solution for this is to use state…

(- 1 (try-catch
       (λ () (* 2 (try-catch
                    (λ () (+ 3 (throw 4)))
                    (λ (err) (- (throw (+ 5 err)))))))
       (λ (err) (sqrt err))))