2.9. Assignment

2.9. Assignment

Although many programs can be written without them, assignments to top-level variables or let-bound and lambda-bound variables are sometimes useful. Assignments do not create new bindings, as with let or lambda, but rather change the values of existing bindings. Assignments are performed with set!.

 (define abcde '(a b c d e)) abcde ⇒ (a b c d e) (set! abcde (cdr abcde)) abcde ⇒ (b c d e) (let ((abcde '(a b c d e)))   (set! abcde (reverse abcde))   abcde) ⇒ (e d c b a) 

Many languages require the use of assignments to initialize local variables, separate from the declaration or binding of the variables. In Scheme, all local variables are given a value immediately upon binding. Besides making the separate assignment to initialize local variables unnecessary, it ensures that the programmer cannot forget to initialize them, a common source of errors in most languages.

In fact, most of the assignments that are either necessary or convenient in other languages are both unnecessary and inconvenient in Scheme, since there is typically a clearer way to express the same algorithm without assignments. One common practice in some languages is to sequence expression evaluation with a series of assignments, as in the following procedure that finds the roots of a quadratic equation.

 (define quadratic-formula   (lambda (a b c)     (let ((root1 0) (root2 0) (minusb 0) (radical 0) (divisor 0))       (set! minusb (- 0 b))       (set! radical (sqrt (- (* b b) (* 4 (* a c)))))       (set! divisor (* 2 a))       (set! root1 (/ (+ minusb radical) divisor))       (set! root2 (/ (- minusb radical) divisor))       (cons root1 root2)))) 

The roots are computed according to the well-known quadratic formula,

which yields the solutions to the equation 0 = ax² + bx + c. The let expression in this definition is employed solely to establish the variable bindings, corresponding to the declarations required in other languages. The first three assignment expressions compute subpieces of the formula, namely −b, , and 2a. The last two assignment expressions compute the two roots in terms of the subpieces. A pair of the two roots is the value of quadratic-formula. For example, the two roots of 2x² − 4x − 6 are x = 3 and x = −1.

 (quadratic-formula 2 -4 -6) ⇒ (3 . -1) 

The definition above works, but it can be written more clearly without the assignments, as shown below.

 (define quadratic-formula   (lambda (a b c)     (let ((minusb (- 0 b))           (radical (sqrt (- (* b b) (* 4 (* a c)))))           (divisor (* 2 a)))       (let ((root1 (/ (+ minusb radical) divisor))             (root2 (/ (- minusb radical) divisor)))         (cons root1 root2))))) 

In this version, the set! expressions are gone, and we are left with essentially the same algorithm. By employing two let expressions, however, the definition makes clear the dependency of root1 and root2 on the values of minusb, radical, and divisor. Equally important, the let expressions make clear the lack of dependencies among minusb, radical, and divisor and between root1 and root2.

Assignments do have some uses in Scheme, otherwise the language would not support them. Consider the following version of cons that counts the number of times it is called, storing the count in a variable named cons-count. It uses set! to increment the count; there is no way to achieve the same behavior without assignments.

 (define cons-count 0) (define cons   (let ((old-cons cons))     (lambda (x y)       (set! cons-count (+ cons-count 1))       (old-cons x y)))) (cons 'a '(b c)) ⇒ (a b c) cons-count ⇒ 1 (cons 'a (cons 'b (cons 'c '()))) ⇒ (a b c) cons-count ⇒ 4 

set! is used both to establish the new top-level value for cons and to update the variable cons-count each time cons is invoked.

Assignments are commonly used to implement procedures that must maintain some internal state. For example, suppose we would like to define a procedure that returns 0 the first time it is called, 1 the second time, 2 the third time, and so on indefinitely. We could write something similar to the definition of cons-count above:

 (define next 0) (define count   (lambda ()     (let ((v next))       (set! next (+ next 1))       v))) (count) ⇒ 0 (count) ⇒ 1 

This solution is somewhat undesirable in that the variable next is visible at top level even though it need not be. Since it is visible at top level, any code in the system can change its value, perhaps inadvertently affecting the behavior of count in a subtle way. We can solve this problem by let-binding next outside of the lambda expression:

 (define count   (let ((next 0))     (lambda ()       (let ((v next))         (set! next (+ next 1))         v)))) 

The latter solution also generalizes easily to provide multiple counters, each with its own local counter. The procedure make-counter, defined below, returns a new counting procedure each time it is called.

 (define make-counter   (lambda ()     (let ((next 0))       (lambda ()         (let ((v next))           (set! next (+ next 1))           v))))) 

Since next is bound inside of make-counter but outside of the procedure returned by make-counter, each procedure it returns maintains its own unique counter.

 (define count1 (make-counter)) (define count2 (make-counter)) (count1) ⇒ 0 (count2) ⇒ 0 (count1) ⇒ 1 (count1) ⇒ 2 (count2) ⇒ 1 

