5  Loops and Functions

Loops play a central role in conventional programming languages. Most of those have three or four different loop statements, e.g., for, while, repeat, and do. Loops are also important in Scheme, indeed far more important than in conventional lanuages. The last time we counted, Scheme had 7,509,304 loops. By now, it probably has a few more. Did we get your attention? Okay, let's explain this now.

In contrast to traditional languages, Scheme implements loops as functions. They are functions for two reasons. First, the set of conventional loops isn't sufficient even for plain conventional imperative programming, as the literature on looping constructs in the 1970s proves. But, if loops are just functions, programmers aren't restricted to those that the designers of the language provide. They define their own if they need one that doesn't exist. Second, loops in imperative languages communicate with their context via effects. In a value-oriented language such as Scheme, a loop should produce results, just like any other expression. For example, if a loop iterates over something like a list of characters, it may produce a boolean, a number, a character, a string, or another list. Returning a result has the advantage of making it totally obvious how the loop communicates with its context -- for both the original programmer and the many successors.

What is a loop or looping construct? The purpose of a loop is to apply a function3 at strategic points during the traversal of a data structure. In primitive languages, loops traverse arrays with counting variables; in post-primitive languages, a so-called iterator supplies the elements in a collection to a statement one at a time. Let's look at Scheme loops now.

5.1  Some Simple Examples

A conventional introductory course says that a loop statement is an abbreviation for a sequence of nearly identical statements. For example, an instructor may say to students ``write a program that prints the numbers between 0 (inclusive) and 10 (exclusive)'' and may get an answer like this:

(begin
  (printf "~a " 0)
  (printf "~a " 1)
  (printf "~a " 2)
  (printf "~a " 3)
  (printf "~a " 4)
  (printf "~a " 5)
  (printf "~a " 6)
  (printf "~a " 7)
  (printf "~a " 8)
  (printf "~a " 9))

Then the instructor may ask ``wouldn't it be nice if we could write this repetition more easily?'' and begin with an explanation of loop statements. A beginning Scheme programmer may end up rewriting the above as a two-line program:

(define (print-one-number i) (printf "~a " i))

