Copying semantics molehill (was Re: True faiths)

Copying semantics molehill (was Re: True faiths)

[Patrick Doyle]

Kaz Kylheku <kaz@ashi.footprints.net> wrote:
>In article <3C4A58B8.10304@mail.com>, Hyman Rosen wrote:
>>Richard Riehle wrote:
>>
>>>         procedure Copy_Deep       (Source : in T; Target : in out T);
>>>         procedure Copy_Shallow  (Source : in T; Target : in out T);
>>
>>I dislike the notion of providing these methods as external interfaces
>>to a type. It seems wrong to me for a client to have to know what kind
>>of copy to use - that's the type's business to know.
>
>This turns out to be circular reasoning, because what a type ``knows''
>is partally defined by the operations you can perform on it.
>
>Suppose that you have N methods for copying an object. I do not take it
>as a theorem that you can always make an (N + 1)-th method which unifies
>the other N, magically choosing the appropriate one. How can this magic
>meta-method possibly know what semantics the caller wants?

I must be crazy.  I have never written a system where the semantics
of the "copy" operation mattered.  Mainly, this is for two reasons:

1. A lot of my data is immutable, so the copying semantics are moot.

2. Instead of copying an existing object, my usual idiom is to create a
new one from scratch.

I suppose there are some cases where these two things don't apply, or
would be inappropriate, and one would have to think very carefully about
the semantics of copying, but I can't think of such a case off the top
of my head.

I suppose that only says something about my inexperience as a programmer.
Can anyone show an example of a situation where copying semantics really
matter?

-- 
--
Patrick Doyle
doylep@eecg.toronto.edu

Re: Copying semantics molehill (was Re: True faiths)

[Steven T Abell]

> Can anyone show an example of a situation where copying semantics really
> matter?

Sure.
Imagine you have an object with some simple attributes,
ans some connections to other complex objects,
and you want to save this object to a file.
A shallow copy would only take those attributes that were simple,
for example, numbers and strings.
A deep copy would also copy out all of the connected complex objects,
and all of their connected objects, and all of their connected objects, etc.
For a great many objects that you will actually build,
a deep copy will eventually copy the entire image,
or get stuck in a copy cycle,
where some referent of the original object
refers back to the original object.
There are tools, such as in VisualWorks,
that scan the copy graph before copying
to work around this cyclic copying.
They work, but they are often unavoidably slow.
The exact meaning of "copy" turns out to be a *really* hard problem:
there is no single answer that works in all cases.

One place where copy depth is often a problem is in copying collections.
The usual copy creates a duplicate collection
with references to the same objects as the original collection.
This might be what you want, or it might not.
For this kind of copy,
you have to remember that changes to a collection element
will appear in *both* collections,
since both collections refer to that object.
A deeper copy copies the elements also,
but the question arises: How deeply do you copy?
Once again, there is no simple answer.
You have to think very carefully about your application's needs
and then code your copy semantics just as carefully.

Steve
--
Steven T Abell
Software Designer
http://www.brising.com

In software, nothing is more concrete than a good abstraction.

Re: Copying semantics molehill (was Re: True faiths)

[Kaz Kylheku]

In article <GqCG1x.nFH@ecf.utoronto.ca>, Patrick Doyle wrote:
>Kaz Kylheku <kaz@ashi.footprints.net> wrote:
>>In article <3C4A58B8.10304@mail.com>, Hyman Rosen wrote:
>>>Richard Riehle wrote:
>>>
>>>>         procedure Copy_Deep       (Source : in T; Target : in out T);
>>>>         procedure Copy_Shallow  (Source : in T; Target : in out T);
>>>
>>>I dislike the notion of providing these methods as external interfaces
>>>to a type. It seems wrong to me for a client to have to know what kind
>>>of copy to use - that's the type's business to know.
>>
>>This turns out to be circular reasoning, because what a type ``knows''
>>is partally defined by the operations you can perform on it.
>>
>>Suppose that you have N methods for copying an object. I do not take it
>>as a theorem that you can always make an (N + 1)-th method which unifies
>>the other N, magically choosing the appropriate one. How can this magic
>>meta-method possibly know what semantics the caller wants?
>
>I must be crazy.  I have never written a system where the semantics
>of the "copy" operation mattered.  Mainly, this is for two reasons:
>
>1. A lot of my data is immutable, so the copying semantics are moot.
>
>2. Instead of copying an existing object, my usual idiom is to create a
>new one from scratch.

Anecdotal evidence. I have written systems where it mattered.

Here is a recent example: a protocol stack where I have three ways
to copy a network buffer buffer object. I can copy a pointer, and
increment a reference count. I can copy the header structure which
maintains various pointers into the buffer, and bump up a lower reference
count on the buffer. Or I can do a deep copy which copies the buffer
as well.

This data is not immutable, so the copying semantics are not moot.

>I suppose there are some cases where these two things don't apply, or
>would be inappropriate, and one would have to think very carefully about
>the semantics of copying, but I can't think of such a case off the top
>of my head.
>
>I suppose that only says something about my inexperience as a programmer.
>Can anyone show an example of a situation where copying semantics really
>matter?

How about a Lisp example?

	(eq 'a 'a)  ==> T

	(eq 'a (copy-symbol 'a)) ==> NIL

A copy of a symbol is usually useless, because a symbol is meaningful
precisely because it is EQ to itself. So you usually need shallow,
reference copies of a symbol.

If a symbol is embedded in an object, and you want to copy that object,
you probably want to copy those embeddded symbols by reference.  And then
you are no longer making an entirely new object from scratch; the common
symbols are shared substructure.

Re: Copying semantics molehill (was Re: True faiths)

[Mike Brenner]

