Section 39


When we design a program to control a traffic light, we probably don't want to control just one traffic light, but several. Similarly, when we design a program to manage names and phone numbers, we might wish to manage several address books, not just one. Of course, we could copy the code for a traffic light controller (or an address book manager) and rename the state variables, but copying code is bad. Furthermore, we might wish to create so many traffic lights that copying code is plain impractical.

The proper solution is to use the power of abstraction. Here we abstract over several instances of the address book program and the traffic light program and so on. This differs from the notion of abstraction in part IV because it involves state variables, but the idea and even the technique is the same. We encapsulate the state variables and the functions in a local-expression and thus give ourselves the power to create as many versions as necessary. We learn how to encapsulate state variables in the first subsection, and practice it in the second one.

39.1  Abstracting with State Variables

Suppose we wish to turn the program in figure 100 (page 45) into a program for managing (simulated) traffic lights. An operator of the simulation should be able to control each traffic light independently of the others. Indeed, the operator should be able to add or shut down traffic lights while the rest of the system remains unchanged and running.

Based on our experience, we know that each traffic light in the simulation requires two definitions:

  1. a state variable, current-color, which keeps track of the light's current color; and

  2. a service function, next, which switches the traffic light to the next color according to the traffic laws.

For a graphical simulation, the service function would also redraw the traffic light so that users can view the current color. Finally, each traffic light has a unique location on the canvas:

[Multiple Traffic Lights]

The sample program of figure 100 deals with a single traffic light and lacks the drawing operation. The problem now is to turn this into a program that can create as many traffic lights as needed, each with its own state variables and switching functions and at its own location. If we were to copy the definitions in figure 100 and add definitions for dealing with the canvas, the various instances would differ in only one aspect: the data concerning the location of the traffic light. This thought experiment suggests that we should develop an abstract function that creates and manages traffic lights at various locations.

Because the original program consists of several top-level definitions, we use the recipe of section 22.2, which suggests wrapping the definitions in a local-expression inside a function. When local definitions include state variables, as in this example, we prefer to say that we ENCAPSULATE definitions. This terminology emphasizes that the abstract function hides the state variables from other parts of the program. In particular, it implies that by putting a state variable in a local-expression we guarantee that it can change only according to the managed services, not by arbitrary assignments. Still, the definition encapsulates and abstracts at the same time, and a programmer must keep this in mind.

;; View:
;; draw-light : TL-color number  ->  true
;; to (re)draw the traffic light on the canvas 
(define (draw-light current-color x-posn) ...))

