Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

Deep copy in lisp: how?

1,040 views
Skip to first unread message

Courageous

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to

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,

Joe Kraska
San Diego
CA

Erik Naggum

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to
* Courageous <jkra...@san.rr.com>

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

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.

#:Erik

Courageous

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to

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

In essence, I'm looking for an implementation of this that uses introspection
on the objects; I require a generic implementation that knows nothing in
specific a-priori about the objects it will deep copy; however, stipulating
certain rules on the structure of the objects may be within reason. I know
this is possible one way or the other, for I have seen automatic deep copy
implemented via code generation in C++. I'm pretty new at lisp; however, so
I'm not sure what language-specific pitfalls I will encounter yet.

Thanks for your tip,

C/

Erik Naggum

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to
* Courageous <jkra...@san.rr.com>

| I know this is possible one way or the other, for I have seen automatic
| deep copy implemented via code generation in C++.

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.

#:Erik

Tim Bradshaw

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to
* Courageous wrote:
> 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?

What you want is something more than deep copying -- something I call
`graph copying' although it may have a proper name. It copies while
keeping track of every object it has copied, and avoiding copying it
again in that case. Graph copying is unavoidably expensive because it
needs an occurs check.

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

--tim
1

Tim Bradshaw

unread,
Apr 9, 2000, 3:00:00 AM4/9/00
to
* Courageous wrote:
> I know this is possible one way or the other, for I have seen
> automatic deep copy implemented via code generation in C++.

I seriously doubt it!

--tim


Courageous

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to

> you encountered a language-specific pitfall and fell headlong into it
> when you believed that C++ had an automatic solution.

I don't believe that C++ has a an automatic solution, rather, I've
seen a code generator (for C++) which correctly copies graphs of
the objects while keeping referential integrity intact.

> and if you fail to implement it right,
> you will in fact destroy valuable information in the copying process.

Never had that happen is all of 3 years using the code generator
that I had, which would, in fact, copy wildly crazy and cyclic
graphs of objects perfectly correctly. Furthermore, if you look
into the world of object oriented databases, you'll find that
various oodbs also do this perfectly well.

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.

C/

Rob Warnock

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Erik Naggum <er...@naggum.no> wrote:
+---------------
| * Courageous <jkra...@san.rr.com>

| | I know this is possible one way or the other, for I have seen automatic
| | deep copy implemented via code generation in C++.
|
| 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.
+---------------

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

-----
Rob Warnock, 41L-955 rp...@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043

Courageous

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to

> I seriously doubt it!

As I said in one of my posts, I'd be willing to accept certain
structural rules of organization. With this particular code generator,
it used the well-defined CORBA IDL (which simply cannot express a
function pointer and the like). Likewise, with the ODMG DDL, you
have a fairly restricted language of expression.

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

...

C/

Tim Bradshaw

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Courageous wrote:

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

Look, you can't write a general copier, get over it. Whatever your
C++ framework is doing it *isn't* doing general copy. You need to
know enough about the objects you want to copy to know what can occur
in these objects, how to copy them, what bits should be copied, what
is not copiable, what equality means when detecting cycles, and so
forth.

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.

--tim

Courageous

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to

> > 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.
>
> Look, you can't write a general copier, get over it.

Well, actually you *can* write a "general" graph copier if the
graph of objects is composed of objects made from a restricted
set of primitives.

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,

C/

Andrew K. Wolven

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
wrong. ignorance rules. this is c.l.l.

Rahul Jain

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
In article <38F14F3F...@san.rr.com> posted on Sunday,

April 9, 2000 10:47 PM, Courageous <jkra...@san.rr.com> wrote:
>
>> > 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.
>>
>> Look, you can't write a general copier, get over it.
>
> Well, actually you *can* write a "general" graph copier if the
> graph of objects is composed of objects made from a restricted
> set of primitives.
>

A general copier that working in specific situations, then :)

--
-> -\-=-=-=-=-=-=-=-=-=-/^\-=-=-=<*><*>=-=-=-/^\-=-=-=-=-=-=-=-=-=-/- <-
-> -/-=-=-=-=-=-=-=-=-=/ { Rahul -<>- Jain } \=-=-=-=-=-=-=-=-=-\- <-
-> -\- "I never could get the hang of Thursdays." - HHGTTG by DNA -/- <-
-> -/- http://photino.sid.rice.edu/ -=- mailto:rahul...@usa.net -\- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
Version 11.423.999.210020101.23.50110101.042
(c)1996-2000, All rights reserved. Disclaimer available upon request.


Philip Lijnzaad

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
On 09 Apr 2000 17:48:09 +0000,
"Erik" == Erik Naggum <er...@naggum.no> writes:

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

--
Not getting what you want is sometimes a wonderful stroke of luck.
-----------------------------------------------------------------------------
Philip Lijnzaad, lijn...@ebi.ac.uk | European Bioinformatics Institute,rm A2-24
+44 (0)1223 49 4639 | Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) | Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53

Tim Bradshaw

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Courageous wrote:

> Well, actually you *can* write a "general" graph copier if the
> graph of objects is composed of objects made from a restricted
> set of primitives.

Perhaps you should be clear about what you mean by `general'. Earlier
you said:

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.

