Scheme Programming/Mutability

Mutation

Mutation is a common side-effect in programming. To mutate a variable once it has been defined means to alter its value. For example,

(define x 3) x

will evaluate to 3. However, suppose x is mutated to the value 5. Then evaluating x will instead yield 5.

Mutation of a variable in Scheme is accomplished with the set! procedure. The reason for the exclamation point (often referred to as a "bang!") is to warn the programmer that calling the set! procedure causes a side effect; this is common practice for naming Scheme functions. For example, we might mutate x from 3 to 5 in the following way:

(define x 3)
x
(set! x 5)
x

This results in the following:

3
5

After calling the set! procedure, all future references to x use its new value of 5 instead of its old value of 3. Attempting to call set! on an undefined identifier or one which is out of scope is an error.

Some Scheme programmers discourage the use of set!, and this is reflected in its naming. Mutation is generally much more common than recursion in many languages (especially those that are prone to stack overflows) but this is not necessarily the case with Scheme. In fact, some implementations of Scheme may even be less efficient when using mutation instead of recursion to design algorithms. This is one reason for many Scheme programmers' reliance on recursion. Standard Scheme is also required to properly handle tail call optimization, which also also helps prevent stack overflow. Some also consider purely functional programs (those that involve no use of mutation or side-effects) easier to formally prove correct.

There are several variations on the set! function. The set-car! and set-cdr! functions mutate the car and cdr values, respectively, of a pair.

(define x (cons 3 4))
x
(set-car! x 5)
x
(set-cdr! x 6)
x
(set! x (list 3 4))
x
(set-car! x 9)
x
(set-cdr! x (list 4 5))
x

This yields

(3 . 4)
(5 . 4)
(5 . 6)
(3 4)
(9 4)
(9 4 5)

As previously mentioned, mutation is not always required in Scheme. It is more natural in Scheme to use recursion to accomplish many simple tasks than it is to use mutation. Consider the following version of list-max:

(define list-max
    (lambda (lst)
      (cond
        ((equal? '() lst) -inf.0)
        (else (find-list-max (cdr lst) (car lst))))))

(define find-list-max
    (lambda (lst max-so-far)
      (cond
        ((equal? '() lst) max-so-far)
        (else (find-list-max (cdr lst) (max (car lst) max-so-far))))))

This version is easy to understand for users who have no prior experience programming and so have no concept of variables. On the other hand, this version of find-list-max looks rather awkward:

(define find-list-max
    (lambda (lst max-so-far)
      (cond
        ((equal? '() lst) max-so-far)
        (else 
         (set! max-so-far (max max-so-far (car lst)))
         (set! lst (cdr lst))
         (find-list-max lst max-so-far)))))

It takes 3 more lines of code to accomplish the same task, but nothing has been gained in terms of speed or clarity. (In fact, on some Scheme implementations this may run even slower.)