[4/12/99]

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

* A quick note: last time we saw the append! function that modifies its first
  argument to point at the second.  This is the code we had:

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

  To make this simpler, we can use the last-pair built-in function that returns
  the last cons pair in a list - so its tail can then be modified:

  --------------------
    (define (append! l1 l2)
      (if (null? l1)
        l2
        (begin
          (set! (tail (last-pair l1)) l2)
          l1)))
  --------------------

  Note that this function should be used in exactly the same way.

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

* Yet another example of a destructive operation (also built-in):

  --------------------
    (define (reverse! l)
      (define (iter l done)
        (let ((tmp (tail l)))
          (set! (tail l) done)
          (if (null? tmp)
            l
            (iter tmp l))))
      (if (null? l)
        l
        (iter l '())))
  --------------------

  Go over this function extra-careful, it is very confusing!

  Also, using it can be tricky:

  --------------------
    (define a '(1 2 3))
    (reverse! a) --> (3 2 1)
    a            --> (1)
  --------------------

  Not to mention the mess you'll get if you'll use this with lots of sharing.

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

* So, as we've already seen, eq? compares object identities, rather than their
  structure, but equal? goes down lists to compare their structure.

  This difference is crucial - many times, the meaning of a piece of code can
  be very different if it is using one predicate or the other to compare
  objects.  For example, here is a demonstration of the difference between the
  built-in functions remq and remove that are basically doing the same, but the
  former uses eq? and the latter equal?:

  --------------------
    (remq 2 '(1 2 3))        --> (1 3)
    (remq '(2) '(1 (2) 3))   --> (1 (2) 3)
    (remove '(2) '(1 (2) 3)) --> (1 3)
    (remq "2" '(1 "2" 3))    --> (1 "2" 3)
    (remove "2" '(1 "2" 3))  --> (1 3)
  --------------------

  Another point to note about the usage of remq/remove is that both are
  non-destructive functions.  This can be tested very easily as follows:

  --------------------
    (define a '(1 2 3))
    (remq 2 a) --> (1 3)
    a          --> (1 2 3)
  --------------------

  Note that 2 can be removed with remq - the reason for this is that we have
  two essentially different types of objects - "boxed" objects and "unboxed"
  objects.

  Boxed objects are such that are wrapped in a "box", so actually the value
  assigned to a variable that holds them is a pointer.  Examples are lists and
  strings.  You can think of these objects as having identity, using eq? on
  boxed objects returns #t only if it is the actual _same _ object.

  --------------------
    (eq? "foo" "foo")      --> #f
    (eq? '(1 2) '(1 2))    --> #f
    (equal? "foo" "foo")   --> #t
    (equal? '(1 2) '(1 2)) --> #t
  --------------------

  Unboxed objects are simple values that are being held directly.  There is no
  meaning to say that these objects have their own identities.  Examples of
  such objects are booleans, small integers and characters.  Using eq? on these
  objects always return #t.

  --------------------
    (eq? 12 12)      --> #t
    (eq? #f #f)      --> #t
    (eq? #\a #\a)    --> #t
  --------------------

  Notes:

  - The empty list () is also an unboxed value.

  - Only small integers are unboxed since Scheme handles integers of unlimited
    size so at some point the value becomes a pointer to an internal structure.

  The main feature of boxed objects is that they have an internal structure
  that can be shared and modified.  This is an issue in most programming
  languages, especially in Java that "borrowed" these ideas from Lisp - for
  example, you have two types of strings, one is a string that is taken as a
  constant, and the other is a string that you are allowed to mutate.

  Sometimes you want to implement boxed values that are _treated_ as if they
  were unboxed.  For example, in Swindle, I compare classes using eq?.
  Singleton "classes" are actually a list of the 'singleton symbol and the
  object.  To make it look like these objects are unboxed, I have to use some
  structure (a hash table) that stores a single value that is returned when the
  singleton function is called (you can actually look for the mechanism that
  does that in the file tiny-clos.ss):

  --------------------
    (singleton 1)                     --> (singleton 1)
    (eq? (singleton 1) (singleton 1)) --> #t
  --------------------

  This method is common for such things, another example is the symbols in
  Scheme - there is a table of symbols that ensures that symbols are treated as
  unboxed objects as in (eq? 'a 'a) --> #t.

  Note about box & pointer diagrams - to point out the difference between boxed
  and unboxed objects, we put unboxed objects _inside_ the boxes, and boxed
  objects have pointers to them.  This is one reason for drawing null in the
  box.

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