setitem and deepcopy
Andreas Micheler
I have a question about setitem in UCBLogo and its derivates.
Normally you would give setitem three arguments:
an index, a thing where to set it into, and a newitem.
The point is the second input:
if one gives setitem a thing, which can be any Logo node,
then the Logo must deep copy that thing first,
when being in the eval arg loop,
to not surprise the user when the thing,
which is mostly stored in some variable,
is changing maybe some other variable(s),
which point to the same node.
But if one has two functions:
a special _setitem, which takes a thing as second argument,
and the new normal setitem, which takes a variable name as second input,
then in most cases you can use setitem:
setitem <index> "<varname> <newitem>
because the thing is most often something like :var .
Only in some special cases you would need:
_setitem <index> <thing> <newitem>
Example:
make "a {1 2 3 4}
setitem 2 "a 20
print :a
{1 20 3 4}
The advantage of this notation is,
if all nodes hava a reference count,
then only when it is referenced somewhere else
it must be deep copied in the new setitem primitive,
and not always on any function call.
It is a copy on write schema.
The trouble is, how to name the new setitem function in aUCBLogo.
I would like it best to just name it setitem,
but this may break some existing programs,
and would raise more portability issues for aUCBLogo programs.
(I have no problem with my own programs here,
they can all be adapted in about half an hour.)
Or is there maybe a different solution to the original problem:
How to avoid deep copying in the arg loop?
Can a copy on write strategy be implemented somehow otherwise?
Andreas
Brian Harvey
Andreas Micheler <Andreas....@gmx.de> writes:
>The advantage of this notation is,
>if all nodes hava a reference count,
>then only when it is referenced somewhere else
>it must be deep copied in the new setitem primitive,
>and not always on any function call.
Sorry for the delayed response -- I have been ridiculously busy and not
reading netnews for a couple of weeks!
If you have a reference count, I don't see why you need the new notation;
setitem 2 :a 20
could notice that at most one thing points to its second argument, and
therefore not bother preserving it. Of course you have the usual problem
about circular structures. And the SETITEM procedure itself might
temporarily increase the reference count, depending exactly how you do the
counting. But those problems can be solved.
UCBLogo doesn't actually have this issue, because SETITEM works only on
arrays, and arrays don't share memory.
Does your SETITEM allow changing the characters within a word?
Andreas Micheler
> If you have a reference count, I don't see why you need the new notation;
> setitem 2 :a 20
> could notice that at most one thing points to its second argument, and
> therefore not bother preserving it.
Unfortunately, although I have a reference count I probably need it,
because whenever refCount > 0, setitem has to copy the whole array,
and (that's the point => ) it has to set the value of the variable a to
the new copied array. If I use :a (call by value),
the setitem primitive does not know the name of :a,
it just gets its value from eval.
> Of course you have the usual problem
> about circular structures.
Not any more, because I have the GC,
and a circcounter mechanism (in almost every place :-( ;-)).
Momentarily I use the refCount only for setitem
and the unary and binary math functions.
In setitem, to correct a very old bug/feature in aUCBLogo:
when one writes to the items of an array,
another array variable that pointed to the first array
would also change.
The same problem arises with lists, words and tables,
whereon setitem is also allowed.
The use of the refCount in the math functions is to eliminate
unnecessary generation of new nodes:
when computing for example (cos (sin :x)),
then the cos function can use the result node of the sin as result node.
Another example might be (x+y+z),
where the first result (x+y) can be used as result node for (x+y)+z.
Somehow it could be possible to eliminate even more new nodes
by use of data flow optimization, whenever a source of a computation
is also the destination of the expression.
> And the SETITEM procedure itself might
> temporarily increase the reference count, depending exactly how you do the
> counting. But those problems can be solved.
I do not use smart pointers
(there's a compilation option for it, only for debugging),
if you meant that. It was much too slow.
There are only a few locations,
where I have the reference counting currently in.
The only trouble is not to forget any incrementation (refCount++).
I don't care much about (refCount--),
because if it is missing somewhere, nothing really bad happens,
it is just not as efficient as it could be by saving even more nodes.
> UCBLogo doesn't actually have this issue, because SETITEM works only on
> arrays, and arrays don't share memory.
Hmm, but don't you also use deep_copy in UCBLogo?
UCBLogo6, eval.c(426f):
"case ARRAY: /* array must be copied */
val = deep_copy(exp);
goto fetch_cont;"
Probably I have not understood something correctly. ;-)
Greetings,
Andreas
Brian Harvey
>and (that's the point => ) it has to set the value of the variable a to
>the new copied array. If I use :a (call by value),
>the setitem primitive does not know the name of :a,
>it just gets its value from eval.
Ah, I see.
>In setitem, to correct a very old bug/feature in aUCBLogo:
>when one writes to the items of an array,
>another array variable that pointed to the first array
>would also change.
Isn't that desirable? If two variables point to the same array, it's
because they're /meant/ to be EQ. The problem with lists is that it's too
easy for one list to be EQ to /a subset of/ another, with confusing results.
>Hmm, but don't you also use deep_copy in UCBLogo?
>
>UCBLogo6, eval.c(426f):
>"case ARRAY: /* array must be copied */
> val = deep_copy(exp);
> goto fetch_cont;"
Yes. But this isn't a case of two variables deliberately pointing to the
same array. It's a case of a variable pointing to /a literal constant/ array.
Nothing should mutate a constant; it's very counterintuitive.
Actually, if I could easily distinguish a /toplevel/ literal constant array,
I wouldn't bother deep-copying it; the problem arises when the literal
constant array is inside a procedure that might get called again.