%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  types.tex                 GAP manual                    Thomas Breuer
%W                                                       Martin Schoenert
%%
%H  @(#)$Id: types.tex,v 4.11 2000/01/21 14:07:11 gap Exp $
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Types of Objects}

Every {\GAP} object has a *type*.
Types are used to decide whether an operation is admissible or possible,
and if so, how it is performed.

For example, the types determine whether two objects can be multiplied
and what function is called to compute the product.
Analogously, the type of an object determines whether and how the size
of the object can be computed.

The type of an object consists of the following parts,
which describe different aspects of the object.
It might be useful to identify each type with the set of objects that
have this type, and likewise to regard each part of a type as a set,
whose intersection is the type itself.

The *family* determines the relation of the object to other objects.
For example, all permutations form a family.
Another family consists of all collections of permutations,
this family contains the set of permutation groups as a subset.
A third family consists of all rational functions with coefficients
in a certain family.

The *categories* determine what operations an object admits.
For example, all integers form a category, all rationals form a category,
and all rational functions form a category.

The *representation* determines how an object is actually represented.
For example, a matrix or a polynomial can be stored sparse or dense;
all dense polynomials form a representation.

The *attributes* describe knowledge about an object.
For example, the set of objects corresponding to the attribute `Size'
is formed by all objects for which the value of `Size' is known resp.
can be computed cheaply.

*Properties* are those attributes with possible values `true' and
`false'.
Additionally to the set of objects for which the value of a property is
known, a property defines another important set,
namely the set of all those objects for which the value is known and
`true'.
For example, all groups for which is known whether they are commutative
belong to the former set, and the groups that are known to be commutative
belong to the latter set of the property `IsCommutative'.

Now we describe these parts of types in more detail.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Families}

The family of an object determines its relation to other objects.

More precisely, the families form a partition of all {\GAP} objects
such that the following two conditions hold.
Objects that are equal w.r.t. '`='' lie in the same family.
The family of the result of an operation depends only on the families
of its operands.

The first condition means that a family can be regarded as a set of
elements instead of a set of objects.
Note that this does not hold for categories and representations
(see below),
two objects that are equal w.r.t. '`='' need not lie in the same
categories and representations.
For example, a sparsely represented matrix can be equal to a densely
represented matrix.
Similarly, each domain is equal w.r.t. '`='' to the sorted list of its
elements, but a domain is not a list, and a list is not a domain.

The family of the object <obj> is itself an object,
it can be accessed as

\>FamilyObj( <obj> )

It should be emphasized that families are created as soon as they are
needed.
For example, the family of elements of a finitely presented group
can be created only after the presentation has been constructed.
Thus families are the dynamic part of the type system,
that is, the part that is not fixed after the initialisation of {\GAP}.

Families can be parametrized.
For example, the elements of each finitely presented group form a family
of their own.
Here the family of elements and the finitely presented group
coincide when viewed as sets.
Note that elements in different finitely presented groups lie in
different families.
This distinction allows {\GAP} to forbid multiplications of elements
in different finitely presented groups.

As a special case, families can be parametrized by other families.
An important example is the family of *collections* that can be formed
for each family.
A collection consists of objects that lie in the same family,
it is either a nonempty dense list of objects from the same family
or a domain.

