chap12.txt

  
  12 Objects and Elements
  
  An  object  is anything in GAP that can be assigned to a variable, so nearly
  everything in GAP is an object.
  
  Different  objects  can be regarded as equal with respect to the equivalence
  relation =, in this case we say that the objects describe the same element.
  
  
  12.1 Objects
  
  Nearly all things one deals with in GAP are objects. For example, an integer
  is an object, as is a list of integers, a matrix, a permutation, a function,
  a  list  of  functions, a record, a group, a coset or a conjugacy class in a
  group.
  
  Examples  of things that are not objects are comments which are only lexical
  constructs,   while   loops  which  are  only  syntactical  constructs,  and
  expressions,  such  as  1  + 1; but note that the value of an expression, in
  this case the integer 2, is an object.
  
  Objects can be assigned to variables, and everything that can be assigned to
  a  variable  is  an object. Analogously, objects can be used as arguments of
  functions, and can be returned by functions.
  
  12.1-1 IsObject
  
  IsObject( obj )  Category
  
  IsObject returns true if the object obj is an object. Obviously it can never
  return false.
  
  It  can  be  used  as  a  filter  in  InstallMethod (78.2-1) when one of the
  arguments can be anything.
  
  
  12.2 Elements as equivalence classes
  
  The equality operation = defines an equivalence relation on all GAP objects.
  The equivalence classes are called elements.
  
  There  are  basically  three  reasons  to regard different objects as equal.
  Firstly the same information may be stored in different places. Secondly the
  same  information may be stored in different ways; for example, a polynomial
  can  be  stored  sparsely  or  densely. Thirdly different information may be
  equal modulo a mathematical equivalence relation. For example, in a finitely
  presented  group  with  the relation a^2 = 1 the different objects a and a^3
  describe the same element.
  
  As  an  example of all three reasons, consider the possibility of storing an
  integer  in  several  places of the memory, of representing it as a fraction
  with   denominator  1,  or  of  representing  it  as  a  fraction  with  any
  denominator, and numerator a suitable multiple of the denominator.
  
  
  12.3 Sets
  
  In GAP there is no category whose definition corresponds to the mathematical
  property  of  being  a  set, however in the manual we will often refer to an
  object  as  a  set  in  order to convey the fact that mathematically, we are
  thinking  of  it  as a set. In particular, two sets A and B are equal if and
  only if, x ∈ A <=> x ∈ B.
  
  There  are  two  types of object in GAP which exhibit this kind of behaviour
  with  respect to equality, namely domains (see Section 12.4) and lists whose
  elements are strictly sorted see IsSSortedList (21.17-4). In general, set in
  this manual will mean an object of one of these types.
  
  More  precisely: two domains can be compared with {=}, the answer being true
  if  and only if the sets of elements are equal (regardless of any additional
  structure) and; a domain and a list can be compared with =, the answer being
  true  if  and  only  if  the  list  is  equal to the strictly sorted list of
  elements of the domain.
  
  A discussion about sorted lists and sets can be found in Section 21.19.
  
  
  12.4 Domains
  
  An  especially  important class of objects in GAP are those whose underlying
  mathematical abstraction is that of a structured set, for example a group, a
  conjugacy  class,  or  a  vector space. Such objects are called domains. The
  equality  relation  between  domains is always equality as sets, so that two
  domains are equal if and only if they contain the same elements.
  
  Domains  play  a  central  role in GAP. In a sense, the only reason that GAP
  supports  objects  such  as  integers  and  permutations is the wish to form
  domains of them and compute the properties of those domains.
  
  Domains are described in Chapter 31.
  
  
  12.5 Identical Objects
  
  Two  objects  that  are equal as objects (that is they actually refer to the
  same  area  of  computer memory) and not only w.r.t. the equality relation =
  are  called  identical.  Identical  objects  do  of course describe the same
  element.
  
  12.5-1 IsIdenticalObj
  
  IsIdenticalObj( obj1, obj2 )  function
  
  IsIdenticalObj  tests  whether the objects obj1 and obj2 are identical (that
  is  they  are  either equal immediate objects or are both stored at the same
  location in memory.
  
  If two copies of a simple constant object (see section 12.6) are created, it
  is  not  defined whether GAP will actually store two equal but non-identical
  objects,  or  just  a  single  object.  For  mutable objects, however, it is
  important  to  know  whether  two values refer to identical or non-identical
  objects,  and  the  documentation  of  operations that return mutable values
  should  make  clear whether the values returned are new, or may be identical
  to values stored elsewhere.
  
    Example  
    gap> IsIdenticalObj( 10^6, 10^6);
    true
    gap> IsIdenticalObj( 10^30, 10^30);
    false
    gap> IsIdenticalObj( true, true);
    true
  
  
  Generally, one may compute with objects but think of the results in terms of
  the  underlying  elements  because  one  is  not  interested in locations in
  memory, data formats or information beyond underlying equivalence relations.
  But  there  are  cases  where  it  is important to distinguish the relations
  identity and equality. This is best illustrated with an example. (The reader
  who  is  not  familiar  with  lists in GAP, in particular element access and
  assignment, is referred to Chapter 21.)
  
    Example  
    gap> l1:= [ 1, 2, 3 ];; l2:= [ 1, 2, 3 ];;
    gap> l1 = l2;
    true
    gap> IsIdenticalObj( l1, l2 );
    false
    gap> l1[3]:= 4;; l1; l2;
    [ 1, 2, 4 ]
    [ 1, 2, 3 ]
    gap> l1 = l2;
    false
  
  
  The  two  lists  l1  and l2 are equal but not identical. Thus a change in l1
  does not affect l2.
  
    Example  
    gap> l1:= [ 1, 2, 3 ];; l2:= l1;;
    gap> l1 = l2;
    true
    gap> IsIdenticalObj( l1, l2 );
    true
    gap> l1[3]:= 4;; l1; l2;
    [ 1, 2, 4 ]
    [ 1, 2, 4 ]
    gap> l1 = l2;
    true
  
  
  Here,  l1  and l2 are identical objects, so changing l1 means a change to l2
  as well.
  
  12.5-2 IsNotIdenticalObj
  
  IsNotIdenticalObj( obj1, obj2 )  function
  
  tests whether the objects obj1 and obj2 are not identical.
  
  
  12.6 Mutability and Copyability
  
  An  object  in  GAP  is  said  to be immutable if its mathematical value (as
  defined  by =) does not change under any operation. More explicitly, suppose
  a is immutable and O is some operation on a, then if a = b evaluates to true
  before  executing  O(a),  a = b also evaluates to true afterwards. (Examples
  for  operations  O  that  change mutable objects are Add (21.4-2) and Unbind
  (21.5-2)  which  are  used  to  change  list  objects,  see  Chapter 21.) An
  immutable  object  may  change,  for example to store new information, or to
  adopt  a  more  efficient  representation,  but  this  does  not  affect its
  behaviour under =.
  
  There  are  two  points here to note. Firstly, operation above refers to the
  functions  and  methods which can legitimately be applied to the object, and
  not  the  !.  operation whereby virtually any aspect of any GAP level object
  may  be  changed.  The  second  point  which follows from this, is that when
  implementing  new types of objects, it is the programmer's responsibility to
  ensure  that  the  functions  and  methods they write never change immutable
  objects mathematically.
  
  In  fact,  most  objects  with  which  one  deals  in GAP are immutable. For
  instance, the permutation (1,2) will never become a different permutation or
  a  non-permutation (although a variable which previously had (1,2) stored in
  it may subsequently have some other value).
  
  For many purposes, however, mutable objects are useful. These objects may be
  changed  to  represent different mathematical objects during their life. For
  example, mutable lists can be changed by assigning values to positions or by
  unbinding  values  at certain positions. Similarly, one can assign values to
  components of a mutable record, or unbind them.
  
  12.6-1 IsCopyable
  
  IsCopyable( obj )  Category
  
  If  a mutable form of an object obj can be made in GAP, the object is called
  copyable.  Examples  of  copyable objects are of course lists and records. A
  new  mutable  version  of the object can always be obtained by the operation
  ShallowCopy (12.7-1).
  
  Objects for which only an immutable form exists in GAP are called constants.
  Examples of constants are integers, permutations, and domains. Called with a
  constant  as  argument,  Immutable  (12.6-3) and ShallowCopy (12.7-1) return
  this argument.
  
  12.6-2 IsMutable
  
  IsMutable( obj )  Category
  
  tests whether obj is mutable.
  
  If  an object is mutable then it is also copyable (see IsCopyable (12.6-1)),
  and  a  ShallowCopy  (12.7-1)  method  should  be supplied for it. Note that
  IsMutable  must  not be implied by another filter, since otherwise Immutable
  (12.6-3)  would  be  able  to  create  paradoxical objects in the sense that
  IsMutable  for such an object is false but the filter that implies IsMutable
  is true.
  
  In many situations, however, one wants to ensure that objects are immutable.
  For  example,  take the identity of a matrix group. Since this matrix may be
  referred  to  as  the  identity  of the group in several places, it would be
  fatal  to  modify  its  entries,  or  add  or  unbind rows. We can obtain an
  immutable copy of an object with Immutable (12.6-3).
  
  12.6-3 Immutable
  
  Immutable( obj )  function
  
  returns an immutable structural copy (see StructuralCopy (12.7-2)) of obj in
  which  the  subobjects are immutable copies of the subobjects of obj. If obj
  is immutable then Immutable returns obj itself.
  
  GAP will complain with an error if one tries to change an immutable object.
  
  12.6-4 MakeImmutable
  
  MakeImmutable( obj )  function
  
  One  can  turn  the  (mutable or immutable) object obj into an immutable one
  with  MakeImmutable;  note  that  this  also  makes  all  subobjects  of obj
  immutable,  so  one  should  call  MakeImmutable only if obj and its mutable
  subobjects  are  newly  created.  If  one  is not sure about this, Immutable
  (12.6-3) should be used.
  
  Note that it is not possible to turn an immutable object into a mutable one;
  only mutable copies can be made (see 12.7).
  
  Using  Immutable  (12.6-3),  it  is  possible to store an immutable identity
  matrix  or an immutable list of generators, and to pass around references to
  this immutable object safely. Only when a mutable copy is really needed does
  the  actual  object have to be duplicated. Compared to the situation without
  immutable  objects,  much  unnecessary  copying is avoided this way. Another
  advantage  of  immutability  is that lists of immutable objects may remember
  whether  they  are  sorted  (see 21.19),  which is not possible for lists of
  mutable objects.
  
  Since  the  operation Immutable (12.6-3) must work for any object in GAP, it
  follows  that an immutable form of every object must be possible, even if it
  is  not sensible, and user-defined objects must allow for the possibility of
  becoming immutable without notice.
  
  
  12.6-5 Mutability of Iterators
  
  An interesting example of mutable (and thus copyable) objects is provided by
  iterators, see 30.8. (Of course an immutable form of an iterator is not very
  useful,  but  clearly  Immutable  (12.6-3) will yield such an object.) Every
  call  of  NextIterator  (30.8-5)  changes  a  mutable  iterator  until it is
  exhausted,  and  this  is  the  only  way to change an iterator. ShallowCopy
  (12.7-1)  for an iterator iter is defined so as to return a mutable iterator
  that  has  no  mutable data in common with iter, and that behaves equally to
  iter  w.r.t. IsDoneIterator  (30.8-4)  and (if iter is mutable) NextIterator
  (30.8-5).  Note that this meaning of the shallow copy of an iterator that is
  returned by ShallowCopy (12.7-1) is not as obvious as for lists and records,
  and must be explicitly defined.
  
  
  12.6-6 Mutability of Results of Arithmetic Operations
  
  Many   operations  return  immutable  results,  among  those  in  particular
  attributes  (see 13.5).  Examples  of  attributes  are  Size  (30.4-6), Zero
  (31.10-3),  AdditiveInverse (31.10-9), One (31.10-2), and Inverse (31.10-8).
  Arithmetic  operations,  such  as the binary infix operations +, -, *, /, ^,
  mod,  the  unary  -,  and operations such as Comm (31.12-3) and LeftQuotient
  (31.12-2), return mutable results, except if all arguments are immutable. So
  the  product of two matrices or of a vector and a matrix is immutable if and
  only  if  the  two  matrices or both the vector and the matrix are immutable
  (see  also 21.11).  There  is one exception to this rule, which arises where
  the  result  is  less deeply nested than at least one of the argument, where
  mutable arguments may sometimes lead to an immutable result. For instance, a
  mutable  matrix with immutable rows, multiplied by an immutable vector gives
  an immutable vector result. The exact rules are given in 21.11.
  
  It  should  be  noted  that  0 * obj is equivalent to ZeroSM( obj ), -obj is
  equivalent  to AdditiveInverseSM( obj ), obj^0 is equivalent to OneSM( obj),
  and  obj^-1  is  equivalent  to  InverseSM(  obj  ).  The SM stands for same
  mutability,  and  indicates  that  the  result is mutable if and only if the
  argument is mutable.
  
  The   operations   ZeroOp   (31.10-3),  AdditiveInverseOp  (31.10-9),  OneOp
  (31.10-2), and InverseOp (31.10-8) return mutable results whenever a mutable
  version  of  the  result  exists, contrary to the attributes Zero (31.10-3),
  AdditiveInverse (31.10-9), One (31.10-2), and Inverse (31.10-8).
  
  If  one  introduces new arithmetic objects then one need not install methods
  for  the  attributes One (31.10-2), Zero (31.10-3), etc. The methods for the
  associated  operations  OneOp (31.10-2) and ZeroOp (31.10-3) will be called,
  and then the results made immutable.
  
  All methods installed for the arithmetic operations must obey the rule about
  the  mutability  of  the  result.  This  means that one may try to avoid the
  perhaps  expensive  creation of a new object if both operands are immutable,
  and of course no problems of this kind arise at all in the (usual) case that
  the  objects  in  question  do  not  admit  a mutable form, i.e., that these
  objects are not copyable.
  
  In  a  few,  relatively  low-level  algorithms, one wishes to treat a matrix
  partly as a data structure, and manipulate and change its entries. For this,
  the  matrix  needs  to  be  mutable,  and the rule that attribute values are
  immutable  is  an  obstacle.  For  these  situations, a number of additional
  operations   are   provided,   for   example  TransposedMatMutable  (24.5-6)
  constructs  a  mutable  matrix  (contrary  to  the  attribute  TransposedMat
  (24.5-6)),  while  TriangulizeMat  (24.7-3)  modifies  a  mutable matrix (in
  place) into upper triangular form.
  
  Note  that being immutable does not forbid an object to store knowledge. For
  example,  if  it is found out that an immutable list is strictly sorted then
  the list may store this information. More precisely, an immutable object may
  change  in  any  way,  provided  that  it  continues  to  represent the same
  mathematical object.
  
  
  12.7 Duplication of Objects
  
  12.7-1 ShallowCopy
  
  ShallowCopy( obj )  operation
  
  ShallowCopy  returns  a new mutable object equal to its argument, if this is
  possible.  The  subobjects  of  ShallowCopy(  obj  )  are  identical  to the
  subobjects of obj.
  
  If  GAP  does  not  support  a  mutable  form  of  the  immutable object obj
  (see 12.6) then ShallowCopy returns obj itself.
  
  Since ShallowCopy is an operation, the concrete meaning of subobject depends
  on  the  type of obj. But for any copyable object obj, the definition should
  reflect the idea of first level copying.
  
  The  definition of ShallowCopy for lists (in particular for matrices) can be
  found in 21.7.
  
  12.7-2 StructuralCopy
  
  StructuralCopy( obj )  function
  
  In  a  few  situations, one wants to make a structural copy scp of an object
  obj.  This  is  defined  as  follows.  scp  and  obj are identical if obj is
  immutable.  Otherwise, scp is a mutable copy of obj such that each subobject
  of  scp  is  a  structural  copy  of  the  corresponding  subobject  of obj.
  Furthermore,   if  two  subobjects  of  obj  are  identical  then  also  the
  corresponding subobjects of scp are identical.
  
    Example  
    gap> obj:= [ [ 0, 1 ] ];;
    gap> obj[2]:= obj[1];;
    gap> obj[3]:= Immutable( obj[1] );;
    gap> scp:= StructuralCopy( obj );;
    gap> scp = obj; IsIdenticalObj( scp, obj );
    true
    false
    gap> IsIdenticalObj( scp[1], obj[1] );
    false
    gap> IsIdenticalObj( scp[3], obj[3] );
    true
    gap> IsIdenticalObj( scp[1], scp[2] );
    true
  
  
  That  both  ShallowCopy  (12.7-1) and StructuralCopy return the argument obj
  itself if it is not copyable is consistent with this definition, since there
  is no way to change obj by modifying the result of any of the two functions,
  because in fact there is no way to change this result at all.
  
  
  12.8 Other Operations Applicable to any Object
  
  There are a number of general operations which can be applied, in principle,
  to  any  object  in  GAP. Some of these are documented elsewhere –see String
  (27.7-6),  PrintObj  (6.3-5) and Display (6.3-6). Others are mainly somewhat
  technical.
  
  12.8-1 SetName
  
  SetName( obj, name )  operation
  
  for a suitable object obj sets that object to have name name (a string).
  
  12.8-2 Name
  
  Name( obj )  attribute
  
  returns the name, a string, previously assigned to obj via a call to SetName
  (12.8-1). The name of an object is used only for viewing the object via this
  name.
  
  There  are no methods installed for computing names of objects, but the name
  may be set for suitable objects, using SetName (12.8-1).
  
    Example  
    gap> R := PolynomialRing(Integers,2);
    Integers[x_1,x_2]
    gap> SetName(R,"Z[x,y]");
    gap> R;
    Z[x,y]
    gap> Name(R);
    "Z[x,y]"
  
  
  12.8-3 InfoText
  
  InfoText( obj )  attribute
  
  is  a  mutable  string  with  information  about the object obj. There is no
  default method to create an info text.
  
  12.8-4 IsInternallyConsistent
  
  IsInternallyConsistent( obj )  operation
  
  For  debugging  purposes,  it  may  be useful to check the consistency of an
  object obj that is composed from other (composed) objects.
  
  There  is  a  default method of IsInternallyConsistent, with rank zero, that
  returns  true.  So it is possible (and recommended) to check the consistency
  of subobjects of obj recursively by IsInternallyConsistent.
  
  (Note that IsInternallyConsistent is not an attribute.)
  
  12.8-5 MemoryUsage
  
  MemoryUsage( obj )  operation
  
  returns  the  amount  of  memory  in  bytes  used  by the object obj and its
  subobjects.  Note  that in general, objects can reference each other in very
  difficult  ways  such  that  determining  the  memory  usage  is a recursive
  procedure.  In  particular,  computing  the  memory  usage  of a complicated
  structure  itself  uses  some  additional memory, which is however no longer
  used  after completion of this operation. This procedure descends into lists
  and records, positional and component objects, however it does not take into
  account the type and family objects! For functions, it only takes the memory
  usage  of  the  function  body,  not  of  the local context the function was
  created in, although the function keeps a reference to that as well!