(I'm using akcl common lisp)
I'm trying to use arrays in a fairly complex program (approx
4000 lines at the minute). The arrays are 21x21 and 21x21x2 large. the
problem is that at some points I want to take a copy of them, to work
on and then maybe reject later leaving the original unchanged.
It seems however that even though arrays behave very much like
structs there is no simple way of copying them. (i.e. for a struct
called fred say created by defstruct there is (copy-fred <arg>) ). So
I wondered if there is a built in or some method I can use to do this
efficiently.
I know that arrays are composed of sequences which is
presumably why the problem occurs but beyond that I'm stuck with
copying each object specifically with a setf or something.
Hope someone can help.
steve.
In article <··········@scotsman.ed.ac.uk> ·······@dai.ed.ac.uk (Steven Willmott) writes:
> (I'm using akcl common lisp)
As a consequence, what I say may or may not work for you. It's possible
some syntax changes were made for ANSI that are not reflected in AKCL, but
my guess is that if it doesn't tell you you have undefined functions or
unrecognized keyword args in the examples I show, you're probably ok.
> I'm trying to use arrays in a fairly complex program (approx
> 4000 lines at the minute). The arrays are 21x21 and 21x21x2 large. the
> problem is that at some points I want to take a copy of them, to work
> on and then maybe reject later leaving the original unchanged.
>
> It seems however that even though arrays behave very much like
> structs there is no simple way of copying them. (i.e. for a struct
> called fred say created by defstruct there is (copy-fred <arg>) ). So
> I wondered if there is a built in or some method I can use to do this
> efficiently.
The problem is whether to descend the contents, whether to copy the fill
pointer, etc. e.g., all of the following would be valid definitions.
Write one that copies what you want:
(defun copy-array (array)
;; This doesn't copy the array element type
(make-array (array-dimensions array) :initial-contents array))
(defun copy-array (array)
;; This doesn't copy the fill pointer
(make-array (array-dimensions array)
:initial-contents array
:element-type (array-element-type array)))
(defun copy-array (array)
;; This doesn't copy array displacement
(make-array (array-dimensions array)
:initial-contents array
:element-type (array-element-type array)
:fill-pointer (if (array-has-fill-pointer-p array)
(fill-pointer array))))
...etc. You can also write stuff that copies the array-displacement.
Worse, you may want to do
(defmethod copy ((array array)) ;you'll need methods for other types
(let ((new (make-array (array-dimensions array)
;; Note again we're omitting copy of
;; fill pointer, etc.
:element-type (array-element-type array))))
(dotimes (i (array-total-size array))
(setf (row-major-aref new i) (copy (row-major-aref array i))))
new))
This is what I mean by "descending". Whether or not copy descends is a policy
question (sort of like the policy that divides EQUAL and EQUALP).
There is no single right answer--choosing an answer that is right for your
application is what you should do. For example, whether you implement
(COPY symbol) as (COPY-SYMBOL symbol) or just symbol [the identity] depends
a lot on your application--my bet is that in spite of its name, COPY-SYMBOL
is rarely the copy function you want for symbols.
> I know that arrays are composed of sequences
NO. They are not. Arrays are a single range of randomly accessible
memory cells with (array-total-size array) elements, which each
element can hold an element of type (array-element-type array). There
are no sub-objects, sequence or otherwise, that compose to make
arrays. Two dimensional arrays are NOT one-dimensional arrays of
one-dimensional arrays. The entire storage space of an array can be
viewed through a one-dimensional lens using ROW-MAJOR-AREF, permitting
certain utilities to work on any-dimensional arrays without having a
zillion different clauses, one for each arity, but there is no
directly obtainable object that is the one-dimensional object
ROW-MAJOR-AREF refers to; it can be conjured indirectly (i.e., with a
wrapper) by using
(defun 1d-array (array)
(make-array (array-total-size array)
:element-type (array-element-type array)
:displaced-to array
:displaced-index-offset 0))
This conses a small wrapper and is slightly slower to access than the original
array, but when AREF'd (as a one-d array) it behaves like ROW-MAJOR-AREF of the
original n-dimensional array.
> which is
> presumably why the problem occurs but beyond that I'm stuck with
> copying each object specifically with a setf or something.
Hopefully the "or something" will be easier with some of the above recipes.
Btw, I didn't test any of this--I'm on a lunch break and just wanted to rattle
this off quickly between other things. I hope if there are typos or problems
in my code, someone will spot and report them.
I wrote a Parenthetically Speaking column about the conceptual complexities of
EQUAL, COPY, etc. and why I think they're doomed to lose in CL. The paper is
online as
http://world.std.com/~pitman/PS/EQUAL.html
Curiously, Henry Baker also wrote a paper about EQUAL with an amazingly similar
title (though very different content) in the same timeframe. I guess it was an
issue that needed writing (or a pun that needed making--both were about `EQUAL
rights'). I don't have a pointer to his paper, but I'm sure with this nice lead-in,
he'll volunteer a URL or FTP address...
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
> (defun copy-array (array)
> ;; This doesn't copy the array element type
> (make-array (array-dimensions array) :initial-contents array))
I don't think this (nor most of your other suggested versions) will work
for multidimensional arrays. :INITIAL-CONTENTS is required to be nested
sequences, where the length of the sequences at each level matches the
corresponding array dimension. I don't remember whether we ever discussed
allowing it to be an array of similar dimensionality, and if so why we
didn't adopt it, but that's the way it is.
See my previous post in this thread for the hoops you're forced to jump
through with displacing in order to write COPY-ARRAY. The other
alternative is your loop using ROW-MAJOR-AREF; however, if the
implementation has optimized handling of :INITIAL-CONTENTS, the loop
wouldn't be able to benefit from it.
>Btw, I didn't test any of this--I'm on a lunch break and just wanted to rattle
>this off quickly between other things. I hope if there are typos or problems
>in my code, someone will spot and report them.
Spotted and reported, as requested!
--
Barry Margolin, ······@bbnplanet.com
BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
In article <··········@tools.bbnplanet.com> Barry Margolin <······@bbnplanet.com> writes:
> pitman> (defun copy-array (array)
> pitman> ;; This doesn't copy the array element type
> pitman> (make-array (array-dimensions array) :initial-contents array))
>
> I don't think this (nor most of your other suggested versions) will work
> for multidimensional arrays. :INITIAL-CONTENTS is required to be nested
> sequences, where the length of the sequences at each level matches the
> corresponding array dimension. I don't remember whether we ever discussed
> allowing it to be an array of similar dimensionality, and if so why we
> didn't adopt it, but that's the way it is.
Blech. I'll make a note for future work. I'm sure I never voted in favor
of the current behavior. I wonder if the restriction pre-dated the presence
of ROW-MAJOR-AREF, when writing code to support iteration across n-dimensional
structures was really hard and/or really time-consuming to compile.
> See my previous post in this thread for the hoops you're forced to jump
> through with displacing in order to write COPY-ARRAY. The other
> alternative is your loop using ROW-MAJOR-AREF; however, if the
> implementation has optimized handling of :INITIAL-CONTENTS, the loop
> wouldn't be able to benefit from it.
Your other post shows something that results in a displaced array.
barmar> (defun copy-array (array)
barmar> (let* ((flattened (make-array (array-total-size array)
barmar> :displaced-to array))
barmar> (new-flat (make-array (array-total-size array)
barmar> :initial-contents flattened)))
barmar> (make-array (array-dimensions array) :displaced-to new-flat)))
Darn. I wanted to do:
(defun copy-array (array)
(let* ((flattened (make-array (array-total-size array)
:element-type (array-element-type array)
:displaced-to array))
(new (make-array (array-total-size array)
:element-type (array-element-type array)
:initial-contents flattened)))
(adjust-array new (array-dimensions array))))
but I see ADJUST-ARRAY doesn't let you change the rank of an array. Ok, I'm
not beat yet. How about this! ...
(defun copy-array (array)
(let* ((flattened (make-array (array-total-size array)
:displaced-to array))
(new-flat (make-array (array-total-size array)
:initial-contents flattened))
(new-shaped (make-array (array-dimensions array)
:displaced-to new-flat)))
(adjust-array new-shaped :displaced-to nil)))
Wow. All that to avoid the use of a simple loop using ROW-MAJOR-AREF, which
would really be -way- more efficient, not to mention consing less (since new-flat's
data area and the wrappers for flattened, new-flat, and new-shape are all
garbage at the end)... Still, if one is intent on having some other operator do
the work, one CAN get it to happen with enough work on one's own part. :-)
BUT, lest you be racing for CLHS to see if that last ADJUST-ARRAY really works,
it does! Here's the case:
----------
[When] A is displaced to B before the call, but not displaced afterward.
(adjust-array A ... :displaced-to B)
(adjust-array A ... :displaced-to nil)
A gets a new ``data region,'' and contents of B are copied into it
as appropriate to maintain the existing old contents; additional
elements of A are taken from initial-element if supplied. However,
the use of initial-contents causes all old contents to be
discarded.
----------
> >Btw, I didn't test any of this--I'm on a lunch break and just wanted to rattle
> >this off quickly between other things. I hope if there are typos or problems
> >in my code, someone will spot and report them.
>
> Spotted and reported, as requested!
Not really--I was hoping only for SMALL errors. ;-)
pitman> (defun copy-array (array)
pitman> (let* ((flattened (make-array (array-total-size array)
pitman> :displaced-to array))
pitman> (new-flat (make-array (array-total-size array)
pitman> :initial-contents flattened))
pitman> (new-shaped (make-array (array-dimensions array)
pitman> :displaced-to new-flat)))
pitman> (adjust-array new-shaped :displaced-to nil)))
barmar> Well, with that ADJUST-ARRAY trick, you don't even need the flattened
barmar> arrays. How about:
barmar>
barmar> (defun copy-array (array)
barmar> (let ((new (make-array (array-dimensions array) :displaced-to array)))
barmar> (adjust-array new :displaced-to nil)))
barmar>
barmar> Beat that, Kent!
Nice job, Barry... I knew something like that was in there... Of
course, a :element-type would be nice (as it would have been in mine
above--oops). Actually, the :element-type part here isn't optional,
since (per CLHS):
the consequences are undefined if the actual array element type of
displaced-to is not type equivalent to the actual array element type
of the array being created.
All right. I'm happy with:
(defun copy-array (array)
(adjust-array (make-array (array-dimensions array)
:displaced-to array
:element-type (array-element-type array))
(array-dimensions array)
:displaced-to nil))
I actually tested this one in LispWorks just to be sure we weren't losing
in some unexpected way.
(setq bar (copy-array (setq foo #2a((a b) (c d)))))
#2A((A B) (C D))
foo => #2A((A B) (C D))
bar => #2A((A B) (C D))
(eq foo bar) => NIL
(equalp foo bar) => T
(setf (aref foo 0 0) 'z) => Z ;test storage not shared
foo => #2A((Z B) (C D))
bar => #2A((A B) (C D))
;; Test some other element types...
(copy-array "foo bar") => "foo bar"
(copy-array #(1 2 3)) => #(1 2 3)
(copy-array #*10101) => #*10101
In article <···············@world.std.com> ······@world.std.com (Kent M Pitman) writes:
From: ······@world.std.com (Kent M Pitman)
Newsgroups: comp.lang.lisp
Date: Fri, 25 Jul 1997 04:45:44 GMT
Organization: The World Public Access UNIX, Brookline, MA
...
All right. I'm happy with:
(defun copy-array (array)
(adjust-array (make-array (array-dimensions array)
:displaced-to array
:element-type (array-element-type array))
(array-dimensions array)
:displaced-to nil))
I actually tested this one in LispWorks just to be sure we weren't losing
in some unexpected way.
It works very well in CMUCL 18a too.
--
Marco Antoniotti
==============================================================================
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472
In article <··········@scotsman.ed.ac.uk>,
Steven Willmott <·······@dai.ed.ac.uk> wrote:
> It seems however that even though arrays behave very much like
>structs there is no simple way of copying them. (i.e. for a struct
>called fred say created by defstruct there is (copy-fred <arg>) ). So
>I wondered if there is a built in or some method I can use to do this
>efficiently.
There's no built-in array copying function. Here's a possible function:
(defun copy-array (array)
(let* ((flattened (make-array (array-total-size array)
:displaced-to array))
(new-flat (make-array (array-total-size array)
:initial-contents flattened)))
(make-array (array-dimensions array) :displaced-to new-flat)))
Note that this only works for general arrays; if you need to support
specialized arrays, you can enhance it to copy the array type in the
intermediary and resulting arrays.
--
Barry Margolin, ······@bbnplanet.com
BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>