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 
         
      (map reveal-one chosen-word status-word)))) 

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 

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:

1. If status-word is (list 'b '_ 'l 'l) and chosen-word is (list 'b 'a 'l 'l), then evaluating

   (reveal-one chosen-wor status-word 'a)
   

   produces (list 'b 'a 'l 'l) and new-knowledge is true.
2. If status-word is (list 'b '_ '_ '_) and chosen-word is (list 'b 'a 'l 'l), then evaluating

   (reveal-one chosen-wor status-word 'x)
   

   produces (list 'b '_ '_ '_) and new-knowledge is false.
3. If status-word is (list 'b '_ '_ '_) and chosen-word is (list 'b 'a 'l 'l), then evaluating

   (reveal-one chosen-wor status-word 'l)
   

   produces (list 'b '_ 'l 'l) and new-knowledge is true.
4. Finally, if status-word is (list 'b '_ 'l 'l) and chosen-word is (list 'b 'a 'l 'l), then evaluating

   (reveal-one chosen-wor status-word 'l)
   

   produces (list 'b '_ 'l 'l) and new-knowledge is false.

;; 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) ) (begin guess)] [else status-letter]))) (begin (set! new-knowledge false) (map reveal-one chosen-word status-word)))) Figure: 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 . 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 . We developed two functions:

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

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

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)) ...])) 

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

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

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

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 .

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 , 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 ):

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

On occasion, route-exists? fails to produce an answer if the graph contains a cycle. In section  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 , 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