9 Control Flow
9.1 Overview
The control flow of a program determines the order in which a program is evaluated. This week, we will talk about two ways of manipulating control flow in Racket:
1. We’ll use a combination of macros and thunks to circumvent the eager evaluation of function calls in Racket.
Copyright By PowCoder代写 加微信 powcoder
2. We’ll introduce a feature of Racket called continuations, which can capture and modify an expression’s
call stack.
Both macros and continuations are not typical features of main-stream programming languages. We’ll explore how to use these techniques to build our own make-shift logic programming language.
9.1.1 Learning Objectives
By the end of this week, you will be able to
1. Explain the difference between lists and streams in Racket, and be able to implement core stream functions in Racket.
2. Write code that uses infinite streams in Haskell.
3. Explain how mutation can be used to implement self-modifying streams, and write Racket functions that
uses mutation.
4. Predict the output of code that uses the shift and reset delimited continuation operations in Racket.
5. Trace the execution of expressions that uses calls to a single ambiguous choice operator –<.
9.1.2 Checklist
• Complete the readings, ideally before lecture
• Attend lecture
• Attend the lab
• Review this week’s materials
• Complete assignment 3
9.2 Streams
In the last few weeks, we saw how to use macros to introduce new syntactic forms to reduce boilerplate code and create name bindings for classes. Hopefully this gave you a taste of the flexibility and power of macros: by changing the very syntax of our core language, we enable new paradigms, and hence new idioms and techniques for crafting software. Now, we’ll start to look more explicitly at another common usage of macros: manipulating control flow to circumvent the eager evaluation of function calls in Racket.
Our first foray into this area will be to implement streams, a “lazy” analogue of the familiar list data type. First, recall the recursive definition of a list:
• A list is either empty, or
• A value “cons’d” with another list.
In Racket, cons is a function, and so all lists built up using cons are eagerly evaluated: all list elements are evaluated when the list is constructed.1 However, this is often not necessary: when we traverse a list, we often only care about accessing one element at a time, and do not need the other elements to have been evaluated at this point. This motivates our implementation of a stream in Racket, which follows the following recursive definition:
• A stream is either empty, or
• A thunk wrapping a value “cons’d” with a thunk wrapping another stream.
As we discussed in the previous chapter, the thunks here are used to delay the evaluation of the elements of the stream until it is called. While we could implement this stream version of cons by explicitly passing thunks into the built-in cons, we again use macros to reduce some boilerplate:
1The same is true of the Racket built-in list, as it too is a function.
Based on notes by 1
#lang racket #| CSC324: Stream Implementation |#
(provide s-null
stream->list)
; Empty stream value, and check for empty stream.
(define s-null ‘s-null)
(define (s-null? stream) (equal? stream s-null))
(s-cons
E.g., s-null or another s-cons expression).
Creates a stream whose first value is
items are the ones in
and
Note: s-cons is a MACRO, not a function!
(define-syntax s-cons (syntax-rules ()
[(s-cons
(cons (thunk
; These two define the stream-equivalents of “first” and “rest”. ; We need to use `car` and `cdr` here for a technical reason that ; isn’t important for this course.
(define (s-first stream) ((car stream)))
(define (s-rest stream) ((cdr stream)))
(make-stream
Returns a stream containing the given values.
Note that this is also a macro. (why?)
(define-syntax make-stream (syntax-rules ()
[(make-stream) s-null]
[(make-stream
(s-cons
(stream->list stream) -> list?
stream: stream?
Returns a list containing the values in this stream.
(define (stream->list stream) (if (s-null? stream)
(cons (s-first stream) (stream->list (s-rest stream)))))
(s-range start end) -> stream?
Based on notes by 2
start: integer?
end: integer?
Returns a stream containing the numbers start, start+1, …, end-1.
Returns an empty stream if start >= end.
(define (s-range start end) (if (>= start end)
(s-cons start
(s-range (+ 1 start) end))))
(s-take stream n) -> stream?
stream: stream?
n: (and/c integer? (not/c negative?))
Returns a new stream that contains the first `n` elements of `stream`,
or all of the elements of `stream` if it has fewer than `n` elements.
(define (s-take stream n) (if (equal? n 0)
(s-cons (s-first stream)
(s-take (s-rest stream) (- n 1)))))
The beauty of this macro-based stream implementation is that its public interface is identical to built-in lists:
> (define s1 (s-cons 3 (s-cons 4 (s-cons 5 s-null))))
> (s-first s1)
> (s-first (s-rest s1))
> (s-first (s-rest (s-rest s1)))
> (s-null? (s-rest (s-rest (s-rest s1))))
The difference, of course, is in the creation of these streams:
> (define items1 (list 1 2 (error “error”)))
ERROR error
> (define items2 (make-stream 1 2 (error “error”))) > (s-first items2)
9.2.1 Lazy lists in ’s been a while since we worked with Haskell, but it’s worth pointing out that Haskell uses lazy evaluation for all of its function calls, and so the cons operation (:) is already lazy. This means that in Haskell, the list data type we’ve been using all along are already streams:
> x = [1, 2, error “error”]
9.2.2 Infinite streams
In this section, we’ll take a brief look at one of the mind-bending consequences of using streams to delay evaluation of the elements in a sequence: constructing and manipulating infinite sequences. While we could do this in Racket, we’ll use Haskell’s built-in list data types to underscore the fact that Haskell’s lists really are streams.
Here are some simple examples.
Based on notes by 3
myRepeat x = x : myRepeat x
> take 3 (myRepeat 6)
nats = 0 : map (+1) nats
> take 5 nats
[0,1,2,3,4]
What’s going on with that wild nats definition? How does take 5 nats work? To understand what’s going on, let’s look at a simpler example: head nats. Let’s carefully trace it using the central mechanic of pure functional programming: substitution.
1. In Haskell, head is defined through pattern-matching as head (x:_) = x.
2. nats is defined as 0 : map (+1) nats. When we pattern-match nats against the definition for head, we
get x = 0, and 0 is returned. Note that head completely ignores the rest of the list, and so we don’t need to look at the recursive part at all!
Now something a bit more complicated: head (tail nats). Again, let’s substitute, keeping in mind the definition for tail, tail (_:xs) = xs.
head (tail nats)
— We can’t call `head` until we can pattern-match on (x:_).
— To do this, we’ll need to expand `(tail nats)` a bit.
head (tail (0 : map (+1) nats))
— We can evaluate the inner part using pattern-matching on the — implementation of tail:
— tail (_:xs) = xs
head (map (+1) nats)
— Now we need the following definition of map:
— map _ [] = []
— map f (x:xs) = (f x) : (map f xs)
— In order to pattern-match, we need to expand nats again.
head (map (+1) (0 : map (+1) nats))
— This allows us to pattern-match: x = 0, and xs = map plus1 nats. — We do the substitution into the second rule, but remember:
— we aren’t evaluating the inner expressions!
head (((+1) 0) : (map (+1) (map (+1) nats)))
— At this point, we can *finally* pattern-match against `head`.
— As before, we get to discard the complex “tail” of the argument. (+1) 0
— Finally, we evaluate ((+1) 0) directly to display the result.
So the first two elements of nats are 0 and 1. The expansion we did suggests what would happen if we access further elements. The part that we discarded, (map plus1 (map plus1 nats)), adds one, twice. In subsequent recursive expansions of nats, the map plus1 function calls accumulate, leading to larger and larger numbers.
Since all of the common higher-order list functions work recursively, they apply equally well to infinite lists:
squares = map (\x -> x * x) nats
evens = filter (\x -> x `mod` 2 == 0) nats
> take 4 squares
We’ll wrap up with a cute example of the Fibonacci numbers.2 fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
9.3 A Self-Updating Stream
In the next part of the course, we will build up to a programming paradigm called logic programming. Logic programming is considered more declarative than the other programming paradigms that you are used to, meaning
2Exercise: how does this work?
Based on notes by 4
that we tend to describe what the desired outputs look like, rather than how the computation should perform the task.
Logic programming is related to artificial intelligence. In particular, we will solve problems (e.g. Sudoku) by enumerating through possible solutions, then filtering those possibilites for actual solutions. With problems like these, we will often work with a large (or even infinite) search space. So, we start this section by reviewing our definition of streams.
9.3.1 Python Generators
Many kinds of data are naturally represented using streams: for example, you could represent all tweets as a stream, or stock prices over time, or the temperature readings from a weather station.
As such, the idea of a stream (decoupled from our Racket implementation) is actually quite general and pervasive. Different programming languages have different ways of representing streams, and use the idea of lazy evaluation in different ways. To motivate our next topic, let’s take a look at how Python implements generators. A generator function in Python is a way of creating an iterator with possibly infinite number of values. Such a function uses the yield keyword, rather than the return keyword. Here is a simple example:
def my_gen(): n=1
print(“yielding 1…”) yield n
print(“yielding 2…”) yield 2
print(“yielding 3…”) yield 3 print(“finished”)
Calling the function my_gen yields an iterator, which can be looped over using a for loop (e.g. for x in my_gen(): …). We can also use the Python function next to obtain the results one by one.
>>> g = my_gen()
>>> next(g)
yielding 1…
>>> next(g)
yielding 2…
>>> next(g)
yielding 3…
>>> next(g)
Traceback (most recent call last):
File “
Every time the function next is called, Python continues execution of the generator function until the next yield is reached. Once that happens, Python returns the yielded value, and suspends execution of the function. The values of local variables like n are preserved, and are used the next time we call next.
Like our Racket streams, Python generators can be used to generate an infinite sequence of values.
define repeat(n): while True: yield n
This generator repeats the value n an infinite number of times:
>>> g = repeat(3)
>>> next(g)
>>> next(g)
>>> next(g)
Based on notes by 5
>>> next(g) 3
9.3.2 A self-updating stream (with mutation)
The Python generator has an interesting and simple syntax that we would like to replicate using streams. In particular, we would like a Racket syntax next! that behaves like this:
> (define s (make-stream 1 2 3))
> (next! s)
> (next! s)
> (next! s) 3
> (next! s) ‘DONE
The exclamation mark ! at the end of next! is pronounced “bang”, and is used to signal a function that uses mutation. As you might have guessed, next! uses mutation to update the value of s. To be more specific, we would like next! to do the following:
When the stream s is non-empty, we would like to • Update the stream to s-rest of the stream
• Return the s-first of the stream
In other words, when s is nonempty, (next! s) is equivalent to the following code:
(let* ([tmp s]) ; save a handle to `s`
(set! s (s-rest s)) ; re-bind `s` to the `(s-rest s)`
(s-first tmp))) ; return the first value, saved from earlier
When the stream s is empty, then we will simply return the symbol ‘DONE.
How can we implement next!? Since we are trying to mutate a variable, next! cannot possibly be a function.
(Why?) Instead, we will define next! as a macro.
(define-syntax next!
(syntax-rules ()
[(next!
(if (s-null?
(let* ([tmp
(set!
(s-first tmp))))]))
Let’s check that this macro can be used with other streams, including infinite streams. We’ll write a repeat function in Racket to create an infininte stream, and take items from that stream:
> (define (repeat n) (s-cons n (repeat n)))
> (define g (repeat 3))
> (next! g)
> (next! g) 3
Based on notes by 6
> (next! g)
> (next! g)
One nice feature of streams is that their values are evaluated lazily. Errors will not appear until an invalid stream element is reached, and are isolated to the single invalid element.
> (define g (make-stream 1 2 (/ 3 0) 4))
> (next! g)
> (next! g)
> (next! g)
ERROR /: division by zero
> (next! g)
> (next! g)
9.4 The Ambiguous Choice Operator and Continuations
In the previous lectures, we used macros to create an implementation of streams, a lazy data structure that decouples the creation of data from the consumption of that data.
In this section, we’ll explore this idea in a different context. In particular, we will create data with expressions that use non-deterministic choice, and consume data using the function next! that we previously wrote . Our implementation of such expressions will introduce one new technical concept in programming language theory: the continuation, a representation of the control flow at a given point in the execution of a program.
9.4.1 The choice operator –<
The operator -< is pronounced “amb”, short for the word “ambiguous”. We will use this operator to generate data and to denote possible choices of values. The intention is that any place in our code where a single expression is used, we would like to instead provide a number of possible choices of values.
This operator therefore takes an arbitrary number of argument subexpressions, representing possible values for the whole -< expression. It then returns a stream of potential answers. We access the stream using the next! function that we previously defined. Here’s a very simple example.
> (define g (-< 1 2 (+ 3 4))) ; Create a stream of potential answers
> (next! g) ; A call to (next!) returns an answer, and updates the stream
> (next! g)
> (next! g)
> (next! g) ; Here our constant ‘DONE shows that there are no more choices
The macro next! is what we have previously defined. We will need to make some changes to this macro later on, but let’s start with the definition that we had previously:
(define-syntax next!
(syntax-rules ()
[(next!
(if (s-null?
(let* ([tmp
(set!
(s-first tmp))))]))
Based on notes by 7
What about the –< operator? So far, it sounds exactly like the make-stream macro that we wrote earlier! The difference is that if we use -< inside a larger expression, we would like the -< operator to be able to capture the surrounding computation. As an example, consider this expression, where -< is used inside the expression (+ 10 ...): (+ 10 (-< 1 2 (+ 3 4))) We would like this code to create and return a stream containing the values 11, 12, and 17. In order to support this new functionality, our current definition of -< is insufficient. In particular, we need some way of saving the computational context surrounding the call to -<. That is, we need to be able to store the fact that the computation (lambda (x) (+ 10 x)), also written as (+ 10 _), needs to be performed after the call to -<. This brings us to the realm of continuations. 9.5 Continuation In our studies to date, we have largely been passive participants in the operational semantics of our languages, subject to the evaluation orders of function calls and special syntactic forms. Even with macros, which do allow us to manipulate evaluation order, we have done so only by rewriting expressions into a fixed set of built-in macros and function calls. However, Racket has a data structure to directly represent (and hence manipulate) control flow from within a program: the continuation. Consider the following simple expression: (+ (* 3 4) (first (list 1 2 3))) By now, you should have a very clear sense of how this expression is evaluated, and in particular the order in which the subexpressions are evaluated.3 For each subexpression s, we define its continuation to be a representation of what remains to be evaluated after s itself has been evaluated. Put another way, the continuation of s is a representation of the control flow from immediately after s has been evaluated, up to the final evaluation of the enclosing top-level expression (or enclosing continuation delimiter, a topic we’ll explore later this chapter). For example, the continuation of the subexpression (* 3 4) is, in English, “evaluate (first (list 1 2 3)) and then add it to the result.” We represent this symbolically using an underscore to represent the “hole” in the remaining expression: (+ _ (first (list 1 2 3))).4 While it might seem like we can determine continuations simply by literally replacing a subexpression with an underscore, this isn’t exactly true. The continuation of the subexpression (first (list 1 2 3)) is (+ 12 _); because of left-to-right evaluation order in function calls, the (* 3 4) is evaluated before the call to first, and so the continuation of the latter call is simply “add 12 to the result.” Since both identifiers and literal values are themselves expressions, they too have continuations. The continuation of 4 in the above expression is (+ (* 3 _) (first (list 1 2 3))), and the continuation of first is (+ 12 (_ (list 1 2 3))). Finally, the continuation of the whole expression (+ (* 3 4) (first (list 1 2 3))) is simply “return the value,” which we represent simply as _. Warning: students often think that an expression’s continuation includes the evaluation of the expression itself, which is incorrect—an expression’s continuation represents only the control flow after its evaluation. This is why we replace the expression with an underscore in the above representation! An easy way to remember this is that an expression’s continuation doesn’t depend on the expression itself, but rather the expression’s position in the larger program. 9.5.1 shift: reifying continuations So far, continuations sound like a rather abstract representation of control flow. What’s quite spectacular about Racket is that it it provides ways to access continuations during the execution of a program. We say that Racket reifies continuations, meaning it exposes continuations as values that a program can access and manipulate as easily as numbers and lists. We as humans can read a whole expression and determine the continuations for each of its subexpressions (like we did in the previous section). How can we write a program that does this kind of meta-analysis for us? Though it turns out to be quite possible to implement reified continuations purely in terms of functions, this is beyond t