CSC 153: Computer Science Fundamentals Grinnell College Spring, 2005 Laboratory Exercise Reading

# Sorting and Mutation

## Abstract

This reading introduces assignment as a mechanism to change a binding as a side effect of a procedure.

## Environments

The reading on the insertion sort described two procedures, `insert-item` and `insertion-sort`, for sorting a list of numbers:

``````
(define insert-item
(lambda (item ls)
(if (or (null? ls) (<= item (car ls)))
(cons item ls)
(cons (car ls) (insert-item item (cdr ls)))
)
)
)
(define insertion-sort
(lambda (ls)
(if (null? ls)
ls
(insert-item (car ls) (insertion-sort (cdr ls)))
)
)
)
``````

Each of these procedures is recursive, and the Scheme interpreter keeps track of various bindings of the parameter `ls`. For example, if `trace-define` is used for `insertion-sort` and the procedure is run on the list `(3 1 4 1 5)`, the following output results:

``````
> (insertion-sort '(3 1 4 1 5))
|(insertion-sort (3 1 4 1 5))
| (insertion-sort (1 4 1 5))
| |(insertion-sort (4 1 5))
| | (insertion-sort (1 5))
| | |(insertion-sort (5))
| | | (insertion-sort ())
| | | ()
| | |(5)
| | (1 5)
| |(1 4 5)
| (1 1 4 5)
|(1 1 3 4 5)
(1 1 3 4 5)
``````

Here, the binding of the parameter `ls` is like writing the variable and its value on a three-by-five card and filing it away in a box of similar cards. Successive procedure calls introduce a new card with the new value on it, and this value is paper-clipped to the front of the card for the old binding. During the procedure call, the new binding takes precedence over the old one, since its card is on top; but when the procedure returns, the top card is removed and thrown away, and the old binding is still in place and in force. The Scheme interpreter maintains an internal table of variables and values that is similar to such a card box. In Scheme, this table of variables and values is called an environment.

A `let`-expression produces a similar effect. This is illustrated by the following interaction in Scheme.

```> (define str "original binding")

> str
"original binding"

> (let ((str "new binding"))
str)
"new binding"

> str
"original binding"
```

In this example, an initial variable str is bound to one value, and a local variable str is bound to another value within a let-expression. After the let-expression is completed, execution returns to the initial str.

### Definitions

In contrast to local bindings, a definition overrides a previous definition, the effect is somewhat different. You should think of the new value in such a case as replacing or overwriting the old one, as if the value printed on the three-by-five card containing the old binding were erased and a new value written in on the same card. After such a redefinition, there is no way to recover the old value, and at the implementation level it is quite possible that the memory location that it used to occupy is now occupied instead by the new value. In short, redefinition has the effect of assigning a new value to an existing variable, rather than creating a second binding for that variable.

In recognition of this difference in the way the bindings are treated, variables that are either predefined or bound by top-level definitions are sometimes called global variables, while procedure parameters and variables that appear in the binding lists of `let`-expressions are local variables. (A top-level redefinition of a variable changes its value "globally" -- through all subsequent uses of that binding -- whereas other rebindings change the value only "locally," within a procedure body or the body of a `let`-expression.)

### Set! Expressions

From past work, you know that Scheme's `define` statement establishes a new variable and gives it a value. Subsequent uses of `define` at Scheme's top level change that value.

Within a procedure, an assignment or `set!` expression changes a binding, as shown in the following example:

```> (define ch #\A)
> ch
#\A

> (define ch #\B)
> ch
#\B

> (set! ch #\C)
> ch
#\C

> (set! ch #\D)
> ch
#\D

> (let ((ch #\E))
(display "0: ") (display ch) (newline)
(set! ch #\F)
(display "1: ") (display ch) (newline)
(set! ch #\G)
(display "2: ") (display ch) (newline)
(set! ch (integer->char 114))
(display "3: ") (display ch) (newline)
(set! ch "I'm tired of this game.")
(display "4: ") (display ch) (newline))
0: E
1: F
2: G
3: r
4: I'm tired of this game.

> ch
#\D
```

When an assignment expression is evaluated, the new-value expression is evaluated first, and then the current binding for the variable is changed so that the variable is bound to the new value. (The old value written on the topmost card for that variable is erased and the new value is written instead.)

It is an error to assign a new value to a variable that is not bound at all -- if there is no card in the box for a certain variable, there's nothing to erase. (Chez Scheme will step in and create a global variable for you if you commit this error, but most implementations of Scheme are not so considerate.)

Similarly, the operations `set-car!`, `set-cdr!`, and `append!` change various parts of a list.

### Assignment Expressions For Sorting Global Data

The above `insert-item` and `insertion-sort` procedures return a newly sorted list, which is separate from the original list. If we always want to sort data stored in a global variable `data`, then we can use `set!` to update such data as follows:

First, we define a simple, parameterless procedure:

``````
(define sort-data
(lambda ()
(set! data (insertion-sort data))
)
)
``````

Then, we call this procedure whenever the `data` list is to be sorted. This is illustrated in the following sequence:

``````
(define data '(3  1  6  -8  4))
(sort-data)
data
==> (-8 1 3 4 6)
``````

### Assignments To Parameter Lists

For a more general sorting algorithm, we can change a list parameter by changing the `car` and `cdr` of the list, as shown in the following variation of `insertion-sort`:
``````
(define insertion-sort
(lambda (ls)
(letrec ((sort-data
(lambda (lst)
(if (null? lst)
lst
(insert-item (car lst) (sort-data (cdr lst)))))))
(let ((result (sort-data ls)))
(set-car! ls (car result))
(set-cdr! ls (cdr result))
result
)
)
)
)
``````
Finally, consider the following variation of the above code:
``````
(define insertion-sort
(lambda (ls)
(letrec ((sort-data
(lambda (lst)
(if (null? lst)
lst
(insert-item (car lst) (sort-data (cdr lst)))))))
(let ((result (sort-data ls)))
(set! ls result)
ls
)
)
)
)
``````

Now consider the following test runs with this procedure:

``````
(define first '(3  1  6  -8  4))
first
==> (3  1  6  -8  4)
(define second '(5 3 7 9 2 6 1 8))
second
==> (5 3 7 9 2 6 1 8)
(insertion-sort first)
(insertion-sort second)
first
==> (3  1  6  -8  4)
second
==> (5 3 7 9 2 6 1 8)
``````

To understand why these results are obtained, consider how lists are represented within Scheme -- using box and pointer diagrams. Originally, `first` points to the designated list:

When `insertion-sort` is called, parameter `ls` is made to point to the same list:

When procedure `sort-data` is called, a new ordered list is returned, and variable `result` is set to designate this new list:

The `set!` expression changes `ls` to point to the new list:

The final line `ls` returns this new list as the result of the procedure. However, as the diagram shows, the variable `first` still points to the original, unchanged list.

This document is available on the World Wide Web as

```http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-mutation.shtml
```

 created November 12, 1997 with parts taken from a lab by John D. Stone, revised on March 8, 1998 revised January 11, 2000 by Henry M. Walker last revised February 3, 2005 For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.