If a state variable must be shared by more than one procedures defined at toplevel, but we do not want the state variable to be visible at top-level, we can use let to bind the variable and set! to make the procedures visible at top level.

 (define shhh #f) (define tell #f) (let ((secret 0))   (set! shhh     (lambda (message)       (set! secret message)))   (set! tell     (lambda ()       message))) (shhh "sally likes harry") (tell) ⇒ "sally likes harry" secret ⇒ Error: variable secret is not bound 

Variables must be defined before they can be assigned, so we define shhh and tell to be #f initially. (Any initial value would do.) We'll see this structure again in Chapter 3.

Local state is sometimes useful for caching computed values or allowing a computation to be evaluated lazily, i.e., only once and only on demand. The procedure lazy below accepts a thunk, or zero-argument procedure, as an argument. Thunks are often used to "freeze" computations that must be delayed for some reason, which is exactly what we need to do in this situation. When passed a thunk t, lazy returns a new thunk that, when invoked, returns the value of invoking t. Once computed, the value is saved in a local variable so that the computation need not be performed again. A boolean ag is used to record whether t has been invoked and its value saved.

 (define lazy   (lambda (t)     (let ((val #f) (flag #f))       (lambda ()         (if (not flag)             (begin (set! val (t))                    (set! flag #t)))         val)))) 

The syntactic form begin, used here for the first time, evaluates its subexpressions in sequence from left to right and returns the value of the last subexpression, like the body of a let or lambda expression. We also see that the alternative subexpression of an if expression can be omitted. This should be done only when the value of the if is discarded, as it is in this case.

Lazy evaluation is especially useful for values that require considerable time to compute. By delaying the evaluation, we may avoid computing the value altogether, and by saving the value, we avoid computing it more than once.

The operation of lazy can best be illustrated by printing a message from within a thunk passed to lazy.

 (define p   (lazy (lambda ()           (display "Ouch!")           (newline)           "got me"))) 

The first time p is invoked, the message Ouch! is printed and the string "got me" is returned. Thereafter, "got me" is returned but the message is not printed. The procedures display and newline are the first examples of explicit input/output we have seen; display prints the string without quotation marks, and newline prints a newline character.

To further illustrate the use of set!, let's consider the implementation of stack objects whose internal workings are not visible on the outside. A stack object accepts one of four messages: empty?, which returns #t if the stack is empty; push!, which adds an object to the top of the stack; top, which returns the object on the top of the stack; and pop!, which removes the object on top of the stack. The procedure make-stack given below creates a new stack each time it is called in a manner similar to make-counter.

 (define make-stack   (lambda ()     (let ((ls '()))       (lambda (msg . args)         (cond           ((eqv? msg 'empty?) (null? ls))           ((eqv? msg 'push!)            (set! ls (cons (car args) ls)))           ((eqv? msg 'top) (car ls))           ((eqv? msg 'pop!)            (set! ls (cdr ls)))           (else "oops")))))) 

Each stack is stored as a list bound to the variable ls; set! is used to change this binding for push! and pop!. Notice that the argument list of the inner lambda expression uses the improper list syntax to bind args to a list of all arguments but the first. This is useful here because in the case of empty?, top, and pop! there is only one argument (the message), but in the case of push! there are two (the message and the object to push onto the stack).

 (define stack1 (make-stack)) (define stack2 (make-stack)) (stack1 'empty?) ⇒ #t (stack2 'empty?) ⇒ #t (stack1 'push! 'a) (stack1 'empty?) ⇒ #f (stack2 'empty?) ⇒ #t (stack1 'push! 'b) (stack2 'push! 'c) (stack1 'top) ⇒ b (stack2 'top) ⇒ c (stack1 'pop!) (stack2 'empty?) ⇒ #f (stack1 'top) ⇒ a (stack2 'pop!) (stack2 'empty?) ⇒ #t 

As with the counters created by make-counter, the state maintained by each stack object is directly accessible only within the object. Each reference or change to this state is made explicitly by the object itself. One important benefit is that we can change the internal structure of the stack, perhaps to use a vector (see Section 6.7) instead of a list to hold the elements, without changing its external behavior. Because the behavior of the object is known abstractly (not operationally), it is known as an abstract object. See Section 9.8 for more about creating abstract objects.

In addition to changing the values of variables, we can also change the values of the car and cdr fields of a pair, using the procedures set-car! and set-cdr!.

 (define p (list 1 2 3)) (set-car! (cdr p) 'two) p ⇒ (1 two 3) (set-cdr! p '()) p ⇒ (1) 

We can use these operators to define a queue datatype, which is like a stack except that new elements are added at one end and extracted from the other. The following implementation of a queue uses a tconc structure, borrowed from old Lisp systems. A tconc consists of a nonempty list and a header. The header is a pair whose car points to the first pair (head) of the list and whose cdr points to the last pair (end) of the list.

The last element of the list is a placeholder and not considered part of the queue.

Four operations on queues are defined below: make-queue, which constructs a queue, putq!, which adds an element to the end of a queue, getq, which retrieves the element at the front of a queue, and delq!, which removes the element at the front of a queue.

 (define make-queue   (lambda ()     (let ((end (cons 'ignored '())))       (cons end end)))) (define putq!   (lambda (q v)     (let ((end (cons 'ignored '())))       (set-car! (cdr q) v)       (set-cdr! (cdr q) end)       (set-cdr! q end)))) (define getq   (lambda (q)     (car (car q)))) (define delq!   (lambda (q)     (set-car! q (cdr (car q))))) 

All are simple operations except for putq!, which modifies the end pair to contain the new value and adds a new end pair.

 (define myq (make-queue)) (putq! myq 'a) (putq! myq 'b) (getq myq) ⇒ a (delq! myq) (getq myq) ⇒ b (delq! myq) (putq! myq 'c) (putq! myq 'd) (getq myq) ⇒ c (delq! myq) (getq myq) ⇒ d 

Exercise 2.9.1.

Modify make-counter to take two arguments: an initial value for the counter to use in place of 0 and an amount to increment the counter by each time.

Exercise 2.9.2.

Look up the description of case in Section 5.3. Replace the cond expression in make-stack with an equivalent case expression. Add mt? as a second name for the empty? message.

Exercise 2.9.3.

Modify the stack object to allow the two messages ref and set!. (stack 'ref i) should return the ith element from the top of the stack; (stack 'ref 0) should be equivalent to (stack 'top). (stack 'set! i v) should change the ith element from the top of the stack to v.

 (define stack (make-stack)) (stack 'push! 'a) (stack 'push! 'b) (stack 'push! 'c) (stack 'ref 0) ⇒ c (stack 'ref 2) ⇒ a (stack 'set! 1 'd) (stack 'ref 1) ⇒ d (stack 'top) ⇒ c (stack 'pop!) (stack 'top) ⇒ d 

[Hint: Use list-ref to implement ref and list-tail with set-car! to implement set!.]

Exercise 2.9.4.

Scheme supports vectors as well as lists. Like lists, vectors are aggregate objects that contain other objects. Unlike lists, vectors have a fixed size and are laid out in one at block of memory, typically with a header containing the length of the vector, as in the ten-element vector below.

This makes vectors more suitable for applications needing fast access to any element of the aggregate but less suitable for applications needing data structures that grow and shrink as needed.

Look up the basic vector operations in Section 6.7 and reimplement the stack object to use a vector instead of a list to hold the stack contents. Include the ref and set! messages of Exercise 2.9.3. Have the new make-stack accept a size argument n and make the vector length n, but do not otherwise change the external (abstract) interface.

Exercise 2.9.5.

Define a predicate, emptyq?, for determining if a queue is empty. Modify getq and delq! to signal an error when an empty queue is found, using the error signaling facility provided by your implementation of Scheme.

Exercise 2.9.6.

In the queue implementation, the last pair in the encapsulated list is a placeholder, i.e., it never holds anything useful. Recode the queue operators to avoid this wasted pair. Make sure that the series of queue operations given earlier works with the new implementation. Which implementation do you prefer?

Exercise 2.9.7.

Using set-cdr!, it is possible to create cyclic lists. For example, the following expression evaluates to a list whose car is the symbol a and whose cdr is the list itself.

 (let ((ls (cons 'a '())))   (set-cdr! ls ls)   ls) 

What happens when you enter the above expression during an interactive Scheme session? What will the implementation of length on page 40 do when given a cyclic list? What does the built-in length primitive do?

Exercise 2.9.8.

Define the predicate list?, which returns #t if its argument is a proper list and #f otherwise (see Section 6.3). It should return #f for cyclic lists as well as for lists terminated by objects other than ().

 (list? '()) ⇒ #t (list? '(1 2 3)) ⇒ #t (list? '(a . b)) ⇒ #f (list? (let ((ls (cons 'a '())))          (set-cdr! ls ls)          ls)) ⇒ #f 

First write a simplified version of list? that does not handle cyclic lists, then extend this to handle cyclic lists correctly. Revise your definition until you are satisfied that it is as clear and concise as possible. [Hint: Use the following "hare and tortoise" algorithm to detect cycles. Define a recursive help procedure of two arguments, the hare and the tortoise. Start both the hare and the tortoise at the beginning of the list. Have the hare advance by two cdrs each time the tortoise advances by one cdr. If the hare catches the tortoise, there must be a cycle.]