Note that every domain is a collection, that is,
it is not possible to construct domains whose elements lie in different
families.
For example, a polynomial ring over the rationals cannot contain
the integer `0' because the family that contains the integers
does not contain polynomials.
So one has to distinguish the integer zero from each zero polynomial.

Let us look at this example from a different viewpoint.
A polynomial ring and its coefficients ring lie in different families,
hence the coefficients ring cannot be embedded ``naturally'' into the
polynomial ring in the sense that it is a subset.
But it is possible to allow, e.g., the multiplication of an integer
and a polynomial over the integers.
The relation between the arguments,
namely that one is a coefficient and the other a polynomial,
can be detected from the relation of their families.
Moreover, this analysis is easier than in a situation where the rationals
would lie in one family together with all polynomials over the rationals,
because then the relation of families would not distinguish
the multiplication of two polynomials,
the multiplication of two coefficients,
and the multiplication of a coefficient with a polynomial.
So the wish to describe relations between elements
can be taken as a motivation for the introduction of families.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Categories}

The categories of an object determine what operations it admits.
Turned the other way around, every operation requires each of its
arguments to lie in certain categories.

An object can lie in several categories.
For example, a row vector lies in the categories `IsList' and `IsVector';
each list lies in the category `IsCopyable',
and depending on whether or not it is mutable, it may lie in the category
`IsMutable'.
Every domain lies in the category `IsDomain'.

Of course some categories of a mutable object may change when the object
is changed.
For example, by assigning values to positions of a mutable list,
one can change the membership of this list in the categories `IsEmpty'
and `IsDenseList'.

However, if an object is immutable then the set of categories it lies in
is fixed.

All categories are created during initialization,
in particular they are not created dynamically at runtime.

The following list gives an overview of important categories of
arithmetic objects.
Indented categories are to be understood as subcategories of the not
indented category listed above it.
\begintt
    IsObject
        IsExtLElement
        IsExtRElement
            IsMultiplicativeElement
                IsMultiplicativeElementWithOne
                    IsMultiplicativeElementWithInverse
        IsExtAElement
            IsAdditiveElement
                IsAdditiveElementWithZero
                    IsAdditiveElementWithInverse
\endtt
Every object lies in the category `IsObject'.

The categories `IsExtLElement' and `IsExtRElement' contain objects
that can be multiplied with other objects via `*' from the left and
from the right, respectively.
These categories are required for the operands of the operation `*'.

The category `IsMultiplicativeElement' contains objects that can be
multiplied from the left and from the right with objects from the
same family.
`IsMultiplicativeElementWithOne' contains objects <obj> for which a
multiplicatively neutral element can be obtained by taking the
zeroth power `<obj>^0'.
`IsMultiplicativeElementWithInverse' contains objects <obj> for which a
multiplicative inverse can be obtained by forming `<obj>^-1'.

Likewise, the categories `IsExtAElement', `IsAdditiveElement',
`IsAdditiveElementWithZero', and `IsAdditiveElementWithInverse'
contain objects that can be added via `+' to other objects,
objects that can be added to objects of the same family,
objects for which an additively neutral element can be obtained by
multiplication with zero,
and objects for which an additive inverse can be obtained by
multiplication with '-1'.

So a vector lies in `IsExtLElement', `IsExtRElement', and
`IsAdditiveElementWithInverse'.
A ring element must additionally lie in `IsMultiplicativeElement'.

Note that it is not guaranteed by the categories of objects whether
the result of an operation with these objects as arguments is defined.
For example, the category `IsMatrix' is a subcategory of
`IsMultiplicativeElementWithInverse'.
Clearly not every matrix has a multiplicative inverse.
But the category `IsMatrix' makes each matrix an admissible argument of
the operation `Inverse'.
Likewise, two matrices can be multiplied only if they are of appropriate
shapes.

Analogously to the categories of arithmetic elements,
there are categories of domains of these elements.
\begintt
    IsObject
        IsDomain
            IsMagma
                IsMagmaWithOne
                    IsMagmaWithInversesIfNonzero
                        IsMagmaWithInverses
            IsAdditiveMagma
                IsAdditiveMagmaWithZero
                    IsAdditiveMagmaWithInverses
            IsExtLSet
            IsExtRSet