> Can anyone show an example of a situation where copying semantics really matter?

In the semantics of the realtime world the most important attribute is speed, since nothing means anything if it does not arrive in time in that realtime world. Therefore, one example would be that unintentionally cloning something (duplicating all of its parts) might take up too many resources (time, memory, network bandwidth, etc.), and might therefore become meaningless, even though speed is not part of the equation in non-realtime semantics. In many situations, such as unchecked_conversions, there is a critical percentage difference between whether the compiler generates code to copy or whether it "does the copy at compile time". 


> Imagine you have an object with some simple attributes, and some connections to other complex objects, and you want to save this object to a file. A shallow copy would only take those attributes that were simple, for example, numbers and strings.

Perhaps it we could also define a shallow copy to also copy the top level of references to those complex objects?


> A deep copy would also copy out all of the connected complex objects,
and all of their connected objects, and all of their connected objects, etc.
For a great many objects that you will actually build,
a deep copy will eventually copy the entire image,
or get stuck in a copy cycle,
where some referent of the original object
refers back to the original object.
There are tools, such as in VisualWorks,
that scan the copy graph before copying
to work around this cyclic copying.
They work, but they are often unavoidably slow.


In addition to tools, there are algorithms that detect cycles in graphs. If such a cycle were not detectable at all, then could we not report a bug against that storage management system. I agree that it can take a long time. 


> The exact meaning of "copy" turns out to be a *really* hard problem: there is no single answer that works in all cases.

I agree one has to think out which kind of copy one wishes to do, and I agree that there is no single answer that works in all cases. But how hard is it really?

The two most common types of copies needed are true clones of everything and top-level shallow copies of just the pointers. These are provided in many languages including, for example, Java and Python. When an intermediate level of copying is required, then it might probably need to be programmed manually.

Although not always used, Ada provides the ability to provide complex data structures without passing access types. In addition, a relational model can be used, implemented in the Ada language, for example, where all data structures would be two-dimensional tables. There are actually many ways to manage the data to avoid difficulty in defining to what level one needs to copy. 

Mike

Re: Copying semantics molehill (was Re: True faiths)

[Patrick Doyle]

In article <3C4D8AC7.37C31EEC@brising.com>,
Steven T Abell  <abell@brising.com> wrote:
>> Can anyone show an example of a situation where copying semantics really
>> matter?
>
>Sure.
>Imagine you have an object with some simple attributes,
>ans some connections to other complex objects,
>and you want to save this object to a file.

Ok, I must admit, that's a good one.  It's not really a copying issue
per se, but a persistence issue, though they have a lot in common.

I'm no expert on object persistence, so I'll have to leave it at that.  :-)

-- 
--
Patrick Doyle
doylep@eecg.toronto.edu

Re: Copying semantics molehill (was Re: True faiths)

[Patrick Doyle]

In article <IMh38.15646$XG4.659269@news2.calgary.shaw.ca>,
Kaz Kylheku <kaz@ashi.footprints.net> wrote:
>
>Here is a recent example: a protocol stack where I have three ways
>to copy a network buffer buffer object. I can copy a pointer, and
>increment a reference count. I can copy the header structure which
>maintains various pointers into the buffer, and bump up a lower reference
>count on the buffer. Or I can do a deep copy which copies the buffer
>as well.
>
>This data is not immutable, so the copying semantics are not moot.

Ok, so when you copy a container object--like lists, arrays, etc.--you
need to know whether to copy its contents too.  Is this the same issue?

>If a symbol is embedded in an object, and you want to copy that object,
>you probably want to copy those embeddded symbols by reference.  And then
>you are no longer making an entirely new object from scratch; the common
>symbols are shared substructure.

I have a hard time picturing how this is implemented.  Does one just
contain a reference to part of the other?

-- 
--
Patrick Doyle
doylep@eecg.toronto.edu

Re: Copying semantics molehill (was Re: True faiths)

[Robert Dewar]

doylep@eecg.toronto.edu (Patrick Doyle) wrote in message news:<GqCG1x.nFH@ecf.utoronto.ca>...
> I must be crazy.  I have never written a system where the > semantics of the "copy" operation mattered.  Mainly, this 
> is for two reasons:
> 
> 1. A lot of my data is immutable, so the copying semantics are moot.
> 
> 2. Instead of copying an existing object, my usual idiom is to create a
> new one from scratch.

Not crazy, but unusual. You are saying that you do not
do assignments of the form

   a := b;

where a and b are both objects and that you do not
use IN OUT parameters. It is certainly possible to write
code with these constraints, but definitely unusual.

Re: Copying semantics molehill (was Re: True faiths)

[Patrick Doyle]

In article <5ee5b646.0201271908.38674a0d@posting.google.com>,
Robert Dewar <dewar@gnat.com> wrote:
>doylep@eecg.toronto.edu (Patrick Doyle) wrote in message news:<GqCG1x.nFH@ecf.utoronto.ca>...
>> I must be crazy.  I have never written a system where the semantics
>> of the "copy" operation mattered.  Mainly, this is for two reasons:
>> 
>> 1. A lot of my data is immutable, so the copying semantics are moot.
>> 
>> 2. Instead of copying an existing object, my usual idiom is to create a
>> new one from scratch.
>
>Not crazy, but unusual. You are saying that you do not
>do assignments of the form
>
>   a := b;
>
>where a and b are both objects and that you do not
>use IN OUT parameters.

No, actually I'm saying what I said.  ;-)

>It is certainly possible to write code with these constraints, but
>definitely unusual.

It is most certainly not unusual.  For instance, Java has neither
object-wise assignment nor in-out parameters.

Do you mean it's unusual in some particular language?

-- 
--
Patrick Doyle
doylep@eecg.toronto.edu