GAP is eager to maintain information that it has gathered about an object, possibly by lengthy calculations. The most important mechanism for information maintenance is the automatic storage and look-up that takes place for attributes; and this was already mentioned in section Tutorial: Attributes. In this chapter we will describe further mechanisms that allow storage of results that are not values of attributes.
The idea which is common to all sections is that certain operations, which are not themselves attributes, have an attribute associated with them. To automatically delegate tasks to the attribute, GAP knows, in addition to the operation and the attributes also a function, which is wrapped around
the other two. This wrapper function
is called by the user and decides whether to call the operation or the attribute or possibly both. The whole function-operation-attribute triple (or FOA triple) is set up by a single GAP command which writes the wrapper function and already installs some methods, e.g., for the attribute to fall back on the operation. The idea is then that subsequent methods, which perform the actual computation, are installed only for the operation, whereas the wrapper function remains unaltered, and in general no additional methods for the attribute are required either.
‣ KeyDependentOperation( name, dom-req, key-req, key-test ) | ( function ) |
There are several functions that require as first argument a domain, e.g., a group, and as second argument something much simpler, e.g., a prime. SylowSubgroup (39.13-1) is an example. Since its value depends on two arguments, it cannot be an attribute, yet one would like to store the Sylow subgroups once they have been computed.
The idea is to provide an attribute of the group, called ComputedSylowSubgroups, and to store the groups in this list. The name implies that the value of this attribute may change in the course of a GAP session, whenever a newly-computed Sylow subgroup is put into the list. Therefore, this is a mutable attribute (see 13.5). The list contains primes in each bound odd position and a corresponding Sylow subgroup in the following even position. More precisely, if p = ComputedSylowSubgroups( G )[ even - 1 ] then ComputedSylowSubgroups( G )[ even ] holds the value of SylowSubgroup( G, p ). The pairs are sorted in increasing order of p, in particular at most one Sylow p subgroup of G is stored for each prime p. This attribute value is maintained by the function SylowSubgroup (39.13-1), which calls the operation SylowSubgroupOp( G, p ) to do the real work, if the prime p cannot be found in the list. So methods that do the real work should be installed for SylowSubgroupOp and not for SylowSubgroup (39.13-1).
The same mechanism works for other functions as well, e.g., for PCore (39.11-3), but also for HallSubgroup (39.13-3), where the second argument is not a prime but a set of primes.
KeyDependentOperation declares the two operations and the attribute as described above, with names name, nameOp, and Computednames, as well as tester and setter operations Hasname and Setname, respectively. Note, however, that the tester is not a filter. dom-req and key-req specify the required filters for the first and second argument of the operation nameOp, which are needed to create this operation with DeclareOperation (78.1-5). dom-req is also the required filter for the corresponding attribute Computednames. The fourth argument key-test is in general a function to which the second argument info of name( D, info ) will be passed. This function can perform tests on info, and raise an error if appropriate.
For example, to set up the three objects SylowSubgroup (39.13-1), SylowSubgroupOp, ComputedSylowSubgroups together, the declaration file lib/grp.gd contains the following line of code.
KeyDependentOperation( "SylowSubgroup", IsGroup, IsPosInt, "prime" );
In this example, key-test has the value "prime", which is silently replaced by a function that tests whether its argument is a prime.
gap> s4 := Group((1,2,3,4),(1,2));; gap> SylowSubgroup( s4, 7 );; ComputedSylowSubgroups( s4 ); [ 7, Group(()) ] gap> SylowSubgroup( s4, 2 );; ComputedSylowSubgroups( s4 ); [ 2, Group([ (3,4), (1,4)(2,3), (1,3)(2,4) ]), 7, Group(()) ] gap> HasSylowSubgroup( s4, 5 ); false gap> SetSylowSubgroup( s4, 5, Group(()));; ComputedSylowSubgroups( s4 ); [ 2, Group([ (3,4), (1,4)(2,3), (1,3)(2,4) ]), 5, Group(()), 7, Group(()) ]
gap> SylowSubgroup( s4, 6 ); Error, SylowSubgroup: <p> must be a prime called from <compiled or corrupted call value> called from <function>( <arguments> ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit;
Thus the prime test need not be repeated in the methods for the operation SylowSubgroupOp (which are installed to do the real work). Note that no methods need be installed for SylowSubgroup (39.13-1) and ComputedSylowSubgroups. If a method is installed with InstallMethod (78.3-1) for a wrapper operation such as SylowSubgroup (39.13-1) then a warning is signalled provided the InfoWarning (7.4-8) level is at least 1. (Use InstallMethod (78.3-1) in order to suppress the warning.)
‣ InParentFOA( name, super, sub, AorP ) | ( function ) |
This section describes how you can add new in parent attributes
(see 31.8 and 31.7). As an example, we describe how Index (39.3-2) and its related functions are implemented.
There are two operations Index (39.3-2) and IndexOp, and an attribute IndexInParent. They are created together as shown below, and after they have been created, methods need be installed only for IndexOp. In the creation process, IndexInParent already gets one default method installed (in addition to the usual system getter of each attribute, see 13.5), namely D -> IndexOp( Parent( D ), D ).
The operation Index (39.3-2) proceeds as follows.
If it is called with the two arguments super and sub, and if HasParent( sub ) and IsIdenticalObj( super, Parent( sub ) ) are true, IndexInParent is called with argument sub, and the result is returned.
Otherwise, IndexOp is called with the same arguments that Index (39.3-2) was called with, and the result is returned.
(Note that it is in principle possible to install even Index (39.3-2) and IndexOp methods for a number of arguments different from two, with InstallOtherMethod (78.3-2), see 13.5).
The call of InParentFOA declares the operations and the attribute as described above, with names name, nameOp, and nameInParent. super-req and sub-req specify the required filters for the first and second argument of the operation nameOp, which are needed to create this operation with DeclareOperation (78.1-5). sub-req is also the required filter for the corresponding attribute nameInParent; note that HasParent (31.7-1) is not required for the argument U of nameInParent, because even without a parent stored, Parent( U ) is legal, meaning U itself (see 31.7). The fourth argument must be DeclareProperty (13.7-5) if nameInParent takes only boolean values (for example in the case IsNormalInParent), and DeclareAttribute (13.5-4) otherwise.
For example, to set up the three objects Index (39.3-2), IndexOp, and IndexInParent together, the declaration file lib/domain.gd contains the following line of code.
InParentFOA( "Index", IsGroup, IsGroup, DeclareAttribute );
Note that no methods need be installed for Index (39.3-2) and IndexInParent.
Chapter 41 and, in particular, the Section 41.1 explain that certain operations such as 41.4), besides their usual usage with arguments G, D, and opr, can also be applied to an external set (\(G\)-set), in which case they can be interpreted as attributes. Moreover, they can also be interpreted as attributes for permutation groups, meaning the natural action on the set of its moved points.
The definition of 41.4 says that a method should be a function with arguments G, D, gens, oprs, and opr, as in the case of the operation ExternalSet (41.12-2) when specified via gens and oprs (see 41.12). All other syntax variants allowed for 41.4 (e.g., leaving out gens and oprs) are handled by default methods.
The default methods for 41.4 support the following behaviour.
If the only argument is an external set xset and the attribute tester HasOrbits( xset ) returns true, the stored value of that attribute is returned.
If the only argument is an external set xset and the attribute value is not known, the default arguments are obtained from the data of xset.
If gens and oprs are not specified, gens is set to Pcgs( G ) if CanEasilyComputePcgs( G ) is true, and to GeneratorsOfGroup( G ) otherwise; oprs is set to gens.
The default value of opr is OnPoints (41.2-1).
In the case of an operation of a permutation group G on MovedPoints( G ) via OnPoints (41.2-1), if the attribute tester HasOrbits( G ) returns true, the stored attribute value is returned.
The operation is called as result:= Orbits( G, D, gens, oprs, opr ).
In the case of an external set xset or a permutation group G in its natural action, the attribute setter is called to store result.
result is returned.
The declaration of operations that match the above pattern is done as follows.
‣ OrbitsishOperation( name, reqs, usetype, AorP ) | ( function ) |
declares an attribute op, with name name. The second argument reqs specifies the list of required filters for the usual (five-argument) methods that do the real work.
If the third argument usetype is true, the function call op( xset ) will –if the value of op for xset is not yet known– delegate to the five-argument call of op with second argument xset rather than with D. This allows certain methods for op to make use of the type of xset, in which the types of the external subsets of xset and of the external orbits in xset are stored. (This is used to avoid repeated calls of NewType (13.9-3) in functions like ExternalOrbits( xset ), which call ExternalOrbit( xset, pnt ) for several values of pnt.)
For property testing functions such as IsTransitive (41.10-1), the fourth argument AorP must be NewProperty (13.7-4), otherwise it must be NewAttribute (13.5-3); in the former case, a property is returned, in the latter case an attribute that is not a property.
For example, to set up the operation Orbits (41.4-2), the declaration file lib/oprt.gd contains the following line of code:
OrbitsishOperation( "Orbits", OrbitsishReq, false, NewAttribute );
The global variable OrbitsishReq contains the standard requirements
OrbitsishReq := [ IsGroup, IsList,
IsList,
IsList,
IsFunction ];
which are usually entered in calls to OrbitsishOperation.
The new operation, e.g., Orbits (41.4-2), can be called either as Orbits( xset ) for an external set xset, or as Orbits( G ) for a permutation group G, meaning the orbits on the moved points of G via OnPoints (41.2-1), or as
Orbits( G, Omega[, gens, acts][, act] ),
with a group G, a domain or list Omega, generators gens of G, and corresponding elements acts that act on Omega via the function act; the default of gens and acts is a list of group generators of G, the default of act is OnPoints (41.2-1).
Only methods for the five-argument version need to be installed for doing the real work. (And of course methods for one argument in case one wants to define a new meaning of the attribute.)
‣ OrbitishFO( name, reqs, famrel, usetype, realenum ) | ( function ) |
is used to create operations like Orbit (41.4-1). This function is analogous to OrbitsishOperation (85.3-1), but for operations orbish like Orbit( G, Omega, pnt ). Since the return values of these operations depend on the additional argument pnt, there is no associated attribute.
The call of OrbitishFO declares a wrapper function and its operation, with names name and nameOp.
The second argument reqs specifies the list of required filters for the operation nameOp.
The third argument famrel is used to test the family relation between the second and third argument of name( G, D, pnt ). For example, famrel is IsCollsElms in the case of Orbit (41.4-1) because pnt must be an element of D. Similarly, in the call Blocks( G, D, seed ), seed must be a subset of D, and the family relation must be IsIdenticalObj (12.5-1).
The fourth argument usetype serves the same purpose as in the case of OrbitsishOperation (85.3-1). usetype can also be an attribute, such as BlocksAttr or MaximalBlocksAttr. In this case, if only one of the two arguments Omega and pnt is given, blocks with no seed are computed, they are stored as attribute values according to the rules of OrbitsishOperation (85.3-1).
If the 5th argument is set to true, the action for an external set should use the enumerator, otherwise it uses the HomeEnumerator (41.12-5) value. This will make a difference for external orbits as part of a larger domain.
For example, to setup the function Orbit (41.4-1) and its operation OrbitOp, the declaration file lib/oprt.gd contains the following line of code:
OrbitishFO( "Orbit", OrbitishReq, IsCollsElms, false, false );
The variable OrbitishReq contains the standard requirements
OrbitishReq := [ IsGroup, IsList, IsObject,
IsList,
IsList,
IsFunction ];
which are usually entered in calls to OrbitishFO (85.3-2).
The relation test via famrel is used to provide a uniform construction of the wrapper functions created by OrbitishFO (85.3-2), in spite of the different syntax of the specific functions. For example, Orbit (41.4-1) admits the calls Orbit( G, D, pnt, opr ) and Orbit( G, pnt, opr ), i.e., the second argument D may be omitted; Blocks (41.11-1) admits the calls Blocks( G, D, seed, opr ) and Blocks( G, D, opr ), i.e., the third argument may be omitted. The translation to the appropriate call of OrbitOp or BlocksOp, for either operation with five or six arguments, is handled via famrel.
As a consequence, there must not only be methods for OrbitOp with the six arguments corresponding to OrbitishReq, but also methods for only five arguments (i.e., without D). Plenty of examples are contained in the implementation file lib/oprt.gi.
In order to handle a few special cases (currently Blocks (41.11-1) and MaximalBlocks (41.11-2)), also the following form of OrbitishFO (85.3-2) is supported.
OrbitishFO( name, reqs, famrel, attr )
The functions in question depend upon an argument seed, so they cannot be regarded as attributes. However, they are most often called without giving seed, meaning choose any minimal resp. maximal block system
. In this case, the result can be stored as the value of the attribute attr that was entered as fourth argument of OrbitishFO (85.3-2). This attribute is considered by a call Blocks( G, D, opr ) (i.e., without seed) in the same way as Orbits (41.4-2) considers OrbitsAttr.
To set this up, the declaration file lib/oprt.gd contains the following lines:
DeclareAttribute( "BlocksAttr", IsExternalSet );
OrbitishFO( "Blocks",
[ IsGroup, IsList, IsList,
IsList,
IsList,
IsFunction ], IsIdenticalObj, BlocksAttr, true );
And this extraordinary FOA triple works as follows:
gap> s4 := Group((1,2,3,4),(1,2));; gap> Blocks( s4, MovedPoints(s4), [1,2] ); [ [ 1, 2, 3, 4 ] ] gap> Tester( BlocksAttr )( s4 ); false gap> Blocks( s4, MovedPoints(s4) ); [ [ 1, 2, 3, 4 ] ] gap> Tester( BlocksAttr )( s4 ); BlocksAttr( s4 ); true [ [ 1, 2, 3, 4 ] ]
generated by GAPDoc2HTML