> 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*.

One of the keys to successful communication on this newsgroup is to
ask for what you want in reasonably specific terms rather than
extremely vague ones.

--tim

Gareth Rees

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Courageous wrote:
> 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.

A generic deep copy function is impossible because in order to copy an
object, you must know the meaning of the object and how it will be used.

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.

--
Gareth Rees

Erik Naggum

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Courageous <jkra...@san.rr.com>

| Never had that happen is all of 3 years using the code generator that I
| had, which would, in fact, copy wildly crazy and cyclic graphs of objects
| perfectly correctly.

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.

#:Erik

Erik Naggum

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Courageous <jkra...@san.rr.com>

| 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*.

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.

#:Erik

Gareth Rees

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Courageous wrote:
> 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.

A generic deep copy function is impossible because in order to copy an
object, you must know the meaning of the object and how it will be used.

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:

Erik Naggum

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Philip Lijnzaad <lijn...@ebi.ac.uk>

| On 09 Apr 2000 17:48:09 +0000,
| "Erik" == Erik Naggum <er...@naggum.no> writes:
|
| 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?

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.

#;Erik

Fernando D. Mato Mira

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Gareth Rees wrote:

> A generic deep copy function is impossible because in order to copy an
> object, you must know the meaning of the object and how it will be used.

I just remembered several years ago, quite fresh from spending a couple
years
`Eiffelling' I wanted a generic copy operation. I think I had even started
writing the obvious trivial proposal for:

(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

www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html


Fernando D. Mato Mira

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Sketetons would also be provided, eg:

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

Tom Breton

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
Philip Lijnzaad <lijn...@ebi.ac.uk> writes:

> On 09 Apr 2000 17:48:09 +0000,
> "Erik" == Erik Naggum <er...@naggum.no> writes:
>
> 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.

No, hare&tortoise is nice, but it only does detection, which allows
you to *stop* examining a circular graph, but doesn't allow you to
immediately detect when you've completely traversed a graph that has
one loop, nor to successfully traverse a graph with cross-loops.

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.

> Erik> detection is easy with the rabbit and the hare algorithm.
>
> Is this an optimized version of the tortoise and the hare algorithm?

Heh!

--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Rethink some Lisp features, http://world.std.com/~tob/rethink-lisp/index.html

Paolo Amoroso

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
On 09 Apr 2000 20:32:37 +0100, Tim Bradshaw <t...@cley.com> wrote:

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

Which paper do you refer to? I have the ELUGM '99 and LUGM '99 proceedings,
but they don't include your papers. So I guess the Franz site doesn't have
them either.

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".


Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/

Tim Bradshaw

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to
* Paolo Amoroso wrote:

> 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".

Creeping features & one step beyond are the same thing, and yes I
didn't make it to elugm. I'm not sure why it's not in the lugm-99
proceedings, it should have been!

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

--tim

Robert Monfera

unread,
Apr 10, 2000, 3:00:00 AM4/10/00
to

Bernhard Pfahringer wrote:

> ACL comes with a specific deep copier, if you abuse their
> fasl-file facilities (kind of what was hinted at for the Java solution):
>
> USER(2): (arglist 'excl:fasl-write)

The documentation says FASL-WRITE does not work for CLOS classes other
than the built-in ones. MAKE-LOAD-FORM has to be used, requiring
specialized methods.

Robert

Bernhard Pfahringer

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
Courageous <jkra...@san.rr.com> writes:

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

> > Look, you can't write a general copier, get over it.
>

> Well, actually you *can* write a "general" graph copier if the
> graph of objects is composed of objects made from a restricted
> set of primitives.
>

ACL comes with a specific deep copier, if you abuse their


fasl-file facilities (kind of what was hinted at for the Java solution):

USER(2): (arglist 'excl:fasl-write)
(COMPILER::DATA STREAM &OPTIONAL COMPILER::*FASL-CIRCLE* *COMPILE-VERBOSE*)
T
USER(3): (setq l '(1 2 3))
(1 2 3)
USER(4): (nconc l l)
(1 2 3 1 2 3 1 2 3 1 ...)
USER(5): (excl:fasl-write l "x.fasl" t t)
;;; Writing fasl file x.fasl
;;; Fasl write complete
T
USER(6): #'excl:fasl-read
#<Function FASL-READ>
USER(7): (arglist 'excl:fasl-read
)
(COMPILER::FILE)
T
USER(8): (excl:fasl-read "x.fasl")
((1 2 3 1 2 3 1 2 3 1 ...))
USER(9): (first *)
(1 2 3 1 2 3 1 2 3 1 ...)
USER(10): (eql * l)
NIL
USER(11): (list-length **)
NIL

Maybe thats sufficient for your problem?

--------------------------------------------------------------------------
Bernhard Pfahringer
Dept. of Computer Science, University of Waikato
G1.25, phone: +64-7-838-4041
bern...@cs.waikato.ac.nz
--------------------------------------------------------------------------

Courageous

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to

> > Well, actually you *can* write a "general" graph copier if the
> > graph of objects is composed of objects made from a restricted
> > set of primitives.
>
> Perhaps you should be clear about what you mean by `general'. Earlier
> you said:

