> < ^ Date: Fri, 10 Dec 1999 11:26:23 +0000
> < ^ From: Steve Linton <sal@dcs.st-and.ac.uk >
^ Subject: Mutability

Dear GAP Forum,

Sergei Haller asked a number of questions about mutable and immutable objects
and copying.

The intended meaning of immutability in GAP4 is a mathematical one. Any GAP
object can be thought of as a representation of an "abstract" mathematical
object of some kind. We call these "mathematical objects" Elements and they
can also be viewed as equivalence classes of GAP objects under the relations
\=. An immutable object should never change in such a way that it represents a
different element.

This is enforced in different ways for built-in objects (like records, or
lists) and for external objects (made using Objectify).

For built-in objects which are flagged as Immutable, the kernel will prevent
you from changing them. Thus

gap> l := [1,2,4];
[ 1, 2, 4 ]
gap> MakeImmutable(l);
gap> l[3] := 5;
Lists Assignment: <list> must be a mutable list
not in any function
Entering break read-eval-print loop, you can 'quit;' to quit to outer loop,
or you can return and ignore the assignment to continue

For external objects, the situation is different. An external object which
claims to be immutable (ie its type does not contain the filter IsMutable)
should not admit any Methods which change the Element it represents. The
kernel does not prevent the use of !. and ![ to change the underlying data
structure. This is used for instance by the code that stores Attribute values
for reuse. In general, these ! operations should only be used in Methods
which depend on the representation of the object. Furthermore, we would NOT
recommend users to install methods which depend on the representations of
objects created by the library or by share packages, as there is certainly no
guarantee of the representations being the same in future versions of GAP.

Here we see an immutable object (the group S4), in which we "improperly"
install a new component.

gap> g := SymmetricGroup(IsPermGroup,4);
Sym( [ 1 .. 4 ] )
gap> IsMutable(g);
gap> NamesOfComponents(g);
[ "GeneratorsOfMagmaWithInverses", "Size", "MovedPoints", "NrMovedPoints" ]
gap> g!.silly := "rubbish";
gap> NamesOfComponents(g);
[ "GeneratorsOfMagmaWithInverses", "Size", "MovedPoints", "NrMovedPoints",
"silly" ]
gap> g!.silly;

On the other hand, if we form an immutable externally represented list, we
find that there is no Method for changing it using list assignment

gap> e := Enumerator(g);
<enumerator of perm group>
gap> IsMutable(e);
gap> IsList(e);
gap> e[3];
gap> e[3] := false;
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error no 1st choice method found for `ASS_LIST' on 3 arguments at

Finally we come to the question of copying. Here ShallowCopy and
StructuralCopy behave quite differently, and another filter, IsCopyable,
enters the game.

Objects can be divided for this purpose into three: mutable objects, immutable
but copyable objects, and non-copyable objects (called constants).

A mutable or copyable object should have a Method for the Operation
ShallowCopy, which should make a new mutable object, sharing its top-level
subobjects with the original. The exact definition of top-level subobject may
be defined by the implementor for new kinds of object.

ShallowCopy applied to a constant simply returns the constant.

StructuralCopy is expected to be much less used than ShallowCopy. Applied to a
mutable object, it returns a new mutable object which shares no mutable
sub-objects with the input. Applied to an immutable object, it just returns
the object. It is not an Operation (indeed, it's a rather special kernel

gap> e1 := StructuralCopy(e);
<enumerator of perm group>
gap> IsMutable(e1);
gap> e2 := ShallowCopy(e);
[ (), (1,2)(3,4), (1,4)(2,3), (1,3)(2,4), (2,3,4), (1,2,4), (1,4,3), (1,3,2), 
  (2,4,3), (1,2,3), (1,4,2), (1,3,4), (3,4), (1,2), (1,4,2,3), (1,3,2,4), 
  (2,3), (1,2,4,3), (1,4), (1,3,4,2), (2,4), (1,2,3,4), (1,4,3,2), (1,3) ]

Immutable makes a new immutable object which shares no mutable subobjects with
the input.

MakeImmutable changes an object and its mutable subobjects in place to be
immutable. It should only be used on "new" objects that you have just created.

Both Immutable and MakeImmutable work on external objects by just reseting the
IsMutable filter. This should make ineligible any methods that might change
the objects. As a consequence, you must allow for the possibility of immutable
versions of any objects you create.

So, if you are implementing your own external objects. The rules amount to the

1. You decide if your objects should be mutable or copyable or constants, by
fixing whether their type includes IsMutable or IsCopyable

2. You install Methods for your objects respecting that decision:

* for constants -- no methods that change the underlying elements
* for copyables -- a method for ShallowCopy
* for mutables -- you may have methods that change the underlying elements
these should explicitly require IsMutable


> < [top]