12 Control

Purpose: To examine new and interesting computational models; achieve the control we crave in our real lives in programming.

STOP! In The Name Of Cycles

Consider the following silly computation:

; product : [List-of Number] -> Number

; The product of lon

(define (product lon)

(cond

[(empty? lon) 1]

[else (* (first lon) (product (rest lon)))]))

(product '(5 8 1 0 2 9 3))

-> (* 5 (product '(8 1 0 2 9 3)))

-> (* 5 (* 8 (product '(1 0 2 9 3))))

-> (* 5 (* 8 (* 1 (product '(0 2 9 3)))))

-> (* 5 (* 8 (* 1 (* 0 (product '(2 9 3))))))

-> (* 5 (* 8 (* 1 (* 0 (* 2 (product '(9 3)))))))

-> (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 (product '(3))))))))

-> (* 5 (* 8 (* 1 (* 0 (* 2 (* 9 (* 3 (product '()))))))))

-> (* 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

Why is this silly? Once we see (* 0 ...), the program continues to compute the product of the remaining sublist, despite the fact the output must be 0.

But wouldn’t it be nice if it also avoided computing every step of (* 5 (* 8 (* 1 0))) and instead replaced the whole computation with 0 immediately? Something like...

(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 a keyword like STOP!-THE-ANSWER-IS then we could refine our implementation of product once more to avoid computing any of the multiplications by 0:

; product : [List-of Number] -> Number

; The product of lon

(define (product lon)

(cond

[(empty? lon) 1]

[else (if (zero? (first lon))

(STOP!-THE-ANSWER-IS 0)

(* (first lon) (product (rest lon))))]))

But how can we get a keyword 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, ISL+ has a strict notion of the control of a program, i.e. in what order to evaluate expressions and their sub-expressions. What we lack is a way to influence this control once a program starts running.

Starter Code: Place the following two lines at the top of your file.

(require racket)

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

We can now access abort, which functions just as we would want STOP!-THE-ANSWER-IS to. ISL+ will evaluate your program as normal, except if it ever needs to evaluate a part that says (abort val), then ISL+ will replace your whole program with val.

Exercise 1 Predict what the following code snippets will return:

(* 2 (+ 1 (abort (* 5 (- 6 2)))))

(string-append "Your total is: $"

((first (list (λ (n) (abort "Hi Mom!"))

number->string))

80))

(string-append "Your total is: $"

((second (list (λ (n) (abort "Hi Mom!"))

number->string))

80))

(map (λ (f) (f 3)) (list add1 sqr number->string abort odd?))

((λ (x) (+ 20 (abort x))) "Oopsies")

(rest (map identity (list abort)))

(map abort (list 1 2 3))

(local [(define (loop x)

(loop x))]

(loop (abort "Hello, World!")))

(local [(define (loop x)

(loop x))]

(abort (loop "Hello, World!"))) ; watch out for this one!

Exercise 2 Determine the signature for abort.

Exercise 3 Implement product with abort.

So this is great, but what if product was just part of a computation? For example,

(+ 20 (product '(0 1 2 3)))

Just reading this, we’d want the outcome to be 20. But that’s not what happens: why not? And how do we fix it? Let’s dive in.

Switch pair programming roles before continuing!

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 skip over just the unnecessary products but leave the rest of the program alone.

In our example

Exercise 4 That there’s a toughy. Re-read and discuss the above with your partner until both of you are certain you understand it.

Exercise 5 What would happen if GO-BACK was not (λ (x) (abort (+ 20 x))), but just (λ (x) (+ 20 x)), without the abort?

So, we need to further examine this supposed WHERE-AM-I? operator. How does it behave?

WHERE-AM-I? 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, instead of WHERE-AM-I?, 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 snippets of code evaluate to? Work them out in your head first, and then use check-expect to test your hypotheses.

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 signature for call/cc be?

Switch pair programming roles before continuing!

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) expr1) val) = replace x with val in expr1

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

Exercise 8 Find an expr1 and expr2 such that ((λ (x) expr1) expr2) is not equivalent to replacing x with expr2 in expr1. Hint: use error.

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, as we saw above control operators are about the continuation of an expression. While we can use variables like expr and val to describe the law of λ, it’s not obvious how to write something similar for the continuation. However, the same idea applies: we can refer to the context of an expression with a variable C, such as in

C [(abort val)] = ...

C [(call/cc val)] = ...

A context C can stand for any program with a hole in it, and C [expr] is the same program with expr plugged in the hole. For example,

(+ 20 •) [(product 1 2 3 0)] = (+ 20 (product 1 2 3 0))

(if (zero? x) (add1 x) •) [(/ 1 x)] = (if (zero? x) (add1 x) (/ 1 x))

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

But if we actually run this, we get 42. Why? Because contexts can be any hole-y program, so C = (if (even? 0) 42 (+ 1 •)) is certainly a legal context. That law essentially says that (abort val) can be evaluated 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. In fact, we have a very particular feeling about the order in which the above expression should evaluate, and it should never include any aborts:

(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. Similarly to how we say value variables val are a restricted subset of expressions, we can revise our definition of contexts to only allow programs where the hole is the current expression to evaluate. 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 by replacing 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 9 What do each of the following snippets of code evaluate to? Work them out in your head first, and then use check-expect (when possible) to test your hypotheses.

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

Exercise 10 Using call/cc, implement product and product-or-go-back so the evaluation of (+ 20 (product (list 5 8 1 0 2 9 3))) works as described above.

Before You Go...

That’s the last lab of the semester! Just two lectures and one homework to go and you are done with the accelerated version of CS2500. Congratulations on all you have achieved! Consider the kinds of problems you can solve now that would have seemed impossible at the beginning of September; you can and should feel proud. We certainly are of you!