Structural Design Recipes and Mutation, Part 1

Surprisingly, programming with mutators does not require any new design recipes--as long as the mutated fields always contain atomic values. Our receipes work perfectly fine. While the design of non-mutating programs requires the combination of values, programming with mutators requires the combination of effects. Hence the key is to add a well-formulated effect statement to a function's contract and to make up examples that illustrate the effects. We practiced both of these activities for set! expressions already in section . In this section we learn to adapt the design recipes and effect statements to structural mutations. To do that, we consider a short series of examples. Each illustrates how an applicable design recipe helps with the design of structure-modifying or vector-modifying functions.

The first example concerns the mutation of plain structures. Suppose we are given a structure and a data definition for personnel records:

(define-struct personnel (name address salary))
;; A personnel record (PR) is a structure:  
;; (make-personnel n a s) 
;; where n is a symbol, a is a string, and s is a number.  

(define (fun-for-personnel pr)
  ... (personnel-name pr) ... 
  ... (personnel-address pr) ... 
  ... (personnel-salary pr) ...)  

Consider a function for increasing the salary field:

;; increase-salary : PR number -> void
;; effect: to modify the salary field of a-pr by adding a-raise 
(define (increase-salary a-pr a-raise) ...) 

Developing examples for increase-salary requires the techniques of section . Specifcially, we must be able to compare the before and after state of some PR structure:

(local ((define pr1 (make-personnel 'Bob 'Pittsburgh 70000)))
  (begin 
    (increase-salary pr1 10000) 
    (= (personnel-salary pr1) 80000))) 

We can now use the template and the example to define the function:

;; increase-salary : PR number -> void
;; effect: to modify the salary field of a-pr by adding in a-raise 
(define (increase-salary a-pr a-raise) 
  (set-personnel-salary! a-pr (+ (personnel-salary a-pr) a-raise))) 

Exercise 41.2.1

Make up examples for increase-salary and test the function. Formulate the tests as boolean-valued expressions. Solution

Exercise 41.2.2

Adapt increase-salary such that it accepts only values for a-raise between 3% and 7% of the salary. It calls error otherwise. Solution

Exercise 41.2.3

Develop increase-percentage. The function consumes a PR and a percentage between 3% and 7%. It increases the value in the salary field of the PR by the lesser of the percentage increase or 7000. Solution

Exercise 41.2.4

Develop the function new-date. It consumes a cheerleader record and adds a date to the beginning of a list. Here are the relevant definitions:

(define-struct cheerleader (name dates))
;; A cheerleader is a structure:  
;; (make-cheerleader n d) 
;; where n is a symbol and d is a list of symbols.  

Exercise 41.2.5

Recall the structure definitions for squares:

(define-struct square (nw length))

A square is a structure: (make-square p s) where p is a posn and s is a number.

Develop the function move-square!. It consumes a square, called sq, and a number, called delta. It modifies sq by adding delta to its x coordinate.

Look up the structure and data definition for circles and develop the function move-circle, which is analogous to move-square. Solution

The second example recalls the design recipe for functions that work on unions of classes. One of our first examples of this kind concerned the class of geometric shapes. Here is the relevant data definition:

A shape is either a circle, or a square.

See exercise  or part  for the definitions of circle and square.

Following our recipe, a template for shape-processing functions consists of a two-clause cond-expression:

(define (fun-for-shape a-shape)
  (cond 
    [(circle? a-shape) ... (fun-for-circle a-shape) ...] 
    [(square? a-shape) ... (fun-for-square a-shape) ...])) 

So, suppose we wish to move a shape in the x direction by a fixed number of pixels. In part , we created a new structure for this purpose. Now we can use the mutators for circle and square structures instead--that is, the function can have an effect:

;; move-shape! : shape number -> void
;; effect: to move a-shape in the x direction by delta pixels 
(define (move-shape! a-shape) 
  (cond 
    [(circle? a-shape) (move-circle a-shape delta)] 
    [(square? a-shape) (move-square a-shape delta)])) 

Exercise 41.2.6

Make up examples for move-shape! and test the function. Formulate the tests as boolean-valued expressions! Solution

Exercise 41.2.7

The following structure definitions are to represent items that a music store sells:

(define-struct CD (price title artist))
(define-struct record (price antique title artist)) 
(define-struct DVD (price title artist to-appear)) 
(define-struct tape (price title artist)) 

Develop the program inflate!, which consumes a music-item and a percentage. Its effect is to increase the price in the given structure according to the percentage. Solution

Exercise 41.2.8

Develop a program that keeps track of the feeding of zoo animals. Our zoo has three kinds of animals: elephants, monkeys, and spiders. Each animal has a name and two feeding times per day: morning and evening. Initially a structure that represents an animal (structure) contains false in the fields for feeding times. The program feed-animal should consume a structure that represents an animal and the name of a feeding time. It should switch the corresponding field in the animal structure to true. Solution

The next two examples are about mutations when the underlying data definitions involve self-references. Self-references are needed if we wish to deal with data that has no size limit. Lists were the first class of such data we encountered and natural numbers the second one.

Let's first take a look at mutation of lists of structures, using the running data example of this part: the address book. An address book is a list of entries; for completeness, here are the structure and data definitions:

(define-struct entry (name number))

An entry is a structure: (make-entry n p) where n is a symbol and p is a number.

An address-book is the empty list, empty, or (cons an-e an-ab) where an-e is an entry and an-ab is an address book.

Only the second one is self-referential, so we focus on the template for it:

;; fun-for-ab : address-book -> XYZ
(define (fun-for-ab ab) 
  (cond 
    [(empty? ab) ...] 
    [else ... (fun-for-entry (first ab)) ... (fun-for-ab (rest ab)) ...])) 

So suppose we want a function that updates an existing entry. The function consumes an address-book, a name, and a phone number. The first entry that contains the name is modified to contain the new phone number:

;; change-number! : symbol number address-book -> void
;; effect: to modify the first entry for name in ab so that its 
;; number field is phone 
(define (change-number! name phone ab) ...) 

Here is an example:

