Sorting and Mutation

Goals

This laboratory exercise provides experience with assignment as a mechanism to change a binding as a side effect of a procedure.

Environments

1. Consider the following definition sequence:

   > (define str "original binding")
   > (let ((str "second binding"))
       (display "2: ") (display str) (newline)
       (let ((str "third binding"))
         (display "3: ") (display str) (newline)
         (let ((str "fourth binding"))
           (display "4: ") (display str) (newline)
           (let ((str "fifth binding"))
             (display "5: ") (display str) (newline))
           (display "4: ") (display str) (newline))
         (display "3: ") (display str) (newline))
       (display "2: ") (display str) (newline))
   

   Run this code, describe the output, and explain how that result is achieved.

2. Consider the following interaction that appears in the reading:

   > (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
   

   Review this interaction, and explain what happens at each step.
   Here, ch is both a global and a local variable. Be sure you can explain which value is changed when and why.

Assignment Expressions For Sorting Global Data

Consider the following definitions for insert-item, insertion-sort, and sort-data:

(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)))
      )
   )
)
(define sort-data
   (lambda ()
     (set! data (insertion-sort data))
   )
)

3. Enter the code for insert-item, insertion-sort, and sort-data, and run the following sequence of operations:

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

   Explain the results you obtain.

Assignments To Parameter Lists

Next consider the following variation of insertion-sort that changes its list parameter by changing its car and cdr:

(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
          )
      )
   )
)

4. After defining this new insertion-sort, run the following sequence of operations:

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

   1. Explain how this insertion-sort produces its output; that is, hypothesize how is the parameter changed.

   2. What is the purpose of the final result within the let statement; what happens if this line is omitted?

(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
          )
      )
   )
)

5. Run this code with the same operations as for step 4, and describe the results.

6. Draw diagrams for the previous version of insertion-sort from step 4 to clarify further why the code with set-car! and set-cdr! works correctly -- even though the latest version with (set! ls result) does not change the global variable.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-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.