2 Method Selection

installs a function method method for the operation opr; args-filts should be a list of requirements for the arguments; if supplied info should be a short but informative string that describes for what situation the method is installed, famp should be a function to be applied to the families of the arguments, each entry being a filter, and val is an integer that measures the priority of the method.

The default values for info, famp, and val are the empty string, the function ReturnTrue, and the integer zero, respectively.

The exact meaning of the arguments famp, args-filts, and val is explained in Section Applicable Methods and Method Selection.

opr expects its methods to require certain filters for their arguments. For example, the argument of a method for the operation Zero must be in the category IsAdditiveElementWithZero. It is not possible to use InstallMethod to install a method for which the entries of args-filts do not imply the respective requirements of the operation opr. If one wants to override this restriction, one has to use InstallOtherMethod instead.

installs a function method method for the operation opr, in the same way as for InstallMethod (see InstallMethod), but without the restriction that the number of arguments must match the declaration of opr and without the restriction that args-filts imply the respective requirements of the operation opr.

For attributes and properties there is InstallImmediateMethod (see InstallImmediateMethod).

For declaring that a filter is implied by other filters there is InstallTrueMethod (see InstallTrueMethod).

2.3 Applicable Methods and Method Selection

A method installed as above is applicable for an arguments tuple if the following conditions are satisfied.

The number of arguments equals the length of the list args-filts, the i-th argument lies in the filter args-filts[i], and famp returns true when applied to the families of the arguments.

So args-filt describes conditions for each argument, and famp describes a relation between the arguments.

For unary operations such as attributes and properties, there is no such relation to postulate, famp is ReturnTrue for these operations, a function that always returns true. For binary operations, the usual value of famp is IsIdenticalObj (see IsIdenticalObj in the Reference Manual), which means that both arguments must lie in the same family.

Note that any properties which occur among the filters in the filter list will not be tested by the method selection if they are not yet known. (More exact: if prop is a property then the filter implicitly uses not prop but Hasprop and prop.) If this is desired you must explicitly enforce a test (see section Redispatching) below.

If no method is applicable, the error message no method found is signaled.

Otherwise, the applicable method with highest rank is selected and then called. This rank is given by the sum of the ranks of the filters in the list args-filt, including involved filters, plus the number val used in the call of InstallMethod. So the argument val can be used to raise the priority of a method relative to other methods for opr.

Note that from the applicable methods, an efficient one shall be selected. This is a method that needs only little time and storage for the computations.

It seems to be impossible for GAP to select an optimal method in all cases. The present ranking of methods is based on the assumption that a method installed for a special situation shall be preferred to a method installed for a more general situation.

For example, a method for computing a Sylow subgroup of a nilpotent group is expected to be more efficient than a method for arbitrary groups. So the more specific method will be selected if GAP knows that the group given as argument is nilpotent.

Of course there is no obvious way to decide between the efficiency of incommensurable methods. For example, take an operation with one method for permutation groups, another method for nilpotent groups, but no method for nilpotent permutation groups, and call this operation with a permutation group known to be nilpotent.

2.4 Partial Methods

After a method has been selected and called, the method may recognize that it cannot compute the desired result, and give up by calling TryNextMethod().

In effect, the execution of the method is terminated, and the method selection calls the next method that is applicable w.r.t. the original arguments. In other words, the applicable method is called that is subsequent to the one that called TryNextMethod, according to decreasing rank of the methods.

For example, since every finite group of odd order is solvable, one may install a method for the property IsSolvableGroup that checks whether the size of the argument is an odd integer, returns true if so, and gives up otherwise.

Care is needed if a partial method might modify the type of one of its arguments, for example by computing an attribute or property. If this happens, and the type has really changed, then the method should not exit using TryNextMethod() but should call the operation again, as the new information in the type may cause some methods previously judged inapplicable to be applicable. For example, if the above method for IsSolvableGroup actually computes the size, (rather than just examining a stored size), then it must take care to check whether the type of the group has changed.

2.5 Redispatching

As mentioned above the method selection will not test unknown properties. In situations, in which algorithms are only known (or implemented) under certain conditions, however such a test might be actually desired.

One way to achieve this would be to install the method under weaker conditions and explicitly test the properties first, exiting via TryNextMethod (see TryNextMethod) if some of them are not fulfilled. A problem of this approach however is that such methods then automatically are ranked lower and that the code does not look nice.

A much better way is to use redispatching: Before deciding that no method has been found one tests these properties and if they turn out to be true the method selection is started anew (and will then find a method).

This can be achieved via the following function:

