I must be off my rocker here. I'm writing a deep copy routine for a
game I'm working on, and can't find any reliable way to copy an array
in the general case.
Here's what I've done so far (not really tested):
(defmethod copy-for-player ((obj array))
(let ((retval (make-array (array-dimensions obj)
:element-type (array-element-type obj)
:adjustable (adjustable-array-p obj)
:fill-pointer (and (array-has-fill-pointer-p obj)
(fill-pointer obj))
:displaced-to nil)))
(dotimes (i (if (array-has-fill-pointer-p obj)
(fill-pointer obj)
(array-total-size obj)))
(setf (row-major-aref retval i)
(copy-for-player (row-major-aref obj i))))
retval))
My quandary revolves around the following bit of the MAKE-ARRAY
documentation, from the spec:
If initial-element is not supplied, the consequences of later reading
an uninitialized element of new-array are undefined unless either
initial-contents is supplied or displaced-to is non-nil.
(See also issue UNINITIALIZED-ELEMENTS:CONSEQUENCES-UNDEFINED.)
That seems to imply that my code invokes "undefined consequences".
What's more-- blow me away-- I can't seem to find any way to copy an
array, or (what I need) to map one array to another (through my deep
copy function).
Any thoughts?
Thanks,
joelh
From: Christopher C. Stacy
Subject: Re: Copying arrays -- generally possible?
Date:
Message-ID: <uelgiwlpa.fsf@grant.org>
>>>>> On 11 May 2002 02:54:12 -0700, Joel Ray Holveck ("Joel") writes:
Joel> I must be off my rocker here. I'm writing a deep copy routine
Joel> for a game I'm working on, and can't find any reliable way to
Joel> copy an array in the general case.
Your issue isn't really about arrays, but rather
about copying the objects in the array.
To make an array that's isomorphic to a given array, you use the
initialization keywords as in your example. If you want those two arrays
to contain the same contents, you can use the :INITIAL-CONTENTS keyword.
But there is no general COPY function in Lisp, because in general,
only the programmer can know what constitutes a proper copy.
So, yes, you will have to write some kind of loop calling your
object copying function.
There's a bug in your COPY-FOR-PLAYER program, though: it always
recursively calls itself on each element of the array. Perhaps
this is what you want, if each element is itself an array.
But eventually there must be some element that is not an array.
(Maybe those elements are PLAYER objects in your game? Or NIL?)
You need a test case for the recursion to bottom out.
Or maybe the recursive call to COPY-FOR-PLAYER was
just a typo for COPY-PLAYER.
Joel> What's more-- blow me away-- I can't seem to find any way to
Joel> copy an array, or (what I need) to map one array to another
Joel> (through my deep copy function).
Mapping one array to another is accomplished with the :DISPLACED-TO keyword.
You used that MAKE-ARRAY option in your program, and probably didn't mean to.
>> I must be off my rocker here. I'm writing a deep copy routine
>> for a game I'm working on, and can't find any reliable way to
>> copy an array in the general case.
> To make an array that's isomorphic to a given array, you use the
> initialization keywords as in your example. If you want those two arrays
> to contain the same contents, you can use the :INITIAL-CONTENTS keyword.
Yes, but how do I create the argument to :INITIAL-CONTENTS? It would
involve reading each element of the OBJ array, and I have no guarantee
that I'm allowed to do that (since it may be sparsely initialized.)
That's the main point of my question.
In other words, in my DOTIMES loop that populated it, I may stumble
across an uninitialized element of the OBJ array. I have no way to
know which elements are uninitialized, so I can't avoid them. If I
read an uninitialized element, then I invoke "undefined consequences".
> But there is no general COPY function in Lisp, because in general,
> only the programmer can know what constitutes a proper copy.
> So, yes, you will have to write some kind of loop calling your
> object copying function.
Of course. I have no problem with there being no general "COPY"
function, so that's why I'm writing this.
> There's a bug in your COPY-FOR-PLAYER program, though: it always
> recursively calls itself on each element of the array. Perhaps
> this is what you want, if each element is itself an array.
> But eventually there must be some element that is not an array.
Of course. There are other methods to COPY-FOR-PLAYER that I did not
include. In particular, it bottoms out on numbers and symbols, but it
recursively copies arrays, lists, and instances of certain classes
(defined in the program).
Here's a few of the other methods I've defined on COPY-FOR-PLAYER:
(defmethod copy-for-player ((obj number))
obj)
(defmethod copy-for-player ((obj symbol))
obj)
(defmethod copy-for-player ((obj sequence))
(map (type-of obj) #'copy-for-player obj))
I didn't include these or the object-specific methods because they
didn't seem relevant to my question. If you want more information on
this, I'd be glad to include the rest of the code.
> (Maybe those elements are PLAYER objects in your game? Or NIL?)
> You need a test case for the recursion to bottom out.
> Or maybe the recursive call to COPY-FOR-PLAYER was
> just a typo for COPY-PLAYER.
No, I just have them in different methods.
>> What's more-- blow me away-- I can't seem to find any way to
>> copy an array, or (what I need) to map one array to another
>> (through my deep copy function).
> Mapping one array to another is accomplished with the :DISPLACED-TO keyword.
> You used that MAKE-ARRAY option in your program, and probably didn't mean to.
When I wrote :DISPLACED-TO NIL, I was explicitly making the point (to
people reading the code) that the newly created array does not share
structure with anything. In particular, it does not share structure
with the original array, or the array (if any) that OBJ shared
structure with. I could have left that argument out.
Cheers,
joelh
Joel Ray Holveck <·····@juniper.net> writes:
> >> I must be off my rocker here. I'm writing a deep copy routine
> >> for a game I'm working on, and can't find any reliable way to
> >> copy an array in the general case.
> > To make an array that's isomorphic to a given array, you use the
> > initialization keywords as in your example. If you want those two arrays
> > to contain the same contents, you can use the :INITIAL-CONTENTS keyword.
>
> Yes, but how do I create the argument to :INITIAL-CONTENTS? It would
> involve reading each element of the OBJ array, and I have no guarantee
> that I'm allowed to do that (since it may be sparsely initialized.)
> That's the main point of my question.
>
> In other words, in my DOTIMES loop that populated it, I may stumble
> across an uninitialized element of the OBJ array. I have no way to
> know which elements are uninitialized, so I can't avoid them. If I
> read an uninitialized element, then I invoke "undefined consequences".
Callers of COPY-FOR-PLAYER are simply not allowed to pass (partially)
uninitialized arrays in. The sole point of not initializing arrays
via either :initial-element or :initial-contents is to allow the
application to initialize the array itself, without incurring the
unnecessary cost of doubly initializing cells.
This feature is not intended to give you a sparse array
implementation (of course the standard doesn't prevent an
implementation from doing that as an extension, but then the
implementation's documentation should give you enough information to
deal with sparse arrays), otherwise you'd have a predicate
"array-cell-initialized" or similarly in the standard.
So leaving unitialized arrays lying around and expecting all general
array operators to work on them is not a valid expectation, IMHO.
Just as AREF is not going to work portably, so COPY-FOR-PLAYER is not
going to work portably (implementations are again free to define the
consequences).
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
>>>> I must be off my rocker here. I'm writing a deep copy routine
>>>> for a game I'm working on, and can't find any reliable way to
>>>> copy an array in the general case.
[snip]
> Callers of COPY-FOR-PLAYER are simply not allowed to pass (partially)
> uninitialized arrays in. The sole point of not initializing arrays
> via either :initial-element or :initial-contents is to allow the
> application to initialize the array itself, without incurring the
> unnecessary cost of doubly initializing cells.
Okay, that makes sense. Thanks for the clarification.
Cheers,
joelh