(define ab
  (list 
    (make-entry 'Adam 1) 
    (make-entry 'Chris 3) 
    (make-entry 'Eve 2)))

(begin 
  (change-number! 'Chris 17 ab) 
  (= (entry-number (second ab)) 17)) 

The next step is to develop the function definition, using the template and the examples. Let's consider each case separately:

1. If ab is empty, name doesn't occur in it. Unfortunately, the purpose statement doesn't specify what the function should compute in this case, and there is indeed nothing sensible the function can do. To be safe, we use error to signal that no matching entry was found.
2. If ab contains a first entry, it might or might not contain name. To find out, the function must distinguish the two cases with a cond-expression:

   (cond
     [(symbol=? (entry-name (first ab)) name) ...] 
     [else ...]) 
   

   In the first subcase, the function must modify the structure. In the second, name can occur only in (rest ab), which means the function must mutate some entry in the rest of the list. Fortunately, the natural recursion accomplishes just that.

Putting everything together, we get the following definition:

(define (change-number! name phone ab)
  (cond 
    [(empty? ab) (error 'change-number! ``name not in list'')] 
    [else (cond 
            [(symbol=? (entry-name (first ab)) name) 
             (set-entry-number! (first ab) phone)] 
            [else 
             (change-number! name phone (rest ab))])])) 

Exercise 41.2.9

Define test-change-number. The function consumes a name, a phone number, and an address book. It uses change-number! to update the address book, and then ensures that it was changed properly. If so, it produces true; if not, it produces an error message. Use this new function to test change-number! with at least three different examples. Solution

Exercise 41.2.10

Develop move-squares. It consumes a list of squares, as defined above, and a number delta. The function modifies each on the list by adding delta to the x-component of its position. Solution

Exercise 41.2.11

Develop the function all-fed. It consumes a list of animals, as defined in exercise , and modifies them so that their field for morning feedings is switched to true. Solution

Exercise 41.2.12

Develop the function for-all, which abstracts move-squares and all-fed from exercises  and . It consumes two values: a function that consumes structures and produces (void); and a list of structures. Its result is (void). Solution

Exercise 41.2.13

Develop the function ft-descendants. It consumes a descendant family tree (see section ) based on the following structure definition:

(define-struct parent (children name date eyes no-descendants))

Natural numbers make up another class of values that requires a self-referential descriptions. Recursion on natural numbers per se isn't useful in conjunction with mutation, but recursion on natural numbers as indices into vectors is useful when a problem's data representation involves vectors.

Let's start with a snippet of an elevator control program. An elevator control program must know at which floor people have pressed the call buttons. We assume that the elevator hardware can mutate some status vector of booleans. That is, we assume that the program contains a vector, call it call-status, and that a field in call-status is true if someone has pushed the call button at the corresponding floor.

One important elevator operation is to reset all the buttons. For example, an operator may have to restart the elevator after it has been out of service for a while. We start the development of reset by restating the known facts in a Scheme outline:

;; call-status : (vectorof boolean)
;; to keep track of the floors from which calls have been issued  
(define call-status (vector true true true false true true true false))

;; reset : -> true 
;; effect: to set all fields in call-status to false 
(define (reset) ...) 

While it is possible to implement the service as

(define (reset)
  (set! call-status 
    (build-vector (vector-length call-status) (lambda (i) false)))) 

;; reset-aux : (vectorof boolean) N -> void
;; effect: to set the fields of v with index in [0, i) to false 
(define (reset-aux v i) 
  (cond 
    [(zero? i) ...] 
    [else ... (reset-aux v (sub1 i)) ...])) 

The effect statement suggests the following examples:

1. (reset-aux call-status 0) leaves call-status unchanged, because the purpose statement says to change all indices in [0,0) and there are none;
2. (reset-aux 1) changes call-status so that (vector-ref call-status 0) is false, because 0 is the only natural number in [0, 1);
3. (reset-aux call-status (vector-length call-status)) sets all fields of call-status to false.

Equipped with examples, we can turn our attention to the definition. The key is to remember that the additional argument must be interpreted as an index into the vector. Keeping the example and the guideline in mind, let's look at each of the two cases separately:

1. If (zero? i) holds, the function has no effect and produces (void).
2. Otherwise i is positive. In that case, the natural recursion sets all fields in call-status with an index in [0,(sub1 i)) to false. Furthermore, to complete the task, the function must set the vector field with index (sub1 i) to false. The combination of the two effects is achieved with a begin-expression that sequences the natural recursion and the additional vector-set!.

;; call-status : (vectorof boolean) ;; to keep track of the floors from which calls have been issued (define call-status (vector true true true false true true true false)) ;; reset : -> void ;; effect: to set all fields in call-status to false (define (reset) (reset-aux call-status (vector-length call-status))) ;; reset-aux : (vectorof boolean) N -> void ;; effect: to set the fields of v with index in [0, i) to false (define (reset-aux v i) (cond [(zero? i) (void)] [else (begin (vector-set! v (sub1 i) false) (reset-aux v (sub1 i)))])) Figure: Resetting call-buttons for an elevator

Exercise 41.2.14

Use the examples to develop tests for reset-aux. Formulate the tests as boolean-valued expressions. Solution

Exercise 41.2.15

Develop the following variant of reset:

;; reset-interval : N N -> void
;; effect: to set all fields in [from, to] to false 
;; assume: (<= from to) holds  
(define (reset-interval from to) ...) 

Exercise 41.2.16

Suppose we represent the position of an object with a vector and the velocity of an object with a second vector. Develop the function move!, which consumes a position vector and an equally long velocity vector. It modifies the position vector by adding in the numbers of the speed vector, field by field:

;; move! : (vectorof number) (vectorof number) -> void
;; effect: to add the fields of v to the corresponding fields of pos  
;;  
;; assumption: pos and v have equal length 
(define (move! pos v) ...) 

Exercise 41.2.17

Develop the function vec-for-all, which abstracts reset-aux and the auxiliary vector-processing function for move! from exercise . It consumes two values: a function f and a vector vec. The function f consumes indices (N) and vector items. The result of vec-for-all is (void); its effect is to apply f to each index and corresponding value in vec:

;; vec-for-all : (N X -> void) (vectorof X) -> void
;; effect: to apply f to all indices and values in vec 
;; equation:  
;; (vec-for-all f (vector v-0 ... v-N))  
;; =  
;; (begin (f N v-N) ... (f 0 v-0) (void)) 
(define (vec-for-all f vec) ...) 

The last example covers the common situation when we wish to compute several numeric values at once and place them in a vector. In section  we saw that the use of effects is on occasion useful to communicate several results. In the same manner, it is sometimes best to create a vector and to modify it within the same function. Consider the problem of counting how many times each vowel occurs in a list of letters:

;; count-vowels : (listof letter) 
;;  -> (vector number number number number number) 
;; where a letter is a symbol in 'a ... 'z 
;; to determine how many times the five vowels occur in chars 
;; the resulting vector lists the counts in the lexicographic order 
(define (count-vowels chars) ...) 

Using the purpose statement, we can also come up with examples:

  (count-vowels '(a b c d e f g h i))
= (vector 1 1 1 0 0)

  (count-vowels '(a a i u u)) 
= (vector 2 0 1 0 2) 

(define (count-vowels chars)
  (cond 
    [(empty? chars) ...] 
    [else ... (first chars) ... (count-vowels (rest chars)) ... ])) 

;; count-vowels : (listof letter) ;; -> (vector number number number number number) ;; where a letter is a symbol in 'a ... 'z ;; to determine how many times the five vowels occur in chars ;; the resulting vector lists the counts in the lexicographic order (define (count-vowels chars) (cond [(empty? chars) (vector 0 0 0 0 0)] [else (local ((define count-rest (count-vowels (rest chars)))) (begin (count-a-vowel (first chars) count-rest) count-rest))])) ;; count-a-vowel : letter -> void ;; effect: to modify counts at the appropriate place if l is a vowel, ;; none otherwise (define (count-a-vowel counts l) ...) Figure: Counting vowels

To fill the gaps in the template, we consider each of the two clauses separately:

1. If (empty? chars) is true, the result is a vector of five 0's. After all, there are no vowels in an empty list.
2. If chars isn't empty, the natural recursion counts how many vowels and which ones occur in (rest chars). To get the correct result, we also have to check whether (first chars) is a vowel, and depending on the outcome, increase one of the vector fields. Since this kind of task is a separate, repeated task, we leave it to an auxiliary function:

   ;; count-a-vowel : letter -> void
   ;; effect: to modify counts at the appropriate place if c is a vowel,  
   ;; none otherwise 
   (define (count-a-vowel counts c) ...) 
   

   In other words, the second clause first counts the vowels in the rest of the list. This computation is guaranteed to yield a vector according to the purpose statement. Let's call this vector counts. Then, it uses count-a-vowel to increase the appropriate field in counts, if any. The result is counts, after the first letter on the list has been counted.

Exercise 41.2.18

Develop the function count-a-vowel. Then test the complete count-vowels program. Solution

Exercise 41.2.19

At the end of intermezzo 5, we could have defined count-vowels as shown in figure . This version does not use vector-set!, but constructs the vector directly using build-vector.

(define (count-vowels-bv chars) (local ((define (count-vowel x chars) (cond [(empty? chars) 0] [else (cond [(symbol=? x (first chars)) (+ (count-vowel x (rest chars)) 1)] [else (count-vowel x (rest chars))])]))) (build-vector 5 (lambda (i) (cond [(= i 0) (count-vowel 'a chars)] [(= i 1) (count-vowel 'e chars)] [(= i 2) (count-vowel 'i chars)] [(= i 3) (count-vowel 'o chars)] [(= i 4) (count-vowel 'u chars)]))))) Figure: Another way of counting vowels

Measure the performance difference between count-vowels-bv and count-vowels. Hint: Define a function that generates a large list of random letters (with, say, 5,000 or 10,000 items).

Explain the performance difference between count-vowels-bv and count-vowels. Does the explanation reflect the measured difference? What does this suggest concerning the vector-set! operation? Solution

Exercise 41.2.20

Develop histogram. The function consumes a list of grades between 0 and 100; it produces a vector of size 101 where each slot contains the number of grades at that level. Solution

Exercise 41.2.21

Develop count-children. The function consumes a descendant family tree, which is a family tree that leads from a family member to the descendants. It produces a vector with six fields. The first five slots contain the number of family members that have that many children; the sixth field contains the number of family members that have five or more children. Solution