Section 37

Examples of Memory Usage

Designing programs with memory requires experience and practice, which, in turn, come from studying examples. In this section we study three more examples of programs that use memory. The first one illustrates the importance of initializers; the second one demonstrates how to design programs whose effects depend on conditions; and the last one shows how effects can be useful in recursive functions. The last two subsections provide opportunities for practicing what we've learned.

37.1 Initializing State

Recall the color-guessing game from exercise 5.1.5. One player picks two colors for two squares; we call those ``targets.'' The other one tries to guess which color is assigned to which square; they are guesses. The first player's response to a guess is to compare the colors and to produce one of the following answers:

'perfect!, if the first target is equal to the first guess and the second target is equal to the second guess;
'OneColorAtCorrectPosition, if the first guess is equal to the first target or the second guess is equal to the second target;
'OneColorOccurs, if either of the guesses is one of the two targets;
and 'NothingCorrect, otherwise.

These four answers are the only answers that the first player gives. The second player is to guess the two chosen target colors in as few guesses as possible.

To simplify the game, the choice of colors is limited: see the top of figure 102. Our goal is to develop a program that plays the role of the master player. That is, we want a program that picks the colors and checks the guesses of the second player.

;; Constants:

;; the legitimate colors 
(define COLORS
  (list 'black 'white 'red 'blue 'green 'gold 'pink 'orange 'purple 'navy))