Oh. Okay. Well then, looking at the *very same message* that you
quoted, but taking a slow gander at the part you deliberately
cut out in order to score points, I see:

"however, stipulating certain rules on the structure of the objects
may be within reason."

Bye now,


C/

Courageous

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to

> A generic deep copy function is impossible because in order to copy an
> object, you must know the meaning of the object and how it will be used.

I understand this. I guess I'm wondering what specific constraints
have to be held to if you reasonably expect a graph-copy to work.
I'm willing to build my objects out of specific primitives, but
being new to lisp, don't know where I'm likely to make mistakes.

If there are many different data structures which cannot be deep
copied, I'm okay with that. I can stipulate that these objects
contain no such structures (checking that they indeed don't is
another issue).

C/

Courageous

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
> unless yo present the limited domain up front as
> inherent engineering decisions. did you do that? no. foo on you for
> that.

I mentioned the possibility of restrictions in my second message
in this very thread. Did you read it? No. Foo on you for that.

> C++ people are extremely arrogant the
> way they think they invented object-orientedness.

????

Non sequitur. This doesn't follow from anything, nor does
anything follow from this. Please keep your crazy rants to
yourself.


C/

Tim Bradshaw

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
* Courageous wrote:
> Oh. Okay. Well then, looking at the *very same message* that you
> quoted, but taking a slow gander at the part you deliberately
> cut out in order to score points, I see:

Believe me, I'm not trying to score points off you, or anyone. I
should obviously have quoted the original article as the one that
caused people to assume you wanted a truly general copier, but I
didn't hit ^ enough times & just picked a bit that looked like it
meant the same thing, which was stupid I realise. I won't quote the
original now as you'll probably think I'm trying to win some stupid
argument.

I'll repeat once more the things you need to write a copier (actually
I notice I forgot to give one of them):

a notion of equality of objects

a method of saying if you've seen an object equal in the above
sense to the one you are looking at now

a method of knowing which slots of an object you need to
descend into to copy it. This depends on the semantics of the
slots as well as their content (this is the one I failed to
mention).

If your notion of equality is EQL or something similar, then the first
two things are done very well by a hashtable, if it is more general
then you need to write some hashtable-type thing.

`Knowing which slots' is application-dependent, but you can do stuff
with the MOP to find them. I'd tend to do it with something like a
map-interesting-slots generic function with progn method combination
which I'd use to define the new interesting slots when I defined a new
class.

--tim

Courageous

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to

> `Knowing which slots' is application-dependent, but you can do stuff
> with the MOP to find them. I'd tend to do it with something like a
> map-interesting-slots generic function with progn method combination
> which I'd use to define the new interesting slots when I defined a new
> class.