\endtt
Of course `IsDomain' is a subcategory of `IsObject'.
A domain that is closed under multiplication `*' is called a magma,
it lies in the category `IsMagma'.
If a magma is closed under taking the identity,
it lies in `IsMagmaWithOne',
and if it is also closed under taking inverses,
it lies in `IsMagmaWithInverses'.
The category `IsMagmaWithInversesAndZero' denotes closure under
taking inverses only for nonzero elements,
every division ring lies in this category.

Note that every set of categories constitutes its own notion of
generation, for example a group may be generated as a magma with inverses
by some elements,
but to generate it as a magma with one it may be necessary to take the
union of these generators and their inverses.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Representation}

The representation of an object determines how it is actually stored.

{\GAP} distinguishes four essentially different ways to represent
objects.
First there are the representations `IsInternalRep' for internal objects
such as integers and permutations,
and `IsDataObjectRep' for other objects that are created and whose data
are accessible only by kernel functions.

% (N.B.: WHAT exactly to write here?)

All other objects are either in the representation `IsComponentObjectRep'
or in the representation `IsPositionalObjectRep',
see~"Component Objects" and~"Positional Objects".

An object can belong to several representations in the sense that it lies
in subrepresentations of `IsComponentObjectRep' or
`IsPositionalObjectRep'.
The representations to which an object belongs form a chain, 
because either two representations are disjoint or one is contained in
the other.
So the subrepresentations of `IsComponentObjectRep' resp.
`IsPositionalObjectRep' form trees.

These trees are  typically rather shallow, since  for one representation  to be
contained in another implies that all the fields of  the data structure implied
by the containing representation, are present in, and have the same meaning in,
the smaller   representation (whose  data  structure  presumably  contains some
additional fields).

Objects may change their representation,
for example a mutable list of characters can be converted into a string.

All representations are created during initialization,
in particular they are not created dynamically at runtime.

Examples of subrepresentations of `IsPositionalObjectRep' are
`IsModulusRep',
which is used for residue classes in the ring of integers,
and `IsDenseCoeffVectorRep',
which is used for elements of algebras that are defined by structure
constants.

An important subrepresentation of `IsComponentObjectRep' is
`IsAttributeStoringRep', which is used for many domains.
It provides automatical storing of all attribute values (see below).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Attributes}

The attributes of an object describe knowledge about it.

An attribute is a unary operation without side-effects.

An object may store values of its attributes once they have been
computed, and claim that it knows these values.
Note that ``store'' and ``know'' have to be understood in the sense that 
it is very cheap to get such a value when the attribute is called again.

% (N.B.: a word on the guarantee that each call of an attribute for an
% object yields the same value?)

Thus an attribute can be identified with the set of all objects for which
the attribute value is known.
For example, all groups whose order is known lie in the set of the
attribute `Size'.

Obviously, the set of attributes to which an object belongs can change;
in general, an object belongs to few attributes when it is created,
and will lie in more and more attributes as their values are computed.

To check whether an object belongs to an attribute <attr>,
the tester

\>Tester( <attr> )

of the attribute is used;
this is a function that returns `true' or `false',
depending on whether or not the value of <attr> for the object is known.
For example, `Tester( Size )( <obj> )' is `true' if the size of the object
<obj> is known.

To store a value of the attribute <attr> in an object,
the setter

\>Setter( <attr> )

of the attribute is used.
The setter is called automatically when the attribute value has been
computed for the first time.
One can also call the setter explicitly,
for example, `Setter( Size )( <obj>, <val> )' sets <val> as size of the
object <obj> if the size was not yet known.

All attributes are created during initialization,
in particular they are not created dynamically at runtime.

Examples of attributes for multiplicative elements are `Inverse', `One',
and `Order'.
`Size' is an attribute for domains, `Centre' is an attribute for a magma,
and `DerivedSubgroup' is an attribute for groups.

For each attribute <attr> that is declared with `DeclareAttribute'
resp.~`DeclareProperty' (see~"Global Variables in the Library"),
tester and setter are automatically made accessible by the names
`Has<attr>' and `Set<attr>', respectively.
For example, the tester for `Size' is called `HasSize',
and the setter is called `SetSize'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Properties}

The properties of an object are those of its attributes whose values are
`true' or `false'.

The main difference between attributes and properties is that a property
defines two sets,
namely the usual set of all objects for which the value is known,
and the set of all objects for which the value is known to be `true'.

Note that it makes no sense to consider a third set, namely the set of
objects for which the value of a property is `true', since there may be
objects for which the containment in this set cannot be decided.

For a property <prop>, the containment of an object <obj> in the first
set is checked again by applying `Tester( <prop> )' to <obj>,
and <obj> lies in the second set if and only if
`Tester( <prop> )( <obj> ) and <prop>( <obj> )' is `true'.

