8  Assignment

Scheme is a functional language. A program creates and manipulates values. The pieces of a program communicate with each other by exchanging values. Programmers compose the pieces of a program in expressions, and, because they know exactly what one expression produces and what another consumes, they can easily reuse functions, reason about such compositions, and document them for others. On some occasions, however, there is no way around imperative programming. Sometimes a function just has to remember things between separate calls, and the best way to achieve this is to assign a value to a variable. Other times a function must record that some structure changed and other functions should know about it. And we can do just that with a structure mutation (assignment) like in any other programming language. In short, the Scheme designers combined the best of both worlds. They encourage programmers to think about computation as the creation and communication of values, but they are also realistic and allow programs to mutate such values.

8.1  Variable Assignment

Scheme supports variable assignments like any conventional programming language. Unlike most languages though, Scheme does not abuse the = notation of mathematics and instead uses a separate keyword for assignment expressions:

(set! <variable> <rhs-expression>)

We pronounce this word as set-bang, with an emphasis on the bang. Pronounced properly, the word warns the programmer that this expression does something dangerous, it modifies the association between a variable and a value. Specifically, it sets the variable to the result of the <rhs-expression>. The result of the set!-expression is void, a value without print representation, which is why it remains invisible.

;; (Listof X)
(define the-queue '())

;; X  -->  void
;; effect: add an item to the end of the-queue
(define (enq x) (set! the-queue (append the-queue (list x))))

;;  -->  Boolean
;; check whether the-queue is empty 
(define (emptyQ?) (null? the-queue))

;;  -->  X
;; effect: remove and return the first item in the-queue, if any
(define (deq)
  (if (emptyQ?)
      (error 'deq "can't remove an item from the empty queue")
	(car the-queue)
	(set! the-queue (cdr the-queue)))))

Figure 14:  A simple queue implementation

The combination of a powerful class of built-in data and variable assignment is potent. Take a look at the program fragment in figure 14. It implements a classical queue for which the enq function adds an item at the end and the deq function removes an item from the front, unless the queue is empty. To enqueue an item, enq append's a singleton list to the end of the current queue and modifies the queue. To dequeue an item, deq extracts the first item and assigns the rest of the queue to the-queue. The sequential ordering is critical for deq because the assignment makes the first item inaccessible for future computations.

Since variables assignments (and other effects) require the sequential evaluation of expressions, Scheme provides the begin and the begin0 expression. Both evaluate their subexpressions in order. The result of the first is the value of its last subexpression; the result of the second is the value of its first subexpression. This explains the definition of deq, which uses begin0 to return the first item in the queue and to chop it of at the time.

Note: Bad Scheme Programming

When programmers who grew up on conventional languages encounter set!, they often forget the functional style of programming and instead fall back on their old ways. With set! and loops, especially for-each, they can more or less write the same old bad code that they are used to from Pascal, C/C++, or Java.

Here is one such typical code fragment:

;; N  -->  Number
;; a loop for adding up the first n numbers
(define (sum-of-first n)
  (local ((define sum 0))
      ;; loop over the first n numbers 
      (for-each (lambda (x) (set! sum (+ sum x)))
 	(build-list n add1))
      ;; return 

This program fragment first sets up a variable and then iterates over the 10 numbers and mutates the variable. The code fragment ends in sum to remind ourselves that the rest of the program needs the value -- which is the primary reason why we even wish to write such code.

Contrast this code fragment with the functional way of doing things, which we have seen in the section on loops:

(define (sum-of-first n) (apply + (build-list n add1)))

It is concise, and clearly expresses its goal directly, namely, ``apply the function for adding numbers to the list 1, ..., n''. Alternatively, we can use a closed formula:

(define (sum-of-first n) (* 1/2 n (- n 1)))

In general, try to think about computation as communication. In most cases, it suffices for a function to compute a value and to return it to its context. Effects should only be used to communicate values if they need to survive function calls.

8.2  Our First Program with Effects

The purpose of an assignment is to change the state of a program's variables so that their values reflect the events that took place. This should immediately remind you of our running example, the UFO simulation. In section 5.5, we discussed how the flight of the UFO is actually a reaction to the sequence of time events and how the firing of shots is a reaction to the sequence of keyboard events.

In other words, both the ufo and the list of shots are state variables, and the program should change the state of these variables when an event happens. Let's set up the state variables first:

;; UFO : the current state of the ufo
(define ufo (ufo-create (random WIDTH)))
;; (Listof Star) : the stars in the background
(define stars (stars-create 50))
;; (Listof Shot) : the current state of the shots 
(define shots '())

;; run program run 

Once the state of the world is described through state variables, we just need to create the canvas and draw the background; there is no need to instantiate the world.

Next, the handler for keyboard events still receives the keyevent and the (empty) world. As before, if the event represents an up-arrow key, the handler creates a shot and adds it to the list of shots:

 ;; effect: create and add shot to shots
 (lambda (e w)
   (when (eq? 'up e)
     (set! shots (cons (shot-create) shots)))))

But, in this new version, the addition of the shot means the world has changed, and this change is performed via an assignment to shots. More precisely, the variable shots is set to the list that is just like the one it contained but with a new shot added at the front.

Finally, we can also write a simpler event handler for time events:

 ;; effect: move the ufo and the shots 
 (lambda (w)
     [(ufo-landed? ufo) (stop-time)]
     [else (begin
             (scene-erase ufo shots)
             (set! ufo (ufo-move ufo))
             (set! shots (map shot-move shots))
             (scene-draw ufo stars shots))])))

Unless the UFO has reached the bottom of the screen, the handler erases the current scene, then modifies the location of the UFO and the locations of all the shots. For the first action, it uses ufo-move, which produces a new UFO; the assignment to ufo changes the value of that variable to this new UFO. For the second action, it uses a loop (map) to apply shot-move to each shot on the list stored in shots. The result is a new list of shots, which is then stored in shots. Last, but not least, the event handler draws the new scenery. Note how important it is to order the statements in a begin carefully so that we don't, say, erase the new scene and draw the old one.

Comparing the respective code fragments in section 5.5 and here shows that the set!-based approach leads to shorter programs. Still, if you carefully re-read the descriptions of the program pieces, it always says that ufo-move and shot-move (with map) create new UFOs, new shots, and new lists of shots. Given that we just move existing UFOs and existing shots, we should also be able to modify the structures that represent those and do away with creating new versions.

8.3  Structural Mutation

The queue implementation suffers from an annoying performance problem. For every use, enq traverses the entire queue (using append) and then adds the new item. For a conventional queue implementation, the enq and deq operation are constant time, that is, they never traverse a linear structure.

To achieve constant-time behavior, a conventional queue implementation maintains a link to the place where enq adds items and another one where deq removes items. It can then manipulate the links of each end in a constant number of operations. Based on what we know, we can easily establish a name for the end of the list, but we cannot use it to add another item because it requires an imperative modification of the list.

Naturally, the designers of Scheme recognized the need to modify the links within a list and other compound values as well. Each class of values therefore comes with primitive functions that can modify the fields of a value. We call such primitives the MUTATORS of a class. The mutators for lists are:

Note that set-cdr! can change a proper list into something that is not a list.

;; (cons 'sentinel (Listof X))
(define the-queue '(sentinel))

;; (Listof X)
(define last-cell the-queue)

;; X  -->  void
(define (enq x)
    (set-cdr! last-cell (cons x null))
    (set! last-cell (cdr last-cell))))

;;  -->  Boolean
(define (emptyQ?) (null? (cdr the-queue)))

;;  -->  X
(define (deq)
  (if (emptyQ?)
      (error 'deq "can't remove an item from the empty queue")
        (second the-queue)
        (set-cdr! the-queue (cdr (cdr the-queue)))
        (when (emptyQ?) (set! last-cell the-queue)))))

Figure 15:  A constant-time queue implementation

Figure 15 illustrates the use of list mutators. The code fragment implements a constant-time queue. As in figure 14, the-queue stands for the current queue. To simplify the code for the queue operations, it always contains a single item: 'sentinel. The variable last-cell always points to the last cell in the-queue. The enq and deq operations maintain this invariant. In turn, the former uses last-cell to add an item to the-queue with a single list mutation. Of course, as it does so, it must also update last-cell to point to this additional cell as the new last cell. The deq operation extracts the second item from the-queue, which is the first item on the queue, and then removes it from the list. The last statement re-establishes the relationship between the-queue and last-cell if the dequeued item was the last one on the list.

(define SIZE 10)

;; (Vectorof X)
(define the-queue (make-vector SIZE 'X))

;; N
(define front 0)

;; N
(define number-of-items 0)

;;  -->  Boolean
(define (emptyQ?)
  (= number-of-items 0))

;;  -->  Boolean
(define (fullQ?)
  (= number-of-items SIZE))

;; X  -->  void
(define (enq x)
  (if (fullQ?)
      (error 'enq "the queue is full")
        (vector-set! the-queue (remainder (+ front number-of-items) SIZE) x)
        (set! number-of-items (+ number-of-items 1)))))

;;  -->  X
(define (deq)
  (if (emptyQ?)
      (error 'deq "can't remove an item from the empty queue")
        (vector-ref the-queue front)
        (set! number-of-items (- number-of-items 1))
        (set! front  (remainder (+ front 1) SIZE)))))

Figure 16:  A finite queue

For many applications, queues are limited to a fixed number of items. One way to accomplish this is to add a counter to the queue implementation and to make sure that the counter never crosses a certain limit. If it does, the queue implementation signals an error. While this strategy works from an operational point of view, it wastes space due to the allocation of a singleton list for each enq operation. This allocation is superfluous because we know exactly how much space a finite queue needs. To avoid this overhead, we can use vectors and mutate them.

Like list mutation, vector mutation uses functions. Since the fields in vectors are uniformly index with natural numbers, a single function suffices: vector-set!. The function consumes a vector, an index into the vector, and a new value for this slot. Its result is void.

Take a look at figure 16. It allocates a single vector of the right size. Two variables, number-of-items and front, are used to keep track of the number of items that are in the queue and the vector fields that are available for additional items, respectively. Both enq and deq uses these variables. The former computes whether and where it can mutate the vector with the new item; the latter computes where the front of the queue is.

Figure 17:  A cyclic queue implementation

Of course, once we can mutate the fields of values, we can easily create cyclic forms of data. To create a cyclic lists of just 1s, we just mutate the cdr field of a singleton list to itself:

(define ones (cons 1 null))

(set-cdr! ones ones)

Scheme, like any language worth its disk space, has provisions for printing such cyclic values. Scheme prints cyclic values as equations:

> ones 
#0=(1 . #0#)

On the left side of the equation, it prints an anchor, which is a # followed by a number. On the right side, it prints the ordinary print representation of the cyclic value interspersed with occurrences of backpointers to the anchor, e.g., #0#.

Figure 17 displays a screenshot with a portion of a finite queue implementation that relies on a cyclic list. The cyclic list is created at the top. Two variables point into the list: head and end. New items are inserted via end, and enqueued items are removed at head. The Interactions window shows how DrScheme prints a queue with three characters.

Finally, Scheme also provides mutators for strings and structures. The former are just like those for vectors. The latter are more interesting. A structure definition creates a mutator for each field in a structure. Thus, when we wrote that this definition

(define-struct person (name gender yob))
;; Person = (make-person String String Number)

introduces five new functions, we lied, a bit. It really creates eight, that is one plus one plus three plus three functions. The last three functions are STRUCTURE MUTATORS. They are:

Naturally, we won't need all these mutators in a realistic program, but structure definitions provide them just in case.

8.4  Our First Program with Structure Mutation

The structure definition for Posns also introduces two mutators: set-posn-x! and set-posn-y!. The former changes the value of the x field in a Posn and the latter changes the value of the y field. Thus, if p is a Posn, then

(set-posn-x! p (+ (posn-x p) 1))

increases the x field of p by 1.

Modifying the fields of Posns comes in handy of course for our UFO game. For example, once a shot is fired, it goes straight up at a constant speed. All that changes as the shot flies upwards is the value in the y field of the Posn that represents the shot:

;; Shot  -->  Shot
;; effect: modify the Posn that represents the UFO
(define (shot-move! s) (set-posn-y! s (- (posn-y s) SHOT-DELTA)))

All the other functions for shots remain the same.

The representation of a UFO is slightly more complex than that of a shot. Still, since its velocity always remains the same -- as agreed upon in the initial planning, we can do almost the same we did for a shot:

;; UFO  -->  Void
;; move u once
;; effect: modify the pos component of u 
(define (ufo-move! u)
  (local ((define pos (ufo-pos u))
          (define vel (ufo-vel u)))
      (set-posn-x! pos (+ (posn-x pos) (posn-x vel)))
      (set-posn-y! pos (+ (posn-y pos) (posn-y vel))))))

This UFO moving function extracts the UFO's current position and its velocity. Then it modifies the x and y fields of the UFO's position, respectively, using the laws of physics.

Since we changed the ``types'' of the shot and UFO moving functions, we must also change the time event handler, because it uses these functions:

 (lambda (w) ;; effect: move the ufo and the shots 
     [(ufo-landed? ufo) (stop-time)]
     [else (begin
             (scene-erase ufo shots)
             (ufo-move! ufo)
             (for-each shot-move! shots)
             (scene-draw ufo stars shots))])))

The two changes are underlined. The first one is that the handler no longer needs to change ufo, the global state variable; instead it just mutates ufo directly with ufo-move!. The second is that it now uses for-each to move each shot. After all, shot-move! just modifies the location of each shot and returns nothing (void). Hence there are no values to be collected in a list. Together the two changes eliminate the creation of new UFOs, shots, and lists of shots. Instead it modifies those structures that represent physical objects and creates the simulation in this way.