1.27 About the Implementation of Domains

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.

1:
How can we represent domains in such a way that we can handle domains of different type in a common way?

2:
How can we make it possible to allow functions that take domains of different type and perform the same operation for those domains (but using different methods)?

3:
How can we make it possible that the implementation of a new type of domains only requires that one implements what distinguishes this new type of domains from domains of an old type (without the need to change any old code)?

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.

1:
How can we represent objects in such a way that we can handle objects of different classes in a common way (e.g., declare variables that can hold objects of different classes)?

2:
How can we make it possible to allow functions that take objects of different classes (with a common base class) and perform the same operation for those objects (but using different methods)?

3:
How can we make it possible that the implementation of a new class of objects only requires that one implements what distinguishes the objects of this new class from the objects of an old (base) class (without the need to change any old code)?

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).

Previous Up Top Next
Index

GAP 3.4.4
April 1997