Yes. With the mop, you can traverse the slot definitions of
a class, and with the right kind of code, you can iterate
over each of these, recursively if need be. I have something
similar (without the graph copying) implemented for non
cyclic graphs. It was interesting to learn how to do this;
I figured it out with _The Art of the Metaobject Protocol_.

Most of the reason I posted my question to the group was
to make sure I wasn't reinventing the wheel. That, and my
"copier" was originally intended to produce a plain text
rendition of the object that followed certain formatting
rules. Therein, I supported a set of basic primitives
(boolean, integer, float, string), sequences (array,
list, vector), and finally any standard-object. To
understand how to correctly serialize boolean as "false"
on my plain text serialization, I ended up having to
have a look-aside table of metadata, which turned out
to be necessary in any case (I forget why, but something
to do with the types of sequence elements upon internal
ization).

If this is just a case of doing what I did before, but
with adding an objref and then using some kind of
hashtable or something, I'm fine with that. I was
hoping there was an implementation already out there...

C/

Erik Naggum

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
* Courageous <jkra...@san.rr.com>

| I mentioned the possibility of restrictions in my second message
| in this very thread. Did you read it? No. Foo on you for that.

this is just great. of course I did that, and that's _why_ I criticize
you for not doing it UP FRONT. perhaps you do ont know what "UP FRONT"
means? well, it means you do it at the very start of your request for
help. sort of like "I use XLISP, and have this problem" instead of just
asking people to guess based on the lack of intelligibility of the
problem as stated in the environments smart people use.

please go back to C++, both communities would benefit from that.

#:Erik

Jon S Anthony

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
Courageous wrote:
>
> > A generic deep copy function is impossible because in order to copy an
> > object, you must know the meaning of the object and how it will be used.
>
> I understand this. I guess I'm wondering what specific constraints
> have to be held to if you reasonably expect a graph-copy to work.
> I'm willing to build my objects out of specific primitives, but
> being new to lisp, don't know where I'm likely to make mistakes.

The very things you are saying here show that you don't understand.
You're still completely missing the point. Any such constraints are
_context_ specific, i.e., specific to the problem space, the various
representations that you have chosen to to encode it, and what those
representations _mean in the given context_. It should be completely
clear that no general solution this is _possible_ no matter what set
of "primitive" representations you are willing to restrict yourself
to.


> If there are many different data structures which cannot be deep
> copied, I'm okay with that. I can stipulate that these objects
> contain no such structures (checking that they indeed don't is
> another issue).

Datastructures are _completely irrelevant_. Of course you can copy
_any_ datastructures (and vastly simpler, more easily correct, and
cleaner in CL than you could even dream of doing in your wildest
fantasies in C++), but that's the _easy_ part. Knowing which parts to
copy, when to copy, and how to copy, is the important part and the
part which is context specific and thus impossible to generalize in
the sense you seem to want.


If you know what you are doing (see above) writing a completely
general graph copier is pretty straightforward. For example, one of
the aspects of our application is that graphs are first class objects
- any kind of graph can be defined (with edge semantics specified and
enforced, information propagation provided, etc., etc., etc.) and they
can be freely manipulated. I wrote a completely general graph copier
in about a page of code.


/Jon

--
Jon Anthony
Synquiry Technologies, Ltd. Belmont, MA 02478, 617.484.3383
"Nightmares - Ha! The way my life's been going lately,
Who'd notice?" -- Londo Mollari

Arthur Lemmens

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to

In my copy of the LUGM-99 proceedings, it is: "One step beyond, or Creeping
metafeaturism" by Tim Bradshaw (10 pages). I enjoyed reading it.

Arthur Lemmens

Tim Bradshaw

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
* I wrote:

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

OK, it is now at http://www.cley.com/articles/one-step-beyond.pdf.
This is the original paper, I had hoped to do an HTML version which
more closely corresponds to the talk I actually gave, but this is all
there is for now.

--tim

Jon S Anthony

unread,
Apr 11, 2000, 3:00:00 AM4/11/00
to
Courageous wrote:
>
> > ......................................... Knowing which parts to

