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:
We must determine that a program requires memory.
We must identify the data that goes into the memory.
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.
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.
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
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
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.
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
From the contract for the state variable, we can conclude that the following assignment is nonsensical:
(set! address-book 5)
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
stands for a list of lists,
(cons (list 'Adam 1) address-book)
constructs a longer list of the right kind. Hence the
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:
'yellow, which suggests a data definition:
A TL-color is either
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
(set! current-color (next-color current-color))
current-color is one of the three legitimate symbols,
we can apply
next-color to the value of
The function also produces one of these three symbols, so that the next
current-color is again proper.
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
or an INITIALIZER. A program's
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))
'red, we follow a
conventional rule of engineering to put devices into their least harmful
state when starting it up.70
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.
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.
Let us now take a look at the stages of our most basic design recipe and how we can accommodate effects on state variables:
For example, the traffic-light example benefits from the data definition
TL-color (see above).
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
'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
Here is the specification for
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.
Let us return to our first running example, the
next function for
traffic lights. It affects one state-variable:
Because this variable can stand for one of three symbols, we can actually
characterize all of its possible effects with examples:
'greenand we evaluate
(next), ;; then
'yellowand we evaluate
(next), ;; then
'redand we evaluate
(next), ;; then
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:
emptyand ;; we evaluate
(add-to-address-book 'Adam 1), ;; then
(list (list 'Adam 1))afterwards.
(list (list 'Eve 2))and ;; we evaluate
(add-to-address-book 'Adam 1), ;; then
(list (list 'Adam 1) (list 'Eve 2))afterwards.
(list E-1 ... E-2)and ;; we evaluate
(add-to-address-book 'Adam 1), ;; then
(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.
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
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
again. The data definition for its input suggests a
(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.
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.
add-to-address-book is an example of the first
kind. The right-hand side of the set!-expression consists of
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
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
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
(next), and then checks whether the effect is
appropriate. We can also do this for the
function, though the tests are less comprehensive than those for
(begin (set! address-book empty) (add-to-address-book 'Adam 1) (equal? '((Adam 1)) address-book))
In this test, we check only that
1 are properly
added to the initially
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)))
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-bookhas the appropriate ;; effect on
address-bookand 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
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
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.
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
70 A device should also go into the least harmful state when it detects an internal failure. Unfortunately, many software engineers don't follow this rule.