copy (moderately long message)

[apollo!dfm@uw-beaver.arpa]

Here's a more detailed description of one possible version of copy.  I believe this
combines most of the features people have suggested in recent mail and clarifies
most of the ambiguities people have pointed out in recent mail.



copy object &key :array :structure :hash-table :readtable :pathname :random-state
                 :gensym :fill-pointer :adjustable :level :circle

Recursively copies object as follows:

  If object is a cons copy returns a new cons (i.e. it is guaranteed that
  (and (consp object) (eq (copy object) object)) => nil) and calls itself
  recursively to fill in the car and cdr.

  If object is an array and :array is non-nil (it defaults to t) copy returns a new
  array as follows:

    The rank, dimensions, and element type are the same as object, subject to the
    restrictions regarding fill pointers below.  Even if object is displaced, the
    result is not.  The contents of the array are recursively copied.  If an element
    of the array is undefined (e. g. not initialized), it is undefined in the
    result.  In particular, if an implementation can recognize that an element
    is undefined it need not copy that element.

    Only if object has a fill pointer and :fill-pointer is non-nil will the result
    have a fill pointer.  The fill pointer is initialized to the same value as
    object's fill pointer, and all the defined elements of object, even those that
    are inactive with respect to the fill pointer, are copied.  If the object has a
    fill pointer but :fill-pointer is nil the result does not have a fill pointer,
    and the length of the resulting vector is reduced to the current value of
    object's fill pointer.  :Fill-pointer defaults to nil.

    Only if object is adjustable and :adjustable is non-nil is the result adjustable.
    :Adjustable defaults to nil.

  If object is a user defined structure and :structure is non-nil copy returns
  a new structure of the same type.  If object is named, the result acquires the
  same name (i.e. if object is a user defined, named structure then
  (eq (type-of object) (type-of (copy object)) => t).  The values of the slots
  of object are recursively copied to the result.  If the value of a slot of object
  is undefined, the value of the corresponding slot in the result is undefined.
  In particular, if an implementation can recognize that a slot's value is
  undefined it need not copy that slot.  Any slots skipped over by the
  :initial-offset option to defstruct are not recursively copied; that is, their
  values in the result are eql to their values in object.  :Structure defaults
  to t.

  If object is a hash table and :hash-table is non-nil copy returns a new hash table
  whose size is at least as large as that of object, and with the same test,
  rehash-size, and rehash-threshold.  An entry is made in the new hash table for
  each entry in object: keys are not recursively copied (i.e. the key in the new
  table is eql to that in the old) but values are recursively copied.  :Hash-table
  defaults to nil.

  If object is a readtable and :readtable is non-nil copy returns the same value as
  (copy-readtable object).  :Readtable defaults to nil.
  
  If object is a pathname and :pathname is non-nil copy returns the same value as
  (make-pathname :host      (pathname-host object)
                 :device    (pathname-device object)
                 :directory (pathname-directory object)
                 :name      (pathname-name object)
                 :type      (pathname-type object)
                 :version   (pathname-version object) )
  :Pathname defaults to t.

  If object is a random state and :random-state is non-nil copy returns the same
  value as (make-random-state object).  :Random-state defaults to t.

  If object is an uninterned symbol and :gensym is non-nil copy returns the same
  value as (copy-symbol object).  :Gensym defaults to t.

  Otherwise copy simply returns a value eql to object.

The :level argument can be used to limit the depth of recursion.  If supplied and
non-nil it should be a non-negative integer, in which case copy will only copy items
at that depth or shallower.  For example, (copy object :level 1) copies only the top
level object itself.  As a boundary case (copy object :level 0) returns object with-
out any copying.  In the case of conses the depth is considered to increase only
through the cars, and not the cdrs; that is, an entire list is considered to be at
the same level.  For example, if L is a list, then (copy L :level 1) returns the
same value as (copy-seq L).  :Level defaults to nil.

If object is circular, or contains circular substructures, copy may fail to
terminate.  If :circle is non-nil copy endeavors to detect cycles and terminate
normally, returning an isomorphic object.  :Circle defaults to nil.




NOTES:

- The basic intention is that (copy object) be similar to
  (read-from-string (write-to-string object :array t)), with objects that would be
  printed using #< notation not being copied.  Exactly what objects are printed
  using #< notation is implementation dependent, and it seems best that the value
  returned by copy be as implementation independent as possible.  Therefore some
  choices have to be made, mostly reflected in the defaults (e.g. I expect most
  implementations to print hash tables using #<, but pathnames in some readable
  format).  These choices are obviously subjective.

- The reason no mechanism for preserving displacement in copying arrays is provided
  is that displacement is typically an effort to deliberately avoid copying.

- It might seem strange to allow numeric and character keys in a #'eq hash table
  to be copied (a la eql).  However, I don't think that it can ever make sense to
  use a #'eq hash table portably with numbers and characters.

- Note that copying a readtable, pathname, or random state may be a "shallow" copy.
  However, since the structure of these items is not defined by the language it
  seems incorrect to try to define it otherwise.

- No mechanism is supplied for copying interned ids or packages as that would appear
  to raise some prohibitively awkward issues.

- No machinism is supplied for copying streams or functions, as the semantics of
  these seem to be too implementation dependent.

- I see no reason why implementations couldn't allow copying other types of objects
  by supplying more keyword arguments.  Such extensions would, of course, not be
  portable.

- Regarding :level and cdrs there seems to be a choice to be made between lists and
  trees of conses.  Lists are by far the more prevalent data structure so it seems
  best to favor them.  This also makes :level parallel the use of :level in write.

- One might expect that if there's a :level there should be a :length.  This is
  awkward for anything but lists, however.  While I would expect
  (copy '((1) (2) (3)) :length 2) to copy the first two elements but not the third,
  what do I do about (copy '#((1) (2) (3)) :length 2)?  One could say that we don't
  copy the entire surrounding structure, and, for consistency, apply the same rule
  to lists; the complexity of this seems to more than outweigh the dubious
  usefulness of :length in copy.

- I believe that (equalp x (copy x)) => t.  Indeed, the intermediate equality
  predicate that Eric Benson proposed (case sensitive equalp) (and that I agree
  is needed -- and should be supported as a hash table test) should also be true.

- I believe that this copy can easily be written in COMMON LISP, once the proposed
  functions hash-table-size, etc. have been added, except for the code dealing with
  structures. That implies to me that COMMON LISP probably needs more functionality
  for manipulating structures.  For example, I don't think that there is even a
  portable way of even telling whether or not an object *is* a user defined
  structure.

                                                - Don Morrison