In this section we will open the black boxes and describe how all this works. This is complex and you do not need to understand it if you are content to use domains only as black boxes. So you may want to skip this section (and the remainder of this chapter).
Domains are represented by records, which we will call domain records in the following. Which components have to be present, which may, and what those components hold, differs from category to category, and, to a smaller extent, from domain to domain. It is possible, though, to generally distinguish four types of components.
The first type of components are called the category components. They
determine to which category a domain belongs. A domain D in a category
Cat has a component isCat with the value true. For example, each
group has the component isGroup. Also each domain has the component
isDomain (again with the value true). Finally a domain may also have
components that describe the representation of this domain. For example,
each permutation group has a component isPermGroup (again with the
value true). Functions such as IsPermGroup test whether such a
component is present, and whether it has the value true.
The second type of components are called the identification components.
They distinguish the domain from other domains in the same category. The
identification components uniquely identify the domain. For example, for
groups the identification components are generators, which holds a list
of generators of the group, and identity, which holds the identity of
the group (needed for the trivial group, for which the list of generators
is empty).
The third type of components are called knowledge components. They
hold all the knowledge GAP has about the domain. For example the size
of the domain D is stored in the knowledge component D.size, the
commutator subgroup of a group is stored in the knowledge component
D.commutatorSubgroup, etc. Of course, the knowledge about a certain
domain will usually increase as you work with a domain. For example, a
group record may initially hold only the knowledge that the group is
finite, but may later hold all kinds of knowledge, for example the
derived series, the Sylow subgroups, etc.
Finally each domain record contains an operations record. The operations record is discussed below.
We want to emphasize that really all information that GAP has about a domain is stored in the knowledge components. That means that you can access all this information, at least if you know where to look and how to interpret what you see. The chapters describing categories and domains will tell you what knowledge components a domain may have, and how the knowledge is represented in those components.
For an example let us return to the permutation group a5 from section
About Domains and Categories. If we print the record using the
function PrintRec we see all the information. GAP stores the
stabilizer chain of a5 in the components orbit, transversal, and
stabilizer. It is not important that you understand what a stabilizer
chain is (this is discussed in chapter Permutation Groups), the
important point here is that it is the vital information that GAP
needs to work efficiently with a5 and that you can access it.
gap> a5 := Group( (1,2,3), (3,4,5) );
Group( (1,2,3), (3,4,5) )
gap> Size( a5 );
60
gap> PrintRec( a5 ); Print( "\n" );
rec(
isDomain := true,
isGroup := true,
identity := (),
generators := [ (1,2,3), (3,4,5) ],
operations := ...,
isPermGroup := true,
isFinite := true,
1 := (1,2,3),
2 := (3,4,5),
orbit := [ 1, 3, 2, 5, 4 ],
transversal := [ (), (1,2,3), (1,2,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5), (2,5,3) ],
orbit := [ 2, 3, 5, 4 ],
transversal := [ , (), (2,5,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5) ],
orbit := [ 3, 5, 4 ],
transversal := [ ,, (), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ ],
operations := ... ),
operations := ... ),
operations := ... ),
isParent := true,
stabChainOptions := rec(
random := 1000,
operations := ... ),
stabChain := rec(
generators := [ (1,2,3), (3,4,5) ],
identity := (),
orbit := [ 1, 3, 2, 5, 4 ],
transversal := [ (), (1,2,3), (1,2,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5), (2,5,3) ],
orbit := [ 2, 3, 5, 4 ],
transversal := [ , (), (2,5,3), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ (3,4,5) ],
orbit := [ 3, 5, 4 ],
transversal := [ ,, (), (3,4,5), (3,4,5) ],
stabilizer := rec(
identity := (),
generators := [ ],
operations := ... ),
operations := ... ),
operations := ... ),
operations := ... ),
size := 60 )
Note that you can not only read this information, you can also modify it. However, unless you truly understand what you are doing, we discourage you from playing around. All GAP functions assume that the information in the domain record is in a consistent state, and everything will go wrong if it is not.
gap> a5.size := 120;
120
gap> Size( ConjugacyClass( a5, (1,2,3,4,5) ) );
24 # this is of course wrong
As was mentioned above, each domain record has an operations record. We
have already seen that functions such as Size can be applied to various
types of domains. It is clear that there is no general method that will
compute the size of all domains efficiently. So Size must somehow
decide which method to apply to a given domain. The operations record
makes this possible.
The operations record of a domain D is the component with the name
D.operations, its value is a record. For each function that you can
apply to D this record contains a function that will compute the
required information (hopefully in an efficient way).
To understand this let us take a look at what happens when we compute
Size( a5 ). Not much happens. Size simply calls
a5.operations.Size( a5 ). a5.operations.Size is a function written
especially for permutation groups. It computes the size of a5 and
returns it. Then Size returns this value.
Actually Size does a little bit more than that. It first tests whether
a5 has the knowledge component a5.size. If this is the case, Size
simply returns that value. Otherwise it calls a5.operations.Size( a5 )
to compute the size. Size remembers the result in the knowledge
component a5.size so that it is readily available the next time Size(
a5 ) is called. The complete definition of Size is as follows.
gap> Size := function ( D )
> local size;
> if IsSet( D ) then
> size := Length( D );
> elif IsRec( D ) and IsBound( D.size ) then
> size := D.size;
> elif IsDomain( D ) then
> D.size := D.operations.Size( D );
> size := D.size;
> else
> Error( "<D> must be a domain or a set" );
> fi;
> return size;
> end;;
Because functions such as Size only dispatch to the functions in the
operations record, they are called dispatcher functions. Almost all
functions that you call directly are dispatcher functions, and almost all
functions that do the hard work are components in an operations record.
Which function is called by a dispatcher obviously depends on the domain
and its operations record (that is the whole point of having an
operations record). In principle each domain could have its own Size
function. In practice however, this would require too many functions.
So different domains share the functions in their operations records,
usually all domains with the same representation share all their
operations record functions. For example all permutation groups share
the same Size function. Because this shared Size function must be
able to access the information in the domain record to compute the
correct result, the Size dispatcher function (and all other dispatchers
as well) pass the domain as first argument
In fact the domains not only have the same functions in their operations
record, they share the operations record. So for example all permutation
groups share a common operations record, which is called PermGroupOps.
This means that changing a function in the operations record for a domain
D in the following way D.operations.function := new-function;
will also change this function for all domains of the same type, even
those that do not yet exist at the moment of the assignment and will only
be constructed later. This is usually not desirable, since supposedly
new-function uses some special properties of the domain D to work
more efficiently. We suggest therefore that you first make a copy of the
operations record with D.operations := Copy( D.operations ); and
only afterwards do D.operations.function := new-function;.
If a programmer that implements a new domain D, a new type of groups
say, would have to write all functions applicable to D, this would
require a lot of effort. For example, there are about 120 functions
applicable to groups. Luckily many of those functions are independent of
the particular type of groups. For example the following function will
compute the commutator subgroup of any group, assuming that
TrivialSubgroup, Closure, and NormalClosure work. We say that this
function is generic.
gap> GroupOps.CommutatorSubgroup := function ( U, V )
> local C, u, v, c;
> C := TrivialSubgroup( U );
> for u in U.generators do
> for v in V.generators do
> c := Comm( u, v );
> if not c in C then
> C := Closure( C, c );
> fi;
> od;
> od;
> return NormalClosure( Closure( U, V ), C );
> end;;
So it should be possible to use this function for the new type of groups. The mechanism to do this is called inheritance. How it works is described in About Defining New Domains, but basically the programmer just copies the generic functions from the generic group operations record into the operations record for his new type of groups.
The generic functions are also called default functions, because they are used by default, unless the programmer overlaid them for the new type of groups.
There is another mechanism through which work can be simplified. It is
called delegation. Suppose that a generic function works for the new
type of groups, but that some special cases can be handled more
efficiently for the new type of groups. Then it is possible to handle
only those cases and delegate the general cases back to the generic
function. An example of this is the function that computes the orbit of
a point under a permutation group. If the point is an integer then the
generic algorithm can be improved by keeping a second list that remembers
which points have already been seen. The other cases (remember that
Orbit can also be used for other operations, e.g., the operation of a
permutation group on pairs of points or the operations on subgroups by
conjugation) are delegated back to the generic function. How this is
done can be seen in the following definition.
gap> PermGroupOps.Orbit := function ( G, d, opr )
> local orb, # orbit of <d> under <G>, result
> max, # largest point moved by the group <G>
> new, # boolean list indicating if a point is new
> gen, # one generator of the group <G>
> pnt, # one point in the orbit <orb>
> img; # image of <pnt> under <gen>
>
> # standard operation
> if opr = OnPoints and IsInt(d) then
>
> # get the largest point <max> moved by the group <G>
> max := 0;
> for gen in G.generators do
> if max < LargestMovedPointPerm(gen) then
> max := LargestMovedPointPerm(gen);
> fi;
> od;
>
> # handle fixpoints
> if not d in [1..max] then
> return [ d ];
> fi;
>
> # start with the singleton orbit
> orb := [ d ];
> new := BlistList( [1..max], [1..max] );
> new[d] := false;
>
> # loop over all points found
> for pnt in orb do
> for gen in G.generators do
> img := pnt ^ gen;
> if new[img] then
> Add( orb, img );
> new[img] := false;
> fi;
> od;
> od;
>
> # other operation, delegate back on default function
> else
> orb := GroupOps.Orbit( G, d, opr );
> fi;
>
> # return the orbit <orb>
> return orb;
> end;;
Inheritance and delegation allow the programmer to implement a new type of groups by merely specifying how those groups differ from generic groups. This is far less work than having to implement all possible functions (apart from the problem that in this case it is very likely that the programmer would forget some of the more exotic functions).
To make all this clearer let us look at an extended example to show you
how a computation in a domain may use default and special functions to
achieve its goal. Suppose you defined g, x, and y as follows.
gap> g := SymmetricGroup( 8 );;
gap> x := [ (2,7,4)(3,5), (1,2,6)(4,8) ];;
gap> y := [ (2,5,7)(4,6), (1,5)(3,8,7) ];;
Now you ask for an element of g that conjugates x to y, i.e., a
permutation on 8 points that takes (2,7,4)(3,5) to (2,5,7)(4,6) and
(1,2,6)(4,8) to (1,5)(3,8,7). This is done as follows (see
RepresentativeOperation and Other Operations).
gap> RepresentativeOperation( g, x, y, OnTuples );
(1,8)(2,7)(3,4,5,6)
Now lets look at what happens step for step. First
RepresentativeOperation is called. After checking the arguments it
calls the function g.operations.RepresentativeOperation, which is the
function SymmetricGroupOps.RepresentativeOperation, passing the
arguments g, x, y, and OnTuples.
SymmetricGroupOps.RepresentativeOperation handles a lot of cases
special, but the operation on tuples of permutations is not among them.
Therefore it delegates this problem to the function that it overlays,
which is PermGroupOps.RepresentativeOperation.
PermGroupOps.RepresentativeOperation also does not handle this special
case, and delegates the problem to the function that it overlays, which
is the default function called GroupOps.RepresentativeOperation.
GroupOps.RepresentativeOperation views this problem as a general tuples
problem, i.e., it does not care whether the points in the tuples are
integers or permutations, and decides to solve it one step at a time. So
first it looks for an element taking (2,7,4)(3,5) to (2,5,7)(4,6) by
calling RepresentativeOperation( g, (2,7,4)(3,5), (2,5,7)(4,6) ).
RepresentativeOperation calls g.operations.RepresentativeOperation
next, which is the function SymmetricGroupOps.RepresentativeOperation,
passing the arguments g, (2,7,4)(3,5), and (2,5,7)(4,6).
SymmetricGroupOps.RepresentativeOperation can handle this case. It
knows that g contains every permutation on 8 points, so it contains
(3,4,7,5,6), which obviously does what we want, namely it takes x[1]
to y[1]. We will call this element t.
Now GroupOps.RepresentativeOperation (see above) looks for an s in
the stabilizer of x[1] taking x[2] to y[2]^(t^-1), since then for
r=s*t we have x[1]^r = (x[1]^s)^t = x[1]^t = y[1] and also
x[2]^r = (x[2]^s)^t = (y[2]^(t^-1))^t = y[2]. So the next step
is to compute the stabilizer of x[1] in g. To do this it calls
Stabilizer( g, (2,7,4)(3,5) ).
Stabilizer calls g.operations.Stabilizer, which is
SymmetricGroupOps.Stabilizer, passing the arguments g and
(2,7,4)(3,5). SymmetricGroupOps.Stabilizer detects that the second
argument is a permutation, i.e., an element of the group, and calls
Centralizer( g, (2,7,4)(3,5) ). Centralizer calls the function
g.operations.Centralizer, which is SymmetricGroupOps.Centralizer,
again passing the arguments g, (2,7,4)(3,5).
SymmetricGroupOps.Centralizer again knows how centralizer in
symmetric groups look, and after looking at the permutation
(2,7,4)(3,5) sharply for a short while returns the centralizer as
Subgroup( g, [ (1,6), (6,8), (2,7,4), (3,5) ] ), which we will call
c. Note that c is of course not a symmetric group, therefore
SymmetricGroupOps.Subgroup gives it PermGroupOps as operations record
and not SymmetricGroupOps.
As explained above GroupOps.RepresentativeOperation needs an element of
c taking x[2] ((1,2,6)(4,8)) to y[2]^(t^-1) ((1,7)(4,6,8)).
So RepresentativeOperation( c, (1,2,6)(4,8), (1,7)(4,6,8) ) is called.
RepresentativeOperation in turn calls the function
c.operations.RepresentativeOperation, which is, since c is a
permutation group, the function PermGroupOps.RepresentativeOperation,
passing the arguments c, (1,2,6)(4,8), and (1,7)(4,6,8).
PermGroupOps.RepresentativeOperation detects that the points are
permutations and and performs a backtrack search through c. It finds
and returns (1,8)(2,4,7)(3,5), which we call s.
Then GroupOps.RepresentativeOperation returns r = s*t =
(1,8)(2,7)(3,6)(4,5), and we are done.
In this example you have seen how functions use the structure of their
domain to solve a problem most efficiently, for example
SymmetricGroupOps.RepresentativeOperation but also the backtrack search
in PermGroupOps.RepresentativeOperation, how they use other functions,
for example SymmetricGroupOps.Stabilizer called Centralizer, and how
they delegate cases which they can not handle more efficiently back to
the function they overlaid, for example
SymmetricGroupOps.RepresentativeOperation delegated to
PermGroupOps.RepresentativeOperation, which in turn delegated to to the
function GroupOps.RepresentativeOperation.
If you think this whole mechanism using dispatcher functions and the operations record is overly complex let us look at some of the alternatives. This is even more technical than the previous part of this section so you may want to skip the remainder of this section.
One alternative would be to let the dispatcher know about the various
types of domains, test which category a domain lies in, and dispatch to
an appropriate function. Then we would not need an operations record.
The dispatcher function CommutatorSubgroup would then look as follows.
Note this is not how CommutatorSubgroup is implemented in GAP.
CommutatorSubgroup := function ( G )
local C;
if IsAgGroup( G ) then
C := CommutatorSubgroupAgGroup( G );
elif IsMatGroup( G ) then
C := CommutatorSubgroupMatGroup( G );
elif IsPermGroup( G ) then
C := CommutatorSubgroupPermGroup( G );
elif IsFpGroup( G ) then
C := CommutatorSubgroupFpGroup( G );
elif IsFactorGroup( G ) then
C := CommutatorSubgroupFactorGroup( G );
elif IsDirectProduct( G ) then
C := CommutatorSubgroupDirectProduct( G );
elif IsDirectProductAgGroup( G ) then
C := CommutatorSubgroupDirectProductAgGroup( G );
elif IsSubdirectProduct( G ) then
C := CommutatorSubgroupSubdirectProduct( G );
elif IsSemidirectProduct( G ) then
C := CommutatorSubgroupSemidirectProduct( G );
elif IsWreathProduct( G ) then
C := CommutatorSubgroupWreathProduct( G );
elif IsGroup( G ) then
C := CommutatorSubgroupGroup( G );
else
Error("<G> must be a group");
fi;
return C;
end;
You already see one problem with this approach. The number of cases that the dispatcher functions would have to test is simply to large. It is even worse for set theoretic functions, because they would have to handle all different types of domains (currently about 30).
The other problem arises when a programmer implements a new domain. Then he would have to rewrite all dispatchers and add a new case to each. Also the probability that the programmer forgets one dispatcher is very high.
Another problem is that inheritance becomes more difficult. Instead of just copying one operations record the programmer would have to copy each function that should be inherited. Again the probability that he forgets one is very high.
Another alternative would be to do completely without dispatchers. In
this case there would be the functions CommutatorSugroupAgGroup,
CommutatorSubgroupPermGroup, etc., and it would be your responsibility
to call the right function. For example to compute the size of a
permutation group you would call SizePermGroup and to compute the size
of a coset you would call SizeCoset (or maybe even
SizeCosetPermGroup).
The most obvious problem with this approach is that it is much more cumbersome. You would always have to know what kind of domain you are working with and which function you would have to call.
Another problem is that writing generic functions would be impossible.
For example the above generic implementation of CommutatorSubgroup
could not work, because for a concrete group it would have to call
ClosurePermGroup or ClosureAgGroup etc.
If generic functions are impossible, inheritance and delegation can not be used. Thus for each type of domain all functions must be implemented. This is clearly a lot of work, more work than we are willing to do.
So we argue that our mechanism is the easiest possible that serves the following two goals. It is reasonably convenient for you to use. It allows us to implement a large (and ever increasing) number of different types of domains.
This may all sound a lot like object oriented programming to you. This is not surprising because we want to solve the same problems that object oriented programming tries to solve. Let us briefly discuss the similarities and differences to object oriented programming, taking C++ as an example (because it is probably the widest known object oriented programming language nowadays). This discussion is very technical and again you may want to skip the remainder of this section.
Let us first recall the problems that the GAP mechanism wants to handle.
For object oriented programming the problems are the same, though the names used are different. We talk about domains, object oriented programming talks about objects, and we talk about categories, object oriented programming talks about classes.
In GAP the first problem is solved by representing all domains using records. Actually because GAP does not perform strong static type checking each variable can hold objects of arbitrary type, so it would even be possible to represent some domains using lists or something else. But then, where would we put the operations record?
C++ does something similar. Objects are represented by struct-s or
pointers to structures. C++ then allows that a pointer to an object of a
base class actually holds a pointer to an object of a derived class.
In GAP the second problem is solved by the dispatchers and the operations record. The operations record of a given domain holds the methods that should be applied to that domain, and the dispatcher does nothing but call this method.
In C++ it is again very similar. The difference is that the dispatcher
only exists conceptually. If the compiler can already decide which
method will be executed by a given call to the dispatcher it directly
calls this function. Otherwise (for virtual functions that may be
overlaid in derived classes) it basically inlines the dispatcher. This
inlined code then dispatches through the so--called virtual method
table (vmt). Note that this virtual method table is the same as the
operations record, except that it is a table and not a record.
In GAP the third problem is solved by inheritance and delegation. To
inherit functions you simply copy them from the operations record of
domains of the old category to the operations record of domains of the
new category. Delegation to a method of a larger category is done by
calling super-category-operations-record.function
C++ also supports inheritance and delegation. If you derive a class from
a base class, you copy the methods from the base class to the derived
class. Again this copying is only done conceptually in C++. Delegation
is done by calling a qualified function base-class::function.
Now that we have seen the similarities, let us discuss the differences.
The first differences is that GAP is not an object oriented programming language. We only programmed the library in an object oriented way using very few features of the language (basically all we need is that GAP has no strong static type checking, that records can hold functions, and that records can grow dynamically). Following Stroustrup's convention we say that the GAP language only enables object oriented programming, but does not support it.
The second difference is that C++ adds a mechanism to support data
hiding. That means that fields of a struct can be private. Those
fields can only be accessed by the functions belonging to this class (and
friend functions). This is not possible in GAP. Every field of
every domain is accessible. This means that you can also modify those
fields, with probably catastrophic results.
The final difference has to do with the relation between categories and their domains and classes and their objects. In GAP a category is a set of domains, thus we say that a domain is an element of a category. In C++ (and most other object oriented programming languages) a class is a prototype for its objects, thus we say that an object is an instance of the class. We believe that GAP's relation better resembles the mathematical model.
In this section you have seen that domains are represented by domain records, and that you can therefore access all information that GAP has about a certain domain. The following sections in this chapter discuss how new domains can be created (see About Defining New Domains, and About Defining New Parametrized Domains) and how you can even define a new type of elements (see About Defining New Group Elements).
GAP 3.4.4