Section 36

Designing Functions with Memory

Section 34 motivated the idea of functions with memory; section 35 explained how variable definitions and set! together can achieve the effect of memory. It is now time to discuss the design of programs with memory.

Designing functions with memory requires three important steps:

1. We must determine that a program requires memory.

2. We must identify the data that goes into the memory.

3. We must understand which of the services are supposed to modify the memory and which are to use the memory.

The need for the first step is obvious. Once we know that a program requires memory, we must conduct a data analysis for the program's memory. That is, we must figure out what kind of data the program puts into memory and retrieves from there. Finally, we must carefully design those functions for the program that change the memory. The others are those that use the variables (without modification); they are typically designed with one of the recipes we have already discussed.

36.1  The Need for Memory

Programs need memory because we want them to work with users who know little or nothing about programming. Even if we wanted users to employ DrScheme's Interactions window, we would organize our programs so that each service corresponds to a function and the functions collaborate through memory. With graphical user interfaces, we are almost forced to think of programs as a collection of collaborating functions attached to various widgets in a window. Finally, even programs that work in physical devices such as elevators or VCRs are forced to interact with the device in some fixed way, and that often includes keeping around information about the history of device-program interactions. In short, the interface between the program and the rest of the world dictates whether a program needs memory and what kind of memory it needs.

Fortunately it is relatively easy to recognize when programs need memory. As discussed already, there are two situations. The first involves programs that provide more than one service to users. Each service corresponds to a function. A user may apply these functions in DrScheme's Interactionswindow, or they may be applied in response to some user action in a graphical user interface. The second involves a program that provides a single service and is implemented with a single user-level function. But the program may have to produce different answers when it is applied to the same arguments.

Let us take a look at some concrete examples for each situation. Software for managing an address book is a classical example of the first kind. In sections 34 and 35, we saw how one function adds entries to the address book and another looks them up. Clearly, the use of the ``addition service'' affects future uses of the ``lookup service'' and therefore requires memory. Indeed, the memory in this case corresponds to a natural physical object: the address book that people used to keep before there were electronic notebooks.

Figure 99:  Organizational charts for programs with memory

Next, consider a warehouse with a clerk that registers the items that people deliver and pick up. Every time someone delivers an item, the clerk enters it into a ledger; an inquiry for a specific item triggers a search in the ledger; when someone picks up an item, the clerk removes it from the ledger. If we were to provide a function for managing the ledger, the program would have to offer three services: one for entering items, one for searching in the ledger, and one for removing entries from the ledger. Of course, we can't remove something that isn't in the warehouse, so the program must ensure that the two services interact properly. The memory in this program will be similar to the ledgers that warehouse clerks use (or used), that is, a physical object.

The second class of memory need also has classical examples. The traffic light simulation mentioned in section 34 is one of them. Recall that the description of the program next says that every time it is applied, it redraws the picture on a canvas according to the common traffic rules. Because two evaluations of (next) in a row produce two different effects, this program needs memory.

For another example, take a look at the Scheme function random. It consumes a natural number n > 1 and produces a number between 0 and n - 1. If we evaluate (random 10) twice in a row, we may or may not obtain the same digit. Again, to achieve this effect, the implementor of random needed to equip the function with some memory.

In general, as we analyze a problem statement, we should draw organization charts. Figure 99 contains sample charts for the phone-book and the traffic-light programs. They represent each service that the program is to support with a rectangular box. Arrows going into the box indicate what kind of data a service consumes; outgoing arrows specify the output. Memory is represented with circles. An arrow from a circle to a box means that the service uses the memory as an input; an arrow to a circle means that the service changes the memory. The two charts show that services commonly use memory and change it.

36.2  Memory and State Variables

Memory is implemented with variable definitions. The memory-using programs we have seen use a single variable to represent the memory of a function. In principle, a single variable is enough to implement all memory needs, but this is usually inconvenient. Typically, the memory analysis suggests how many variables we need and which services need which variables. When memory changes, the corresponding variables assume a new value or, put differently, the state of the variable declaration changes and reflects the memory change over time. We therefore refer to variables that implement memory as STATE VARIABLES.

