CS 1 Fall 2008

Lab 9: Mutated car Grows cdr, Terrorizes Local Environment.

Assigned: Monday, November 24, 2008
Due: Saturday, December 6, 2008, 18:00:00

Note: There will be no opportunity for rework on this lab assignment. As a result, it will not be graded on a minimum-score scale. More importantly, though, late submission on this lab may make it difficult or impossible for your TA to grade it in a timely manner. Since your TA's feedback will be helpful in preparing for the final, please make every effort to complete the assignment on time.

DrScheme notes

Many of the procedures below will use the set-car! and set-cdr! procedures we discussed in day 17's lecture. As of version 4.0, DrScheme doesn't support these procedures in their traditional forms (in other words, in DrScheme cons pairs are immutable). There are good reasons for this, but they aren't important for our purposes. Instead, you should use the DrScheme "R5RS" language level for the problems in this assignment. Unfortunately, this will mean that you won't be able to use check-expect to test your code, so you will need to test your code manually.

Part A: Exercises

  1. [20] Compute the result for a in the code below. Do not use the Scheme interpreter; do this offline. You might want to draw a box-and-pointer diagram on a piece of paper to guide your reasoning, but if you do you don't have to hand it in.

    (define (copy-list x)
  (if (null? x) 
      (list)
      (cons (car x) (copy-list (cdr x)))))

(define (bash-cdr! x)
  (if (null? x) 
      x
      (begin
        (set-cdr! (car x) (caar x))
        (bash-cdr! (cdr x)))))

(define a (list (cons 1 2) (cons 3 4) (cons 5 6)))
(define b (copy-list a))
(bash-cdr! b)
a ;; this is what we want the value of

  2. Provide Scheme code that, when evaluated, produces structures shown in the following box-and-pointer diagrams. (You may use intermediate variables along the way as needed.)

    1. [10] a3a.gif
    2. [15] a3b.gif

  3. Consider the following Scheme code:

    (define (copy-list existing-list)
  (if (null? existing-list)
      (list)
      (cons (car existing-list)
            (copy-list (cdr existing-list)))))

(define (insert-in-order new-elem existing-list)
  (if (null? existing-list)
      (list new-elem)
      (if (> new-elem (car existing-list))
          (cons (car existing-list)
                (insert-in-order new-elem (cdr existing-list)))
          (cons new-elem existing-list))))

(define (insert-in-order-newlist new-elem existing-list)
  (if (null? existing-list)
      (list new-elem)
      (if (> new-elem (car existing-list))
          (cons (car existing-list)
                (insert-in-order-newlist new-elem (cdr existing-list)))
          (cons new-elem (copy-list existing-list)))))

(define (insert-in-order! new-elem existing-list)
  (define (insert-in-order-aux! new-elem existing-list)
    (if (null? (cdr existing-list))
        (set-cdr! existing-list (list new-elem))
        (if (< new-elem (cadr existing-list))
            (set-cdr! existing-list (cons new-elem (cdr existing-list)))
            (insert-in-order-aux! new-elem (cdr existing-list)))))
  (if (null? existing-list) 
      (list new-elem)
      (if (< new-elem (car existing-list))
          (cons new-elem existing-list)
          (begin
            (insert-in-order-aux! new-elem existing-list)
            existing-list))))

(define (delete-element! elm existing-list)
  (define (delete-element-aux! elm existing-list)
    (if (null? (cdr existing-list))
        'done
        (if (= (cadr existing-list) elm)
            (set-cdr! existing-list (cddr existing-list))
            (delete-element-aux! elm (cdr existing-list)))))
  (if (null? existing-list) 
      existing-list
      (if (= elm (car existing-list))
          (cdr existing-list)
          (begin
            (delete-element-aux! elm existing-list)
            existing-list))))

(define ref (list 1 2 5 6 7))
(define a (copy-list ref))
(define b (copy-list a))
(define c (insert-in-order 3 a))
(define d (insert-in-order-newlist 3 a))

    Here is the environment diagram at this point [also available here for xfig]:

    A_3.gif

    1. [30] By reasoning about and with the given box-and-pointer diagram, and not by querying the Scheme interpreter, determine the values of each of the following:

      (define t1 (cons (eq? a b) (equal? a b)))
