My Lisp program is doing something strange. I have the following code
segment
(setf temp1 game-board)
(setf temp2 game-board)
(setf temp3 game-board)
(swap-elements temp1)
(swap-elements temp2)
(swap-elements temp3)
(list temp1 temp2 temp3)
Where game-board is a parameter to the function and is defined as an
two-dimensional array. Swap elements changes the position of two
elements in the array. I then want to return a list of those arrays.
What is happening is it looks like temp1, temp2, temp3, and game-board all
share the same copy of the array because a changed to temp1 affects
the rest of the elements. Any help with this problem would be greatly
appreciated.
Chris Gund
In article <··················@sdg.dra.com> ······@sdg.dra.com writes:
>My Lisp program is doing something strange. I have the following code
>segment
>
> (setf temp1 game-board)
> (setf temp2 game-board)
> (setf temp3 game-board)
> (swap-elements temp1)
> (swap-elements temp2)
> (swap-elements temp3)
> (list temp1 temp2 temp3)
>
>Where game-board is a parameter to the function and is defined as an
>two-dimensional array. Swap elements changes the position of two
>elements in the array. I then want to return a list of those arrays.
>What is happening is it looks like temp1, temp2, temp3, and game-board all
>share the same copy of the array because a changed to temp1 affects
>the rest of the elements. Any help with this problem would be greatly
>appreciated.
>
Keep in mind that (setf foo bar) makes foo point to exactly the same place in
the computer's memory as bar.
Thus, you *don't* have an original and three copies of game-board. You have
four variables all pointing to game-board.
Do:
(setf temp1 (copy-seq game-board))
(setf temp2 (copy-seq game-board))
(setf temp3 (copy-seq game-board))
(swap-elements temp1)
(swap-elements temp2)
(swap-elements temp3)
(list temp1 temp2 temp3)
--
"TANSTAAFL" ·····@aristotle.ils.nwu.edu
In <··················@sdg.dra.com> ······@sdg.dra.com writes:
>My Lisp program is doing something strange. I have the following code
>segment
>
> (setf temp1 game-board)
> (setf temp2 game-board)
> (setf temp3 game-board)
> (swap-elements temp1)
> (swap-elements temp2)
> (swap-elements temp3)
> (list temp1 temp2 temp3)
>
>Where game-board is a parameter to the function and is defined as an
>two-dimensional array. Swap elements changes the position of two
>elements in the array. I then want to return a list of those arrays.
>What is happening is it looks like temp1, temp2, temp3, and game-board all
>share the same copy of the array because a changed to temp1 affects
>the rest of the elements. Any help with this problem would be greatly
>appreciated.
Well, it's not really strange. And you seem to already know the
answer yourself. The problem is that you only have one array, and as
you say, all the symbols share the same copy of it. I assume you
swapped elements by doing "(setf (aref ...) ...)", which destructively
replaces an array element -- this changes the one array which they all
share, so they all change. You would have gotten the same behavior
had game-board been a list, and you had done "(setf (nth ...) ...)".
The problem is not variables and scope, but rather destructive
operations on shared structures. The solution is to make a totally
new copy of the array, so no structure is shared. I don't think a
"copy-array" function (similar to "copy-list") exists in Common Lisp
(at least, I couldn't find one in CLTL), so you may have to define
your own.
Hope this helps.
--
Milt Epstein
Department of Computer Science
University of Illinois
·······@cs.uiuc.edu
In article <····················@sunb10.cs.uiuc.edu> ·······@sunc2.cs.uiuc.edu (Milt Epstein) writes:
The solution is to make a totally
new copy of the array, so no structure is shared. I don't think a
"copy-array" function (similar to "copy-list") exists in Common Lisp
(at least, I couldn't find one in CLTL), so you may have to define
your own.
COPY-SEQ is what you want. See CLtL p 248, or CLtL2 p 393.
-Jeff Berger
--
Jeff Berger |USmail: Ryerson 256
······@cs.uchicago.edu | Artificial Intelligence Lab
PH: (312) 702-8584 | 1100 East 58th Street
FX: (312) 702-8487 | Chicago, IL 60637
In article <···················@pride.cs.uchicago.edu> ······@tartarus.uchicago.edu (Jeff Berger) writes:
In article <····················@sunb10.cs.uiuc.edu> ·······@sunc2.cs.uiuc.edu (Milt Epstein) writes:
The solution is to make a totally
new copy of the array, so no structure is shared. I don't think a
"copy-array" function (similar to "copy-list") exists in Common Lisp
(at least, I couldn't find one in CLTL), so you may have to define
your own.
COPY-SEQ is what you want. See CLtL p 248, or CLtL2 p 393.
This only works if the array is a sequence i.e., a vector. I get the
impression that the original poster's array was two-dimensional (it
was a game board.)
--
Tim Moore ·····@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Ah, youth. Ah, statute of limitations."
-John Waters
In article <··················@defmacro.cs.utah.edu>, ·····@cs.utah.edu (Tim Moore) writes:
>
>>> The solution is to make a totally
>>> new copy of the array, so no structure is shared. I don't think a
>>> "copy-array" function (similar to "copy-list") exists in Common Lisp
>>> (at least, I couldn't find one in CLTL), so you may have to define
>>> your own.
>
>> COPY-SEQ is what you want. See CLtL p 248, or CLtL2 p 393.
>
> This only works if the array is a sequence i.e., a vector. I get the
> impression that the original poster's array was two-dimensional (it
> was a game board.)
The following function will copy an array.
(DEFUN CopyArray (array)
(LET* (
(arrayType (ARRAY-ELEMENT-TYPE array))
(arraySize (ARRAY-TOTAL-SIZE array))
(newArray (MAKE-ARRAY (ARRAY-DIMENSIONS array)
:ELEMENT-TYPE arrayType
:ADJUSTABLE (ADJUSTABLE-ARRAY-P array)))
(source (MAKE-ARRAY arraySize
:ELEMENT-TYPE arrayType
:DISPLACED-TO array))
(dest (MAKE-ARRAY arraySize
:ELEMENT-TYPE arrayType
:DISPLACED-TO newArray))
)
(DOTIMES (i arraySize)
(SETF (AREF dest i) (AREF source i)))
newArray))
Does anyone know a faster way to do this?
·····@farallon.com (Danny Brewer) writes:
> The following function will copy an array.
>
> (DEFUN CopyArray (array)
> (LET* (
> (arrayType (ARRAY-ELEMENT-TYPE array))
> (arraySize (ARRAY-TOTAL-SIZE array))
> (newArray (MAKE-ARRAY (ARRAY-DIMENSIONS array)
> :ELEMENT-TYPE arrayType
> :ADJUSTABLE (ADJUSTABLE-ARRAY-P array)))
> (source (MAKE-ARRAY arraySize
> :ELEMENT-TYPE arrayType
> :DISPLACED-TO array))
> (dest (MAKE-ARRAY arraySize
> :ELEMENT-TYPE arrayType
> :DISPLACED-TO newArray))
> )
> (DOTIMES (i arraySize)
> (SETF (AREF dest i) (AREF source i)))
> newArray))
>
> Does anyone know a faster way to do this?
X3J13 has added ROW-MAJOR-AREF, which can be used to avoid making the
displaced arrays. You could just do:
(DEFUN CopyArray (array)
(LET* (
(arrayType (ARRAY-ELEMENT-TYPE array))
(arraySize (ARRAY-TOTAL-SIZE array))
(newArray (MAKE-ARRAY (ARRAY-DIMENSIONS array)
:ELEMENT-TYPE arrayType
:ADJUSTABLE (ADJUSTABLE-ARRAY-P array)))
)
(DOTIMES (i arraySize)
(SETF (ROW-MAJOR-AREF newArray i) (ROW-MAJOR-AREF array i)))
newArray))
In most lisps, displaced arrays involve an extra indirection every
time you aref them. ROW-MAJOR-AREF avoids this. (In fact, in CMU
Common Lisp, ROW-MAJOR-AREF will be faster then AREF for
multi-dimensional arrays because it does not have to compute the
row-major index itself.)
-William Lott
CMU Common Lisp Group
In article <···@farallonfarallon.com> ·····@farallon.com (Danny Brewer) writes:
>
>The following function will copy an array.
>
>(DEFUN CopyArray (array)
> (LET* (
> (arrayType (ARRAY-ELEMENT-TYPE array))
> (arraySize (ARRAY-TOTAL-SIZE array))
> (newArray (MAKE-ARRAY (ARRAY-DIMENSIONS array)
> :ELEMENT-TYPE arrayType
> :ADJUSTABLE (ADJUSTABLE-ARRAY-P array)))
> (source (MAKE-ARRAY arraySize
> :ELEMENT-TYPE arrayType
> :DISPLACED-TO array))
> (dest (MAKE-ARRAY arraySize
> :ELEMENT-TYPE arrayType
> :DISPLACED-TO newArray))
> )
> (DOTIMES (i arraySize)
> (SETF (AREF dest i) (AREF source i)))
> newArray))
>
>Does anyone know a faster way to do this?
Well, William Lott gave you the right answer for CommonLisp that
implement X3J13's ROW-MAJOR-AREF. But not all lisps have it, and I
happen to have this code laying around that I wrote I while back.
It's huge and it's ugly, but it does everything a person could possibly
want to do while copying an array or vector. And because it checks
for about every possible special case you could imagine, it's actually
pretty efficient.
- Trent Lange
;;;;
(defun copy-any-array (old-array &rest keys-passed &key key dimensions)
;; Returns a copy of old-array. If :key is provided, then the
;; elements of the new-array are the result of key applied to
;; old-array's elements. If :dimensions is provided, and it is
;; different than old-array's dimensions, then the new-array is created
;; with those dimensions, and everything that can be copied from
;; old-array is copied into it. It is an error if the rank of
;; the array specified by dimensionss is different than that of the
;; old-array.
(declare (list keys-passed)
(dynamic-extent keys-passed))
(cond
((simple-vector-p old-array)
(apply #'copy-array-contents
old-array
(make-array (or dimensions (length (the simple-vector old-array))))
keys-passed))
((vectorp old-array)
(apply #'copy-array-contents
old-array
(make-array (or dimensions (length (the vector old-array)))
:element-type (array-element-type old-array)
:adjustable (adjustable-array-p old-array))
keys-passed))
((arrayp old-array)
(let* ((old-dimensions (array-dimensions old-array))
(new-dimensions (or dimensions old-dimensions))
(element-type (array-element-type old-array))
(new-array
(make-array new-dimensions
:element-type element-type
:adjustable (adjustable-array-p old-array))))
(if (or (null dimensions) (equal new-dimensions old-dimensions))
(let* ((displaced-old-array
(make-array (array-total-size old-array)
:element-type element-type
:displaced-to old-array))
(displaced-new-array
(make-array (array-total-size new-array)
:element-type element-type
:displaced-to new-array)))
(copy-array-contents displaced-old-array
displaced-new-array
:key key))
(let ((first-dimension
(min (the fixnum (car new-dimensions))
(the fixnum (car old-dimensions)))))
(walk-dimensions
(loop for new-dim fixnum in (cdr new-dimensions)
as old-dim fixnum in (cdr old-dimensions)
collect (min new-dim old-dim))
#'(lambda (post-indices)
(copy-array-contents old-array new-array
:key key
:length first-dimension
:post-indices post-indices)))))
new-array))))
(defun copy-array-contents
(old-array new-array &key key length post-indices &allow-other-keys)
;; Copies the contents of old-array into new-array, using key if
;; supplied. Only the first :length items are copied (defaulting
;; to the length of the old-array). If :post-indices are passed, then
;; they are used as "post" indices to an aref.
(macrolet
((do-copy (aref old new key key-type len post-indices)
(let ((atype (if (eq aref #'svref) 'simple-vector 'array)))
`(loop for i fixnum from 0 to (the fixnum (1- (the fixnum ,len)))
do (setf ,(if post-indices
`(apply #'aref (the ,atype ,new) i ,post-indices)
`(,aref (the ,atype ,new) i))
,(if key-type
`(funcall
(the ,key-type ,key)
,(if post-indices
`(apply #'aref (the ,atype ,old)
i ,post-indices)
`(,aref (the ,atype ,old) i)))
(if post-indices
`(apply #'aref (the ,atype ,old) i ,post-indices)
`(,aref (the ,atype ,old) i)))))))
(expand-on-key (aref key old new len post-ind)
`(cond
((null ,key)
(do-copy ,aref ,old ,new ,key NIL ,len ,post-ind))
((compiled-function-p ,key)
(do-copy ,aref ,old ,new ,key compiled-function ,len ,post-ind))
(T
(do-copy ,aref ,old ,new ,key function ,len ,post-ind)))))
(if (simple-vector-p old-array)
(progn
(when post-indices
(error "Can't pass post-indices given to COPY-ARRAY-CONTENTS
from simple-vector"))
(unless length
(setf length (min (length (the simple-vector old-array))
(length (the simple-vector new-array)))))
(expand-on-key svref key old-array new-array length NIL))
(progn
(unless length
(setf length (min (the fixnum (car (array-dimensions old-array)))
(the fixnum (car (array-dimensions new-array))))))
(if post-indices
(expand-on-key #'aref key old-array new-array length post-indices)
(expand-on-key aref key old-array new-array length NIL)))))
new-array)
(defun walk-dimensions (dimensions function)
;; Given a list of dimensions (e.g. '(3 2 8)), this function walks
;; through every possible combination from 0 to 1- each of those
;; dimensions, calling function on each of them.
(let ((compiled-p (compiled-function-p function)))
(labels
((doit (dims apply-dims)
(if (cdr dims)
(let ((last-dim NIL)
(dims-left NIL))
(loop (when (null (cdr dims))
(setf last-dim (car dims))
(return))
(if dims-left
(nconc dims-left (list (car dims)))
(setf dims-left (list (car dims))))
(setf dims (cdr dims)))
(loop for i fixnum from 0
to (the fixnum (1- (the fixnum last-dim)))
do (doit dims-left (cons i apply-dims))))
(if compiled-p
(loop for i fixnum from 0
to (the fixnum (1- (the fixnum (car dims))))
do (funcall (the compiled-function function)
(cons i apply-dims)))
(loop for i fixnum from 0
to (the fixnum (1- (the fixnum (car dims))))
do (funcall function (cons i apply-dims)))))))
(doit dimensions NIL))))