(for-each print-one-number-per-line '(0 1 2 3 4 5 6 7 8 9))

Note how the library function for-each consumes the user-defined function print-one-number as the first argument and a list as the second one. Its task is to apply the function to each item on this list. Hence, this expression prints the numbers 0, ..., 9 on separate lines.

;; average : (cons num (listof num))  -->  num 
;; to compute the average of a non-empty list of numbers

 
;; the expert version 
(define (average alon)
  (/ (apply + alon) 
     (length alon)))













            
;; the beginner version
(define (average alon)
  (/ (sum alon) 
     (how-many alon)))

;; sum : (listof num)  -->  num
(define (sum alon)
  (cond
    [(null? alon) 0]
    [else (+ (car alon) (sum (cdr alon)))]))

;; how-many : (listof num)  -->  num
(define (how-many alon)
  (cond
    [(null? alon) 0]
    [else (+ (how-many (cdr alon)) 1)]))


 

Figure 5:  Computing the average of a list of numbers

Writing a summation program is another typical example that motivates the use of loops in conventional language. Once loops have been motivated, an instructor may challenge the students to write a program that receives a bunch of numbers and produces their sum. In Scheme, we naturally represent a bunch of numbers with a list. Then the program becomes a one-line function:

;; (Listof Number)  -->  Number
;; compute the sum of a list of numbers
(define (sum-a-bunch-of-numbers alon) (apply + alon))

The loop here is Scheme's apply primitive. It consumes a function and a list of arguments and applies the function to these arguments. For example,

(apply + '(0 1 2 3 4 5 6 7 8 9))

is equal to

(+ 0 1 2 3 4 5 6 7 8 9)

To use sum-a-bunch-of-numbers, we just apply it to a list of numbers:

(sum-a-bunch-of-numbers '(0 1 2 3 4 5 6 7 8 9))

The call is equivalent to (apply + '(0 1 2 3 4 5 6 7 8 9)), and its evaluation follows the above rules. Of course, we don't have to have a literal list as the second argument to apply. Figure 5 shows how to use it in a different context.

The combination of lists and apply is powerful. Using it, we can write all kinds of programs easily:

  1. (apply + (vector->list a-vector)) sums up the numbers in a vector, using a built-in translation from vectors to lists.

  2. (apply append a-list-of-lists) concatenates the lists in the second argument and (apply string-append a-list-of-strings) concatenates the list of strings;

  3. and (apply max a-list-of-numbers) finds the maximum of a bunch of numbers.

For a final example, consider the problem of turning a list of strings into a sentence. To make things truly simple, we assume that the words are separated by a space. Thus, if the function is given

'("the"  "world" "deserves" "one" "big" "hello")

it produces

"the world deserves one big hello "

and, if it is given

'("hello" "world" "," "how" "are" "you")

the result is this string:

"hello world , how are you "

Notice the extra space to the left of the comma and at the end of the sentence; we discuss this little problem later.

We already know how to concatenate the strings in a list of strings using apply and string-append but first we must add a blank space to each string in the list. To achieve this, we use another loop:

;; (Listof String)  -->  String
;; produce a sentence from a list of strings
(define (make-a-sentence a-list-of-strings)
  (apply string-append (map add-a-space a-list-of-strings)))

;; String  -->  String
(define (add-a-space s) (string-append s " "))

Roughly speaking, map is like for-each. It consumes a function and a list and applies the function to each item on the list. Unlike for-each, map collects all the results in a new list. Hence, make-a-sentence consists of two loops: one for adding the space and one for concatenating all of the resulting strings. Since the task description itself mentions both of these tasks, it is not surprising that we structure our function that way. Of course, a ``born'' programmer would use at most one loop to accomplish this task. Hold on, we will soon see how to do this in Scheme, too, and how to get rid of the silly space to the left of ``,''.

In summary, we see that we can write concise loop-style code in Scheme, especially as long as we keep in mind that the purpose of an expression is to produce a value (not (just) an effect). On the average, this kind of code is as short, or shorter, as equivalent code in a conventional language. Still, the examples indicate that there is a problem with Scheme's approach. Often, we need to define small, auxiliary functions that are then handed over to a loop. This is clearly too awkward for a real programmer. Fortunately, Scheme has anonymous functions, and with them, we can write true one-liners.

5.2  Anonymous Functions

At first glance, a function definition is a complex beast. A function definition specifies the name of the function so that we can refer to it later. It also specifies the names of the function arguments, which represent a bunch of unknown values. And last, but not least, it also specifies an expression that computes a value from the arguments. In contrast, a variable definition appears to be much simpler; it just associates a name with the value of an expression. If we had a way to create a function independently, we could use simple variable definitions to introduce functions.

With the lambda-expression, Scheme provides just such an mechanism. A lambda-expression is an expression like every other expression. It consists of a bunch of argument names and an expression that uses these names; its result is a function. Consider the following two variable definitions:

;; Number Number  -->  Number
;; to compute the volume of a cylinder 
(define volume-cylinder
  (lambda (radius height)
    (* (area-disk radius) height)))

;; Number  -->  Number
;; to compute the area of a disk 
(define area-disk
  (lambda (radius)
    (* pi radius radius)))

They associate the name volume-cylinder and area-disk with a two-argument and a one-argument function, respectively. Indeed, these functions are the very same functions that we first defined in section 3.1, but we now create them first and associate them with a name in a plain old variable definition afterwards.

We do not have to associate functions with names to use them. Let's study this point with a short series of examples:

(lambda (x) (+ 3 x))

This first function consumes one argument and adds 3 to this argument. The result of the addition is the result of the function. To apply this function, we can just use the lambda-expression in a function application:

((lambda (x) (+ 3 x)) 5)

Since the lambda-expression evaluates to a function of one argument, and since the application supplies one argument, namely 5, this is a perfectly fine application. We can also use our evaluation rule for named functions to figure out the result:

((lambda (x) (+ 3 x)) 5)
equals
(+ 3 5)

because we just replace x by 5 in the body of the nameless function and replace the application with the new body. The rest is plain arithmetic.

Here is a second lambda-expression:

(lambda (radius height) (* (* 3.14 radius radius) height))

It shows a nameless function that consumes two arguments. Ergo, to apply this function we must supply two values:

((lambda (radius height) (* (* 3.14 radius radius) height)) 10 22)

The arguments and the result of this function are still numbers. This doesn't have to be the case though:

(lambda (f) (+ (f 0) 3))

This third nameless function consumes a function and applies it to 0. To produce the final result, it also adds 3. Let's apply this function:

((lambda (f) (+ (f 0) 3)) sin)

Since the function expects a function from numbers to numbers as an argument, we supply sin, a library function. Replacing f with sin yields the next step in the calculation:

(+ (sin 0) 3)

And now we see that a function that consumes a library function isn't a big deal. We use the same old rules to figure out the final value, which is 3 in this example because (sin 0) is 0. Of course, we can also make up our own function and supply it as an argument:

((lambda (f) (+ (f 0) 3)) (lambda (i) (+ (* 10 i) 5)))

To understand the meaning of this expression, we need to replace f with an entire lambda-expression:

(+ ((lambda (i) (+ (* 10 i) 5)) 0) 3)

The result looks a bit complicated, but if we apply our function evaluation rule one more time -- to the underlined subexpression -- everything works out just fine:

(+ (+ (* 10 0) 5) 3)

Now we can use plain old arithmetic to figure out the final result.

Anonymous functions greatly simplify the use of loops. Recall the two small functions print-one-number and add-a-space from section 5.1. We defined those functions only so that we could use them with for-each and map, respectively. Now we don't have to define functions anymore; we just create them with lambda and hand them over to loops. The loop for printing numbers becomes a one-liner:

(for-each (lambda (i) (printf "~a ")) '(0 1 2 3 4 5 6 7 8 9))

And the function for creating sentences becomes a single function:

;; (Listof String)  -->  String
;; produce a sentence from a list of strings
(define (make-a-sentence alos)
  (apply string-append (map (lambda (s) (string-append s " ")) alos)))

Now we just need to figure out what all the Scheme loops are so that we can write concise functions.

5.3  Many Loops for Lists

Scheme's loops for lists come in three major varieties:

  1. list constructors, such as build-list, which constructs lists from other kinds of data, e.g., natural numbers and functions;

  2. mapping functions, such as map, which apply some function to each item on a list and create a list from the results; and

  3. folds, such as foldl, which apply a function to each item on a list and fold the results into a single, possible atomic, value.

The classification is coarse. Some functions, such as andmap, have attributes of more than one category. The classification does help illustrate the point that Scheme loops communicate with their use contexts via values.

;; build-list : N (N  -->  X)  -->  (listof X)
;; (build-list f n) constructs (list (f 0) ... (f (- n 1)))
(define (build-list n f) ...)

;; for-each : (X  -->  Y) (listof X)  -->  (listof Y)
;; applies f to each item on alox
;; that is, (for-each f (list x ... z)) = (begin (f x) ... (f z))
(define (for-each f alox) ...)

;; map : (X  -->  Y) (listof X)  -->  (listof Y)
;; to construct a list by applying f to each item on alox
;; that is, (map f (list x ... z)) = (list (f x) ... (f z))
(define (map f alox) ...)

;; andmap : (X  -->  boolean) (listof X)  -->  boolean
;; to determine whether p holds for every item on alox
;; that is, (andmap p (list x ... z)) = (and (p x) (and ... (p z)))
(define (andmap p alox) ...)

;; ormap : (X  -->  boolean) (listof X)  -->  boolean
;; to determine whether p holds for at least one item on alox
;; that is, (ormap p (list x ... z)) = (or (p x) (or ... (p z)))
(define (ormap p alox) ...)

;; foldr : (X Y  -->  Y) Y (listof X)  -->  Y
;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base)) 
(define (foldr f base alox) ...)

;; foldl : (X Y  -->  Y) Y (listof X)  -->  Y
;; (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base)) 
(define (foldl f base alox) ...)

;; apply : (X ...  -->  Y) (listof X)  -->  Y
;; to apply f to the values in l
;; that is, (apply f (list x ... z)) = (f x ... z)
(define (apply f l) ...)

Figure 6:  Some Important Scheme Loops

Figure 6 presents some of the most important Scheme loops for creating and processing lists. Each loop (function) comes with a contract that specifies what it consumes and produces and a purpose statement in the form of an equation that explains how the function computes with its arguments. The two lines are good guides for finding the matching loop for your problem.

While we have already seen uses of map, for-each, and apply in use, let's study each loop in figure 6 with a few examples to see how things really work:

build-list
The comment says that build-list constructs a list from a natural number and a function. So suppose we need the list 1 through 100. Naturally we use
(build-list 100 f)

for some function f. To figure out what f must do, we use the equation to figure out abstractly what the expression does:

(list (f 0) ... (f 99))

That is, build-list applies f to 0, 1, and so on until 99. Clearly, if we add 1 to each of these numbers, we get exactly what we want.

;; Python's range function:
;; (range1 n) =(list 0 ... n-1)
;; (range2 n m) =(list n ... m-1),
;; if n < m
;; (range3 n m k) =(list n n+1*k n+2*k ... n+l*k)
;; if n < m, k > 0 for l = ceiling[m-n/k]

(define (range1 n) (build-list n identity))
(define (range2 n m)
  (if (< n m)
      (build-list (- m n) (lambda (i) (+ n i)))
      (error 'range (format range1 n m))))
(define (range3 n m k)
  (if (and (< n m) (> k 0))
      (build-list (ceiling (/ (- m n) k)) (lambda (i) (+ n (* i k))))
      (error 'range (format range2 n m k))))

Figure 7:  Building ranges

What if we want to create the range of numbers between 10 and 22? Or say we need only every other number between 10 and 22? With build-list and a tiny bit of thinking about arithmetic, this is just an exercise. See figure 7.

for-each
The for-each function applies its function as a command to each item in a list. A command doesn't return anything (useful) and therefore for-each doesn't return anything useful. The equational example for for-each also shows that an application of for-each is literally like a repeated sequence of commands.

map
The map function applies its function to each item in the list and forms a new list from the results. Thus, if we wanted to compute the locations for a number of UFOs in a list, we would write
(map move-ufo all-ufos-in-alist)

The result would be a list of UFOs, all moved by one step.

andmap
The andmap function is roughly like map except that it doesn't collec the results in a list. Instead, it checks whether all of them are true.

ormap
In contrast, ormap checks whether just one of the results is true. Suppose we have a number of red circles (bombs) and a green circle (a player), and we wish to find out whether any of the red circles intersects with the green circle. With ormap and lambda, this is a one-liner:
;; (Listof Circle) Circle  -->  Boolean 
(define (hit? red-circle-list green-circle)
  (ormap (lambda (red-circle) (circle-intersect red-circle green-circle)) red-circles))

foldr, foldl
Recall that
(make-a-sentence '("hello" "world" "," "how" "are" "you"))
produces
"hello world , how are you "

which contains a superflouos space between ``d'' and ``,''. More generally, the function should deal with punctuation marks separately. In particular, it should not add spaces to the left of a punctuation mark.

This suggests that we go over each string, one by one, and append a space unless the string is a punctuation mark. The resulting strings are then concatenated into one word; naturally, we also want a final punctuation mark:

;; (Listof String) String  -->  String
;; produce a sentence from a list of strings and a final punctuation mark
(define (full-sentence a-list-of-strings end-of-sentence)
  (foldr (lambda (s r)
           (string-append s (if (punctuation? (substring r 0 1)) "" " ") r))
         (string end-of-sentence)
	 a-list-of-strings))

;; String  -->  Boolean
;; is c a punctuation mark? 
(define (punctuation? c)
  (pair? (member c '("." "," ";" ":" "?" "!"))))

The function full-sentence consumes a list of strings and a punctuation mark. Using foldr, it iterates over the list of strings, one string (s) and one suffix (r) at a time. The suffix is the word built so far, from the right, starting with the final punctuation mark.

After a few step, the expression evaluation looks like this, according to the equations in figure 6:

  (full-sentence '("hello" "world" "," "how" "are" "you") "?")
= ((lambda (s r)
     (string-append s (if (punctuation? (substring r 0 1)) "" " ") r))
   "hello"
   ((lambda (s r)
      (string-append s (if (punctuation? (substring r 0 1)) "" " ") r))
    "world"
    ((lambda (s r)
       (string-append s (if (punctuation? (substring r 0 1)) "" " ") r))
     ","
     "how are you?")))

The string is "," and the suffix is "how are you?". The next step is that the ``action'' function builds ", how are you?" and thus produces the next suffix.

What would happen if we had used foldl?

In short, we have solved the ``superfluous space'' problem, and we have done so using a single loop.

apply
The final loop in the figure is apply for functions that already accept an arbitrary number of arguments, e.g., +, string-append, and so on. For functions that don't, we can always use foldl or foldr.

These examples give some first idea of how these loops work. We will encounter plenty of other uses soon.

As long as you need to step through sequences one item at a time, lists and loops for lists work just fine. Fortunately, for most built-in forms of data, there are functions that translate a piece of data into lists anyway. Remember swap3 the function that reverses a string of length 3? Well, here is reverse-string:

;; String  -->  String
(define (reverse-string s)
  ( list--> string (reverse ( string--> list s))))

Now we can reverse words such as "anna", "kayak", "peep", or "doof".

The same is naturally true for vectors. Programs often access vectors in a totally sequential manner, which means that they use them to represent lists. In such cases, it is also best to map a vector to a list and to process it with a list-loop:

;; (Vectorof Number) Number Number  -->  void
;; print all numbers in v that are between low and high
(define (within-tolerance v low high)
  (for-each (lambda (x) (when (<= low x high) (printf "~s~n" x)))
            (vector->list v)))

Try this function with (vector 1.1 3.7 1.2 2.6 4.0 0.8) and 1.2 and 3.8. You will see three lines: one each for 3.7, 1.2, and 2.6.

On some occasions though, it is important to iterate over a sequence of numbers. In such cases, a Scheme programmer often builds a list and uses one of list-loops to do the work. Say we need to print a list of names prefixed with sequence numbers.

;; (Listof String)  -->  String
;; print an enumeration of the names in a-list-of-names with indices
(define (print-enumeration a-list-of-names)
  (for-each (lambda (i name) (printf "~s. ~a~n" i name))
            (build-list (length a-list-of-names) add1) 
            a-list-of-names))

Here build-list creates the list (list 1 ... n) where n is the number of names in a-list-of-names. Then for-each iterates over both lists, the numbers and the names, in parallel, printing a line for each pair. For example,

> (print-enumeration '("matthias" "matthew" "robby" "shriram"))

     1. matthias
     2. matthew
     3. robby
     4. shriram

In general, most built-in loops can be applied to as many lists as desired, as long as the iterated function can consume an appropriate number of arguments.

;; assf : (X  -->  Boolean) (Listof (cons X Y))  -->  (union #f (cons X Y))
;; to search for the first pair in l whose car satisfies f
(define (assf f l) ...)

;; filter : (X  -->  Boolean) (Listof X)  -->  (Listof X) 
;; to extract the list of those X's that satisfy f
(define (filter f l) ...)

;; memf  : (X  -->  Boolean) (Listof X)  -->  (union #f (Listof X))
;; to search for the first item in l that satisfies f
(define (memf f l) ...)

Figure 8:  More Scheme loops from list.ss

With build-list, foldl, foldr, for-each, and map, Scheme covers most bases for lists. Still, some times a programmer needs to traverse a list in yet another way. Chances are that someone else needed a function like that and it is already defined in a library. Say we need to determine the common items of two lists of symbols, that is, we would like to filter out those symbols from list1 that are also on list2. A little bit of searching in Help Desk suggests that we look at the function filter (see figure 8) and with that, the desired function becomes a one-liner:

;; (Listof X) (Listof X)  -->  (Listof X)
(define (common-symbols list1 list2)
  (filter (lambda (x) (member x list2)) list1))

Or, say we wish to find out whether a list of structures contains a structure with certain properties. Again, searching in Help Desk suggests the function memf and the problem is solved:

(define-struct student (name id enrolled?))
;; Student = (make-student String N Boolean)

;; (Listof Student)  -->  (union #f Student)
(define (find-an-enrolled-student los)
  (memf student-enrolled? los))

Example: 
> (find-an-enrolled-student
    (list (make-student "matthias" 1 #f)
      (make-student "matthew" 2 #f)            
      (make-student "robby" 3 #f)
      (make-student "shriram" 4 #t)))
(make-student "shriram" 4 #t)

In summary, Scheme has plenty of loops for lists, and people add more loops all the time. When your program needs to traverse a list or some other data structure sequentially, try some of the basic mapping and fold functions. If that doesn't work, look for alternatives in Help Desk. If, and only if, this doesn't work, write your own loop.

5.4  Our First Program with Loops

The UFO program can obviously benefit from loops, as quick look at figure 4 shows. The function stars-create builds a list of stars; stars-paint draws all of them by applying star-paint to each of them.

;; Number Number  -->  true
(define (background-draw)
  (and (draw-solid-rect (make-posn 0 0) WIDTH HEIGHT BACKGROUND)))

;; Stars = (Listof Posn)

;; Number  -->  Stars
(define (stars-create n)
  (build-list n (lambda (i) (make-posn (random WIDTH) (random HEIGHT)))))

;; Stars  -->  true
(define (stars-paint stars)
  (andmap (lambda (s) (draw-solid-disk s STAR-RADIUS 'white)) stars))

(define STAR-RADIUS 1)

(define WIDTH  110)
(define HEIGHT 400)

(define BACKGROUND 'blue)

Figure 9:  A Background for UFO via Loops (cmp with fig. 4)

Figure 9 is a revision of this code. Now the function stars-create uses build-list to create the stars, shortening the function to one line. Similarly, stars-paint uses andmap to paint all the stars. Furthermore, both functions use lambda to perform their actions directly. Since there is no need to ever deal with individual stars independently and since the new looping functions are short, we might as well eliminate them.

5.5  Looping over Time and other Events

With just a slight squinting of the eyes, time is a ``data structure'' ready for traversal. The clock counts seconds or some fraction of seconds, and it is quite natural that a programmer may wish to execute an action per clock tick. In general, a program may need to execute a command for several different sequences of events, not just time.

The draw.ss teachpack exports functions for just this style of programming:

  1. on-tick-event : (World  -->  World)  -->  true;

  2. on-key-event : ((union char symbol) World  -->  World)  -->  true;

  3. big-bang : Number World  -->  true; and

  4. stop-time :  -->  true.

To create a World and to make a clock tick, we use big-bang. The first function, on-tick-event, consumes a function, dubbed a TIME HANDLER, and iterates it over all the ticks of the clock (spaced according to the number given to big-bang), which we call TIME EVENTS. Just so that we can remember some of our past, the time handler consumes a World and produces another one. Finally, stop-time terminates it all.

Here is a small program that slowly draws a circle around the center of a canvas:

;; World = N
(start 100 100)

(big-bang .5 0)

(on-tick-event 
 (lambda (tock) 
   (begin
    (draw-solid-disk 
     (make-posn (+ 50 (* 50 (sin tock))) (+ 50 (* 50 (cos tock)))) 3 'red)
    (+ tock 1))))

More precisely, the expression makes the clock tick every .5 seconds and, on every clock tick, it draws a solid, red disk at the same distance, but a different position, to (make-posn 50 50), the center of the world.

The on-key-event function consumes an action function -- called EVENT HANDLER -- and iterates it over the sequence of keyboard events. Each keyboard event is either translated into a character (e.g., #\space) or a symbol (e.g., 'up). Thus, if we want to use the four arrow symbols to move an object around on the screen, we can do so as follows:

;; World = Posn

;; KeyEvent World  -->  World
(define (move e w)
  (case e
    [(up) (make-posn (posn-x w) (- (posn-y w) 10))]
    [(down) (make-posn (posn-x w) (+ (posn-y w) 10))]
    [(left) (make-posn (- (posn-x w) 10) (posn-y w))]
    [(right) (make-posn (+ (posn-x w) 10) (posn-y w))]
    [else w]))

(on-key-event  
 (lambda (e w@t)   
   (let ([w@t+1 (move e w@t)]) 
     (begin (clear w@t)
            (draw w@t+1)))))

In this case, the World is a Posn, indicating the current location of our object. Every time the ``player'' presses a key on the keyboard, the event handler moves the object, naming the resulting object w@t+1. (In Scheme, we can and do use meaningful names. This one could be pronounced the world at time t+1.) Then it clears the old world and draws the new one.

;; Shot = Posn

;;  -->  Shot
(define (shot-create) (make-posn (random WIDTH) HEIGHT))

;; Shot Color  -->  true
(define (make-shot-paint shot color)
  (begin
    (draw-solid-line (make-posn (- (posn-x shot) SHOT-WIDTH) (posn-y shot))
                     (make-posn (posn-x shot) (- (posn-y shot) SHOT-HEIGHT))
                     color)
    (draw-solid-line (make-posn (+ (posn-x shot) SHOT-WIDTH) (posn-y shot))
                     (make-posn (posn-x shot) (- (posn-y shot) SHOT-HEIGHT))
                     color)))

;; Shot  -->  true
(define (shot-paint s) (make-shot-paint s SHOT-COLOR))

;; Shot  -->  true
(define (shot-erase s) (make-shot-paint s BACKGROUND))

;; Shot  -->  Shot
(define (shot-move s) (make-posn (posn-x s) (- (posn-y s) SHOT-DELTA)))

(define SHOT-HEIGHT 10)
(define SHOT-WIDTH   1)
(define SHOT-COLOR 'red)
(define SHOT-DELTA  3)

;; UFO (Listof Star) (Listof Shot)  -->  true
(define (scene-draw b s shots)
  (and (stars-paint s)
       (andmap shot-paint shots)
       (ufo-paint b)))

;; UFO (Listof Shots) -> true 
(define (scene-erase b shots)
  (and (andmap shot-erase shots) 
       (ufo-erase b)))

Figure 10:  Managing Shots

Keyboard events are a great way to enhance our UFO simulation. For example, to enable a player to shoot at the UFO, the game can interpret a key stroke on the

^
|
key as a signal to fire a shot from the ground:

;; World = (list UFO (Listof Star) (Listof Shot))

;; KeyEvent World  -->  World
(define (shoot e w) ;; KeyEvent World  -->  World
  (if (not (eq? 'up e)) 
      w 
      (let ([ufo@0 (first w)]
	    [stars (second w)]
	    [shots (third w)])
        (list ufo@0 stars (cons (shot-create) shots)) w))))

The event handler first checks what kind of event it consumed. If it the event does not represent an up-arrow key, nothing changes and it just returns the world. Otherwise, it takes apart the three-item list that represents the world, creates a shot, and adds this shot to the list of shots that already exist in the world. It returns this new world to the function that manages the iteration for future uses with event handlers.

Figure 10 contains the code that deals with individual shots. It creates shots at random locations at the bottom of the screen; a shot moves upwards in small increments; and painting and erasing a shot is done with the same function but different colors.

The bottom of the figure also shows what two functions that draw and erase entire scenes. Since they deal with an entire list of shots, they use loops to draw and erase the shots, one by one.

Last, but not least, we need to say what happens as the clock ticks:

;; World  -->  World
(define (tick w)
  (let ([ufo0 (first w)]
	[stars (second w)]
	[shots0 (third w)])
    (cond
      [(ufo-landed? ufo0) (stop-time)]
      [else 
        (let ([ufo (ufo-move ufo0)]
              [shots (map shot-move shots0)])
          (begin
            (scene-erase ufo0 shots0)
            (scene-draw ufo stars shots)
            (list ufo stars shots)))])))

Like the (keyboard) event handler, the time handler disassembles the world into its three pieces. Then it checks whether the UFO has landed. If so, everything stops. Otherwise, it moves the UFO and all the shots, erases the old scene and draws the new one. The result is the list with the new ufo, the old stars, and the new shots.

Here is how all the things fit together:

;; run program run 
(start WIDTH HEIGHT)
(background-draw)
(big-bang .05 (list (ufo-create (random WIDTH)) (stars-create 50) '()))
(on-key-event shoot)
(on-tick-event tick)

We create the canvas and draw a background. Then we set up the world, its two handlers, and that's all.

If you want to turn this program into a working and somewhat interesting game, add a function that determines whether any of the shots in the list has hit the ufo:

;; UFO (Listof Shot)  -->  Boolean
(define (hit? ufo shots)
  (ormap (lambda (s) (ufo-shot-hit ufo s)) shots))

To figure out whether an individual shot has hit a UFO, just check whether the two are close enough. Keep in mind that we represent both Shots and UFOs with Posns.

Another enhancement of interest is to have a vehicle on the ground that fire the shots. Naturally, we want to move this vehicle with the left and right arrows on the keyboard. To add this feature, you will need to modify the (keyboard) event handler.


3 In conventional languages, this function is written as if were a statement, but that doesn't make a difference.