| CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
| Laboratory Exercise Reading | ||
This reading introduces assignment as a mechanism to change a binding as a side effect of a procedure.
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.
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.)
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.
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)
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
)
)
)
)
(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. |