<html><head><title>[ref] 12 Objects and Elements</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP011.htm">Previous</a>] [<a href ="CHAP013.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>12 Objects and Elements</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP012.htm#SECT001">Objects</a> <li> <A HREF="CHAP012.htm#SECT002">Elements as equivalence classes</a> <li> <A HREF="CHAP012.htm#SECT003">Sets</a> <li> <A HREF="CHAP012.htm#SECT004">Domains</a> <li> <A HREF="CHAP012.htm#SECT005">Identical Objects</a> <li> <A HREF="CHAP012.htm#SECT006">Mutability and Copyability</a> <li> <A HREF="CHAP012.htm#SECT007">Duplication of Objects</a> <li> <A HREF="CHAP012.htm#SECT008">Other Operations Applicable to any Object</a> </ol><p> <p> An <strong>object</strong> is anything in <font face="Gill Sans,Helvetica,Arial">GAP</font> that can be assigned to a variable, so nearly everything in <font face="Gill Sans,Helvetica,Arial">GAP</font> is an object. <p> Different objects can be regarded as equal with respect to the equivalence relation <code>`='</code>, in this case we say that the objects describe the same <strong>element</strong>. <p> <p> <h2><a name="SECT001">12.1 Objects</a></h2> <p><p> Nearly all things one deals with in <font face="Gill Sans,Helvetica,Arial">GAP</font> are <strong>objects</strong>. 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. <p> Examples of things that are not objects are comments which are only lexical constructs, <code>while</code> loops which are only syntactical constructs, and expressions, such as <code>1 + 1</code>; but note that the value of an expression, in this case the integer <code>2</code>, is an object. <p> 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. <p> <a name = "SSEC001.1"></a> <li><code>IsObject( </code><var>obj</var><code> ) C</code> <p> <code>IsObject</code> returns <code>true</code> if the object <var>obj</var> is an object. Obviously it can never return <code>false</code>. <p> It can be used as a filter in <code>InstallMethod</code> (see <a href="../prg/CHAP002.htm#SECT002">Method Installation</a> in ``Programming in GAP'') when one of the arguments can be anything. <p> <p> <h2><a name="SECT002">12.2 Elements as equivalence classes</a></h2> <p><p> <a name = "I0"></a> The equality operation ``<code>=</code>'' defines an equivalence relation on all <font face="Gill Sans,Helvetica,Arial">GAP</font> objects. The equivalence classes are called <strong>elements</strong>. <p> 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 <i>a</i><sup>2</sup> = 1 the different objects <i>a</i> and <i>a</i><sup>3</sup> describe the same element. <p> 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. <p> <p> <h2><a name="SECT003">12.3 Sets</a></h2> <p><p> In <font face="Gill Sans,Helvetica,Arial">GAP</font> 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 <strong>set</strong> in order to convey the fact that mathematically, we are thinking of it as a set. In particular, two sets <i>A</i> and <i>B</i> are equal if and only if, <i>x</i> ∈ <i>A</i> ⇔ <i>x</i> ∈ <i>B</i>. <p> There are two types of object in <font face="Gill Sans,Helvetica,Arial">GAP</font> which exhibit this kind of behaviour with respect to equality, namely domains (see Section <a href="CHAP012.htm#SECT004">Domains</a>) and lists whose elements are strictly sorted see <code>IsSSortedList</code> (see <a href="CHAP021.htm#SSEC017.4">IsSSortedList</a>). In general, <strong>set</strong> in this manual will mean an object of one of these types. <p> More precisely: two domains can be compared with ``<code>=</code>'', the answer being <code>true</code> 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 ``<code>=</code>'', the answer being <code>true</code> if and only if the list is equal to the strictly sorted list of elements of the domain. <p> A discussion about sorted lists and sets can be found in the Reference Manual section ``Sorted Lists and Sets'' <a href="CHAP021.htm#SECT019">Sorted Lists and Sets</a>. <p> <p> <h2><a name="SECT004">12.4 Domains</a></h2> <p><p> An especially important class of objects in <font face="Gill Sans,Helvetica,Arial">GAP</font> 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 <strong>domains</strong>. The equality relation between domains is always equality <strong>as sets</strong>, so that two domains are equal if and only if they contain the same elements. <p> Domains play a central role in <font face="Gill Sans,Helvetica,Arial">GAP</font>. In a sense, the only reason that <font face="Gill Sans,Helvetica,Arial">GAP</font> supports objects such as integers and permutations is the wish to form domains of them and compute the properties of those domains. <p> Domains are described in Chapter <a href="CHAP030.htm">Domains and their Elements</a>. <p> <p> <h2><a name="SECT005">12.5 Identical Objects</a></h2> <p><p> Two objects that are equal <strong>as objects</strong> (that is they actually refer to the same area of computer memory) and not only w.r.t. the equality relation <code>`='</code> are called <strong>identical</strong>. Identical objects do of course describe the same element. <p> <a name = "SSEC005.1"></a> <li><code>IsIdenticalObj( </code><var>obj1</var><code>, </code><var>obj2</var><code> ) F</code> <p> <code>IsIdenticalObj( </code><var>obj1</var><code>, </code><var>obj2</var><code> )</code> tests whether the objects <var>obj1</var> and <var>obj2</var> are identical (that is they are either equal immediate objects or are both stored at the same location in memory. <p> If two copies of a simple constant object (see section <a href="CHAP012.htm#SECT006">Mutability and Copyability</a>) are created, it is not defined whether <font face="Gill Sans,Helvetica,Arial">GAP</font> 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 value 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. <p> <pre> gap> IsIdenticalObj( 10^6, 10^6); true gap> IsIdenticalObj( 10^12, 10^12); false gap> IsIdenticalObj( true, true); true </pre> <p> 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 <font face="Gill Sans,Helvetica,Arial">GAP</font>, in particular element access and assignment, is referred to Chapter <a href="CHAP021.htm">Lists</a>.) <pre> 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 </pre> The two lists <code>l1</code> and <code>l2</code> are equal but not identical. Thus a change in <code>l1</code> does not affect <code>l2</code>. <pre> 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 </pre> Here, <code>l1</code> and <code>l2</code> are identical objects, so changing <code>l1</code> means a change to <code>l2</code> as well. <p> The library also provides: <p> <a name = "SSEC005.2"></a> <li><code>IsNotIdenticalObj( </code><var>obj1</var><code>, </code><var>obj2</var><code> ) F</code> <p> tests whether the objects <var>obj1</var> and <var>objs2</var> are not identical. <p> <p> <h2><a name="SECT006">12.6 Mutability and Copyability</a></h2> <p><p> An object in <font face="Gill Sans,Helvetica,Arial">GAP</font> is said to be <strong>immutable</strong> if its mathematical value (as defined by =) does not change under any operation. More explicitly, suppose <i>a</i> is immutable and <i>O</i> is some operation on <i>a</i>, then if <i>a</i> = <i>b</i> evaluates to <code>true</code> before executing <i>O</i>(<i>a</i>), <i>a</i> = <i>b</i> also evaluates to <code>true</code> afterwards. (Examples for operations <i>O</i> that change mutable objects are <code>Add</code> and <code>Unbind</code> which are used to change list objects, see Chapter <a href="CHAP021.htm">Lists</a>.) An immutable object <strong>may</strong> change, for example to store new information, or to adopt a more efficient representation, but this does not affect its behaviour under =. <p> 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 <code>!.</code> operation whereby virtually any aspect of any <font face="Gill Sans,Helvetica,Arial">GAP</font> 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. <p> In fact, most objects with which one deals in <font face="Gill Sans,Helvetica,Arial">GAP</font> are immutable. For instance, the permutation <code>(1,2)</code> will never become a different permutation or a non-permutation (although a variable which previously had <code>(1,2)</code> stored in it may subsequently have some other value). <p> For many purposes, however, <strong>mutable</strong> 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. <p> <a name = "SSEC006.1"></a> <li><code>IsCopyable( </code><var>obj</var><code> ) C</code> <p> If a mutable form of an object <var>obj</var> can be made in <font face="Gill Sans,Helvetica,Arial">GAP</font>, the object is called <strong>copyable</strong>. Examples of copyable objects are of course lists and records. A new mutable version of the object can always be obtained by the operation <code>ShallowCopy</code> (see <a href="CHAP012.htm#SECT007">Duplication of Objects</a>). <p> Objects for which only an immutable form exists in <font face="Gill Sans,Helvetica,Arial">GAP</font> are called <strong>constants</strong>. Examples of constants are integers, permutations, and domains. Called with a constant as argument, <code>Immutable</code> and <code>ShallowCopy</code> return this argument. <p> <a name = "SSEC006.2"></a> <li><code>IsMutable( </code><var>obj</var><code> ) C</code> <p> tests whether <var>obj</var> is mutable. <p> If an object is mutable then it is also copyable (see <a href="CHAP012.htm#SSEC006.1">IsCopyable</a>), and a <code>ShallowCopy</code> (see <a href="CHAP012.htm#SSEC007.1">ShallowCopy</a>) method should be supplied for it. Note that <code>IsMutable</code> must not be implied by another filter, since otherwise <code>Immutable</code> would be able to create paradoxical objects in the sense that <code>IsMutable</code> for such an object is <code>false</code> but the filter that implies <code>IsMutable</code> is <code>true</code>. <p> In many situations, however, one wants to ensure that objects are <strong>immutable</strong>. 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: <p> <a name = "SSEC006.3"></a> <li><code>Immutable( </code><var>obj</var><code> ) O</code> <p> returns an immutable structural copy (see <a href="CHAP012.htm#SSEC007.2">StructuralCopy</a>) of <var>obj</var> in which the subobjects are immutable <strong>copies</strong> of the subobjects of <var>obj</var>. If <var>obj</var> is immutable then <code>Immutable</code> returns <var>obj</var> itself. <p> <font face="Gill Sans,Helvetica,Arial">GAP</font> will complain with an error if one tries to change an immutable object. <p> <a name = "SSEC006.4"></a> <li><code>MakeImmutable( </code><var>obj</var><code> ) F</code> <p> One can turn the (mutable or immutable) object <var>obj</var> into an immutable one with <code>MakeImmutable</code>; note that this also makes all subobjects of <var>obj</var> immutable, so one should call <code>MakeImmutable</code> only if <var>obj</var> and its mutable subobjects are newly created. If one is not sure about this, <code>Immutable</code> should be used. <p> Note that it is <strong>not</strong> possible to turn an immutable object into a mutable one; only mutable copies can be made (see <a href="CHAP012.htm#SECT007">Duplication of Objects</a>). <p> Using <code>Immutable</code>, 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 <a href="CHAP021.htm#SECT019">Sorted Lists and Sets</a>), which is not possible for lists of mutable objects. <p> Since the operation <code>Immutable</code> must work for any object in <font face="Gill Sans,Helvetica,Arial">GAP</font>, 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. <p> Another interesting example of mutable (and thus copyable) objects is provided by <strong>iterators</strong>, see <a href="CHAP028.htm#SECT007">Iterators</a>. (Of course an immutable form of an iterator is not very useful, but clearly <code>Immutable</code> will yield such an object.) Every call of <code>NextIterator</code> changes a mutable iterator until it is exhausted, and this is the only way to change an iterator. <code>ShallowCopy</code> for an iterator <var>iter</var> is defined so as to return a mutable iterator that has no mutable data in common with <var>iter</var>, and that behaves equally to <var>iter</var> w.r.t. <code>IsDoneIterator</code> and (if <var>iter</var> is mutable) <code>NextIterator</code>. Note that this meaning of the ``shallow copy'' of an iterator that is returned by <code>ShallowCopy</code> is not as obvious as for lists and records, and must be explicitly defined. <p> Many operations return immutable results, among those in particular attributes (see <a href="CHAP013.htm#SECT005">Attributes</a>). Examples of attributes are <code>Size</code>, <code>Zero</code>, <code>AdditiveInverse</code>, <code>One</code>, and <code>Inverse</code>. Arithmetic operations, such as the binary infix operations <code>+</code>, <code>-</code>, <code>*</code>, <code>/</code>, <code>^</code>, <code>mod</code>, the unary <code>-</code>, and operations such as <code>Comm</code> and <code>LeftQuotient</code>, return <strong>mutable</strong> results, <strong>except</strong> 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 <a href="CHAP021.htm#SECT011">Arithmetic for Lists</a>). There is one exception to this rule, which arises where the result is less deeply nested that 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 <a href="CHAP021.htm#SECT011">Arithmetic for Lists</a>. <p> It should be noted that <code>0 * </code><var>obj</var><code></code> is equivalent to <code>ZeroSM( </code><var>obj</var><code> )</code>, <code>-</code><var>obj</var><code></code> is equivalent to <code>AdditiveInverseSM( </code><var>obj</var><code> )</code>, <code></code><var>obj</var><code>^0</code> is equivalent to <code>OneSM( </code><var>obj</var><code>)</code>, and <code></code><var>obj</var><code>^-1</code> is equivalent to <code>InverseSM( </code><var>obj</var><code> )</code>. The ``SM'' stands for ``same mutability'', and indicates that the result is mutable if and only if the argument is mutable. <p> The operations <code>ZeroOp</code>, <code>AdditiveInverseOp</code>, <code>OneOp</code>, and <code>InverseOp</code> return <strong>mutable</strong> results whenever a mutable version of the result exists, contrary to the attributes <code>Zero</code>, <code>AdditiveInverse</code>, <code>One</code>, and <code>Inverse</code>. <p> If one introduces new arithmetic objects then one need not install methods for the attributes <code>One</code>, <code>Zero</code>, etc. The methods for the associated operations <code>OneOp</code> and <code>ZeroOp</code> will be called, and then the results made immutable. <p> 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. <p> 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 <code>TransposedMatMutable</code> constructs a mutable matrix (contrary to the attribute <code>TransposedMat</code>), while <code>TriangulizeMat</code> modifies a mutable matrix (in place) into upper triangular form. <p> 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. <p> <p> <h2><a name="SECT007">12.7 Duplication of Objects</a></h2> <p><p> <a name = "I1"></a> <a name = "I2"></a> <a name = "I2"></a> <a name = "I3"></a> <a name = "SSEC007.1"></a> <li><code>ShallowCopy( </code><var>obj</var><code> ) O</code> <p> If <font face="Gill Sans,Helvetica,Arial">GAP</font> supports a mutable form of the object <var>obj</var> (see <a href="CHAP012.htm#SECT006">Mutability and Copyability</a>) then this is obtained by <code>ShallowCopy</code>. Otherwise <code>ShallowCopy</code> returns <var>obj</var> itself. <p> The subobjects of <code>ShallowCopy( </code><var>obj</var><code> )</code> are <strong>identical</strong> to the subobjects of <var>obj</var>. Note that if the object returned by <code>ShallowCopy</code> is mutable then it is always a <strong>new</strong> object. In particular, if the return value is mutable, then it is not <strong>identical</strong> with the argument <var>obj</var>, no matter whether <var>obj</var> is mutable or immutable. But of course the object returned by <code>ShallowCopy</code> is <strong>equal</strong> to <var>obj</var> w.r.t. the equality operator <code>=</code>. <p> Since <code>ShallowCopy</code> is an operation, the concrete meaning of ``subobject'' depends on the type of <var>obj</var>. But for any copyable object <var>obj</var>, the definition should reflect the idea of ``first level copying''. <p> The definition of <code>ShallowCopy</code> for lists (in particular for matrices) can be found in <a href="CHAP021.htm#SECT007">Duplication of Lists</a>. <p> <a name = "SSEC007.2"></a> <li><code>StructuralCopy( </code><var>obj</var><code> ) F</code> <p> In a few situations, one wants to make a <strong>structural copy</strong> <var>scp</var> of an object <var>obj</var>. This is defined as follows. <var>scp</var> and <var>obj</var> are identical if <var>obj</var> is immutable. Otherwise, <var>scp</var> is a mutable copy of <var>obj</var> such that each subobject of <var>scp</var> is a structural copy of the corresponding subobject of <var>obj</var>. Furthermore, if two subobjects of <var>obj</var> are identical then also the corresponding subobjects of <var>scp</var> are identical. <p> <pre> 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 </pre> <p> That both <code>ShallowCopy</code> and <code>StructuralCopy</code> return the argument <var>obj</var> itself if it is not copyable is consistent with this definition, since there is no way to change <var>obj</var> by modifying the result of any of the two functions, because in fact there is no way to change this result at all. <p> <p> <h2><a name="SECT008">12.8 Other Operations Applicable to any Object</a></h2> <p><p> There are a number of general operations which can be applied, in principle, to any object in <font face="Gill Sans,Helvetica,Arial">GAP</font>. Some of these are documented elsewhere -- see <a href="CHAP026.htm#SSEC005.1">String</a>, <a href="CHAP006.htm#SSEC003.3">PrintObj</a> and <a href="CHAP006.htm#SSEC003.4">Display</a>. Others are mainly somewhat technical. <p> <a name = "SSEC008.1"></a> <li><code>SetName( </code><var>obj</var><code>, </code><var>name</var><code> ) F</code> <p> for a suitable object <var>obj</var> sets that object to have name <var>name</var> (a string). <p> <a name = "SSEC008.2"></a> <li><code>Name( </code><var>obj</var><code> ) A</code> <p> returns the name, a string, previously assigned to <var>obj</var> via a call to <code>SetName</code> (see <a href="CHAP012.htm#SSEC008.1">SetName</a>). The name of an object is used <strong>only</strong> for viewing the object via this name. <p> There are no methods installed for computing names of objects, but the name may be set for suitable objects, using <code>SetName</code>. <p> <pre> gap> g := Group((1,2,3),(1,2)); Group([ (1,2,3), (1,2) ]) gap> SetName(g, "S3"); gap> g; S3 gap> Name(g); "S3" </pre> <p> <a name = "SSEC008.3"></a> <li><code>IsInternallyConsistent( </code><var>obj</var><code> ) O</code> <p> For debugging purposes, it may be useful to check the consistency of an object <var>obj</var> that is composed from other (composed) objects. <p> There is a default method of <code>IsInternallyConsistent</code>, with rank zero, that returns <code>true</code>. So it is possible (and recommended) to check the consistency of subobjects of <var>obj</var> recursively by <code>IsInternallyConsistent</code>. <p> (Note that <code>IsInternallyConsistent</code> is not an attribute.) <p> <a name = "SSEC008.4"></a> <li><code>MemoryUsage( </code><var>obj</var><code> ) O</code> <p> returns the amount of memory in bytes used by the object <var>obj</var> 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 descents 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! <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP011.htm">Previous</a>] [<a href ="CHAP013.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>