> > copy, when to copy, and how to copy, is the important part and the
> > part which is context specific and thus impossible to generalize in
> > the sense you seem to want.
>
> > If you know what you are doing (see above) writing a completely
> > general graph copier is pretty straightforward. ... I wrote a

> > completely general graph copier in about a page of code.
>
> However it is that you're reconciling these two paragraphs
> is what I'm interested in. You say that it's not structure,
> but semantics that indicates the meaning of a copy, and I'm
> fine with that, too. It doesn't matter. I have a practical
> problem to solve, here.

Well, then just go and write the silly thing. You are the only one
(at least around here) that knows the specifics of your application
context and thus the only one who can answer the semantic questions
poised above and thus the only one who can write your specific graph
copier. It should be a "yawner exercise".


> I'm not quite sure why in the part I cut out you felt a

Why not?

Courageous

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to

> ......................................... Knowing which parts to
> copy, when to copy, and how to copy, is the important part and the
> part which is context specific and thus impossible to generalize in
> the sense you seem to want.

> If you know what you are doing (see above) writing a completely
> general graph copier is pretty straightforward. ... I wrote a
> completely general graph copier in about a page of code.


However it is that you're reconciling these two paragraphs
is what I'm interested in. You say that it's not structure,
but semantics that indicates the meaning of a copy, and I'm
fine with that, too. It doesn't matter. I have a practical
problem to solve, here.

I'm not quite sure why in the part I cut out you felt a
need to describe the wonders of lisp to me. Do you get a
lot of hostile-to-lisp posters here? I am someone who is
voluntarily learning to use lisp, and as is I suspect
of many first time users, I've found it so flexible and
useful that most of my questions involve where its
limitations lie.

When I say that something can be done in some other language
with some particular mechanism, this isn't some sort of
snide comment on the capabilities of lisp, but rather me
pointing out that if an approach works in one language,
there ought to be a way, no matter how labyrinthine, to
achieve it in another.

C/

Erik Naggum

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to
* Courageous <jkra...@san.rr.com>

| It doesn't matter. I have a practical problem to solve, here.

thank you. I think this sums up your position admirably.

#:Erik

Courageous

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to

Yes, it does. Some of us do, in fact, work on real problems
which need solving. Theoretical constraints are interesting
and valuable to know, but the project moves on.

I suspect that you need to look inward and not outward to
solve the problem that you need to work on. Usenet won't
offer your ego what it's looking for, no matter how hard
you look for it.

Good luck to you,

C/

Erik Naggum

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to
* Courageous <jkra...@san.rr.com>

| Yes, it does. Some of us do, in fact, work on real problems which need
| solving. Theoretical constraints are interesting and valuable to know,
| but the project moves on.

just because you cannot fathom the theoretical implications of your
questions does not mean that those who do don't solve practical problems.
think about this. please.

and, incidentally, if I have "made" you feel like an idiot, why not just
do something that would put such impressions to _shame_ instead of going
out of your way to _prove_ that you really _are_ hopelessly lost?

| I suspect that you need to look inward and not outward to solve the
| problem that you need to work on. Usenet won't offer your ego what it's
| looking for, no matter how hard you look for it.

I'm sure you and your shrink have worked something out that works for you
(although by the looks of it, you have some ways to go), but just like he
or she should have told you that you shouldn't give other people your
medication, you also shouldn't believe that your personal problems apply
to other people.

but I'll give you this: you are indeed courageous. I know of few other
people who would expose themselves the way you do. here's a hint: you
really don't need to -- nobody cares about _you_, personally, and it's an
affront to your audience, _any_ audience, to think they do.

#:Erik

Paolo Amoroso

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to
On Tue, 11 Apr 2000 21:34:42 +0200, Arthur Lemmens <lem...@simplex.nl>
wrote:

> In my copy of the LUGM-99 proceedings, it is: "One step beyond, or Creeping
> metafeaturism" by Tim Bradshaw (10 pages). I enjoyed reading it.

Huh... That paper is missing from my copy of the LUGM '99 proceedings...
Does yours also include the paper by Chuck Fry listed as "Lisp in Space" in
the index (i.e. the list of talks printed on a green sheet), and the one by
Fred Gilham listed as "Dist. Transactions"?

Arthur Lemmens

unread,
Apr 12, 2000, 3:00:00 AM4/12/00
to

Paolo Amoroso wrote:

