Deep copy in lisp: how?
Courageous
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
| 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
> 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
| 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
> I have a CLOS object which may contain an arbitrary graph of
> 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.
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
> 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
> 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
+---------------
| * 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++.
|
| 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
> 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
> 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
> > 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
Rahul Jain
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
"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
> 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
> 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
| 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
| 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*.
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
> 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
| 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
> 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
(defmethod copy (context type (source list))
(mapcar #'(lambda (x) (copy context type x)) source))
Tom Breton
> 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
> 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
> 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
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
> > > 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
> > 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.
>
> 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
> 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
> 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
> 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
> `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
| 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
>
> > 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
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
> 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
>
> > ......................................... 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
> > completely general graph copier in about a page of code.
>
> 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
> ......................................... 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
| It doesn't matter. I have a practical problem to solve, here.
thank you. I think this sums up your position admirably.
#:Erik
Courageous
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
| 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
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
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
> I'm sure you and your shrink have worked something out that...
You just can't stop, can you Erik?
C/
Erik Naggum
| 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
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
> 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
> 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
| 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
> 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
It's good advice for both of you.
Speaking as a one-time Lisper wandering in the the C++ wilderness for
years, I think some more slack could be shown to users of other languages
who stumble into comp.lang.lisp, either because they've just gotten into
Lisp or for whatever reason. Topics such as "How do I do a deep copy
in Lisp?" cause blood pressures to rise because Lispers know it's
impossible, but that's because the language is much richer and exposes one
to situations where deep copy is in fact quite hard if not impossible.
Deep copy is hard in C++ too, but other factors (such as primitive memory
management) may discourage the use of data structures that are hard to
deep copy, or classes may do a reasonable job of deep copying in limited
domains (vis. the distributed object database example), so C++ers become
confused and hurt when they are told that their apparently reasonable
request is intractable and, by the way, silly on the face of it.
Apropos of nothing, C++ hasn't stood still and isn't quite as cretinous as
it was 10 years ago. I use a C++ garbage collector (Boehm) in my work and
home projects for example, and the things that are being done with
templates and partial evaluation are extremely cool. I'm glad to be
returning to Lisp, if only as an amateur, but the C++/Perl world doesn't
totally suck.
Tim
Erik Naggum
| 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.
when object identity matters, copying too much is destroying information.
such destruction can lead to very serious errors that are impossible to
trace after the fact. if you don't get it right, you're hosed. if you
don't even recognize that you can get this wrong, you're hosed a priori.
such is the tragic case for that hack we've been trying to teach there's
more to life than his C++ wonderworld.
(do we really _need_ to educate people at this level in this newsgroup?)
#:Erik
Erik Naggum
| Topics such as "How do I do a deep copy in Lisp?" cause blood pressures
| to rise because Lispers know it's impossible, but that's because the
| language is much richer and exposes one to situations where deep copy is
| in fact quite hard if not impossible.
you're missing the point, as one would expect from a bystander. it isn't
the _topic_ that cause any problems. it's the dimwits who come here and
ask for advice, and resoundingly _reject_ the advice they get from
well-meaning, highly educated people who try to teach pigs to sing, which
we know wastes your time and annoys the pig (witness the "practical" line
that just _had_ to come our way) only they don't know the dimwits they
try to help _are_ pigs until after a while, and then they get annoyed
when the pig turns out to be severely limited in learning _ability_, too.
#:Erik
Tom Breton
> 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).
And that no longer match under shallow equality.
(defconstant my-obj (cons 1 2) "" )
(defconstant alist-0 (list (cons my-obj "its value")) "" )
(defconstant alist-1 (copy-tree alist-0) "" )
(assoc my-obj alist-0 :test #'eq)
(assoc my-obj alist-1 :test #'eq)
> > 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.
Good point.
> > 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.
It also matters for shallow equality.
--
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
Tom Breton
> > I'm sure you and your shrink have worked something out that...
>
> You just can't stop, can you Erik?
Apparently he can't.
Erik Naggum
| Apparently he can't.
Microsoft hired Ralph Reed of Christian Coalition fame as their lobbyist
in Washington to get George Dubya to be favorable to their antitrust
lawsuit. this was widely considered a serious mistake, especially after
the New York Times uncovered it.
I haven't hired Tom Breton as my spokesman or lobbyist, but it would be
the same kind of mistake if I had.
so, can _you_ stop, Tom? but we know the answer: "apparently he can't".
#:Erik
tom...@my-deja.com
> > 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.
>
> 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.
It depends on the definition of "deep copy" you choose. My
definition is based on mutability, not any form of equality.
I think that's what most people really mean by "deep copy", and that's
what most systems that have it actually provide.
Conceptually, you can implement deep copy by simply copying the
complete object graph of the system and returning a reference to the
copy of the object referenced by the original reference. This is
guaranteed to terminate and will have the semantics I describe.
Note that that doesn't mean everything is smooth sailing.
For example, code that uses references into the old data
data structure as, say, iteration guards will simply fail
when used with the copy. And if you have objects in the Lisp data
structure, like an integer file descriptor, that refer to some external
state, then that external state will obviously not get copied
(nor should it).
> Making things that are
> only incidentally equal remain equal is only bad for efficiency.
The problem with defining equality is not things that are
incidentally equal, it's that many common data structures
(hash tables, splay trees, association lists, etc.) are semantically
equal even though they are structurally different; mutable structures
are also ambiguous from the point of view of equality.
It is possible to define general deep structural equality predicates and
many languages do. They usually don't map onto semantic equality,
but they are still quite useful, and generally quite
conservative (e.g., mutable structures are not equal, regardless of
content).
Many recent languages also have some simple conventions about what
should
participate in deep copies and deep equality by default, simple means
for
overriding that, and a standard way of communicating programmer intent
to the runtime. This allows them to implement distributed object
systems,
object persistence, and a lot of other facilities, almost completely
automatically.
In general, I think there are consistent definitions of
"deep copy" and "deep structural equality" possible in Lisp,
just like they are in most other languages. But these operations
are probably not going to be all that useful in Lisp due to
the semantics of the language: Lisp has a very general set of
types, most of them are mutable, and Lisp has almost no
conventions for how to define deep copy and deep equality.
In languages with less mutability (ML, Haskell, ...), restricted
sets of data structures (APL, Matlab4, ...), or very uniform
conventions on how to define new data structures (Java, ...),
notions of deep copy and deep structural equality are actually
useful.
Tom.
Tim Moore
Pigs are highly intelligent. Sometimes pigs turn out to be humans under a
spell. In any event, who cares if the recipient isn't receptive? Posting
on Usenet is not a zero-sum game between you and someone who asks a
question; you don't give up your precious bodily essence everytime you
answer a question. You're educating thousands of silent readers (maybe
that's a bit optimistic for comp.lang.lisp :) who may be confused about
the same topic, and often as not you're educating and enriching yourself.
OK, this has nothing to do with Lisp at all anymore, so I promise not to
follow up.
Tim
Erik Naggum
| Pigs are highly intelligent.
pardon me for elaborating on a saying. speaking of which, this must be a
regional thing -- in some parts of the English-speaking world, people
tend to use idioms almost constantly, but do not reflect on them at all,
which makes them into a mere set of ersatz vocabulary, while in other
parts of the English-speaking world, puns and elaborations and mixing and
matching idioms and expressions to travel between many layers of meaning
is considered natural. I tend to be puzzled when I meet people who don't
reflect on their language, because it's hard to tell which part of the
many meanings they got and which they completely missed out on.
| In any event, who cares if the recipient isn't receptive?
you do, when you take the role of a bystander and raise the discussion to
a meta-level. others do, when they are in middle of the discussion that
started it all. many find it very annoying to see recurring dimwits fail
to get over a personal hangup or their desperately trying to recover
something they are the only ones to remember they lost.
newsgroup volume is a measure of discontent.
#:Erik
Courageous
> Pigs are highly intelligent. Sometimes pigs turn out to be humans under a
The more interesting question to ask is: if the recipient doesn't
attach the import to your angle on a problem that you do, does
it justify crumbling into hurling insult after insult like a
spoiled child? Merely a rhetorical question, of course.
I've been called worse things than a pig. :)
C/
Jon S Anthony
>
> 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
Which is one thing that many here have been trying to point out.
> 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).
That's one meaning.
> > 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.
I'm not sure about streams, but I've actually copied closures in
(effectively) your sense. Of course, it requires having the proper
source around to do it.
Jon S Anthony
>
> No, in fact, some very common data structures in CommonLisp
> cannot be copied because they are opaque, among them closures
> and streams.
On second thought, you're right - the kind of copy that I did for
closures would not (in general) fit your definition.
William Deakin
> ....in some parts of the English-speaking world, people tend to use idioms
> almost constantly, but do not reflect on them at all...
This is very true.
As an example of this, when a machine is running is slow it is described as
`running like a pig' or `a dog.' If you have ever tried racing either of these
animals you would realise that the idiom is foolish and a more appropriate one
would be `running like an IT professional'.
;) will
Tim Bradshaw
> As an example of this, when a machine is running is slow it is described as
> `running like a pig' or `a dog.' If you have ever tried racing either of these
> animals you would realise that the idiom is foolish and a more appropriate one
> would be `running like an IT professional'.
One of the most frightening experiences I've ever had was coming
across a wild boar while resting from cycling half way up a hill in
Germany. It moved *really fast*. Fortunately it wasn't out to get me
I think, and adrenaline can make you climb even quite steep hills at a
great rate for a few hundred yards.
--tim
Joerg-Cyril Hoehle
original message (for reference):
Courageous <jkra...@san.rr.com> writes:
> 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
Later:
> 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*.
I believe there's also tips and netiquette about reading the FAQ and
the newsgroup for some time. Maybe you would have come across a
reference to Kent M. Pitman article
http://world.std.com/~pitman/PS/EQUAL.html about why there can't be an
all general copy, so you'd have known not to ask the question - but
maybe there aren't bad questions, just bad answers.
I sincerely hope that by now, you read both this and Tim Bradshaw's
article at http://www.cley.com/articles/one-step-beyond.pdf
Also, it was an extremely bad move in your second posting to talk
about c++, especially about deep copying. And later about databases,
since there are some strong opinions here about "the worse is better",
90% working solutions, unfinished APIs and the like.
Later:
> 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.
Here again, you aren't going to make friends here, since the way you
phrase it people will believe you implicitly said that the language
requiring labyrinthine or byzanthine solutions would be Lisp, whereas
it's shared opinion here that it's just the other way round.
I believe you weren't specific enough about your needs, trying to be
too abstract. But with all that was pointed at you by now
(esp. Bradshaw) , I also believe you should now be able to write a
one-page deep graph copy that'll fit your application (more precisely
the specific restrictions on data that your application
manipulates). It seems to me you need at least some hashtable for
detection of redundancy and some declarative interface (not
necessarily MOP or even CLOS) to tell how specific limited objects and
their slots must be copied.
Regards
Jorg Hohle
Telekom Research Center -- SW-Reliability
Fernando
wrote:
>years, I think some more slack could be shown to users of other languages
>who stumble into comp.lang.lisp, either because they've just gotten into
>Lisp or for whatever reason.
[...]
>domains (vis. the distributed object database example), so C++ers become
>confused and hurt when they are told that their apparently reasonable
>request is intractable and, by the way, silly on the face of it.
I don't think you are being very fair: _onlY_ Erik behaves
like that, everybody else in the newsgroup is normal...
Just like the proliferation of parens, he may be a minor
annoyance to newbies, but fortunately, parens stop annoying you in a
week, and as soon as you plonk him, he'll stop annoying you. ;-)
>Apropos of nothing, C++ hasn't stood still and isn't quite as cretinous as
>it was 10 years ago. I use a C++ garbage collector (Boehm) in my work and
Interesting... Any links to this gc? O:-)
>home projects for example, and the things that are being done with
>templates and partial evaluation are extremely cool. I'm glad to be
>returning to Lisp, if only as an amateur, but the C++/Perl world doesn't
>totally suck.
Agreed for C++, but Perl does totally suck... };-)
//-----------------------------------------------
// Fernando Rodriguez Romero
//
// frr at mindless dot com
//------------------------------------------------
Tim Bradshaw
> It depends on the definition of "deep copy" you choose. My
> definition is based on mutability, not any form of equality.
> I think that's what most people really mean by "deep copy", and that's
> what most systems that have it actually provide.
I'm not quite sure what you mean by this. Copying immutable objects
is something that I think Lisp people would find extremely
uninteresting except in some special cases (like copying an object
into another lisp image). But there pretty much are no immutable
objects in Lisp (numbers are the only case I can think of off the top
of my head, and there are special exceptions in the definition of EQ
to allow the system to copy numbers secretly anyway). I'm
deliberately not counting any object with components, since even if it
is itself immutable, you have to know all its components are too.
Obviously you could have objects which were immutable *in an
application*, but that's application-dependent.
> Conceptually, you can implement deep copy by simply copying the
> complete object graph of the system and returning a reference to the
> copy of the object referenced by the original reference. This is
> guaranteed to terminate and will have the semantics I describe.
Yes, this I think is what I called `graph copy' in my paper. But I
think it's painful because you need an occurs check, unless you can
rely on either being able to smash the object you are copying (as a
copying GC would) or you can do a very efficient occurs check (for
instance if you can get at the address of objects and rely on it not
changing during the copy -- neither of which is true for Lisp -- then
you can use a bitmap to check if you've seen the object before which
will be 1/32nd or 1/64th the size of the address space you are
interested in -- this may be prohibitive if the graph is scattered
through the address space of course).
Perhaps there is some trick I don't know to doing this.
> It is possible to define general deep structural equality predicates and
> many languages do. They usually don't map onto semantic equality,
> but they are still quite useful, and generally quite
> conservative (e.g., mutable structures are not equal, regardless of
> content).
Right, so they're useless for our purposes if everything is mutable...
> In general, I think there are consistent definitions of
> "deep copy" and "deep structural equality" possible in Lisp,
> just like they are in most other languages.
The whole point is that there are not *useful* definitions of these
things -- ((a . b) (c . d)) is equal to ((c . d) (a . b) (c . e)) as
an alist, but it would be hard to define a structural equality
predicate which gave you this, because it has to know that you are
comparing these things *as an alist*.
I don't think we have any actual substantive difference on any of
these issues in fact -- although I may have misunderstood you. I'm
just trying to draw the conclusion that typically copying is extremely
application-dependent and that the language cannot provide copy or
equality operation which are useful in more than very restricted
applications, and Lisp has done the right thing in not doing this.
The implication then is that the approach Lisp should take is to
provide tools which let you write copiers and equality tests, such as
more MOP stuff.
--tim
Erik Naggum
| Just like the proliferation of parens, he may be a minor annoyance to
| newbies, but fortunately, parens stop annoying you in a week, and as soon
| as you plonk him, he'll stop annoying you. ;-)
but how long before the obsessed stalkers stop annoying the newsgroup?
#:Erik
Tim Moore
> On 13 Apr 2000 17:01:03 GMT, Tim Moore <mo...@herschel.bricoworks.com>
> wrote:
> >Apropos of nothing, C++ hasn't stood still and isn't quite as cretinous as
> >it was 10 years ago. I use a C++ garbage collector (Boehm) in my work and
>
> Interesting... Any links to this gc? O:-)
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Tim
thi
> As an example of this, when a machine is running is slow it is
> described as `running like a pig' or `a dog.' If you have ever tried
> racing either of these animals you would realise that the idiom is
> foolish and a more appropriate one would be `running like an IT
> professional'.
all professionals run quickly when the boss is around.
thi
Arne Knut Roev
My sentiments entirely.
I read this newsgroup for technical contents, not "social graces".
Which is why I have no intention of "plonking" Mr Naggum: His technical
comments seem to be among the most reliable here.
-akr
PS:
A short comment may be in order, for those of narrow mind: In this
posting, I am not, repeat _not_, repeat _NOT_, trying to "kiss Mr
Naggum's arse": I mean every word of what I wrote above!
DS.
--
Arne Knut Roev <akr...@online.no> Snail: N-6141 ROVDE, Norway
=
The Gates of Hell shall not prevail:
Darkness now; then Light!
Arne Knut Roev
> all professionals run quickly when the boss is around.
For all such cases, at least one of the following statements apply:
1. There is something wrong with said professional.
2. There is something wrong with said boss.
3. You are watching a theatre play.
[note absence of smiley]
Tom Breton
> Which is why I have no intention of "plonking" Mr Naggum: His technical
> comments seem to be among the most reliable here.
Look, I won't belabor how absurd that is, but to make this group
usable for myself, I'll be plonking you along with him. No hard
feelings, but I really have no use for his nonsense, reflected or
otherwise. Don't take it personally; you made your choice, I just
respond.
Rob Warnock
+---------------| about why there can't be an all general copy...
| I sincerely hope that by now, you read both this and Tim Bradshaw's
| article at http://www.cley.com/articles/one-step-beyond.pdf
One of the examples in Tim's paper was very telling -- a "queue" object
which contains pointers to *shared* sub-structure. If one had *any*
lingering doubts about the impossibility of a "universal" or "generic"
copy doing the right thing, that example would surely blow them away.
Objects may have *application*-defined internal consistency invariants
which are destroyed by copying, and a general copy operator *can't* know
(in general) how to preserve (or at least, restore) those invariants
through the copying process.
-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
> I believe you weren't specific enough about your needs, trying to be
> too abstract.
True. However, it's funny. At my place of work, I'm the one all
the newbies come to for answers, because I understand that sometimes
the question is wrong, and instead attempt to answer their question
from the point of view of helping them achieve the solution to
the problem they are facing. I also understand that they are
beginners, and so I take special care to guide them through their
learning process. There's more than one way of looking at things,
if you get my drift.
"Can't" isn't in my vocabularly.
> But with all that was pointed at you by now
> (esp. Bradshaw) , I also believe you should now be able to write a
> one-page deep graph copy that'll fit your application (more precisely
> the specific restrictions on data that your application
> manipulates). It seems to me you need at least some hashtable for
> detection of redundancy and some declarative interface (not
> necessarily MOP or even CLOS) to tell how specific limited objects and
> their slots must be copied.
As it so happens, I already happen to have some externalization
software I wrote to handle translation of graphs of objects that
don't have any internal references. My only reason for asking
the question at all was that I was hoping there was some built
in feature in lisp that would attempt to deep copy objects
irrespective of the obvious errors that this could introduce.
No big deal, though.
More rhetorically, I wonder if the people over at Franz will
be "morons" if they attempt to implement the Objects By
Value section of the CORBA standard in their ORBLink product?
C/
Tom Breton
>
> Later:
> > 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*.
>
> I believe there's also tips and netiquette about reading the FAQ and
> the newsgroup for some time. Maybe you would have come across a
> reference to Kent M. Pitman article
> http://world.std.com/~pitman/PS/EQUAL.html about why there can't be an
> all general copy, so you'd have known not to ask the question - but
> maybe there aren't bad questions, just bad answers.
>
> I sincerely hope that by now, you read both this and Tim Bradshaw's
> article at http://www.cley.com/articles/one-step-beyond.pdf
Thanks for the reference. It's a good article, and not primarily for
his comments on deep copying.
Erik Naggum
| However, it's funny. At my place of work, I'm the one all the newbies
I'm sure you think you're the hero of your work-place, but it doesn't
help just to _tell_ people when you have done so much damage to your
public impression as you have, and as a line of self-defense, it's so
pathetic it stinks. _anyone_ could write a self-serving self-appraisal.
that's why people _don't_ write such personal defenses on the Net -- it's
self-defeating and on top of it, it's embarrassing when those "newbies"
who came to you for answers ask you something you don't know and search
for the answer on the Net, only to find that you don't have a clue in
some very important areas and are incredibly self-defensive and personal
about it. to really top it off, you haven't understood _any_ of the many
very good explanations you have received to your question. such arrogant
ignorance is a very questionable quality in an employee who doles out
answers to helpless "newbies" in an organization. so you should start to
worry about yourself, and much less about others: if you can't take care
of yourself, you certainly are in no position to give advice to others.
| More rhetorically, I wonder if the people over at Franz will be "morons"
| if they attempt to implement the Objects By Value section of the CORBA
| standard in their ORBLink product?
why do you want to hurt yourself so much? you didn't have to _prove_
that you still have not understood the difference between implementing a
carefully constrained specification of a protocol and _general_ deep
copier, did you? normal people don't insist on making the same mistake
over and over just because they don't like being called morons when they
do and continue with it until they are no longer called morons (it works
the other way around, in case you wonder). the people over at Franz have
understood this difference long ago (like at _least_ 15 years ago), and
are in no danger at all of being called morons. and in case you wonder
about more things, smart people who don't defend themselves can disagree
violently without even the hint of a danger of getting personal, so even
if implementing CORBA _were_ a really moronic thing to do, that itself
doesn't mean someone who does it is a moron. it's the getting _personal_
that is the first hint of someone being a moron. you have never quit
giving that hint, on the contrary: you have reinforced it over and over,
and this is a pretty strong argument that it is a correct assessment of
your mental acuity and childish, retarded stubbornness. you can change
this by snapping out of your "personal" mental state and realize that
your ego is not under attack from anyone other than your own imagination.
most everyone here will utter a sigh of relief if you get the idea, and
nobody will ever "remind" you of your past mistake when you have learned
-- that's what makes possibly heated technical discussions _impersonal_
to people who aren't morons.
I'm _expecting_ another knee-jerk moronic response. surprise me. (of
course, now that I said that, your childish stubbornness prohibits you
from showing any trace of adult, smart behavior, but try, anyway.)
#:Erik
Courageous
> are in no danger at all of being called morons. and in case you wonder
> about more things, smart people who don't defend themselves can disagree
> violently without even the hint of a danger of getting personal,
You're complaining about *me* making matters personal.
Oh, that's rich. Between the two of us, who's posting
page-long diatribes sometimes filled with profanity?
> you can change
> this by snapping out of your "personal" mental state and realize that
> your ego is not under attack from anyone other than your own imagination.
Says he who fills up pages with insults & profanity...
C/
Tim Bradshaw
> More rhetorically, I wonder if the people over at Franz will
> be "morons" if they attempt to implement the Objects By
> Value section of the CORBA standard in their ORBLink product?
It's not stupid to implement a design that may broken if you need to
do that to be able to say that you conform to a standard and therefore
get sales. But it doesn't tell you anything about the brokenness of
the design either -- being a popular standard does not correlate
particularly well with being a good design, as Lisp people have found
by bitter experience.
--tim
Will Deakin
>all professionals run quickly when the boss is around.
And yet more slowly than an elephant. The top speed of the worlds fastest
sprinter ~21mph. Speed of an irate charging elephant ~24mph.
;) will
thi
so when looking for elephants, put a boss at the end of africa!
thi
Fernando
wrote:
>On Fri, 14 Apr 2000, Fernando wrote:
>
>> On 13 Apr 2000 17:01:03 GMT, Tim Moore <mo...@herschel.bricoworks.com>
>> wrote:
>> >Apropos of nothing, C++ hasn't stood still and isn't quite as cretinous as
>> >it was 10 years ago. I use a C++ garbage collector (Boehm) in my work and
>>
>> Interesting... Any links to this gc? O:-)
>http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Thanks. :-)
Courageous
Well, that's a fair criticism.
I suppose I have a different attitude about these things than you
do. I was thinking back to a message where I said that I used a
C++ deep copier from generated code for several years, and that it
always worked perfectly. I realized in retrospect that there were
a number of occasions where when I used it, things were screwed up.
But then upon analysis, I always ended up blaming myself and not
the code; it did, from my perspective, always only do exactly what
I told it to do. It never so much as occured to me to blame the
copier.
That inspires the question: "Should programmers be protected from
themselves?". Obviously, I don't think so. Such is fairly typical
of my C background, I suppose.
C/
Paolo Amoroso
(Joerg-Cyril Hoehle) wrote:
> since there are some strong opinions here about "the worse is better",
> 90% working solutions, unfinished APIs and the like.
For those unfamiliar with "worse is better":
"Lisp: Good News, Bad News, How to Win Big" By Richard Gabriel
http://www.naggum.no/worse-is-better.html
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/
Coby Beck
Courageous <jkra...@san.rr.com> wrote in message
news:38F83EB8...@san.rr.com...
The technical part of this thread was quite interesting, but it has really
degenerated. You both should give it a rest. (and i really doubt Eric will
let you have the last word. You can only "win" but quitting).
Thank you for bringing up the topic, by the way.
Coby
Ian Upright
>Erik Naggum <er...@naggum.no> wrote:
>> * Fernando <spa...@must.die>
>> | Just like the proliferation of parens, he may be a minor annoyance to
>> | newbies, but fortunately, parens stop annoying you in a week, and as soon
>> | as you plonk him, he'll stop annoying you. ;-)
>>
>> but how long before the obsessed stalkers stop annoying the newsgroup?
>
>My sentiments entirely.
>
>I read this newsgroup for technical contents, not "social graces".
As a Smalltalker who doesn't read this newsgroup very often, I was quite
irritated by Mr. Naggum's absurd and highly inflamitory opinions. It seemed
to be a perfectly reasonable question to ask, not warranting even a *hint*
of inflammatory comments.
Are all Lisper's f***ing belligerent ass*****? ;-)
I still don't understand what the problem is. If you consider a completey
generic one-size fits all deepCopy to be useless, I'd have to strongly
disagree. In Smalltalk I do what I consider "true" deep copies all the
time, and I get a lot of use out of them. There even exists this tool
called a DeepCopyArbiter that generically traverses any arbitrary graph of
objects, and allows you to add rulesets to define at what point the deep
copy should end, based on a specific instance, type of object, or other
criteria. I'm baffled as to why you can't do this sort of thing easily in
CLOS. Maybe I'm just not familiar enough with CLOS yet, or maybe this sort
of pattern doesn't fit in well with the language?
Ian
----------------------------------------------------------------------------
One Accord Technologies i...@oneaccordinc.com
----------------------------------------------------------------------------
Ian Upright
>I still don't understand what the problem is. If you consider a completey
>generic one-size fits all deepCopy to be useless, I'd have to strongly
>disagree. In Smalltalk I do what I consider "true" deep copies all the
>time, and I get a lot of use out of them.
BTW, Smalltalk does have closures and streams and similar concepts to CLOS
so I'm still baffled as to why that causes a problem in CLOS but not in
Smalltalk. (A common way in Smalltalk is to simply not deepCopy closures
and streams, etc., or don't deepCopy objects that contain them) :-)
Courageous
> time, and I get a lot of use out of them. There even exists this tool
> called a DeepCopyArbiter that generically traverses any arbitrary graph of
> objects, and allows you to add rulesets to define at what point the deep
> copy should end, based on a specific instance, type of object, or other
> criteria. I'm baffled as to why you can't do this sort of thing easily in
> CLOS. Maybe I'm just not familiar enough with CLOS yet, or maybe this sort
> of pattern doesn't fit in well with the language?
Actually, with the MOP, you *could* do it. It took me a reread to see
what you were saying, and I just think that's wicked cool. Several
years ago we developed for C++ a similar product that would terminate
a deep copy based on depth or classes of interest. You could, for
example, express something like "deep copy for me this graph of
objects, but terminate recursion if any node you encounter is not
inherited from MyClass". Needless to say, the code generation for this
was a bitch. I have a feeling that as a Smalltalker, you're probably
just plain spoiled (I've been explaining to my boss lately that it
was a mistake making me learn Lisp, because he'll never be able
to persuade me to leave). :)
If found the book _The Art of the Metaobject Protocol_ to be very
useful for learning what you need to know about what's under the
hood of CLOS.
C/
Tom Breton
>
> As a Smalltalker who doesn't read this newsgroup very often, I was quite
> irritated by Mr. Naggum's absurd and highly inflamitory opinions. It seemed
> to be a perfectly reasonable question to ask, not warranting even a *hint*
> of inflammatory comments.
>
> Are all Lisper's f***ing belligerent ass*****? ;-)
I can certainly understand why you mite think so!
But I promise you, there are a good number of less vocal posters who
frequent cll who are both knowledgeable and civil.
--
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
Suggestion: Use your killfile liberally in cll
Tom Breton
Let me answer the technical question separately:
> I still don't understand what the problem is. If you consider a completey
> generic one-size fits all deepCopy to be useless, I'd have to strongly
> disagree. In Smalltalk I do what I consider "true" deep copies all the
> time, and I get a lot of use out of them. There even exists this tool
> called a DeepCopyArbiter that generically traverses any arbitrary graph of
> objects, and allows you to add rulesets to define at what point the deep
> copy should end, based on a specific instance, type of object, or other
> criteria. I'm baffled as to why you can't do this sort of thing easily in
> CLOS. Maybe I'm just not familiar enough with CLOS yet, or maybe this sort
> of pattern doesn't fit in well with the language?
In Lisp, some important structures haven't got that sort of type
information. IIUC this is not true in Smalltalk, which is strongly
typed.
For instance, alists ("dictionaries" to you) can't be distinguished
from ordinary lists without outside help. But they need to be copied
in a special way. So a deep copy in Lisp that found a list wouldn't
know whether to copy it as a regular list or an alist, and if it
guessed wrong it would make a mess.
As you suggest, it's all about how deep to copy; where to stop
descending.
FWIW, I wouldn't give up the ease with which Lisp operates on general,
untyped graphs just to have a deep copy.
Tom Breton
[Erik Naggum wrote]
> > are in no danger at all of being called morons. and in case you wonder
> > about more things, smart people who don't defend themselves can disagree
> > violently without even the hint of a danger of getting personal,
>
> You're complaining about *me* making matters personal.
> Oh, that's rich. Between the two of us, who's posting
> page-long diatribes sometimes filled with profanity?
Heh. I understand from second-hand quotes that he called me an
"obsessed stalker", a very strange name to call me when he is in my
killfile.
Tim Bradshaw
> I still don't understand what the problem is. If you consider a completey
> generic one-size fits all deepCopy to be useless, I'd have to strongly
> disagree. In Smalltalk I do what I consider "true" deep copies all the
> time, and I get a lot of use out of them. There even exists this tool
> called a DeepCopyArbiter that generically traverses any arbitrary graph of
> objects, and allows you to add rulesets to define at what point the deep
> copy should end, based on a specific instance, type of object, or other
> criteria.
Can you copy a queue correctly with this tool -- more generally does
it preserve arbitrary structure sharing? Can you use it to do several
different sorts of copies of an object depending on what kind of copy
you want? Does it have a user-definable version of equality and can
you have several different notions of equality for the same object?
--tim
Arne Knut Roev
> I still don't understand what the problem is. If you consider a completey
> generic one-size fits all deepCopy to be useless, I'd have to strongly
> disagree.
Well, there are two problems:
1. Is a completely generic/general "Deep copier" _possible_ ? (Which, if you
can recall, was at the heart of the original topic.)
2. A guy asks one question, gets a few answers, then asks a different
question, and claims that he has asked the same question both times.
Not a very good way of assuring us that he is interested in a sensible
answer, is it ?
Mr Upright also wrote:
> There even exists this tool called a DeepCopyArbiter that generically
> traverses any arbitrary graph of objects, and allows you to add rulesets
> to define at what point the deep copy should end, based on a specific
> instance, type of object, or other criteria.
"and allows you to add..." - but does it _require_ you to give it such
rulesets before using it, or can you just hand it an instance of
"something" and have it return a complete, deep copy, where it has walked
through all the substructures correctly, without destroying any
information or doing anything inappropriate with the things it
encountered on its way ? Because that is what the original question was
about, before all the manoeuvring began... (Yes, I _really_ want to know the
answer to this question...)
Erik Naggum
| You're complaining about *me* making matters personal.
| Oh, that's rich. Between the two of us, who's posting
| page-long diatribes sometimes filled with profanity?
well, here's the clue: _you_ take it personally. _you_ cannot even
imagine that it _isn't_ personal, but that's _your_ choice. you don't
have to make this choice. so make another choice if you aren't satisfied
with it. if you _are_ satisfied with your choice, and still complain,
you do in fact merit the personal insults and the label "moron" and much,
much more and much, much worse assessments of your mental state.
| Says he who fills up pages with insults & profanity...
obviously, _you_ have a personal problem with what _you_ think is insults
and profanity because your wiener brain makes you see _nothing_ else if
this trigger is fired within you. this is not somebody else's problem.
so just _deal_ with it if you don't like its consequences for you.
I take it that you are happy with your choice to take negative comments
personally and as destructively for yourself as possible, and so want
others to stop making negative comments that you could take personally.
face that facts, moron: that's not going to happen when you post as much
evidence of stupidity as you do.
#:Erik
thi
> That inspires the question: "Should programmers be protected from
> themselves?". Obviously, I don't think so. Such is fairly typical
> of my C background, I suppose.
programmers should be protected from each other.
thi
Rahul Jain
Only if one of them is a blatant troll
--
-> -\-=-=-=-=-=-=-=-=-=-/^\-=-=-=<*><*>=-=-=-/^\-=-=-=-=-=-=-=-=-=-/- <-
-> -/-=-=-=-=-=-=-=-=-=/ { 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.
Harley Davis
news:ng9ifsse746mdksfp...@4ax.com...
> I still don't understand what the problem is. If you consider a completey
> generic one-size fits all deepCopy to be useless, I'd have to strongly
> called a DeepCopyArbiter that generically traverses any arbitrary graph of
> objects, and allows you to add rulesets to define at what point the deep
> copy should end, based on a specific instance, type of object, or other
> CLOS. Maybe I'm just not familiar enough with CLOS yet, or maybe this
sort
> of pattern doesn't fit in well with the language?
Naturally, you *could* write such a system in Lisp - and many have. The
point being made (apparently with great difficulty) is that the proposed
system is just wrong, in Lisp, SmallTalk, or any other language, except in
somewhat limited circumstances. The correct semantics for deep copy depends
not only on the type and state of the objects being copied, but on the
*purpose* of the copy - information which cannot in general be stored in the
objects but depends on the application context.
I suspect that the rules in the proposed rules system would need to do some
sort of local network examination if you descend into generic system objects
such as lists or vectors. If the do spend time trying to guess the purpose
of the copy from the state of the local network around the current object in
the copy, the system is probably inefficient, heuristic, and
unmaintainable - it would be easier just to have several versions of deep
copy. Of course, in languages without closures and generic functions it can
be a pain to write recursive descent algorithms of arbitrary data
structures, so the programmer is discouraged from doing so and encouraged to
use generic facilities, even if they are inefficient and potentially
incorrect.
-- Harley
Courageous
> | Says he who fills up pages with insults & profanity...
>
> obviously, _you_ have a personal problem with what _you_ think is insults
You mean like when you say things like "fucking retarded" and
moronic and ah "wiener brain", and so on?
*mocking laughter*
C/
Tim Bradshaw
> Can you copy a queue correctly with this tool -- more generally does
> it preserve arbitrary structure sharing? Can you use it to do several
> different sorts of copies of an object depending on what kind of copy
> you want? Does it have a user-definable version of equality and can
> you have several different notions of equality for the same object?
I think this sounds a bit glib, so I'll try and be a bit clearer. I
hope this will be the last thing I write about this, because I've said
everything I have to I think, and probably more than I should have.
What I was mostly getting at was something that I kind of touched on
in the metafeatures paper, but I don't think I quite said it
explicitly, so here it is.
Programs, especially programs in a language like Lisp where
memory-management issues don't make complex data structures a
nightmare to deal with, can have objects which have shared
structure, and typically do.
This can be incidental -- without free() to kill you, it's OK
to share bits of other people's objects so long as you are
careful about modifying them.
Or it can be intentional, where the sharing is an important
part of the nature of the object. This is actually really
common in Lisp both in user code and also in things like
closures sharing environments.
A good example of this is a very obvious Lisp implementation
of a queue, or fifo object. This can be made in Lisp by an
object with two slots, one of which is a list, from which
things are peeled off one by one, and one of which is the last
cons of that same list. To add something to the queue you
destructively modify the last cons of the list something
like this:
(setf (cdr lastcons) (cons new nil)
lastcons (cdr lastcons))
(of course, there are boundary conditions to deal with when
the queue empties and so on, but those don't matter here).
It's absolutely crucial that a copier for this object do the
right thing:
a shallow copy will create something which is kind of
the same as the old queue, except that strange things
will happen if either queue empties;
a deep copy which does not preserve sharing will
create something which is just not a queue at all --
new objects added to the `queue' don't actually get
added.
There are two approaches to copying such an object which will
work.
You could write a special queue-copier, which would be
efficient. This is, I think, the right solution.
You could make a general-purpose copier which preserves
structure sharing (I call this graph-copying). This requires
an occurs check, and that is just inherently expensive I
believe[*], as such a general copier needs to check *every*
object in the thing being copied, whereas a special one can
know that only certain bits of sharing matter. Even then it
is questionable as to whether such a general copier is really
plausible.
It seems to me that there are two kinds of `general deep
copier' out there -- ones that don't preserve sharing and can
thus cause mysterious bugs, and ones that do and thus are much
more expensive than you would like. Java for instance (which
seems to have done mostly the right thing by defining an
interface for copying but no actual implementation), seems to
have a sharing-preserving copier in its serialisation
protocol: I wonder how many people realise this, and realise
the potential costs.
I would be interested in knowing what the SmallTalk and CORBA
copiers do.
--tim
[*] I'd also be interested in knowing if this can be made cheap. I
don't think it can because I think it's basically a theorem that's
known in places like the logic programming community (prolog has no
occurs check). There is a neat special case that *can* be made cheap,
which is when you're allowed to destroy the graph you are copying.
That's what copying GCs do. This is kind of reminiscent of Henry
Baker's Linear Lisp stuff, and in fact it might be the same case in
some way deeper than I can see.
Fernando D. Mato Mira
> Skeletons would also be provided, eg:
>
> (defmethod copy (context type (source list))
> (mapcar #'(lambda (x) (copy context type x)) source))
Let's emphasize the `eg'. ie, the Right Way would be to provide
something
a little more elaborate not making a linear proper list assumption, with
the protocol
becoming:
(defgeneric copy (context type source &optional map))
where /map/ should conform to a generic hashtable interface (eg,
hash-get, hash-put, hash-remove, hash-replace, hash-try-put)
--
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