;; Model:
;; make-traffic-light : symbol number  ->  ( ->  true)
;; to create a red light with (make-posn x-posn 0) as the upper-left corner
;; effect: draw the traffic light on the canvas
(define (make-traffic-light street x-posn)
  (local (;; current-color : TL-color
          ;; to keep track of the current color of the traffic light
          (define current-color 'red)
	  ;; init-traffic-light :  ->  true
	  ;; to (re)set current-color to red and to (re)create the view 
	  (define (init-traffic-light)
	      (set! current-color 'red)
	      (draw-light current-color x-posn)))
          ;; next :  ->  true
          ;; effect: to change current-color from 'green to 'yellow, 
          ;; 'yellow to 'red, and 'red to 'green
          (define (next)
              (set! current-color (next-color current-color))
              (draw-light current-color x-posn)))
          ;; next-color : TL-color  ->  TL-color
          ;; to compute the successor of current-color based on the traffic laws
          (define (next-color current-color)
              [(symbol=? 'green current-color) 'yellow]
              [(symbol=? 'yellow current-color) 'red]
              [(symbol=? 'red current-color) 'green])))
      ;; Initialize and produce next

Figure 113:  Managing multiple traffic lights

The next step is to consider what this function should do, that is, what it should consume, what it should produce, and what effects it should have, if any. Let's start with the name. We call the new function make-traffic-light; after all, making a simulated traffic light is the purpose of the abstracted program. Furthermore, according to our abstraction recipes, an abstraction must consume values that represent the unique aspects of an instance. The unique aspect of a traffic light is its position on the canvas; for clarity, let's add a physical address, too.

Every use of make-traffic-light should create a traffic light and enable the operator to switch it from one state to the next. The first part suggests an effect. Specifically, the function should initialize the state variable and draw the initial state of the traffic light at the designated position on the canvas. The second part of the statement suggests a result: a function for switching the state of the traffic light.

Figure 113 contains the outline of the traffic simulator, including the complete definition of make-traffic-light. The simulator consists of a model and a view. The model is make-traffic-light. The view is called draw-light and is only sketched; the full definition of the view is left as an exercise.

The definition of make-traffic-light is an ordinary function definition. It uses a local definition to set up the single state variable, the initializer, and the state-changing function. The body of the local-expression uses the initializer and then produces next as the function's value.

Using make-traffic-light we can create several individual traffic lights or entire collections of them. We could also add lights as time goes by. First, we create a sufficiently large canvas:

;; create the canvas first 
(start 300 160)

Second, we apply make-traffic-light as often as needed:

;; lights : (listof traffic-light)
;; to manage the lights along Sunrise 
(define lights
  (list (make-traffic-light 'sunrise@rice 50)
        (make-traffic-light 'sunrise@cmu 150)))

Here we define lights to be a list of two traffic lights. Each traffic light is a function, so lights stands for a list of two functions.

After creating the traffic lights, we can change their states as desired. To do so, we must keep in mind that each traffic light is represented by a function that consumes nothing and produces true. Its effect is to change the hidden state variable and the drawing on the canvas. In our running example, we could use the Interactions window as follows:

> ((second lights)) 
> (andmap (lambda (a-light) (a-light)) lights)

The first interaction extracts the second item from lights and applies it. This sets the light at 'sunrise@cmu to green. The second one switches the state of all items on lights.

Each application of make-traffic-light turns variants of the local definitions into top-level definitions, after renaming them. Because the above define contains two applications of make-traffic-light, it creates two copies of each locally defined function and state variable during an evaluation:

;; definitions for 'sunrise@rice
(define current-color@rice 'red)

(define (init-traffic-light@rice) 
    (set! current-color@rice 'red)
    (draw-light current-color@rice 50)))

(define (next@rice) ...)

(define (next-color@rice current-color) ...)

;; definitions for 'sunrise@cmu (define current-color@cmu 'red) (define (init-traffic-light@cmu) (begin (set! current-color@cmu 'red) (draw-light current-color@cmu 150))) (define (next@cmu) ...) (define (next-color@cmu current-color) ...) (define lights (list next@rice next@cmu))

The new top-level definitions of init-traffic-light show how the renaming ensures that one of them takes care of 'sunrise@rice and the other one of 'sunrise@cmu.

Exercise 39.1.1.   What is the effect of the second interaction above?    Solution

Exercise 39.1.2.   Fill in the bodies of next@rice and next@cmu in the hand-evaluated program. Then evaluate ((second lights)) in the context of these definitions.    Solution

Exercise 39.1.3.   Develop the function draw-light. It realizes the view part of the traffic light simulation in figure 113. Each traffic light should be as tall as the canvas, delineated by solid lines on the left and right. The suggested dimensions of a single light are

(define WIDTH 50)
(define RADIUS 20)
;; the minimum canvas height
(define HEIGHT 
     (* 2 RADIUS)
     (* 2 RADIUS)
     (* 2 RADIUS)

Develop the necessary definitons separate from the rest of the traffic light program, then create a single function definition using local.    Solution

Now suppose we wish to provide the additional service of resetting an individual traffic light. That is, in addition to switching from the current color to the next, an operator should be able to set a traffic light to red. The function for doing so already exists: init-traffic-light. It sets current-color to 'red and redraws the image on the canvas. But, init-traffic-light is inaccessible because it is defined within the local-expression of make-traffic-light. If we wish the function to be visible, it must be the result of make-traffic-light just like next.

;; make-traffic-light : symbol number  ->  (symbol  ->  true)
;; to create a red light with (make-posn x-posn 0) as the upper-left corner
;; effect: draw the traffic light on the canvas
(define (make-traffic-light street x-posn)
  (local (;; Model:
          ;; current-color : TL-color
          ;; to keep track of the current color of the traffic light
          (define current-color 'red)
	  ;; init-traffic-light :  ->  true
	  ;; to (re)set current-color to red and to (re)create the view 
	  (define (init-traffic-light) ...)
          ;; next :  ->  true
          ;; effect: to change current-color from 'green to 'yellow, 
          ;; 'yellow to 'red, and 'red to 'green
          (define (next) ...)
          ;; next-color : TL-color  ->  TL-color
          ;; to compute the successor of current-color based on the traffic laws
          (define (next-color current-color) ...)
	  ;; service-manager : (symbol  ->  true)
	  ;; to apply either next or init-traffic-light
	  (define (service-manager msg)
	      [(symbol=? msg 'next) (next)]
	      [(symbol=? msg 'reset) (init-traffic-light)]
	      [else (error 'traffic-light "message not understood")])))
      ;; Initialize and produce service-manager

Figure 114:  Managing multiple traffic lights with a reset service

To make both next and init-traffic-light a result of make-traffic-light requires some way of combining the two functions into a single value. Since functions are values in Scheme, we could combine the two functions in a list, a structure, or even a vector. Another possibility is to combine the two functions in a third function. Here we discuss this third possibility because it is an important technique in the context of managing state variables and services.

We call the new kind of function service-manager, because it hides and manages functions that implement services. The function accepts two symbols:

  1. 'next, which indicates that (next) should be evaluated, and

  2. 'reset, which indicates that (reset) should be evaluated.

Furthermore, the function is the result of the revised version of make-traffic-light.

Figure 114 contains the modified definition of make-traffic-light. Since an operator may mistakenly apply functions to inappropriate arguments, service-manager is a checked function in the sense of section 7.5. It signals an error if the input is a symbol other than 'next or 'reset.

We use the new make-traffic-light function exactly like the old one:

;; create the canvas first 
(start 300 160)

;; lights : (listof traffic-light)
;; to manage the lights along Sunrise 
(define lights
  (list (make-traffic-light 'sunrise@rice 50)
        (make-traffic-light 'sunrise@cmu 150)))

The result, however, is that now every traffic light is represented as a function on symbols:

> ((second lights) 'next) 
> (andmap (lambda (a-light) (a-light 'reset)) lights)

The first interaction switches the initially red light labeled 'sunrise@cmu to 'green. The second one changes the state of every light back to 'red skipping the 'yellow stage for the light at 'sunrise@cmu.

Exercise 39.1.4.   Complete the definition of the program in figure 114, using the function from exercise 39.1.3. Then use DrScheme's Interactions window to switch and reset traffic lights.    Solution

Exercise 39.1.5.   Evaluate the above program by hand and confirm that the light labeled 'sunrise@rice switches from 'green directly back to 'red.    Solution

For the address-book example from part VII, the need for managing two services is even more apparent. After all, the motivating idea behind the example is that users can access one state variable with two different services: add-to-address-book for adding new entries and lookup for looking up the phone number for a given name. Following our encapsulation recipe, we must

  1. define a function make-address-book whose body is a local-expression;

  2. place the definitions in this local-expression; and

  3. introduce a function called service-manager to manage the two services.

By now, we have the first two steps firmly under control; the last one, however, is complex here, because unlike in the previous case, the two functions that implement the services consume different numbers of arguments and produce different kinds of results.

Let's first agree on the inputs for service-manager. Two good mnemonic symbols are 'add for adding phone numbers and 'search for looking up the number for some given name. This suggests the following template:

(define (service-manager msg)
    [(symbol=? msg 'add) ... A ...]
    [(symbol=? msg 'search) ... B ...]
    [else (error 'address-book "message not understood")]))

The problem is that it is not clear how to replace A and B with valid Scheme expressions that compute the appropriate value and effect. For A, we need not only msg but also a name and a phone number. For B, we need the name.

One solution is to produce functions that consume the additional arguments and then perform the appropriate computation. In other words, service-manager is now a function that produces a function for two symbols. Since we have not encountered this kind of result before, we introduce a new form of data definition:

An address-book is an interface:

  1. 'add :: symbol number  ->  void

  2. 'search :: symbol  ->  number

The data definition refers to the concept of INTERFACE, which is a function that consumes a finite number of symbols and produces functions with different types in return. Because this kind of function is radically different from what we have seen before, we use a different name.

Now it is possible to write a contract and a purpose statement:

;; service-manager : address-book
;; to manage addition to, and searches in, the address book 
(define (service-manager msg) ...)

To define the function, we distinguish the two cases. In the case of 'add, it is obvious what we produce: add-to-address-book.

In the case of 'search, we need a function that consumes a symbol and then applies lookup to this symbol and the locally defined address-book. Using lambda, we can create such a function on the fly:

(lambda (name) 
  (lookup name address-book))

Since the function is a value, it is the natural answer to 'search.

;; make-address-book : string  ->  address-book
;; to create a function that manages all the services for a hidden address book
(define (make-address-book title)
  (local ((define-struct entry (name number))
	  ;; address-book : (listof (list name number))
	  ;; to maintain a list of name-phone number associations
	  (define address-book empty)
          ;; add-to-address-book : symbol number void
	  ;; effect: to add a name-phone number association to address-book
          (define (add-to-address-book name phone)
            (set! address-book (cons (make-entry name phone) address-book)))
          ;; lookup : symbol (listof (list symbol number))  ->  number or false
          ;; to lookup the phone number for name in address-book
          (define (lookup name ab)
              [(empty? ab) false]
              [else (cond
                      [(symbol=? (entry-name (first ab)) name)
		       (entry-number (first ab))]
                      [else (lookup name (rest ab))])]))
          ;; service-manager : address-book object
          ;; to manage addition to, and searches in, the address book 
          (define (service-manager msg)
              [(symbol=? msg 'add)
              [(symbol=? msg 'search)
	       (lambda (name)
		 (lookup name address-book))]
              [else (error 'address-book "message not understood")])))

Figure 115:  Managing multiple address books

Figure 115 shows the complete definition of make-address-book. The definition is standard by now. It consists of a local-expression, which in turn produces the locally defined service-manager as the result. There is no need for an initializer because the only state variable is immediately initialized and there is no graphical view.

To use an address book, we first create it with make-address-book:

;; friends : an address book
;; to maintain an address book for friends 
(define friends
  (make-address-book "Friends of Charles"))

;; business : an address book
;; to maintain an address book for business colleagues
(define business
  (make-address-book "Colleagues @ Rice, Inc."))

The two definitions create two distinct address books, one for a collection of friends and a second one for business acquaintances.

Second, we add names and phone numbers to the address book, or we retrieve numbers as desired:

> ((friends 'add) 'Bill 2)
> ((friends 'add) 'Sally 3)
> ((friends 'add) 'Dave 4)
> ((business 'add) 'Emil 5)
> ((business 'add) 'Faye 18)

In this case, we added three entries to the address book named friends and two to the one called business.

An addition to, say, friends works in two steps. The first step is to apply friends to 'add. This yields the (hidden) function add-to-address-book. The second step is to apply this resulting function to a name and a number. In a similar vein, looking up a phone number also works in two steps. The application of, say, friends to 'search yields a function that consumes a name. This function is then applied to a symbol:

> ((friends 'search) 'Bill)
> ((business 'search) 'Bill)

The two applications show that the number for 'Bill in friends is 2 and that there is no number for 'Bill in colleagues. According to the above additions, that's exactly what we should expect. Of course, we could also co-mingle the two actions in the Interactions window, adding and searching for phone numbers at will.

Exercise 39.1.6.   Develop an interface definition for the results of the revised version of make-traffic-light (see figure 114).    Solution

Exercise 39.1.7.   Show the top-level definitions that the evaluation of friends and colleagues creates.

What is the state of these definitions after the five 'add expressions have been evaluated? Evaluate ((friends 'search) 'Bill) in this context.    Solution

Exercise 39.1.8.   Design gui-for-address-book. The function consumes a list of strings and creates a new address book for each one of them. It also creates and displays a graphical user interface for an address book with a choice menu that lets users choose to which address book they want to add an entry and in which address book the program should search for a number.    Solution

39.2  Practice with Encapsulation

Exercise 39.2.1.   Develop the program make-city. It manages a collection of traffic lights. The program should provide four services:

  1. adding a traffic light with a label (string);

  2. removing a traffic light by label;

  3. switching the state of a traffic light with some given label; and

  4. resetting a traffic light to red with some given label.

Hint: The first two services are provided directly; the last two are implemented by the simulated traffic lights.

After the development of the program is completed, develop a graphical user interface.    Solution

Exercise 39.2.2.   Develop make-master. The program consumes nothing, creates an instance of the color-guessing game of section 37.1, and produces the master-check function as the only result. After the player has guessed the answer, the function should simply respond with ``game over.'' A typical dialog would proceed as follows:

> (define master1 (make-master))
> (master-check 'red 'red)
> (master-check 'black 'pink)

Compare this with the first dialogue in section 37.1.

Add a service to make-master that reveals the hidden colors. That way a player who is tired of playing the game can find out the answer.    Solution

Exercise 39.2.3.   Develop make-hangman. The program consumes a list of words, creates a hangman game using the list, and produces the hangman-guess function as a result. A player would use the dialogue as follows:

> (define hangman-easy (make-hangman (list 'a 'an 'and 'able 'adler)))
> (define hangman-difficult (make-hangman (list 'ardvark ...)))
> (hangman-easy 'a)
"You won"
> (hangman-difficult 'a)
(list 'head (list '_ '_ '_ '_ '_ '_))
> ... 

Compare this with the first dialogue in section 37.2.

Add a service to make-master that reveals the chosen word.

An optional extension is to equip the program with a graphical user interface and a graphical view of the stick figure. Reuse existing solutions as much as possible.    Solution

Exercise 39.2.4.   Develop make-player. The program abstracts over the functions of section 37.5. Using the program, we can create several players that wander through the campus:

(define player1 (make-player 'BioEngineering))
(define player2 (make-player 'MuddBuilding))

The argument to make-player specifies the initial position of the player.

Each instance should be able to produce

  1. a picture of the current surroundings;

  2. a list of the available building connections; and

  3. a move from one place to another through an available connection.

Extension: Two players may be in the same building at the same time, but they cannot interact. Extend the game so that two players in the same building can interact in some form.    Solution

Exercise 39.2.5.   Develop the program moving-pictures. It consumes a position and a picture, that is, a list of shapes as defined in sections 6.6, and 7.4, and 10.3. (Also see 21.4 for functions on moving pictures.) It supports two services. First, it can place the shape at a specific position. Second, it can reset the picture to the initially given position.    Solution