Functions that Change Memory

Once we have the state variables and their initializers in place, we turn our attention to the design of functions that modify a program's memory. Unlike the functions in the preceding parts of the book, the memory-changing functions not only consume and produce data, they also affect the definitions of the state variables. We therefore speak of the EFFECT that functions have on the state variables.

;; Data Def.: A TL-color is either 'green, 'yellow, or 'red. ;; State Variable: ;; current-color : TL-color ;; to keep track of the current color of the traffic light (define current-color 'red) ;; Contract: next : -> void ;; Purpose: the function always produces (void) ;; Effect: to change current-color from 'green to 'yellow, ;; 'yellow to 'red, and 'red to 'green ;; Header: omitted for this particular example ;; Examples: ;; if current-color is 'green and we evaluate (next), then current-color is 'yellow ;; if current-color is 'yellow and we evaluate (next), then current-color is 'red ;; if current-color is 'red and we evaluate (next), then current-color is 'green ;; Template: data-directed on state-variable that is to be mutated ;; (define (f) ;;    (cond ;; [(symbol=? 'green current-color) (set! current-color ...)] ;; [(symbol=? 'yellow current-color) (set! current-color ...)] ;; [(symbol=? 'red current-color) (set! current-color ...)])) ;; Definition: (define (next) (cond [(symbol=? 'green current-color) (set! current-color 'yellow)] [(symbol=? 'yellow current-color) (set! current-color 'red)] [(symbol=? 'red current-color) (set! current-color 'green)])) ;; Tests: (begin (set! current-color 'green) (next) (symbol=? current-color 'yellow)) (begin (set! current-color 'yellow) (next) (symbol=? current-color 'red)) (begin (set! current-color 'red) (next) (symbol=? current-color 'green)) Figure: The design recipe for state variables: A complete example

Let us now take a look at the stages of our most basic design recipe and how we can accommodate effects on state variables:

Data Analysis:

Even functions that affect the state of variables consume and (possibly) produce data. Thus we still need to analyze how to represent information and, if necessary, introduce structure and data definitions.

For example, the traffic-light example benefits from the data definition for TL-color (see above).

Contract, Purpose, and Effect:

The first major change concerns the second step. In addition to specifying what a function consumes and produces, we must also write down which variables it affects and how it affects those state variables. The effect of a function on state variables must be consistent with the purpose statement of a variable.

Consider the traffic-light example again. It requires a function that switches the color of the traffic light in accordance with the traffic laws. The function checks the variable current-color and affects its state. Here is how we should specify this function:

;; next : -> void
;; effect: to change current-color from 'green to 'yellow,  
;; 'yellow to 'red, and 'red to 'green 
(define (next) ...) 

The function consumes no data and always produces the invisible value; in Scheme this value is called void. Because the function has no purpose in the traditional sense, it is accompanied by an effect statement only.

Here is the specification for add-to-address-book:

;; add-to-address-book : symbol number -> void
;; effect: to add (list name phone) to the front of address-book 
(define (add-to-address-book name phone) ...) 

We can tell from the effect statement that the definition of address-book is modified in a fashion that's coherent with its purpose statement and contract.

Program Examples:

Examples are as important as ever, but formulating them has become more difficult. As before, we must develop examples that illustrate the relationship between inputs and outputs, but, because functions now have effects, we also need examples that illustrate those.

Let us return to our first running example, the next function for traffic lights. It affects one state-variable: current-color. Because this variable can stand for one of three symbols, we can actually characterize all of its possible effects with examples:

;; if current-color is 'green and we evaluate (next), 
;; then current-color is 'yellow afterwards 

;; if current-color is 'yellow and we evaluate (next), 
;; then current-color is 'red afterwards 

;; if current-color is 'red and we evaluate (next), 
;; then current-color is 'green afterwards 

In contrast, the state variable address-book can stand for an infinite number of values, so it is impossible to make up a comprehensive series of examples. But it is still important to state a few, because examples make it easier to develop the function body later:

;; if address-book is empty and 
;; we evaluate (add-to-address-book 'Adam 1),  
;; then address-book is (list (list 'Adam 1)) afterwards.  

;; if address-book is (list (list 'Eve 2)) and 
;; we evaluate (add-to-address-book 'Adam 1),  
;; then address-book is (list (list 'Adam 1) (list 'Eve 2)) afterwards.  

;; if address-book is (list E-1 ... E-2) and 
;; we evaluate (add-to-address-book 'Adam 1),  
;; then address-book is (list (list 'Adam 1) E-1 ... E-2) afterwards.  

Not surprisingly, the language of examples involves words of a temporal nature. After all, assignments emphasize the notion of time in programming.

Warning: The state variable is never a parameter of a function. 

The Template:

The template for state-changing functions is like that of an ordinary function, but the body should also contain set! expressions to specify the state variables that are to be modified:

(define (fun-for-state-change x y z)
  (set! a-state-variable ...)) 

The computation of the next value for a-state-variable can be left to an auxiliary function, which consumes x, y, and z. Our two examples fit this pattern.

On occasion, we should add selector and cond-expressions, based on the data definitions for the function's inputs. Consider next again. The data definition for its input suggests a cond-expression:

(define (next)
  (cond 
    [(symbol=? 'green current-color) (set! current-color ...)] 
    [(symbol=? 'yellow current-color) (set! current-color ...)] 
    [(symbol=? 'red current-color) (set! current-color ...)])) 

In this simple case, we can indeed go with either alternative and design a proper program.

The Body:

As always, the development of the full function requires a solid understanding of the examples, of how they are computed, and of the template. For functions with effects, the completion of the set! expression is the most demanding step. In some cases, the right-hand side involves nothing but primitive operations, the function's parameters, and the state variable (or several of them). In others, it is best to develop an auxiliary function (without effect) that consumes the current value of the state variable and the function's parameters and that produces the new value of the state variable.

The function add-to-address-book is an example of the first kind. The right-hand side of the set!-expression consists of address-book, cons, list, and nothing else.

The traffic-light example, in contrast, is an example for both choices. Here is a definition that is based on the template:

(define (next)
  (cond 
    [(symbol=? 'green current-color) (set! current-color 'yellow)] 
    [(symbol=? 'yellow current-color) (set! current-color 'red)] 
    [(symbol=? 'red current-color) (set! current-color 'green)])) 

Writing one based on an auxiliary function is also straightforward:

(define (next)
  (set! current-color (next-color current-color))) 

For the definition of next-color, see page .

Testing:

In the past, we have tested functions by translating the examples into boolean-valued expressions and by adding them to the bottom of the Definitions window. For functions with effects, we use a similar approach, but to verify that functions have the desired effect on state variables is a complex task.

There are two ways to test functions with efffects. First, we can set the state variable into a desired state, apply the function, and then check whether the functions has the desired result and effect. The next function is a particular good one for this approach. We characterized its complete behavior with three examples. All three can be translated into begin-expressions that test as suggested. Here is one example:

(begin (set! current-color 'green)
       (next) 
       (symbol=? current-color 'yellow)) 

Each line sets the state variable current-color to the desired color, evaluates (next), and then checks whether the effect is appropriate. We can also do this for the add-to-address-book function, though the tests are less comprehensive than those for next:

(begin (set! address-book empty)
       (add-to-address-book 'Adam 1) 
       (equal? '((Adam 1)) address-book)) 

In this test, we check only that Adam and 1 are properly added to the initially empty list.

Second, we can capture the value of a state variable before it is tested, apply the memory-changing function, and then conduct appropriate tests. Consider the following expression:

(local ([define current-value-of address-book])
  (begin 
    (add-to-address-book 'Adam 1) 
    (equal? (cons (list 'Adam 1) current-value-of) address-book))) 

It defines current-value-of to be the value of address-book at the beginning of the evaluation, and at the end checks that the appropriate entry was added at the front and that nothing changed for the rest of the value.

To conduct tests for functions with effects, especially tests of the second kind, it is useful to abstract the test expression into a function:

;; test-for-address-book : symbol number -> boolean
;; to determine whether add-to-address-book has the appropriate 
;; effect on address-book and no more than that 
;; effect: same as (add-to-address-book name number) 
(define (test-for-address-book name number) 
  (local ([define current-value-of address-book]) 
    (begin 
      (add-to-address-book name number) 
      (equal? (cons (list name number) current-value-of) 
              address-book)))) 

Using this function, we can now easily test add-to-address-book several times and ensure for each test that its effects are appropriate:

 
(and (test-for-address-book 'Adam 1) 
     (test-for-address-book 'Eve 2) 
     (test-for-address-book 'Chris 6145384)) 

The and-expression guarantees that the test expressions are evaluated in order and that all of them produce true.

Future Reuse:

Once we have a complete, tested program, we should remember its existence, what it computes, and what its effects are. We do not, however, need to remember how it computes. If we encounter a situation that calls for the same computation and the same effects, we can reuse the program as if it were a primitive operation. Warning: In the presence of effects, it is much more difficult to reuse a function than in the world of algebraic programs.

;; Data Def.: lists of arbitrary length: (listof X), lists of two items: (list Y Z) ;; State Variable: ;; address-book : (listof (list symbol number)) ;; to keep track of pairs of names and phone numbers (define address-book empty) ;; Contract: add-to-address-book : symbol number -> void ;; Purpose: the function always produces (void) ;; Effect: to add (list name phone) to the front of address-book ;; Header: ;; (define (add-to-address-book name phone) ...) ;; Examples: ;; if address-book is empty and we evaluate ;; (add-to-address-book 'Adam 1), address-book is (list (list 'Adam 1)). ;; if address-book is (list (list 'Eve 2)) and we evaluate ;; (add-to-address-book 'Adam 1), address-book is (list (list 'Adam 1) (list 'Eve 2)). ;; if address-book is (list E-1 ... E-2) and we evaluate ;; (add-to-address-book 'Adam 1), address-book is (list (list 'Adam 1) E-1 ... E-2). ;; Template: omitted ;; Definition: (define (add-to-address-book name phone) (set! address-book (cons (list name phone) address-book))) ;; Tests: (begin (set! address-book empty) (add-to-address-book 'Adam 1) (equal? '((Adam 1)) address-book)) Figure: The design recipe for state variables: A second example

Exercise 36.4.1

Modify the traffic light program in figure  to draw the current state of the traffic light onto a canvas. Start by adding the initializer. Use the solutions for section . Solution

Exercise 36.4.2

Modify the phone book program in figure  so that it offers a graphical user interface. Start by adding the initializer. Use the solution of exercise . Solution