Re: copying arrays
- From: Kent M Pitman <pitman@xxxxxxxxxxx>
- Date: 29 Apr 2007 13:07:06 -0400
Warning: The "rant" below might or might not be relevant to Dan's remarks
directly. So don't take this as necessarily responding to his particular
situation. I'm pretty sure my remarks below need to be said to SOMEONE,
and I'm somewhat opportunistically (and hence possibly slightly unfairly)
dumping on Dan's remarks here... I really just wanted to be pro-active,
a bit, rather than reactive, and to address a common behavior at a time
when we're dancing around a common set of misconceptions. So if you're
still game, read on...
Dan Bensen <randomgeek@xxxxxxxxxxxxxx> writes:
Alan Manuel K. Gloria wrote:
In my experience it's quite rare to have to have to *copy* a
sequence. If you're manipulating an array, why would you want to
retain the previous version?
In a game, you might want to pass the state of the game
(e.g. the board in a board game) to a computer player
so it can decide what it wants to do.
I've seen this argument made many times in my career and I really have
to say that I personally cringe at this use of "safe". While indeed
one must use care in setting up one's programs so that things
cooperate, it's no "more safe" to call a function that's supposed to
add 1 to a number only to find that it subtracts 1. A program that does
not understand its contract is unsafe. If a program does understand its
contract, it can use side-effects safely.
Yes, it's true, there are cases where you give a piece of structure to
a program that is supposed to do some computation, and it's true that
it can accidentally do a side-effect if the programmer is not aware that
they are receiving shared structure. But there's a strong question of
whether this is a bug in the use of operators or in the definition of
protocol.
The fact that this word "safe" is used in relation to destructive
operators that people simply learn badly and use badly suggests that
it is just code for talking about another attribute of people because
they are uncomfortable talking directly to the issue of programmer
competence. I'd rather teach people to be competent than pamper them
in this way. I've seen people who purport to be serious programmers
stare at programs and say out loud "what if we replace these
destructive operators with non-destructive ones, does that fix it?"
It reminds me of when I first got in-range of solving Rubik's cube. I
could get it to what seemed to me like a 1 in 4 (or maybe 1 in 3)
chance of accidentally working, because I couldn't spin some corners.
Rather than learn how to complete the thing right, I was so
exasperated that I learned to just randomize the cube and re-do it
(which took me only a minute and a half). After a handful (so to
speak) of iterations, it would naturally end up that I got to the end
without needing to spin the corners, and I'd win... But there was no
real substitute for actually learning the transforms needed, and I was
being ridiculous by just treating randomization as an actual design
choice, even though it could be shown... while it can probably be
shown theoretically to converge, it gives up control of when and how
convergence will happen to probabilities in a place where there's no
need to give up that control.
I feel the same about yielding up the control of protocol design to the
chance sense that someone might not make or read a protocol definition.
The safe way to do that would be to pass the player a copy, so the
player doesn't corrupt the game.
Safe is relative. What if safety is based on space as a criterion?
Running out of space in a lot of cases will swamp a program just as
quickly as a program error, and the idea of copying a large game board
an a possibly-exponential number of times seems destined to do badly
in terms of space (and even if not, the amount of time needed to copy
and reclaim all those copies). [This is the place where someone will
trot out some proof that this doesn't always lose, but let me just say
preemptively say that wouldn't refute my point. I'm not saying you
can't win that way. I'm saying you can't know you're going to win
unless you've studied the issue. Studying the issue requires a quite
carefully coordinated design and implementation. And if you're going
to do that level of design, why not just factor in the notion that side
effects will be competently included and implemented.]
Often the player will destructively modify the board, but undo all
its changes at the end.
Ownership is something everyone should understand, whether it's
something in the real world or something in the imaginary world.
People need to know what they can modify and what they can't. This is
as fundamental as "caller saves vs callee saves", and cannot be left
to chance. You're talking like people can independently choose their
favorites, and I'm not sure I see that's so.
Indeed, you can create a convention in which this statement is true,
but please do not presuppose that this convention is a natural truth
and that there is no alternative. I think, in fact, the default state
of Lisp is just the opposite. Lisp, as a natural set of operations,
assumes callee-saves, since it assumes that pointer-passing is the
efficient way. It is therefore incumbent on someone who writes a
function, any function, that plans a side effect to advertise the fact
of that side effect. And surely, then, it's incumbent upon the caller
to take note of that fact.
There are also issues of multiprocessing and synchronized access, but
again it is a myth to think that the answer to multiprocessing and
synchronized access is that no one should ever do a side effect just
in case someone replaces mapcar with parallel-mapcar and "breaks things".
Any replacement of any operator with another operator that does not
respect the contract of the program will break things, but somehow only
side-effects get this shabby treatment of saying that somehow the world
should be specially prepared in advance of a change of protocol so that
the protocol change can be injected without cost.
With a copy, you can also check the player for correctness by
comparing the final state of the player's copy with the original
board.
This statement isn't just a statement by itself but is offered in a context
where it has increased importance. It's in a situation where it's defending
not just making a copy, but making one often. I infer that it's on each
call that we're talking. And my point is that this is a reasoned choice,
based on domain knowledge, not an obvious truth. You could make a
(defun set-array-element-returning-array (value array &rest indices)
(let ((copy (copy-array array))) ;for some definition of copy-array
(setf (apply #'aref copy indices) value)
copy))
and you could then easily use this operation, but the creation of such an
operation would make it easier to accidentally make lots of needless copies,
when in fact even in the situation you're describing, you might want to do
three modifies in a row, and why would you do
(defun foo (a i j x) ;just a randomly chosen example
(set-array-element-returning-array x
(set-array-element-returning-array x a i)
j))
which makes a needless copy, when you could just as well do
(defun foo (a i j x)
(let ((copy (copy-array a)))
(setf (aref copy i) x)
(setf (aref copy j) x)
copy))
and get the same effect, leaving around half as much garbage? Lisp doesn't
provide an easy way to do that, in part, because the array datatype exists
specifically for data so large that it has to be direct accessed. (For lists
known to never grow bigger than two or three in length, the functions first
and second and third, even though they chain through list links, are probably
faster in many if not all implementations than an array access because they
don't have to do type and bounds checking, dimension decoding, etc.)
And we teach people to be thoughtful about when a copy would help and when not.
Certainly we copy things. But we don't think to copying as so important that
it should be done by default all the time; just the opposite, we think object
identity is central and we should think carefully about when to risk a
separation of identity.
In the case of a game, for example, comparing initial and final states requires
a separation of identity, so of course a copy is warranted. But there's a
subtext of your remarks that seems to imply you can get from there to
"copies are good, and it's non-copies that are a danger", and I don't think
any such sweeping claim (if it's intended by you, or would be intended by
others reading this discussion) is warranted.
One can always save a copy when one needs it. I take Alan's point not
to be why would one ever copy, but rather, why would one be surprised
that copying was something that was left to the user to decide.
And, incidentally, copying is not a canonically-defined concept. Copying is
something that can only be done with due regard to the semantics of the
components. A copy of a cons and a copy of a list are different, yet
a cons is a list, and Lisp is dynamically typed, so the intent of the one
is indistinguishable from the intent of the other. [See my article
http://www.nhplace.com/kent/PS/EQUAL.html
for details on this. It treats EQUAL, not COPY, but it notes and I continue
to believe that the philosophical issues are the same.]
[There's perhaps, too, a hidden assumption that arrays are homogenous,
and somehow easier to copy safely than other types. But that's just
not true. Lisp arrays are often homogenous, but there's no requirement.
So some elements might need deep copying and others not... indeed, if
one of the cells is a domain-managed reference count, a proper "copy"
of that data structure might not even copy all of the top level items
in it, since otherwise you'd be lying about how many domain-managed
objects were pointing to the copy. You might wish Lisp had a matrix
datatype like mathematics uses, but then you're asking for a new
representational type, or you'd never be able to detect it. And that
just reaffirms my point, which is that copies in Lisp must be made based
on what the programmer knows about his application, not on the basis of
whim and in contradiction of domain-specific, carefully worked out and
agreed-upon protocol specs.]
I'll stop there for now. Thanks for listening.
.
- Follow-Ups:
- Re: copying arrays
- From: Dan Bensen
- Re: copying arrays
- From: Richard M Kreuter
- Re: copying arrays
- References:
- copying arrays
- From: Q
- Re: copying arrays
- From: Alan Manuel K. Gloria
- Re: copying arrays
- From: Dan Bensen
- copying arrays
- Prev by Date: Re: copying arrays
- Next by Date: Re: copying arrays
- Previous by thread: Re: copying arrays
- Next by thread: Re: copying arrays
- Index(es):
Relevant Pages
|
