recitation 13: mutation

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

(set! <variable> <value>)

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>)
set-car!: pair,A -> undefined
(set-cdr! <arg1> <arg2>)
set-cdr!: pair,A -> 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 & changing an object?
  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.

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

(set-car! (cdr (list 1 2 3)) (cons 4 5))  ->  <works ok, but nothing useful printed>

-------------------------------------------------------
* what do we mean when we say "we've broken the substitution model"?

(define (foo x)
  (display (car x))
  (set-car! x 5)
  (display (car x))
  x)

(foo (cons 1 2))
  
* what's functional programming?  
  - An expression has the same value each time it is evaluated.

* if we have assignment (set!), an expression's value depends
  on *when* it is evaluated.  We need a notion of time.

* mutation introduces complexity & unexpected side effects

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

(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  ->  (4)
b  ->  (4 3 2 1)

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

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

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

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

(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 (change-nth-element ring n elt)
  (if (= n 0)
      (set-car! ring elt)
      (change-nth-element (cdr ring) (- n 1) elt)))

(change-nth-element! x 2 'testing)
(print-n-elements x 6)  ->   1 2 testing 4 1 2
(print-n-elements y 6)  ->   4 1 2 testing 4 1

(define (count-links ring)
  (define (helper count current)
    (if (eq? current ring) 
        count
        (helper (+ 1 count) (cdr current))))
  (helper 1 (cdr ring)))

(count-links x)  ->  4

(define (forward ring) 
  (cdr ring))

(define (backward ring) 
  (define (helper current)
    (if (eq? ring (forward current))
        current
        (helper (forward current))))
  (helper (forward 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

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

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

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

* 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 all of these operations O(1)?
    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.

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