Section 34

Memory for Functions


No matter how often we use a function with one and the same argument, we always get the same result. Even an accumulator-style function produces the same result every time we apply it to the same argument, as long as the accumulator argument is also the same. Functions simply do not have any memory about their past uses.

Many programs, though, must remember something about their past uses. Recall that a program typically consists of several functions. In the past we have always assumed that there is one main function and that all others are auxiliary and invisible to the user. In some cases, however, a user may expect more than one service from a program, and each service is best implemented as a function. When a program provides more than one function as a service to the user, it is common that, for sheer convenince or possibly because we add a graphical user interface, the functions must have memory.

Because this point is difficult to grasp in the abstract, we study some examples. The first one concerns a program for managing telephone numbers in an address book. The standard address book software provides at least two services:

  1. a service for looking up the phone number of some person; and

  2. a service for adding a name and a phone number to the address book.

Based on our guidelines, the program provides two functions to the user. The user can apply those functions in DrScheme's Interactions window to appropriate data. Or, we can develop a graphical user interface with text fields and buttons so that the user doesn't need to know anything about programming. Figure 95 displays such an interface.

Figure 95:  A phonebook GUI

The two services roughly correspond to two functions:

;; lookup : list-of-symbol-number-pairs symbol  ->   number or false
;; to lookup the number associated with name in pb
;; if it doesn't find name, the function produces false
(define (lookup pb name) ...)

;; add-to-address-book : symbol number  ->  void
;; to add name and number to address-book
(define (add-to-address-book name number) ...)

  (list (list 'Adam 1)
        (list 'Eve 2)))

We also introduce a variable definition for maintaining a list of name-number associations.

The first function is a variant of our very first recursive function. A user applies it to a list of name-number associations, such as ADDRESS-BOOK, and a name. It produces a number, if the name is on the list, or false otherwise. The second function is radically different from what we have seen. The user would apply it to a name and a number; any future lookup of that name would then produce that number.

Let's imagine an interaction in DrScheme:

> (lookup ADDRESS-BOOK 'Adam)
> (lookup ADDRESS-BOOK 'Dawn)
> (add-to-address-book 'Dawn 4)
> (lookup ADDRESS-BOOK 'Dawn)

The first two confirm that 'Adam has the phone number 1 and that we don't have a phone number for 'Dawn. The third one adds the phone number 4 for 'Dawn to ADDRESS-BOOK. And the last interaction shows that the very same use of lookup as before now produces the expected phone number.

In the past, the only way we could have achieved this same effect is by editing the definition of ADDRESS-BOOK. But, we do not wish users to edit our programs. Indeed, they shouldn't even have access to our programs. We are therefore forced to provide an interface with a function that permits such changes. We could go even further and implement the graphical interface of figure 95. A dialogue equivalent to the above interaction would proceed as follows:

  1. Type Adam into the text field, click the Lookup button, and ``1'' appears in the lower text field.

  2. Enter Dawn into the text field, click the Lookup button, and some message concerning a missing number appears in the lower text field.

  3. Replace the message with ``4'' and click the Add button.

  4. Erase the ``4'' from the lower text field, click the Lookup and the ``4'' shows up again.

In short, providing a convenient interface to a user forces us to develop a program whose functions know about each other's usage history.

Figure 96:  The three stages of a traffic light canvas and its GUI

The second example, a traffic light simulation, illustrates how a single function may need to have some memory. Recall the function next from exercise 6.2.5. It consumes the current color of a traffic light and, with the help of clear-bulb and draw-bulb, switches the state of the traffic light on a canvas to the next traffic color. The result is the next color.

A user who wishes to switch the traffic light four times in a row must enter

(next (next (next (next 'red))))

into the Interactions window. An even more convenient user interface, however, would provide a button that the user can click.

Providing a button means providing a call-back function that somehow knows about the current state of the traffic light and changes it. Let's call this function next, too, but let's assume that it consumes no arguments. Here is an imaginary interaction using this function:

> (next)
> (next)
> (next)

Every time we apply next to no arguments, it produces the invisible value and simulates the switch of state in the traffic light on the canvas. In other words, the canvas cycles through the three states depicted in figure 96. Equivalently, we can have a user click the ``NEXT'' button three times, which would apply the next function and have the same visual effect. To accomplish this effect, the use of next must affect its own future uses.

Figure 97:  Three stages in the hangman game and its GUI

The final example concerns the hangman game, which is also the subject of section 6.7. The game program requires us to develop three functions: make-word, reveal, and draw-next-part. We start the game by evaluating

(hangman make-word reveal draw-next-part)

which picks a word, creates the graphical user interface of the lower half of figure 97, and draws the left-most picture in the sequence of the upper half of the figure. The player can then choose a letter from the choice menu in the GUI and click on the ``Check'' button to determine whether the letter occurs in the word. If so, the hangman function reveals where the letter occurs; if not, it uses our draw-next-part function to draw the next stage in the hangman picture. The more bad guesses the player makes, the more of the stick figure appears in the picture (see top-half of figure 97).

Our description suggests that the hangman function in the teachpack employs a callback function for the ``Check'' button. Let's call this function check. It consumes the letter and produces true if the check reveals new knowledge:

> (check 'b)

If not, because the letter has already been guessed, the function produces false to indicate that the player didn't gain new knowledge:

> (check 'b)

In this case, check also employs draw-next-part to draw another part of the hangman figure. Of course, to accomplish this, hangman and check must have some memory about how often the ``Check'' button was used and how often it was used with a negative result.

With our current knowledge of Scheme, we cannot formulate functions such as add-to-address-book, next, or check. To fill this gap in our knowledge, the next section introduces set!67 expressions. This new form of expression permits functions to change the value that a defined variable represents. Using this new construct, we can formulate Scheme functions that have memory. That is, we can define functions that know something about their history and the history of other functions.

67 This keyword is pronounced set-bang.