recitation 12: mutation

-------------------------------------------------------
data abstraction & contract:
constructors (often tagged), selectors, MUTATORS, operations

(set! <variable> <value>) ==> undefined
looks for the binding of <variable>, and changes the binding to <value>

* Is set! a special form?
  yes. it doesn't follow the normal evaluation rules, because we don't 
  want to evaluate <variable>

(set-car! <arg1> <arg2>) ==> undefined
(set-cdr! <arg1> <arg2>) ==> undefined
change the car/cdr part of the cons cell <arg1> to be <arg2>

* Is set-car!/set-cdr! a special form?
  no.  we may not have the details of how the mutation is performed, but we 
  do follow the normal evaluation rules and evaluate both arguments.

* What's the difference between changing a binding (set!) & changing
  an object (set-car!, set-cdr!)?
  if multiple things (variable names) point to the same object, changing 
  one of the bindings won't affect the other variables.  however if we 
  change the object, all the variables will be reflect the change.

* What do we mean when we say "we've broken the substitution model"?
  - If we have assignment (set!), an expression's value depends
    on *when* it is evaluated.  We need a notion of time.

* What's functional programming?  
  - An expression has the same value each time it is evaluated.

-------------------------------------------------------
drawing cons cell diagrams:
      * any time you see cons, draw a double box with 2 pointers
      * any time you see list with n items, draw a chain of n cons cells
      * (list) with no items is nil
      * evaluate the stuff inside & point to it
NEW!  * when you see set-car!/set-cdr!, figure out which cons cell 
        <arg1> is referring to, evaluate <arg2> and point the first/second 
        part of the cons cell to that value.

-------------------------------------------------------
(define x (list (list 1 2) (list 1 2)))
(define y (let ((temp (list 1 2)))
	    (list temp temp)))
x ==> ((1 2) (1 2))
y ==> ((1 2) (1 2))
(set-car! (car x) 3)
(set-car! (car y) 3)
x ==> ((3 2) (1 2))
y ==> ((3 2) (3 2))

(set-cdr! (car (cons 1 2)) 3)  ==> 
error! the first argument to set-cdr! is not a pair

(set-car! (cdr (list 1 2 3)) (cons 4 5))  ==> 
works ok, but nothing useful happens since the return value is
unspecified and we lose the data structure since we didn't name it

-------------------------------------------------------
(define (mystery x)
  (define (loop x y)
    (if (null? x)
	y
	(let ((temp (cdr x)))
	  (set-cdr! x y)
	  (loop temp x))))
  (loop x '()))

(define a (list 1 2 3 4))
a  ==> (1 2 3 4) 
(define b (mystery a))
a  ==> (1) 
b  ==> (4 3 2 1) 

-------------------------------------------------------
Let's play with a ring data structure!

(define (last-pair lst)
  (cond ((not (pair? lst)) (error "should be a pair!"))
	((null? (cdr lst)) lst)
	(else (last-pair (cdr lst)))))

(define (make-ring lst)
  (set-cdr! (last-pair lst) lst)
  lst)

* Draw the box & pointer diagram: 

  (define x (make-ring (list 1 2 3 4)))
  x  ==>  (1 2 3 4 1 2 3 4 .... 
          <infinite loop> (unless a print depth is set)
  (last-pair x)  ==>  <infinite loop>

* Write (print-n-elements ring n):

  (print-n-elements x 6)  ==>   1 2 3 4 1 2
  (define y (cdddr x))
  (print-n-elements y 6)  ==>   4 1 2 3 4 1
  
(define (print-n-elements ring n)
  (cond ((null? ring) (error "not enough elements"))
        ((= n 0) (newline))
        (else (display (car ring))
              (display " ")
              (print-n-elements (cdr ring) (- n 1)))))

* Write (change-nth-element ring n elt):

  (change-nth-element! x 2 'testing)
  (print-n-elements x 6)  ==>   1 2 testing 4 1 2
  (print-n-elements y 6)  ==>   
  
(define (change-nth-element ring n elt)
  (if (= n 0)
      (set-car! ring elt)
      (change-nth-element (cdr ring) (- n 1) elt)))

* Write (count-links ring):

  (count-links x)  ==>  4
  
(define (count-links ring)
  (define (helper count current)
    (if (eq? current ring) 
        count
        (helper (+ 1 count) (cdr current))))
  (helper 1 (cdr ring)))

* Write (forward ring) and (backward ring):

  (print-n-elements (forward x) (count-links x))  ==> 2 testing 4 1
  (print-n-elements (backward x) (count-links x)) ==> 4 1 2 testing
  
(define (forward ring) 
  (cdr ring))

(define (backward ring) 
  (define (helper current)
    (if (eq? ring (forward current))
        current
        (helper (forward current))))
  (helper (forward ring)))

* What's the order of growth in time of forward & backward?
    forward:  O(1)     backward:  O(n)

* Write (insert-after! ring elt) and (insert-before! ring elt):

  (insert-after! x 'after)
  (print-n-elements x (count-links x))  ==> 1 after 2 testing 4
  (insert-before! x 'before)
  (print-n-elements x (count-links x))  ==> 1 after 2 testing 4 before

(define (insert-after! ring elt)
  (let ((tmp (cons elt (cdr ring))))
    (set-cdr! ring tmp)))
    
(define (insert-before! ring elt) 
  (insert-after! (backward ring) elt))

* What's the order of growth of insert-after! & insert-before!
    insert-after!:  O(1)     insert-before!:  O(n)

* How can we change the design of our ring data structure to make
  these operations O(1) time?
    use a doubly-linked list.  each element points to the next element, 
    like a regular list, but also to the previous element.  this could
    be done with two cons cells (or vectors of length 3!)

-------------------------------------------------------