# CS 2500 Honors Lab 12: Control

Work in pairs.

Switch roles often.

This lab uses features not included in the student languages. Add these two lines at the top of your file to include them:

```
(require racket)
(require (only-in racket/control abort))
```

## 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:

```
((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:

```
((second (list (λ (n) (abort "Hi Mom!"))
number->string))
80))
= (string-append "Your total is: \$"
(number->string
80))
= (string-append "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?))
(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.

Exercise 1

What do each of the following programs evaluate to? Work them out in your head first, and then use DrRacket to check your understanding.

```
(+ 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))))
```

Exercise 2

What should the contract for `abort` be?

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)`.

Exercise 3

Yikes! … Got that?

Partners, take turns explaining to each other how `WHERE-AM-I?` behaves in the above example.

Exercise 4

What would happen if `GO-BACK = (λ (x) (abort (- old-balance x)))` was just `(λ (x) (- old-balance x))`, without the `abort`?

Exercise 5

Assuming the operator `WHERE-AM-I`?, what is the implementation of `product` and `product-helper` that behaves as above?

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.

Exercise 6

What do each of the following programs evaluate to? Work them out in your head first, and then use DrRacket to check your understanding.

Your first step in each should be to figure out what `k` is, the continuation that's current when `call/cc` is invoked.

```
(+ 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)
```

Exercise 7

What should the contract for `call/cc` be?

## 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.

Exercise 8

What do each of the following programs evaluate to? Work them out in your head first, and then use DrRacket to check your understanding.

These are more challenging than the last set. As before, start by figuring out all the relevant continuations—if you get stuck, step the program in your head (or on paper) to find the evaluation context when `(call/cc val)` becomes the current expression.

```
(+ 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)`.

Exercise 9

What should each of the following programs do? (You'll have to work them out in your head, since `try-catch` and `throw` aren't written yet!)

```
(+ 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"))
```

Exercise 10

What should the contracts be for `throw` and `try-catch`? Assume a type `Error` for the inputs to `throw` and the handler. (There's no reason to expect it to always be a `String` or `Number`, as above.)

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

Exercise 11

Using `call/cc` and `set!`, implement `try-catch` and `throw` as described above. Formulate the examples from Exercise 9 as tests for your implementation. (You might find `check-error` useful for the last two.)

Make sure you're in Advanced Student Language to use `set!`. Refer to the help desk and sections 35 and 38 in the book for more information about programming with state and using set!.

Exercise 12

Consider a program with nested `try-catch` expressions:

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

The description above doesn't specify how nested expressions should behave… The least surprising behavior would be for a `throw` to jump to the handler of the `try-catch` expression encountered most recently, but only for `try-catch` expressions that we're still inside of. Thus, the above program should throw twice and evaluate to ```(- 1 (sqrt (+ 5 4))) = -2```.

Formulate additional tests involving nested `try-catch` expressions and refine your implementation, if necessary, to handle them.

Exercise 13 (challenge)

Research coroutines and implement them using `call/cc`. A quick google search should get you started… (But watch out for spoilers!)