Attributes and Methods

Overview

Teaching: 40 min
Exercises: 10 min
Questions
• How to record information in GAP objects

Objectives
• Declaring an attribute

• Installing a method

• Understanding method selection

• Using debugging tools

Which function is faster?

Try to repeatedly calculate `AvgOrdOfGroup(M11)` and `AvgOrdOfCollection(M11)` and compare runtimes. Do this for a new copy of `M11` and for the one for which this parameter has already been observed. What do you observe?

Of course, for any given group the average order of its elements needs to be calculated only once, as the next time it will return the same value. However, as we see from the runtimes below, each new call of `AvgOrdOfGroup` will repeat the same computation again, with slightly varying runtime:

``````A:=AlternatingGroup(10);
``````
``````Alt( [ 1 .. 10 ] )
``````
``````AvgOrdOfCollection(A); time; AvgOrdOfCollection(A); time;
``````
``````2587393/259200
8226
2587393/259200
8118
``````

In the last example, the group in question was the same – we haven’t constructed another copy of `AlternatingGroup(10)`; however, the result of the calculation was not stored in `A`.

If you need to reuse this value, one option could be to store it in some variable, but then you should be careful about matching such variables with corresponding groups, and the code could become quite convoluted and unreadable. On the other hand, GAP has the notion of an attribute – a data structure that is used to accumulate information that an object learns about itself during its lifetime. Consider the following example:

``````G:=Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ]);
gap> NrConjugacyClasses(G);time;NrConjugacyClasses(G);time;
``````
``````Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ])
10
39
10
0
``````

In this case, the group `G` has 10 conjugacy classes, and it took 39 ms to establish that in the first call. The second call has zero cost since the result was stored in `G`, since `NrConjugacyClasses` is an attribute:

``````NrConjugacyClasses;
``````
``````<Attribute "NrConjugacyClasses">
``````

Our goal is now to learn how to create own attributes.

Since we already have a function `AvgOrdOfCollection` which does the calculation, the simplest way to turn it into an attribute is as follows:

``````AverageOrder := NewAttribute("AverageOrder", IsCollection);
InstallMethod( AverageOrder, "for a collection", [IsCollection], AvgOrdOfCollection);
``````

In this example, first we declared an attribute `AverageOrder` for objects in the category `IsCollection`, and then installed the function `AvgOrdOfCollection` as a method for this attribute. Instead of calling the function `AvgOrdOfCollection`, we may now call `AverageOrder`.

Now we may check that subsequent calls of `AverageOrder` with the same argument are performed at zero cost. In this example the time is reduced from more than 16 seconds to zero:

``````S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;
``````
``````39020911/3628800
16445
39020911/3628800
0
``````

You may wonder why we have declared the operation for a collection and not only for a group, and why we have installed the inefficient `AvgOrdOfCollection`. After all, we have already developed the much more efficient `AvgOrdOfGroup`.

Imagine that you would like to be able to compute an average order both for a group and for a list which consists of objects having a multiplicative order. You may have a special function for each case, as we have. If it could happen that you don’t know in advance the type of the object in question, you may add checks into the code and dispatch to a suitable function. This could quickly become complicated if you have several different functions for various types of objects. Instead of that, attributes are bunches of functions, called methods, and GAP’s method selection will choose the most efficient method based on the type of all arguments.

To illustrate this, we will now install a method for `AverageOrder` for a group:

``````InstallMethod( AverageOrder, [IsGroup], AvgOrdOfGroup);
``````

If you apply it to a group whose `AverageOrder` has already been computed, nothing will happen, since GAP will use the stored value. However, for a newly created group, this new method will be called:

``````S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;
``````
``````39020911/3628800
26
39020911/3628800
0
``````

Which method is being called

• Try to call `AverageOrder` for a collection which is not a group (a list of group elements and/or a conjugacy class of group elements).

• Debugging tools like `TraceMethods` may help you see which method is being called.

• `ApplicableMethod` in combination with `PageSource` may point you to the source code with all the comments.

A property is a boolean-valued attribute. It can be created using `NewProperty`

``````IsIntegerAverageOrder := NewProperty("IsIntegerAverageOrder", IsCollection);
``````

Now we will install a method for `IsIntegerAverageOrder` for a collection. Observe that it is never necessary to create a function first and then install it as a method. The following method installation instead creates a new function as one of its arguments:

``````InstallMethod( IsIntegerAverageOrder,
"for a collection",
[IsCollection],
coll -> IsInt( AverageOrder( coll ) )
);
``````

Note that because `AverageOrder` is an attribute it will take care of the selection of the most suitable method.

Does such a method always exist?

No. “No-method-found” is a special kind of error, and there are tools to investigate such errors: see `?ShowArguments`, `?ShowDetails`, `?ShowMethods` and `?ShowOtherMethods`.

The following calculation shows that despite our success with calculating the average order for large permutation groups via conjugacy classes of elements, for pc groups from the Small Groups Library it could be faster to iterate over their elements than to calculate conjugacy classes:

``````l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfGroup);;time;
``````
``````56231
``````
``````l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfCollection);;time;
``````
``````9141
``````

Don’t panic!

• Install a method for `IsPcGroup` that iterates over the group elements instead of calculations its conjugacy classes.

• Estimate practical boundaries of its feasibility. Can you find an example of a pc group where iterating is slower than calculating conjugacy classes?