Mutators

• Introduction
• Mutators and Postconditions
• List Mutators
• Mutating Map
• Generating Vectors
• Accumulating Procedures
• Mutating Strings

Introduction

As you may have noted in the reading and the lab on vectors, vector-set! is a very strange procedure for a few reasons. First, it does not return any value, so it is only called for its effect. Second, because it is only called for its effect, it is only useful if we call it on a named value. Third, and perhaps most importantly, it changes a value.

You may not have noticed it, but every method we wrote previously created new values without changing the previous value. For example, if we mapped square onto the list (5 2 7), we'd get the new list (25 4 49), but the original list would still be (5 2 7)

> (define square (lambda (x) (* x x))
> (define stuff (list 5 2 7))
> stuff
(5 2 7)
> (map square stuff)
(25 4 49)
> stuff
(5 2 7)

However, if we do something similar using vector-set!, the original vector does change.

> (define stuff (vector 5 2 7))
> stuff
#3(5 2 7)
*gt; (vector-set! stuff 0 (square (vector-ref stuff 0)))
> stuff
#3(25 2 7)

We call procedures that modify their arguments mutators.

Mutators and Postconditions

Once you start using mutators, it becomes necessary to be very careful to document your postconditions. After all, we now know of two general kinds of procedures: those that change their arguments and those that don't. For every procedure, you should include a postcondition that indicates whether or not it changes its arguments. For example, we need to make it clear that map creates a new list and does not affect its arguments.

Scheme programmers have the tradition of ending every mutator with an exclamation point (also called a bang) so that it's clear that it's a mutator. Please follow that tradition.

List Mutators

Scheme provides some simple mutators for each of its basic data structures. There are two list/pair mutators, set-car! and set-cdr!.

The set-car! procedure takes two arguments -- a pair pr and a Scheme value obj -- and, as a side effect, replaces the car of pr with obj.

> (define sample-pair (cons 'alpha 'beta))

> sample-pair
(alpha . beta)

> (set-car! sample-pair 'gamma)

> sample-pair
(gamma . beta)

Similarly, the set-cdr! procedure takes pr and obj as arguments and, as a side effect, replaces the cdr of pr with obj.

Pairs that are named by quoted list or dotted-pair expressions are immutable, and it is an error to apply set-car! or set-cdr! to such a pair. It appears that DrScheme does not enforce this condition. Nonetheless, code you write that mutates pairs created by quoated list or dotted-pair expression is not guaranteed to be portable.

As noted earlier, mutators can be dangerous. The set-cdr! procedure in particular should be used with great caution, since it is all too easy to create (by accident) a data structure for which the box-and-pointer diagram contains a cycle -- for instance, a structure in which box A contains a pointer to box B, which contains a pointer back to box A.

When a list-recursive procedure is confronted with such a structure, a runaway recursion may result, since you can't reach a null list by repeatedly taking the cdr. Note that many of the built-in Scheme procedures check to ensure that their parameter is a ``proper list''.

Mutating Map

In the reading and the lab on vectors, In the lab on vectors, we developed some procedures that took vectors as arguments and constructed and returned other vectors as results -- for instance, the double-every-element procedure:

(define double-every-element
  (lambda (vec)
    (let* ((size (vector-length vec))
           (result (make-vector size)))
      (let kernel ((position 0))
        (if (= position size)
            result
            (begin
              (vector-set! result position (* 2 (vector-ref vec position)))
              (kernel (+ position 1))))))))

Instead of constructing an entirely new vector, it is sometimes appropriate to replace the elements of the original vector with the newly computed elements:

(define double-every-element!
  (lambda (vec)
    (let ((size (vector-length vec)))
      (let kernel ((position 0))
        (if (< position size)
            (begin
              (vector-set! vec position (* 2 (vector-ref vec position)))
              (kernel (+ position 1))))))))

> (define sample-vector (vector 3 1 4 1 5 9))

> sample-vector
#(3 1 4 1 5 9)

> (double-every-element! sample-vector)

> sample-vector
#(6 2 8 2 10 18)

As the exclamation point at the end of double-every-element! indicates, calling the procedure causes an irreversible change of state in its argument, sample-vector. The original contents of that vector are gone. Each of the original elements has been replaced by its double. This ``destructive'' procedure is likely to be more efficient than double-every-element, because it is unnecessary to allocate storage for a result vector, but it is also somewhat trickier to use. The timing is important: one must not replace the elements of the vector too soon, at a time when one still needs some of the old values for other computations.

This pattern of computation is common enough that it is useful to define a destructive version of vector-map:

(define vector-map!
  (lambda (proc vec)
    (let ((size (vector-length vec)))
      (let kernel ((position 0))
        (if (< position size)
            (begin
              (vector-set! vec position (proc (vector-ref vec position)))
              (kernel (+ position 1))))))))

> (define sample-vector (vector 3 1 4 1 5 9))

> (vector-map! square sample-vector)

> sample-vector
#(9 1 16 1 25 81)

Generating Vectors

Another way of using the vector-set! procedure is illustrated by our implementation of the vector-generator procedure:

(define vector-generator
  (lambda (proc)
    (lambda (size)
      (let ((result (make-vector size)))
        (let kernel ((position 0))
          (if (= position size)
              result
              (begin
                (vector-set! result position (proc position))
                (kernel (+ position 1)))))))))

> ((vector-generator (lambda (x) (+ x 1))) 6)
#(1 2 3 4 5 6)

In this case, the calls to vector-set! are used to initialize the contents of the vector. The results of the call to proc overwrite the previous elements of result, but those elements were the unspecified dummy values that make-vector installed as place-holders.

Accumulating Procedures

An accumulation procedure is one that traverses a vector from left to right, replacing each element with the result of performing some given operation on all of the elements up to and including that one. For example, here is a procedure that accumulates partial sums in a vector of numbers:

(define accumulate-sum!
  (lambda (vec)
    (let ((size (vector-length vec)))
      (let kernel ((position 0)
                 (sum 0))
        (if (< position size)
            (let ((new-sum (+ sum (vector-ref vec position))))
              (vector-set! vec position new-sum)
              (kernel (+ position 1) new-sum))))))))

> (define sample-vector (vector 3 1 4 1 5 9))

> (accumulate-sum! sample-vector)

> sample-vector
#(3 4 8 9 14 23)

And here is one that accumulates strings by concatenation:

(define accumulate-strings!
  (lambda (vec)
    (let ((size (vector-length vec)))
      (let kernel ((position 0)
                 (so-far ""))
        (if (< position size)
            (let ((new-value (string-append so-far
                                            (vector-ref vec position))))
              (vector-set! vec position new-value)
              (kernel (+ position 1) new-value))))))))

> (define string-vector (vector "To " "be " "or " "not " "to " "be "))

> (accumulate-strings! string-vector)

> string-vector
#("To "
  "To be "
  "To be or "
  "To be or not "
  "To be or not to "
  "To be or not to be ")

Mutating Strings

The string-set! procedure takes two three arguments -- a string str, a natural number k less than the length of str, and a character ch -- and, as a side effect, replaces the character at position k in str with ch:

> (define sample-string (string #\s #\a #\m #\p #\l #\e))

> sample-string
"sample"

> (string-set! sample-string 1 #\i)

> sample-string
"simple"

Like vectors named by quoted mesh-and-parentheses expressions, strings named by constants beginning and ending with double quotation marks are ``immutable,'' and it is an error to apply string-set! to them. (DrScheme does not object to the erroneous operation, but some other implementations of Scheme do.)