;; the number of colors
(define COL# (length COLORS))

;; Data Definition:
;; A color is a symbol on COLORS.

Figure 102: Guessing colors

The game description suggests that the program must offer two services: one for setting up two target colors and another one for checking the guesses. Naturally, each service corresponds to a function. Let's call the first master and the second one master-check. Here is a possible dialogue, based on the two functions:

> (master)
> (master-check 'red 'red)
'NothingCorrect
> (master-check 'black 'pink)
'OneColorOccurs
...

> (master)
> (master-check 'red 'red)
'perfect!

The master function consumes nothing and produces the invisible value; its effect is to initialize the two targets. Depending on what the chosen colors are, checking the same two guesses may produce 'perfect! or 'NothingCorrect. In other words, master sets up some memory that master-check uses.

Let us now study how the design recipe applies to the development of the program. The first step is to define the state variables and to specify the purpose of each variable. Our analysis suggests that we need two state variables, one per target:

;; target1, target2 : color
;; the variables represent the two colors that the first player chooses
(define target1 (first COLORS))
(define target2 (first COLORS))

Both variables are set to the first item from COLORS, so that they stand for some color.

The second step is to develop an initializer for the two state variables. A single initializer is enough because the two variables go together. Indeed, the initializer is the desired master function:

;; master :  ->  void
;; effect: set target1 and target2 to randomly chosen items in COLORS
(define (master)
  (begin
    (set! target1 (list-ref COLORS (random COL#)))
    (set! target2 (list-ref COLORS (random COL#)))))

The effect comment explains how master changes the two state variables by picking an item from COLORS based on a random number between 0 and the length of COLORS.

Finally, we can turn to the functions that modify and utilize the program's memory. As it turns out, the memory isn't modified after the two target variables are initialized; it is only used to compare to the two guesses of the player. The only other service we need is master-check. It uses check-color, the solution of exercise 5.1.5, to conduct the comparison. For a summary, see figure 103, which contains the variable and function definitions that we just discussed.

;; target1, target2 : color 
;; the two variables represent the two colors that the first player chose
(define target1 (first COLORS))
(define target2 (first COLORS))

;; master :  ->  void
;; effect: set target1 and target2 to two randomly chosen items from COLORS
(define (master)
  (begin
    (set! target1 (list-ref COLORS (random COL#)))
    (set! target2 (list-ref COLORS (random COL#)))))

;; master-check : color color  ->  symbol
;; to determine how many colors at how many positions are guessed correctly
;; The function defers to check-color, the solution of exercise 5.1.5.
(define (master-check guess1 guess2)
  (check-color guess1 guess2 target1 target2))

Figure 103: Guessing colors (Part 2)

Exercise 37.1.1. Draw a diagram that shows how master and master-check interact with memory. Solution

Exercise 37.1.2. Abstract the repeated expressions in master into the function random-pick. It consumes a list and chooses a random item from that list. Then use the function to eliminate the repeated expressions in master. Solution

Exercise 37.1.3. Modify the color guessing program so that its final answer isn't just 'perfect! but a list of two items: the symbol perfect! and the number of guesses that the second player made. Start by modifying the diagram of exercise 37.1.1. Solution

Exercise 37.1.4. Modify the color guessing program so that it automatically restarts the game when a player has guessed the correct target colors. Solution

Exercise 37.1.5. Develop a graphical user interface, similar to that of the teachpack master.ss. Instead of colored buttons, use buttons labeled with the color. Show the current selection in message fields. Solution

37.2 State Changes from User Interactions

Recall the hangman game from 6.7. The goal of the game is to test a person's active vocabulary. One player thinks of a word and draws the noose of a gallows; the other player tries to guess the word, one letter at a time. For every wrong guess, the first player adds another part to the drawing (see figure 15): first the head, then the body, the arms, and the legs. If, however, the player's guess reveals new knowledge about the chosen word, the first player indicates where the the letter occurs in the word. The game is over when the second player guesses the complete word or when the first player has completed the stick figure.

;; Data Analysis and Definitions:

;; A letter is a symbol in: 'a ... 'z plus '_

;; A word is a (listof letter).

;; A body-part is one of the following symbols:
(define PARTS '(head body right-arm left-arm right-leg left-leg))

;; Constants:
;; some guessing words: 
(define WORDS 
  '((h e l l o)
    (w o r l d)
    (i s)
    (a)
    (s t u p i d)
    (p r o g r a m)
    (a n d)
    (s h o u l d)
    (n e v e r)
    (b e)
    (u s e d)
    (o k a y)
    ...
    ))

;; the number of words we can choose from 
(define WORDS# (length WORDS))

Figure 104: Hangman Basics

Figure 104 contains the data definitions for letters, words, and body-parts. In particular, PARTS not only specifies the body parts that are drawn, but also the order in which they are drawn. The figure also defines an incomplete list of words so that the hangman program can randomly pick a word for us to guess.

The random picking of words occurs at the beginning of the game, which suggests a random initialization function, similar to that of the color-guessing program in the preceding section. In contrast to the latter, the hangman program must also remember the number of guesses that a player made, because there is only a limited number of them. After 'left-leg is drawn, the game is over. Counting down the number of body parts also implies that as the program checks each guess, it must inform the player not only what the guess revealed but also which body part, if any, was lost.

Let us capture this thought in a data definition that specifies the legitimate class of responses:

A response is either

"You won"
(list "The End" word)
(list "Good guess!" word)
(list "Sorry" body-part word)

Three of the responses are lists so that the program can provide several pieces of information at once. Specifically, the first response says that filling in the guess turns the status word into the chosen word and that the player survived the game. The second response indicates the opposite; the list of available body parts is exhausted and the game is over because the player did not guess all the letters in the word. In the third case, the player's guess was successful and the second item in the list shows how much the player knows about the word. Finally, the fourth response represents a bad guess, in which case the response is a list of three items: a greeting, the lost body part, and a reminder of what the player has found about the word.

We can now imagine the role of the two services in the hangman program. The first, called hangman, picks a new word; the second, called hangman-guess, consumes a letter and produces one of the four possible responses. Here is a feasible dialogue:

> (hangman)
> (hangman-guess 'a)
(list "Sorry" 'head (list '_ '_ '_ '_ '_ '_))
> (hangman-guess 'i)
(list "Good guess!" (list '_ '_ '_ '_ 'i '_))
> (hangman-guess 's)
(list "Good guess!" (list 's '_ '_ '_ 'i '_))
> (hangman-guess 'i)
(list "Sorry" 'body (list 's '_ '_ '_ 'i '_))
...
> (hangman)
> (hangman-guess 'a)
"You won"

The dialogue consists of two rounds of hangman. They show that the results of hangman-guess depend on the prior use of hangman. Furthermore, the first round illustrates how hangman-guess applied to the same guess twice produces two different answers. This again means that hangman-guess modifies and uses memory, specifically, it counts down the body parts as the player makes useless guesses.

;; chosen-word : word
;; the word that the player is to guess
(define chosen-word (first WORDS))

;; status-word : word
;; represents which letters the player has and hasn't guessed
(define status-word (first WORDS))

;; body-parts-left : (listof body-part)
;; represents the list of body parts that are still "available"
(define body-parts-left PARTS)

;; hangman :  ->  void
;; effect: initialize chosen-word, status-word, and body-parts-left
(define (hangman)
  (begin
    (set! chosen-word (list-ref WORDS (random (length WORDS))))
    (set! status-word ...)
    (set! body-parts-left PARTS)))

Figure 105: Hangman Basics (Part 2)

In addition, the dialogue shows that the player loses a body part whenever a guess doesn't contribute any new knowledge. Consider the second guess: 'i. It occurs in the penultimate position of the word and the response of hangman-guess says so. When the player enters 'i again as the fourth guess, hangman-guess detects no progress because the positions of 'i have already been revealed. In the informal description of the game, this aspect had been left open. By putting together an example, we become aware of this ambiguity and can make a decision.

Thus far, our reasoning has revealed the need for two services and three state variables:

chosen-word, which is the word to be guessed;
status-word, which records how much of the word has been guessed;
and body-parts-left, which remembers how many and which imaginary body parts the player can still lose.

The first two variables always stand for words, as their name says. A natural value for the last one is a list of body parts; indeed, the list should always be a suffix of PARTS.

Figure 105 contains the definitions of the state variables and their purpose statements. The first two, chosen-word and status-word, are set to the first items of WORDS, so that they represent some word. The third one is set to PARTS because this list represents the entire collection of available body parts.

Next we must develop an initializer for the state variables. As in the preceding section, a single initializer suffices. It is the hangman function, and its purpose is to set up the program's memory. Specifically, it picks a word for chosen-word, and it sets status-word and body-parts-left to values that reflect that the game has just begun. The last one is easy because PARTS is the appropriate list. The initial value for status-word requires a short analysis. First, the value must be a word. Second, it must consist of as many letters as chosen-word. Finally, each of the letters is unknown, because the player hasn't made any guesses yet. Thus, the matching action is to build a word as long as chosen-word from '_.

Exercise 37.2.1. Develop the function make-status-word, which consumes a word and produces an equally long word consisting of just '_. Use the function to complete the definition of hangman in figure 105. Solution

Exercise 37.2.2. Use build-list to create the status word in a single expression. Complete the definition of hangman in figure 105. Solution

Now we are ready to deal with the most difficult part: the design of hangman-guess, a function that uses and modifies the memory. It consumes a letter and produces an answer, specifically a response, which depends on how the current value of status-word, chosen-word, and guess compare. At the same time, the function must affect the state variable status-word if the player's guess added new knowledge. If not, the function must shorten body-parts-left, the list of available body parts. The matching contract, purpose, and effect statements are as follows:

;; hangman-guess : letter  ->  response
;; to determine whether the player has won, lost, or may continue to
;; play and, if no progress was made, which body part was lost
;; effect:
;; (1) if the guess represents progress, update status-word
;; (2) if not, shorten the body-parts-left by one

We have already considered a sample dialogue that illustrates the workings of hangman-guess. By dissecting this dialogue, we can develop specific examples for hangman-guess.

The sample dialogue and the purpose/effect statements imply that the result of hangman-guess depends on whether or not the guess constitutes progress and, if not, whether or not the guess was the last one. Let's use these distinctions for the development of examples:

If status-word is (list 'b '_ '_ '_) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
 (hangman-guess 'l)
```
produces (list "Good guess!" (list 'b '_ 'l 'l)) and status-word becomes (list 'b '_ 'l 'l).
If status-word is (list 'b '_ 'l 'l) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
 (hangman-guess 'a)
```
produces "You won". The evaluation has no effect in this case.
If status-word is (list 'b '_ 'l 'l), chosen-word is (list 'b 'a 'l 'l), and body-parts-left is (list 'right-leg 'left-leg), then evaluating
```
 (hangman-guess 'l)
```
produces (list "Sorry" 'right-leg (list 'b '_ 'l 'l)) and body-parts-left becomes (list 'left-leg).
Finally, if status-word is (list 'b '_ 'l 'l), chosen-word is (list 'b 'a 'l 'l), and body-parts-left is (list 'left-leg), then evaluating
```
 (hangman-guess 'l)
```
produces (list "The End" (list 'b 'a 'l 'l)) and body-parts-left becomes empty.

The first two examples illustrate what happens when the player enters a guess that reveals new information; the last two focus on those cases where the guess contributes nothing.

The case split naturally suggests a basic template based on a distinction between the possible situations:

(define (hangman-guess guess)
  (cond
    [... ;; guess did reveal new information: 
      (cond
	[... ;; guess completed the search for the word
	 ...]
	[... ;; guess did not complete the search for the word
          (begin 
            (set! status-word ...)
	    ...)])]
    [... ;; guess did not reveal any new information: 
     (begin 
       (set! body-parts-left ...)
       ... )]))

The location of the set!-expressions in the template's nested conds specify exactly under which conditions effects happen. First, the outermost conditional distinguishes whether or not guess produces new knowledge about the hidden word; if it doesn't, the function must modify body-parts-left. Second, if guess reveals new knowledge, the function updates the status-word variable unless the player has just finished the entire word.

Because we haven't considered yet how to express these tests, we use comments to indicate what the conditions are. Let us turn to this problem first, so that we can start the function-definition step with a full-fledged template. The first missing condition concerns the question whether guess reveals new information. To this end, we must compare guess with the letters in chosen-word. This comparison should produce the new status word. Here is the specification for the auxiliary function that conducts this computation:

;; reveal-list : word word letter  ->  word
;; to compute the new status word from chosen-word,
;; status-word, and guess
(define (reveal-list chosen-word status-word guess) ...)

Fortunately, we have discussed this auxiliary function twice before (see sections 6.7 and exercise 17.6.2) and know how to define it; figure 106 contains a suitable definition. Using reveal-list, we can now formulate a condition that determines whether guess reveals new knowledge:

(equal? status-word (reveal-list status-word chosen-word guess))

The condition uses equal? to compare the current value of status-word with its new value, as computed by reveal-list. If the two lists are equal, guess doesn't produce new knowledge; otherwise it does.

The second missing condition concerns the question whether the given guess completes the search for the word. If guess is equal to all missing letters in status-word, then the player has found the complete word. Here is the corresponding condition:

(equal? chosen-word (reveal-list status-word chosen-word guess))

That is, the game is over if chosen-word is equal to the result of reveal-list.

Let's put everything together in a single template:

(define (hangman-guess guess)
  (local ((define new-status (reveal-list status-word chosen-word guess)))
    (cond
      [(equal? new-status status-word)
       (begin 
	 (set! body-parts-left ...)
	 ... )]
      [else
       (cond
	 [(equal? new-status chosen-word)
	  ...]
	 [else 
	  (begin 
	    (set! status-word ...)
	    ...)])])))

The template uses a local-expression because the result of reveal-list is used twice. Also, the two outer cond-clauses are swapped because it is more natural to write (equal? new-status status-word) than its negation. We can now turn to the function-design step.

Because the template is conditional, we develop each clause separately:

Assume that (equal? new-status status-word) evaluates to true, that is, the player made no progress. This implies that the player loses an imaginary body part. To capture this effect, the set!-expression must change the value of body-parts-left. Specifically, it must set the state variable to the rest of its current value:
```
(set! body-parts-left (rest body-parts-left))
```
The answer depends on the new value of body-parts-left. If it is empty, the game is over; the appropriate response is (list "The End" chosen-word) so that the player finds out what the chosen word was. If body-parts-left is not empty, the response is (list "Sorry" ??? status-word). The response says that guess is useless. Its last part is the current value of status-word so that the player sees what he has discovered. The ??? indicates a problem. To understand the problem, take a look at what we have:
```
(begin 
  (set! body-parts-left (rest body-parts-left))
  (cond
    [(empty? body-parts-left) (list "The End" chosen-word)]
    [else (list "Sorry" ??? status-word)]))
```
In principle, the question marks should be the body part that the player just lost to the gallows. But, because set! modifies body-parts-left, we can no longer just say (first body-parts-left). As mentioned in section 35.2, when programming with set! timing matters. We can solve the problem with a local-expression that names the first item on body-parts-left before the state variable is modified.
The second case is much simpler than the first. We distinguish two subcases:
1. If new-status is equal to chosen-word, the player has won. The response is "You won"; there is no effect.
2. If the two are not equal, the player made some progress and must be told. Furthermore, the function must keep track of the progress; a (set! status-word new-status) accomplishes this effect. The response consists of an encouragement and the new status.

Figure 106 contains the complete definition of hangman-guess.

;; hangman-guess : letter  ->  response
;; to determine whether the player has won, lost, or may continue to play
;; and, if so, which body part was lost, if no progress was made
;; effects: (1) if the guess represents progress, update status-word
;; (2) if not, shorten the body-parts-left by one 
(define (hangman-guess guess)
  (local ((define new-status (reveal-list chosen-word status-word guess)))
    (cond
      [(equal? new-status status-word)
       (local ((define next-part (first body-parts-left)))
         (begin 
           (set! body-parts-left (rest body-parts-left))
           (cond
             [(empty? body-parts-left) (list "The End" chosen-word)]
             [else (list "Sorry" next-part status-word)])))]
      [else
       (cond
         [(equal? new-status chosen-word) "You won"]
         [else 
          (begin 
            (set! status-word new-status)
            (list "Good guess!" status-word))])])))

;; reveal-list : word word letter  ->  word
;; to compute the new status word
(define (reveal-list chosen-word status-word guess)
  (local ((define (reveal-one chosen-letter status-letter)
	    (cond
	      [(symbol=? chosen-letter guess) guess]
	      [else status-letter])))
    (map reveal-one chosen-word status-word)))

Figure 106: Hangman Basics (Part 3)

Exercise 37.2.3. Draw a diagram that shows how hangman and hangman-guess interact with the state variables. Solution

Exercise 37.2.4. Formulate the four examples for hangman-guess as boolean-valued expressions that produce true if hangman-guess is correct. Develop an additional example for each case; turn these new examples into additional tests. Solution

Exercise 37.2.5. Develop a graphical user interface, similar to that of the teachpack hangman.ss. Connect the functions in this section as call-backs. Solution

Exercise 37.2.6. Modify the program so that it keeps track of all the guesses. Then, if a player enters the same guess twice for the same round of a hangman game, the response of hangman-guess is "You have used this guess before." Solution

Exercise 37.2.7. Consider the following variant of reveal-list!:

;; reveal-list! : letter  ->  void
;; effect: to modify status-word based on a comparison of chosen-word,
;; the status-word, and the player's guess
(define (reveal-list! cw sw guess)
  (local ((define (reveal-one chosen-letter status-letter)
	    (cond
	      [(symbol=? chosen-letter guess) guess]
	      [else status-letter])))
    (set! status-word (map reveal-one cw sw))))

It changes the state variable status-word to a value that is computed from the old value of status-word, chosen-word, and the guess.

Modify hangman-guess so that it works properly with the reveal-list! function. Solution

37.3 State Changes from Recursion

Functions that affect the memory of a program may not only process simple forms of data but also arbitrarily large pieces of data. To understand how this works, let us take a closer look at the purpose of reveal-list from the hangman game program.

As we have just seen, the function compares guess with each letter in chosen-word. If it is the same, guess may uncover new knowledge and is included at the appropriate position in the word; otherwise, the corresponding letter from status-word represents what the player knows.

The hangman-guess function then compares the result of reveal-list with the old value of status-word to find out whether the player uncovered new knowledge. Furthermore, the result is compared with chosen-word again if the player found new knowledge, because guess might have matched all remaining unknown letters. Clearly, both of these comparisons repeat the computations of reveal-one. The problem is that the result of reveal-one is useful to reveal-list and that the result of its individual comparisons are useful in the conditionals of hangman-guess.

We can solve the first part of the problem with the use of an additional piece of memory: a state variable that records whether reveal-one uncovers a letter. The state variable, let's call it new-knowledge, is modified by reveal-one if it determines that guess uncovers a currently hidden letter in chosen-word. The hangman-guess function can use new-knowledge to find out what reveal-one discovered.

Let us now translate our idea into new program definitions systematically. First, we need to specify the state variable and its meaning:

;; new-knowledge : boolean
;; the variable represents whether the most recent application of
;; reveal-list has provided the player with new knowledge
(define new-knowledge false)

Second, we must consider what it means to initialize the new state variable. From what we know, the state variable is used every time reveal-list is applied to guess. When the application starts, the state variable should be false; it should change to true if guess is useful. This suggests that new-knowledge is to be initialized to false every time reveal-list is applied. We can achieve this reinitialization by changing reveal-list so that it sets the state variable before it computes anything else:

;; reveal-list : word word letter  ->  word
;; to compute the new status word
;; effect: to set new-knowledge to false first
(define (reveal-list chosen-word status-word guess)
  (local ((define (reveal-one chosen-letter status-letter) ...))
    (begin
      (set! new-knowledge false)
      (map reveal-one chosen-word status-word))))

The underlined expression is the essential modification. The local expression defines the auxiliary function reveal-one and then evaluates the local's body. The first step of the body is to initialize new-knowledge.

Third, we must develop the program that modifies new-knowledge. Here the program already exists: reveal-list, so our task is to modify it in such a way that it changes the state variable appropriately. Let's describe the idea with a modified effect statement:

;; reveal-list : word word letter  ->  word
;; to compute the new status word
;; effect: 
;; (1) to set new-knowledge to false first
;; (2) to set new-knowledge to true if guess reveals new knowledge

The first part of the effect is necessary for the second one; an experienced programmer may drop it.

Next we should modify the examples for the function to illustrate what kind of effects happen. The purpose of the function is to compute the new status word by checking whether guess occurs in the chosen-word. There are two basic situations depending on whether guess reveals new knowledge or not:

If status-word is (list 'b '_ 'l 'l) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
(reveal-one chosen-word status-word 'a)
```
produces (list 'b 'a 'l 'l) and new-knowledge is true.
If status-word is (list 'b '_ '_ '_) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
(reveal-one chosen-word status-word 'x)
```
produces (list 'b '_ '_ '_) and new-knowledge is false.
If status-word is (list 'b '_ '_ '_) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
(reveal-one chosen-word status-word 'l)
```
produces (list 'b '_ 'l 'l) and new-knowledge is true.
Finally, if status-word is (list 'b '_ 'l 'l) and chosen-word is (list 'b 'a 'l 'l), then evaluating
```
(reveal-one chosen-word status-word 'l)
```
produces (list 'b '_ 'l 'l) and new-knowledge is false.

The first two examples cover the basic situations; the third one shows that if guess reveals several new positions in the word, new-knowledge also becomes true; and the last shows how guessing a letter that has been uncovered before means no new knowledge has been added.

;; reveal-list : word word letter  ->  word
;; to compute the new status word
;; effect: to set new-knowledge to true if guess reveals new knowledge
(define (reveal-list chosen-word status-word guess)
  (local ((define (reveal-one chosen-letter status-letter)
	    (cond
	      [(and (symbol=? chosen-letter guess)
		    (symbol=? status-letter '_))
	       (begin
		 (set! new-knowledge true)
		 guess)]
	      [else status-letter])))
    (begin
      (set! new-knowledge false)
      (map reveal-one chosen-word status-word))))

Figure 107: The reveal-list function

Given that we already have a function, we can skip the template step and instead focus on the question of what we need to change in the existing function. The given version of reveal-list maps reveal-one over the two words, which are lists of letters. It is reveal-one that compares guess with the letters in chosen-word and that determines whether the player has uncovered new knowledge. Hence we must modify the auxiliary function so that it recognizes when guess represents new knowledge and to set new-knowledge to true in that case.

As it is currently defined, reveal-one merely compares guess with the letters in chosen-word. It does not check whether the player discovers truly new knowledge if guess and chosen-letter are the same. The letter guess, however, represents new knowledge only if the matching letter in the status word is still '_. This suggests the two modifications shown in figure 107. That is, reveal-one changes the value of new-knowledge if, and only if, both (symbol=? chosen-letter guess) and (symbol=? status-letter '_) are true.

In summary, we can use state variables if we wish to communicate several results from one computation to distant places. For such cases, the interface of a function is under our control but we choose to design it such that the function has both a result and an effect. The proper way to achieve these combinations is to develop the computations separately and to merge them later, if necessary.

Exercise 37.3.1. Draw a diagram that shows how hangman, hangman-guess, and reveal-list interact with the state variables. Solution

Exercise 37.3.2. Turn the three examples into tests, that is, boolean-valued expressions, and test the new version of reveal-list. How many times does reveal-one modify new-knowledge for the third test case? Solution

Exercise 37.3.3. Modify hangman-guess in the hangman program to take advantage of the additional information that reveal-list provides through new-knowledge. Solution

Exercise 37.3.4. Modify the hangman program a second time to eliminate the second equal? in hangman-guess. Hint: Introduce a state variable that counts how many letters the player doesn't know yet. Solution

Let us study a second example of a function that consumes an arbitrarily large piece of data and modifies the program's memory. The example is a natural extension of the traffic light simulator in section 36. We developed two functions:

;; init-traffic-light :  ->  void 
;; effects: (1) to initialize current-color; (2) to draw traffic light

and

;; next :  ->  void
;; effects: (1) to change current-color from 'green to 'yellow, 
;; 'yellow to 'red, and 'red to 'green
;; (2) to redraw the traffic light appropriately

The first one starts the process; with the second one, we can repeatedly switch the state of the light by evaluating (next) in the Interactions window.

Typing in (next) over and over again is tiring, so it is natural to wonder how to write a program that switches the state of the traffic light 100 or 1000 or 10000 times. In other words, we should develop a program -- let's call it switch -- that consumes a natural number and that switches the light from one color to another that many times.

The function consumes a natural number and produces (void), after it succeeds in switching the traffic light a sufficient number of times. By now we can immediately write down all the basics, including the template, for a function that consumes a natural number:

;; switch : N  ->  void
;; purpose: it computes nothing of interest
;; effect: switch the traffic light n times, 
;; holding each color for three seconds
(define (switch n)
  (cond
    [(zero? n) ...]
    [else ... (switch (- n 1)) ...]))

The template is that of a conventional, structurally recursive function.

Making up an example is also straightforward. If we evaluate (switch 4), we wish to see a change from 'red to 'yellow, 'green, and 'red again, with each stage visible for three seconds.

Defining the full function based on the template is straightforward. We proceed by cases. If n is 0, the answer is (void). Otherwise, we know that

(switch (- n 1))

simulates all the necessary switching actions but one. To accomplish this one additional switch, the function must use (next) to perform all the state changes and the change of canvas and must wait three seconds. If we put everything together in a begin-expression, things happen in the right order:

(begin (sleep-for-a-while 3)
       (next)
       (switch (- n 1)))

The top of figure 108 is the complete definition for switch.

;; switch : N  ->  void
;; effect: switch the traffic light n times, holding each color for 3 seconds
;; structural recursion 
(define (switch n)
  (cond
    [(= n 0) (void)]
    [else (begin (sleep-for-a-while 3)
                 (next)
                 (switch (- n 1)))]))

;; switch-forever :  ->  void
;; effect: switch the traffic light forever, holding each color for 3 seconds
;; generative recursion 
(define (switch-forever)
  (begin (sleep-for-a-while 3)
         (next)
         (switch-forever)))

Figure 108: Two ways of switching traffic lights

An alternative is to switch the traffic light forever or at least until it breaks because of some external event. In this case, the simulator does not consume any argument and, when applied, runs forever. This is the simplest form of generative recursion we can possibly encounter:

;; switch-forever :  ->  void
;; effect: switch the traffic light forever, 
;; holding each color for 3 seconds
(define (switch-forever) 
  ...
  (switch-forever))

Because the program does not terminate under any conditions, the template contains only one recursive call. This suffices to construct an eternally looping function.

Using this template, we can define the complete function as before. Before recurring, the function must sleep and switch the light with next. We can accomplish this with a begin-expression, as shown in the bottom definition of figure 108.

In summary, when we must develop recursive functions that modify the program's memory, we choose the design recipe that best matches our situation and proceed accordingly. In particular, if the function has both an interesting purpose and an effect, as for example reveal-list, we should first develop the pure function and then add the effects later.

Exercise 37.3.5. In section 30.2, we discussed how to search for routes in simple graphs. The Scheme representation of a simple graph is a list of pairs (of symbols). The pairs specify the direct connections between the nodes in the graph. Each node is the beginning of exactly one connection, but may be the end of several such connections or none. Given two nodes in a simple graph, the problem is to find out whether one can go from the first to the second.

Recall our first attempt at a function that determines whether the route exists (see also figure 86):

;; route-exists? : node node simple-graph  ->  boolean
;; to determine whether there is a route from orig to dest in sg
;; generative recursion 
(define (route-exists? orig dest sg)
  (cond
    [(symbol=? orig dest) true]
    [else (route-exists? (neighbor orig sg) dest sg)]))

The function checks whether the origination and destination nodes are the same. If not, it generates a new problem by looking up the neighbor of the origination node in the graph.

On occasion, route-exists? fails to produce an answer if the graph contains a cycle. In section 30.2 we solved the problem with an accumulator. It is also possible to solve it with a state variable that keeps track of the origination nodes that route-exists? has visited for one particular attempt. Modify the function appropriately. Solution

Exercise 37.3.6. In section 16.2, we developed several simple models of a computer's file system. Develop the function dir-listing, which consumes a directory and produces a list of all file names in the directory and all of its subdirectories. The function also sets the state variable how-many-directories to the number of subdirectories it encounters during the process. Solution

37.4 Finger Exercises on State Changes

Exercise 37.4.1. Modify check-guess-for-list from exercise 9.5.5 so that it also counts how many times the player has clicked on the ``Check'' button of the interface. Hint: The call-back function for the button uses check-guess-for-list once per click. Solution

Exercise 37.4.2. Develop a program that manages a task queue. The program should support at least four services:

enter, which adds a task to end of the queue;
next, which determines the next task in the queue, if any;
remove, which removes the first task from the queue, if any;
and count, which computes the number of items in the queue.

A user should start the task manager with start-task-manager.

After the program is developed and tested, use gui.ss to develop a graphical user interface to the task manager. The interface should start up with a friendly message and should always display the first task in the queue and the number of items in the queue:

Unless the queue is empty, clicking the ``Next'' button should remove an item from the queue and display the first item in the remainder of the queue. If the queue is empty, clicking the ``Next'' button should have no effect.

Hint: The greeting and the year are two separate message items. Solution

Exercise 37.4.3. In section 10.3, we developed a program that moves pictures across a canvas. A picture is a list of shapes; the program consists of functions that draws, erases, and translates pictures. The main function is move (exercise 10.3.6). It consumes a picture and a number n. It produces a new picture, moved by n pixels; it also erases the original picture and draws the new one.

Develop the program drive. It draws a (fixed) picture on a canvas and permits players to move the picture left or right by a player-specified number of pixels.

Modify drive so that it also keeps track of some given amount of fuel. A move by one pixel should consume a fixed amount of fuel. Solution

Exercise 37.4.4. Modify the two functions that control the state of a single traffic light so that they control the state of the two traffic lights at an ordinary intersection. Each light can assume one of three states: 'red, 'green, and 'yellow. When one is 'green or 'yellow, the other one must be 'red.

Recall the basics about the two functions for a single traffic light:

;; init-traffic-light :  ->  void 
;; effects: (1) to initialize current-color; (2) to draw traffic light

and

;; next :  ->  void
;; effects: (1) to change current-color from 'green to 'yellow, 
;; 'yellow to 'red, and 'red to 'green
;; (2) to redraw the traffic light appropriately

Modify the basics first.

When the program is developed and tested, develop a graphical display like the following:

Use the functions init-traffic-light and next to drive the display, but keep the functions that display information separate from these two functions. Solution

Exercise 37.4.5. In sections 14.4 and 17.7 we developed an evaluator for a portion of Scheme. A typical Scheme implementation also provides an INTERACTIVE user interface. In DrScheme, the Interactions window plays this role.

An interactive system prompts the reader for definitions and expressions, evaluates them appropriately, and possibly produces some result. Definitions are added to some repository; to confirm the addition, the interactive system may produce a value like true. Expressions are evaluated relative to the definition repository. The function interpret-with-defs from section 17.7 performs this role.

Develop an interaction system around interpret-with-defs. The system should provide at least two services:

add-definition, which adds (the representation of) some function definition to the system's repository;
evaluate, which consumes (the representation of) some expression and evaluates it relative to the current repository.

If a user adds two (or more) definitions for some function f, the last addition is the one that matters. The previous ones can be ignored. Solution

37.5 Extended Exercise: Exploring Places

Figure 109: A tour of a university

Figure 110: Take the tour

Early computer games asked players to find their way through dangerous mazes and caves. The player wanders from cave to cave, finds treasures, encounters creatures of all kinds, fights, kisses, picks up energy, and eventually reaches paradise. This section lays out the basics of such a game, using our iterative approach to program design.

Our tour takes place at one of the scariest places of all: campus. A campus consists of buildings, some more dangerous than others. Each building has a name and is connected to a group of other buildings.

The player is always in a building. We refer to this building as the current location. To find out more about the location, the player can ask for a picture of the building and for the list of connections. The player can also move to one of the connected buildings by issuing a go command.

Exercise 37.5.1. Provide structure and data definitions for buildings. Include a picture field in the structure.

A campus is a list of buildings. Define a sample campus. See figure 109 for a small example. Solution

Exercise 37.5.2. Develop a program that permits a player to move through the sample campus of exercise 37.5.1. The program should support at least three services:

show-me, which produces the picture of the current location: see figure 110;
where-to-go, which produces the list of connected buildings;
go, which changes the current location of the player.

If the player issues the command (go s) and s is not connected to the current location, the function must report an error. Develop other functions as necessary or as desired. Solution

Players of early maze games could also gather objects and trade objects at the various sites. Specifically, the player had a bag for carrying objects, and each site contained objects that the player could trade for things in the bag.

Exercise 37.5.3. Modify the tour program so that each building contains one object. Furthermore, the player should have a bag that contains (at most) one object. At each location, the player can pick up an object, if the bag is empty, or swap the object in the bag for the object in the building otherwise.

Modify the program further so that the player can carry an arbitrary number of objects in the bag. Solution