> Huh... That paper is missing from my copy of the LUGM '99 proceedings...
> Does yours also include the paper by Chuck Fry listed as "Lisp in Space"

No, I can't find that one.

> and the one by Fred Gilham listed as "Dist. Transactions"?

Yes: "SDTP - A Multilevel-Secure Distributed Transaction Processing System"
by Fred Gilham and David Shih (12 pages).

Arthur Lemmens

Courageous

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to

> I'm sure you and your shrink have worked something out that...

You just can't stop, can you Erik?

C/

Erik Naggum

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to
* Courageous <jkra...@san.rr.com>

| You just can't stop, can you Erik?

if I can stop you, that's good enough for me, because I don't start the
kind of insane drivel you seem to enjoy starting. but have you asked
yourself your own question, lately? I don't appreciate your line of
psychologizing crap, but now that you get it back in your face, I see
that you are a lot more sensitive to the matter than I am, which is good,
because you may realize that if you plan to win any games that way, you
won't do it here, and you're clearly the kind of moron who needs to be
hurt to stop to think. will _that_ make you stick to your issues,
whatever they may be, or will you smear more of your personality all over
the place with yet more moronic psychologizing and irrelevant personal
attacks? it's your call, "Courageous".

#:Erik

tom...@my-deja.com

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to
In article <38F370...@synquiry.com>,

Jon S Anthony <j...@synquiry.com> wrote:
> Any such constraints are
> _context_ specific, i.e., specific to the problem space, the various
> representations that you have chosen to to encode it, and what those
> representations _mean in the given context_. It should be completely
> clear that no general solution this is _possible_ no matter what set
> of "primitive" representations you are willing to restrict yourself
> to.

Well, it depends on what you mean by "deep copy". The obvious
meaning is that after a deep copy, you have two references
that behave identically, but updates through one won't affect
the behavior of the other (that idea can be formalized).
Most languages can't implement this, but it's still well-defined.

> Of course you can copy
> _any_ datastructures (and vastly simpler, more easily correct, and
> cleaner in CL than you could even dream of doing in your wildest
> fantasies in C++), but that's the _easy_ part.

No, in fact, some very common data structures in CommonLisp
cannot be copied because they are opaque, among them closures
and streams.

> Knowing which parts to
> copy, when to copy, and how to copy, is the important part and the
> part which is context specific and thus impossible to generalize in
> the sense you seem to want.

Unlike equality, where it matters if you compare too much,
for the semantics of a deep copy, it doesn't matter if you
copy too much--it will simply be inefficient.

Automatic deep copy is actually a pretty common operation in
dynamic distributed object systems and persistent object stores,
and a number of systems do a very good job implementing it
almost completely automatically. Even CL compilers end up
having to be able to perform some pretty general deep copies.

Tom.


Sent via Deja.com http://www.deja.com/
Before you buy.

Courageous

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to

> Automatic deep copy is actually a pretty common operation in
> dynamic distributed object systems and persistent object stores,
> and a number of systems do a very good job implementing it
> almost completely automatically.

Having worked with distributed systems and object databases
for 8 years now, I've noticed the same thing. Said systems
do a lot of bending over backwards to fit a square peg into
a round hole, but they get the job done.

C/

Courageous

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to

> insane drivel... crap... in your face... you won't do it here...
> and you're clearly the kind of moron... who needs to be
> hurt to stop to think... moronic...

"Needs to be hurt". I especially like that one.
With messages like this, the only person who's
getting hurt is you. How embarrassing for you.

Take a step back.


C/

Erik Naggum

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to
* Courageous <jkra...@san.rr.com>
| Take a step back.

let me know when your advice has worked for you. make an effort to show
that you can listen to anything but your own voice while you're at it.

#:Erik

Tim Bradshaw

unread,
Apr 13, 2000, 3:00:00 AM4/13/00
to
* tom 98 wrote:

> Unlike equality, where it matters if you compare too much,
> for the semantics of a deep copy, it doesn't matter if you
> copy too much--it will simply be inefficient.

Actually, it does matter, especially if you copy things that should be
equal so they stop being equal. If you copy things that not DAGs then
this can not only fail to preserve the semantics of your data
structure but fail to terminate, which is bad. Making things that are
only incidentally equal remain equal is only bad for efficiency.

--tim

Tim Moore

unread,
Apr 13, 2000, 3:00:00 AM4/13/00