(define t2 (cons (eq? c d) (equal? c d)))
(define t3 (cons (eq? (cdr (cdr (cdr c))) (cdr (cdr a)))
                 (eq? (cdr (cdr (cdr d))) (cdr (cdr a)))))

    2. [20] Make a copy of the previous environment diagram and modify it to reflect the following additional operation. (You do not need to leave intermediate frames lying about for this exercise.)

      (define e (insert-in-order! 3 b))

    3. [10] Now, compute the values of each of the following:

      (define t4 (cons (eq? e b) (equal? e b)))
(define t5 (cons (eq? a b) (equal? a b)))

    4. [25] Make a copy of the previous environment diagram and modify it to reflect the following operations. (Likewise, no need to draw in temporary frames which do not persist.)

      (define f (delete-element! 6 d))
(define g (delete-element! 6 c))
(define h (delete-element! 6 e))

    5. [10] Finally, compute the values of each of the following:

      (define t6 (cons (eq? a ref) (equal? a ref)))
(define t7 (cons (equal? (cdr (cdr (cdr d))) (cdr (cdr a)))
                 (eq? (cdr (cdr (cdr d))) (cdr (cdr a)))))

  4. [10] What's wrong with these expressions?

    1. (set-car! (list))

    2. (define a 4)
      (set-cdr! a 3)

    3. (define a (cons 1 2))
      (set! (car a) 42)
      (set! (cdr a) 666)

    4. (define x 10)
(define a (cons 'x 'y))
(set! (car a) 10)

    5. (define lst (list 1 2 3 4 5))
(set-cadr! lst 10)

    After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".

Part B: Book Exercises

Please work the following exercises from the textbook:

  1. [20] Exercise 3.13 (circular lists)

  2. [20] Exercise 3.16 (counting pairs I)

  3. [40] Exercise 3.17 (counting pairs II). You may find the memq function to be useful. Hint: Use a helper function to create a list of all the pairs in the original list, and then compute the length of this list. Note that list mutation is not needed to solve this problem. Here is some code and some tests to get you started:

    ;; collect-pairs: any (list-of pairs) -> (list-of pairs)
;; This function creates a list of all the pairs in x.  x may be 
;; a data structure formed from pairs, or just a Scheme value.
(define (collect-pairs x allpairs)
   ...) ;; fill in your code here

;; cyclic-count-pairs: list-of any -> number
;; This function counts the number of distinct pairs in a list.
;; The list may be circular i.e. it may have any number of internal connections.
(define (cyclic-count-pairs x) 
  (length (collect-pairs x (list))))