If a property value is known for an immutable object then this value is
also stored, as part of the type of the object.
To some extent, also property values of mutable objects can be stored,
for example a mutable list all of whose entries are immutable can store
whether it is strictly sorted.

Important properties for domains are `IsAssociative', `IsCommutative',
`IsAnticommutative', `IsLDistributive', and `IsRDistributive',
which mean that the multiplication of elements in the domain satisfies
$(a \* b ) \* c = a \* ( b \* c )$, $a \* b = b \* a$,
$a \* b = - ( b \* a )$, $a \* ( b + c ) = a \* b + a \* c$,
and $( a + b ) \* c = a \* c + b \* c$, respectively,
for all $a$, $b$, $c$ in the domain.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Filters}

As introduced above, each category, representation, or attribute tester
can be identified with the set of all objects that lie in the respective
category, representation, or attribute.
For properties, not only the tester but also the property itself is such
a set,
namely the set of all objects for which the property value is known to be
`true'.

{}From this viewpoint, these different concepts can be described
uniformly as *filters*,
which are special {\GAP} functions that return either `true' or `false',
depending on whether or not the argument lies in the set defined by the
filter.

The intersection (or meet) of two filters <filt1>, <filt2> is again a
filter,
it can be formed as

\)<filt1> and <filt2>

For example, `IsList and IsEmpty' is a filter that returns `true'
if its argument is an empty list, and `false' otherwise.
The filter `IsGroup' is defined as the intersection of the category
`IsMagmaWithInverses' and the property `IsAssociative'.

A filter that is not the meet of other filters
is called a *simple filter*.
For example, each attribute tester is a simple filter.

Every filter <filt> has a *rank*, which is used to define a ranking of
the methods installed for an operation, see "Method Installation".
The rank of a filter can be accessed as

\>RankFilter( <filt> )

For simple filters, an *incremental rank* is defined when the filter is
created, see the sections about the creation of filters
"Creating Categories", "Creating Representations",
"Creating Attributes and Properties", "Creating Other Filters".
For an arbitrary filter, its rank is given by the sum of incremental
ranks of the *involved* simple filters;
additionally to the implied filters, these are also the required filters
of attributes (again see the sections about the creation of filters).
In other words, for the purpose of computing the rank and *only* for this
purpose, attribute testers are treated as if they would imply the
requirements of their attributes.
% say something about the implementation via `InstallHiddenTrueMethod'?

\>NamesFilter( <filt> )

`NamesFilter' returns a list of names of the *implied* simple filters
of the filter <filt>, these are all those simple filters <imp> such that
every object in <filt> does also lie in <imp>.
For implications between filters, see the sections "Filters",
"Logical Implications", "Creating Categories",
"Creating Representations", "Creating Attributes and Properties".

Technical remark:
Filters which are not explicitly set are guaranteed to be `false'.
Therefore, if `IsProp' is a property, creating a type with the filter
`IsProp' yields a type for which the property is known to be true. Creating
a type with the tester filter `HasIsProp' *without* giving the property
filter will yield a type for which the property is known to be false.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Types}

For an object <obj>, its *type* is formed by the following data.
The family of <obj>,
the filters in which <obj> lies,
and, possibly, defining data of the type.

Two types are equal if and only if the two families are identical,
the filters are equal, and, if present, also the defining data of the
types are equal.

The last part of the type, defining data, has not been mentioned before.
It is used, e.g., for residue classes of integers, where the type of each
residue class modulo <n> contains the modulus <n> as defining data.
As a consequence, two residue classes mod <n> and <m> can have the same
type only if `<n> = <m>'.
The defining data of the type <type> can be accessed as
%
% In this case, is it necessary? he family also records this information.
%
% The original example was cosets, and there is a small gain there, but
% I wonder if we need type data at all
%
% The only other thing which uses it is the general mapping representation,
% which is quite nice, but maybe not so important.
%

\>DataType( <type> )

The type of an object is itself an object,
it can be accessed as

\>TypeObj( <obj> )

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E