I have a CLOS object which may contain an arbitrary graph of
other objects. This graph may be cyclic. I'm looking for an
easy way to deep copy the object. I've been told that
generic deep copy might be implementing by writing the
object to a stream, and then reading back from that stream.
Is this the best way of doing it? Is there another way?

Thank you,

  the only easy way out is to write a copier that knows what it's doing.
  any easier way out would violate "as simple as possible, but no simpler".

| I've been told that generic deep copy might be implementing by writing
| the object to a stream, and then reading back from that stream.

  you've been told that?  what a joker that must have been!  how do you
  think you would proceed to implement readers and writers for the objects?
  do you think _they_ come in generic versions that do everything right?

  (for the languages where you may use a generic version that does it wrong
  most of the time, which you usuallyq observe if you try, there _is_ the
  merit to this language design that most "modern programmers" (= dummies)
  are a lot happier when they something out and see it fail, then do it
  "right" (= less _obviously_ wrong), than to know it would fail and know
  they had to do it right from the start.)

  implementing a mechanism that avoids descending into cyclic structures is
  amazingly easy.  detection is easy with the rabbit and the hare algorithm.
  a hash table of copied objects avoids all possible problems to begin with.

Thanks for your tip,

  I'm sorry, but you have been tricked.  just because it exists for C++ is
  not in any way, shape, or form an argument for the _correctness_ of the
  implementation or the algorithm or even the concept to begin with.

| I'm pretty new at lisp; however, so I'm not sure what language-specific
| pitfalls I will encounter yet.

  you encountered a language-specific pitfall and fell headlong into it
  when you believed that C++ had an automatic solution.  you will get out
  of this sorry state of affairs when you realize that such automated tools
  are not able to do their job.  the key to understand this is that even in
  a class for which "deep copy" makes non-zero sense, you don't _always_
  want to deep copy _everything_, and if you fail to implement it right,
  you will in fact destroy valuable information in the copying process.

