[4/7/99]

===============================================================================

* The meaning of cons cells and lists using box and pointer diagrams.

  Note: the graphs are not in the section notes.

  Draw these constructions:
    (cons 1 2)
    (list 1 2)
    (list 1 2 3 4)
    (cons 1 (cons 2 (cons 3 4)))  the list? predicate will return #f for this
    (list (cons 1 2) (cons 3 4) (cons 5 6))
    (list (list (list 1 2)) (list 3) 4 (list (cons 5 5)))

  Two importat concepts that pop up when you use these pointers (and in fact
  other pointers), is sharing and destructive operations.  Sharing happens when
  two variables (or objects) point to the same exact objects.  Destructive
  operations are operations that modify the pointer structure of an existing
  construction instead of creating a new one.

  All kinds of problems can arise if use sharing and destructive operations,
  and you are not extra careful with what you're doing.

  A simple example for sharing:

  --------------------
    (define x (list 1 2 3))
    (define y (cons 10 x))
    (define z (cons 20 x))
  --------------------

  An example for a destructive operation is:

  --------------------
    (define (inc-second! x)
      (set! (second x) (+ 1 (second x))))
  --------------------

  Now if we do this:

  --------------------
    (inc-second! y)
    (inc-second! z)
  --------------------

  Then y evaluates to (10 3 2 3) and z to (20 3 2 3).

  Notes:
  - set! can work on most accessor functions, examples are head, tail, first,
    second etc.
  - It can also work on slots with a defined accessor.
  - The convention is to have a "!" at the end of function ames that are doing
    side effect.  This is sometimes dropped in object system, since the main
    idea about OOP is objects with local state that is modified.

===============================================================================

* An example for destructive operations and their usage:

  --------------------
    (define (append! l1 l2)
      (define (do-it! l1)
        (if (null? (tail l1))
          (set! (tail l1) l2)
          (do-it! (tail l1))))
      (if (null? l1)
       l2
       (begin
         (do-it! l1)
         l1)))
    (define a '(1 2 3))
    (define b (append! '(10) a))
    (define c (append! '(10) a))
    a                       --> (1 2 3)
    b                       --> (10 1 2 3)
    c                       --> (10 1 2 3)
    (eq? b c)               --> #f
    (equal? b c)            --> #t
    (eq? (tail b) (tail c)) --> #t
  --------------------

  Show the box/pointer diagrams from the above.

  Important notes:

  - Make sure you understand the difference between eq? and equal?.

  - Note that generally, if you want a to be appended with b using sharing,
    then this is an error: (append! a b) because a might be null.

  - This is the reason that append! _must_ return a value.

  - This function is actually built in.  It can help you in the near future.

===============================================================================