This function installs a method for the operation oper under the conditions fampred and reqs which has absolute value val; that is, the value of the filters reqs is disregarded. cond is a list of filters. If not all the values of properties involved in these filters are already known for actual arguments of the method, they are explicitly tested and if they are fulfilled and stored after this test, the operation is dispatched again. Otherwise the method exits with TryNextMethod (see TryNextMethod). This can be used to enforce tests like IsFinite in situations when all existing methods require this property. The list cond may have unbound entries in which case the corresponding argument is ignored for further tests.

2.6 Immediate Methods

Usually a method is called only if its operation has been called and if this method has been selected.

For attributes and properties, one can install also immediate methods. An immediate method is called automatically as soon as it is applicable to an object, provided that the value is not yet known. Afterwards the attribute setter is called in order to store the value.

Note that in such a case GAP executes a computation for which it was not explicitly asked by the user. So one should install only those methods as immediate methods that are extremely cheap. To emphasize this, immediate methods are also called zero cost methods. The time for their execution should really be approximately zero.

An immediate method method for the attribute or property attr with requirement req is installed via

where val is an integer value that measures the priority of method among the immediate methods for attr.

Note the difference to InstallMethod (see InstallMethod) that no family predicate occurs because attr expects only one argument, and that req is not a list of requirements but the argument requirement itself.

For example, the size of a permutation group can be computed very cheaply if a stabilizer chain of the group is known. So it is reasonable to install an immediate method for Size with requirement IsGroup and Tester( stab ), where stab is the attribute corresponding to the stabilizer chain.

Another example would be the implementation of the conclusion that every finite group of prime power order is nilpotent. This could be done by installing an immediate method for the attribute IsNilpotentGroup with requirement IsGroup and Tester( Size ). This method would then check whether the size is a finite prime power, return true in this case and otherwise call TryNextMethod() (see TryNextMethod). But this requires factoring of an integer, which cannot be guaranteed to be very cheap, so one should not install this method as an immediate method.

Immediate methods are thought of as a possibility for objects to gain useful knowledge. They must not be used to force the storing of ``defining information'' in an object. In other words, GAP should work even if all immediate methods are invalidated.

2.7 Logical Implications

It may happen that a filter newfil shall be implied by another filter filt, which is usually a meet of other properties, or the meet of some properties and some categories. Such a logical implication can be installed as an immediate method for newfil that requires filt and that always returns true. It should be installed via

This has the effect that newfil becomes an implied filter of filt, see Filters in the Reference Manual.

For example, each cyclic group is abelian, each finite vector space is finite dimensional, and each division ring is integral. The first of these implications is installed as follows.

InstallTrueMethod( IsCommutative, IsGroup and IsCyclic );

Contrary to other immediate methods, logical implications cannot be switched off. This means that after the above implication has been installed, one can rely on the fact that every object in the filter IsGroup and IsCyclic will also be in the filter IsCommutative.

2.8 Operations and Mathematical Terms

Usually an operation stands for a mathematical concept, and the name of the operation describes this uniquely. Examples are the property IsFinite and the attribute Size. But there are cases where the same mathematical term is used to denote different concepts, for example Degree is defined for polynomials, group characters, and permutation actions, and Rank is defined for matrices, free modules, p-groups, and transitive permutation actions.

It is in principle possible to install methods for the operation Rank that are applicable to the different types of arguments, corresponding to the different contexts. But this is not the approach taken in the GAP library. Instead there are operations such as RankMat for matrices and DegreeOfCharacter (in fact these are attributes) which are installed as methods of the ``ambiguous'' operations Rank and Degree.

The idea is to distinguish between on the one hand different ways to compute the same thing (e.g. different methods for \=, Size, etc.), and on the other hand genuinely different things (such as the degree of a polynomial and a permutation action).

The former is the basic purpose of operations and attributes. The latter is provided as a user convenience where mathematical usage forces it on us and where no conflicts arise. In programming the library, we use the underlying mathematically precise operations or attributes, such as RankMat and RankOperation. These should be attributes if appropriate, and the only role of the operation Rank is to decide which attribute the user meant. That way, stored information is stored with ``full mathematical precision'' and is less likely to be retrieved for a wrong purpose later.

One word about possible conflicts. A typical example is the mathematical term ``centre'', which is defined as { x Î M | a * x = x * a "a Î M } for a magma M, and as { x Î L | l * x = 0 "l Î L } for a Lie algebra L. Here it is not possible to introduce an operation Centre that delegates to attributes CentreOfMagma and CentreOfLieAlgebra, depending on the type of the argument. This is because any Lie algebra in GAP is also a magma, so both CentreOfMagma and CentreOfLieAlgebra would be defined for a Lie algebra, with different meaning if the characteristic is 2. So we cannot achieve that one operation in GAP corresponds to the mathematical term ``centre''.

``Ambiguous'' operations such as Rank are declared in the library file overload.g.

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
May 2002