Common Lisp does not have a generic object copying function because
the notion of `copying' is something that is typically
application-dependent.  Languages that provide one typically provide
one that doesn't work most of the time (C++ is a good example) so you
end up overriding it most of the time.

For objects that CL knows how to print & read, than it is often
possible do a graph copy by printing them to a stream & reading back,
but it's almost always better to write an application-specific
copier.

Here's a (badly written I think) example of dealing with circularities
& sharing for cons trees (only!):

    (defun copy-cons-graph (x)
      (let ((octab (make-hash-table)))
        (labels ((cp (y)
                   (typecase y
                     (cons
                      (or (gethash y octab)
                          (let ((c (cons nil nil)))
                            ;; the new cons needs to be in OCTAB
                            ;; before we try and descend into it.
                            ;; This seems a pretty clunky way of doing
                            ;; this, but it's sunday night.
                            (setf (gethash y octab) c)
                            (setf (car c) (cp (car y)))
                            (setf (cdr c) (cp (cdr y)))
                            c)))
                     (t y))))
          (cp x))))

Finally: I gave a paper on stuff related to this at last year's lugm,
I don't know if it's on the web anywhere, but franz's web site would
be a good place to look (I will put up a descendent of it at some
point, when I have some time).

Perhaps we're having a definition of terms problem?

I can't write a specific graph copier, because I don't have a-
priori knowledge of the structure of the objects that I will be
copying.

Indeed. Perhaps it's time once again to drag out Kent Pitman's classic
"Parenthetically Speaking" article on the subject:

        <URL:http://world.std.com/~pitman/PS/EQUAL.html>
        The Best of Intentions: EQUAL Rights--and Wrongs--in Lisp

which addresses the question "Why is there no generic COPY function?"
[in Common Lisp], and explains why any so-called "automatic" deep copy
is inherently *wrong*.

-Rob

If you think about it, it's strictly impossible to implement utterly
generic graph copy, reflectivity or not (imagine a simple C array of
int; how long is it? Dunno).

My second post hinted at this. In C/C++, we use a vector type, and only
support that. For objects to persist or be relocatable, they have to
be defined using a set of very specific primitives. The arrangement of
these primitives will not be known in advance. Cycles may be present
and must be (and can be) accounted for.

I'm just looking for a simple way to do this with Lisp. Given Lisp's
flexibility, I doubt very highly it would require a code generator,
but I've been wrong before.

(BTW, as Franz has a CORBA binding, and presumably this binding does
Objects By Value, this would suggest that at least one commercial
implementation of what I'm looking for already exists).

...

If this isn't obvious, think for a few seconds about how a general
copier should behave when it comes across a package object, say.

A tip for some of you folks: one of the keys to successful
communication is not to assume that the other person is wrong,
but rather to figure out what they're right *for*.

Bye now,

Erik> implementing a mechanism that avoids descending into cyclic structures is
Erik> amazingly easy.  

if slightly non-obvious at first. For those confused, you have two parts of
your function step through the elements of a list, one going in single steps,
the other in steps of two. If they ever end up in the same element, the list
must have been circular.

Erik> detection is easy with the rabbit and the hare algorithm.

Is this an optimized version of the tortoise and the hare algorithm?

Erik> a hash table of copied objects avoids all possible problems to begin with.

but may not scale.
                                                                      Philip

        I require a generic implementation that knows nothing in
        specific a-priori about the objects it will deep copy

which people have interpreted to mean something like, given an object
O, return a copy of O when you do not know anything about what O is.
But actually, what you really seem to want is something that is very
specific, and works on some small set of classes.  That is easy to
write -- so easy to write that I'm kind of confused why you are asking
for it.  You just need a notion of equality, and way of telling if you
have seen an object equal to the one you are looking at before (if
your notion of equality is EQL or something, then Lisp provides this
functionality in hash tables, if it is some user-defined predicate you
may have to write a small hashtable implementation based on it), and
some basic recursive programming.

There's an information essay by Kent Pitman on this very subject -- see
http://world.std.com/~pitman/PS/EQUAL.html

Here's are extracts:

  ``Why is there no generic COPY function?'' Common Lisp programmers
  often ask this question. [...]

  Programmers want a generic COPY function that somehow ``does the right
  thing,'' but relying solely on the representation type is insufficient
  to resolve intentional distinctions between conses, lists, alists, and
  trees, so we wouldn't know whether to call COPY-CONS (if there were
  such a thing), COPY-LIST, COPY-ALIST, or COPY-TREE.

  Of course, we could just define that COPY-LIST is what's used, but
  that could (and probably would) give the misleading impression that
  such a choice was ``uniquely determined'' or even ``morally correct,''
  instead of just arbitrarily chosen. Also, an arbitrary choice would
  leave users feeling funny about the presence of an operator that can
  copy many--but not all--kinds of objects.

  that's a ridiculously bold statement.  how do you _know_?  would you even
  have _seen_ an error if it occurred?

| Furthermore, if you look into the world of object oriented databases,
| you'll find that various oodbs also do this perfectly well.

  they do it by restricting the domain to fit what they implement, but it
  fits the C++ mind-set to think this way and take it for granted that
  others will understand that "of _course_ we don't do the hard stuff".  in
  this newsgroup and in Lisp, the trivial problems are uninspiring, and so
  we tend to think in broader terms.  this means that arbitrary limits are
  regarded as cheating, unless yo present the limited domain up front as
  inherent engineering decisions.  did you do that?  no.  foo on you for
  that.

| Perhaps we're having a definition of terms problem?

  yes, you come from the C++ world.  C++ people are extremely arrogant the
  way they think they invented object-orientedness.  they didn't, OK?  C++
  doesn't even touch upon the really hard areas.  you have to face this
  fact, or you'll make more ridiculously bold statements that reflect very
  badly on your ability to deal with complexity.

| I can't write a specific graph copier, because I don't have a- priori
| knowledge of the structure of the objects that I will be copying.

  at issue is knowing the _intent_ of the slots, not which they are.  in
  Common Lisp we have the MOP to ask for the structure of the objects.
  piece of cake, really.  just like databases can report on such things.
  it doesn't help one bit in deciding whether to make a shallow or deep
  copy, though.

  do you follow this tip yourself?  if so, how come you don't listen?
  it seems to me you're telling us we're wrong because you have "seen"
  something you believe is sufficient when it isn't.

  a tip for tippers: follow them yourself first, to _show_ how they work
  well for you.  if not, just shut up about the tips.

There's an informative essay by Kent Pitman on this very subject -- see
http://world.std.com/~pitman/PS/EQUAL.html

Here are some extracts:

  ``Why is there no generic COPY function?'' Common Lisp programmers
  often ask this question. [...]

  Programmers want a generic COPY function that somehow ``does the right
  thing,'' but relying solely on the representation type is insufficient
  to resolve intentional distinctions between conses, lists, alists, and
  trees, so we wouldn't know whether to call COPY-CONS (if there were
  such a thing), COPY-LIST, COPY-ALIST, or COPY-TREE.

  Of course, we could just define that COPY-LIST is what's used, but
  that could (and probably would) give the misleading impression that
  such a choice was ``uniquely determined'' or even ``morally correct,''
  instead of just arbitrarily chosen. Also, an arbitrary choice would
  leave users feeling funny about the presence of an operator that can
  copy many--but not all--kinds of objects.

  yes (my silly mistake).  you just described it in the above paragraph, so
  you must know it under a different name, but the key is to realize that
  it only _detects_ a circularity, after it has happened -- there is no
  guarantee that you find the first such element.

(defgeneric copy (context type source)
    (:documentation "Make a /type/ copy of /source/ according to
/context/"))

and where all the standard predefined copy operations would be already
hooked up, eg:

(defmethod copy ((context NULL) (type (eql :shallow)) (source list))
   (copy-list source))

(defmethod copy ((context NULL) (type (eql :deep)) (source list))
   (copy-tree source))

--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1                   email: matomira AT acm DOT org
CH-2007 Neuchatel                 tel:       +41 (32) 720-5157
Switzerland                       FAX:       +41 (32) 720-5720

(defmethod copy (context type (source list))
  (mapcar #'(lambda (x) (copy context type x)) source))

--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1                   email: matomira AT acm DOT org
CH-2007 Neuchatel                 tel:       +41 (32) 720-5157
Switzerland                       FAX:       +41 (32) 720-5720

To avoid descending more than once, you simply need to remember what
you've already explored and not explore it again.  Basically what a GC
does.

The ELUGM '99 proceedings' index refers to a talk by you titled "One Step
Beyond" without the corresponding paper (but someone in this group said
that you had problems attending the event). The LUGM '99 proceedings' index
lists another talk without paper titled "Creeping features".

I'll put it up on our web site asap.