;; structures to test
(define a (list 'a 'b 'c))
(define b1 (cons 'b 'c))
(define b (cons 'a (cons b1 b1)))
(define c1 (cons b1 b1))
(define c (cons c1 c1))
(define d (list 'a 'b 'c))
(set-cdr! (cddr d) d)
;; tests
(cyclic-count-pairs a) ;; should be 3
(cyclic-count-pairs b) ;; also 3 
(cyclic-count-pairs c) ;; also 3 
(cyclic-count-pairs d) ;; also 3

Part C: Good Code, Bad Code

Ben Bitdiddle is very excited about his new ability to mutate data structures. Using the new set-cdr! capability, he boasts he can make a really efficient set implementation. He has developed the following side-effecting, message-passing set implementation:


(define (make-set . initial-contents)

  (define (make-uniq! some-list)
    (if (null? some-list) 
        'done
        (begin
          (remq! (car some-list) some-list)
          (make-uniq! (cdr some-list)))))

  (define (remq! element some-list)
    (cond ((or (null? some-list) (null? (cdr some-list)))
           ;; can't splice out first element   
           'done)
          ((eq? (cadr some-list) element)
           (set-cdr! some-list (cddr some-list)) ;; splice out element
           ;; then recheck for element in cadr position
           (remq! element some-list))
          (else
           ;; cadr position doesn't have element, so restart on cdr
           (remq! element (cdr some-list)))))

  (define (intersect! list-a list-b)
    (if (null? (cdr list-a)) ;; don't remove first element
        'done  
        (begin
          (if (not (memq (cadr list-a) list-b))
              (begin
                (remq! (cadr list-a) list-a)
                (intersect! list-a list-b))
              (intersect! (cdr list-a) list-b)))))

  (let ((contents (cons '*set* initial-contents)))
    (lambda (op . args)
      (cond ((eq? op 'add!)
             (set-cdr! contents (cons (car args) (cdr contents))))
            ((eq? op 'remove!)
             (remq! (car args) contents) 
             (cdr contents))
            ((eq? op 'contains?)
             (if (memq (car args) (cdr contents)) #t #f))
             ;; this could also be written as (list? (memq (car args) (cdr contents)))
            ((eq? op 'get-list)
             (make-uniq! (cdr contents))
             (cdr contents))
            ((eq? op 'union!)
             (set-cdr! contents (append (cdr contents) ((car args) 'get-list)))
             (cdr contents))
            ((eq? op 'intersection!)
             (intersect! contents ((car args) 'get-list))
             (cdr contents))
            (else (error "undefined operation" op))))))

He shows that it works by performing the following operations:

(define a (make-set 1 2 3))
(define b (make-set 2 3 4))
(b 'union! a)
(b 'get-list)

for which the Scheme interpreter reports:

(2 3 4 1)

Alyssa looks at Ben's code and claims it has some unintended side effects. "But look at the value of a now!" she says:

(a 'get-list)

"And that's not all! Consider:"

(define c (make-set 1 2 3 4 5))
(define d (make-set 6 7 8 9 10))
(c 'get-list)
(d 'get-list)
(d 'union! c)
(d 'get-list)
(d 'remove! 4)
(d 'get-list)
(c 'get-list)

  1. [45] What errors do Alyssa's examples demonstrate? Why does Ben's code have this problem?

  2. [10] Describe a general principle you can follow to help avoid problems like Ben's in your own implementations.

  3. [45] Fix Ben's code so that it behaves correctly. Explain why the fix works. (How does it solve the problem identified above?)

Part E: Exposure: Macros

NOTE: This section is optional. It is intended to fill out your understanding of Scheme, and cover some useful and practical aspects of the language that we don't have time to cover thoroughly in lectures. To repeat: YOU DO NOT HAVE TO DO THIS SECTION. If you are pressed for time, feel free to skip it. If you submit it, it will be graded but the mark will not count towards your lab grade.

Some of you already know how to program in C and/or Java. In this section we're going to use macros (as described in day 17's lecture) to re-create many of the syntactic features of C and Java. This is not meant to imply that this is the kind of macro one would normally write; normal Scheme code is perfectly sufficient to handle these kinds of problems. However, these are some of the easiest macros you can write, so they're useful for illustration purposes.

For reference material on macros, look here and here.

  1. [10] You're tired of typing set! all the time when you do an assignment operation. Instead, you'd like to use something simpler, like  :=   (a colon followed by an equal sign), so that instead of writing:

    (set! x 10)

    You can write

    (:= x 10)

    Write a simple macro using define-syntax that defines the := special form in this way. [3 lines]

    Note: C and Java actually use the = sign for this operation, but we don't want to conflict with the built-in = function in Scheme, so we use := instead.

  2. [15] C and Java provide several shortcut operators to handle common situations. Translated into Scheme, these would include:

    (++ x)    ;; same as (set! x (+ x 1))
(*= x y)  ;; same as (set! x (* x y))

    Write two simple macros to define ++ and *= as special forms. [3 lines each]

  3. [40] C and Java also have a looping construct called a while loop that will execute a block of code repeatedly as long as some condition stays true. We could use this, in conjunction with some of the macros we defined above, to write a definition of the factorial function like this:

    (define (factorial n)
  (let ((result 1)
        (i 1))
    (while (<= i n)        ;; test
           ((*= result i)  ;; body
            (++ i)))       ;; body
    result))

    Use the do special form we introduced in lecture 17 to write a macro defining while as a special form in terms of do. [4 lines]

[end lab 9]