Every service in a program corresponds to a function that may employ auxiliary functions. A service that changes the memory of a program is implemented with a function that uses set! on some of the state variables. To understand how a function should change a state variable, we need to know what kind of values the variable may represent and what its purpose is. In other words, we must develop a contract and a purpose statement for state variables in the same manner in which we develop contracts and purpose statements for function definitions.

Let us take a look at the address-book and the traffic-light examples. The first one has one state variable: address-book. It is intended to represent a list of entries, where each entry is a list of two items: a name and a number. To document that address-book may represent only such lists, we add a contract as follows:

;; address-book : (listof (list symbol number))
;; to keep track of pairs of names and phone numbers
(define address-book empty)

By the definition of (listof X), it is permissible to use empty as the initial value of address-book.

From the contract for the state variable, we can conclude that the following assignment is nonsensical:

(set! address-book 5)

It sets address-book to 5, which is not a list. The expression therefore violates the state variable's contract. But

(set! address-book empty)

is proper, because it sets address-book back to its initial value. Here is a third assignment:

(set! address-book (cons (list 'Adam 1) address-book))

It helps us gain some understanding of how functions can change the value of address-book in a useful manner. Because address-book stands for a list of lists, (cons (list 'Adam 1) address-book) constructs a longer list of the right kind. Hence the set! expression just changes the state variable to stand for a different value in the class of (listof (list symbol number)).

A program that controls a traffic light should have a state variable for the current color of the traffic light. This variable should assume one of three values: 'red, 'green, or 'yellow, which suggests a data definition: A TL-color is either 'green, 'yellow, or 'red.

Here is the variable definition with a contract and purpose statement:

;; current-color : TL-color
;; to keep track of the current color of the traffic light
(define current-color 'red)

As before, the expression

(set! current-color 5)

is nonsensical because 5 is not one of the three legitimate symbols mentioned in the contract. In contrast,

(set! current-color 'green)

is perfectly okay.

The right-hand side of an assignment does not have to consist of a value or an expression that almost instantaneously produces a value. In many cases it makes sense to use a function to compute the new value. Here is a function that computes the next color for our traffic light:

;; next-color : TL-color  ->  TL-color
;; to compute the next color for a traffic light 
(define (next-color c)
  (cond
    [(symbol=? 'red c) 'green]
    [(symbol=? 'green c) 'yellow]
    [(symbol=? 'yellow c) 'red]))

Using this function, we can now write an assignment that switches the state of current-color appropriately:

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

Because current-color is one of the three legitimate symbols, we can apply next-color to the value of current-color. The function also produces one of these three symbols, so that the next state of current-color is again proper.

36.3  Functions that Initialize Memory

After we have developed contracts and purpose statements for the state variables of a program, we immediately define a function that sets the state variables to proper values. We call this function an INITIALIZATION FUNCTION or an INITIALIZER. A program's initializer is the first function that is used during an execution; a program may also provide other means to invoke the initializer.

For our current examples, the initializers are straightforward. Here is one for the address-book example:

;; init-address-book :  ->  void 
(define (init-address-book)
  (set! address-book empty))

The one for traffic-light is equally trivial:

;; init-traffic-light :  ->  void 
(define (init-traffic-light)
  (set! current-color 'red))

In setting current-color to 'red, we follow a conventional rule of engineering to put devices into their least harmful state when starting it up.⁷⁰

At first glance, these initializers don't seem to add much to our programs. Both set the respective state variables to the values that are their defined values. For both cases, however, it is easy to see that the initializer could do some additional useful work. The first one, for example, could create and display the graphical user interface for an address book; the second one could create and display a canvas that displays the current state of the traffic light.

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

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 45.

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 effects. First, we can set the state variable into a desired state, apply the function, and then check whether the function has the desired result and effect. The next function is a particularly 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.

Figures 100 and 101 summarize our two running examples; the header in the first one is omitted because it is useless for the purpose and effect statements in this particular case.

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

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

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