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 Attributes in the tutorial. 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.
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 is an example.
Since its value depends on two arguments, it cannot be an attribute,
yet one would like to store 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 Creating Attributes and Properties in ``Programming in GAP'').
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 operation SylowSubgroup,
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.
The same mechanism works for other functions as well, e.g., for PCore,
but also for HallSubgroup,
where the second argument is not a prime but a set of primes.
KeyDependentOperation( name, dom-req, key-req, key-test )
declares at the same time all three: two operations with names name
and nameOp, respectively, and an attribute with name
and the attribute as described above,
with names name, nameOp, and Computednames.
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 NewOperation
(see NewOperation).
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, SylowSubgroupOp,
and 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, 5 );; ComputedSylowSubgroups( s4 ); [ 5, Group(()) ] gap> SylowSubgroup( s4, 2 );; ComputedSylowSubgroups( s4 ); [ 2, Group([ (3,4), (1,4)(2,3), (1,3)(2,4) ]), 5, 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 and
ComputedSylowSubgroups.
If a method is installed with InstallMethod for a wrapper operation
such as SylowSubgroup then a warning is signalled
provided the InfoWarning level is at least 1.
(Use InstallOtherMethod in order to suppress the warning.)
This section describes how you can add new ``in parent attributes''
(see Constructing Subdomains and Parents in the Reference Manual).
As an example, we describe how Index and its related functions
are implemented.
There are two operations Index 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 Attributes in the Reference Manual),
namely D -> IndexOp( Parent( D ), D ).
The operation Index proceeds as follows.
HasParent( sub ) and IsIdenticalObj( super, Parent( sub ) )
are true, IndexInParent is called with argument sub,
and the result is returned.
IndexOp is called with the same arguments that Index was
called with, and the result is returned.
Index and
IndexOp methods for a number of arguments different from two,
with InstallOtherMethod,
see Creating Attributes and Properties in ``Programming in GAP'').
InParentFOA( name, super-req, sub-req, DeclareAttribute )
InParentFOA( name, super-req, sub-req, DeclareProperty )
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 NewOperation
(see NewOperation).
sub-req is also the required filter for the corresponding attribute
nameInParent;
note that HasParent is not required for the argument U of
nameInParent, because even without a parent stored,
Parent( U ) is legal, meaning U itself
(see Parents in the Reference Manual).
The fourth argument is DeclareProperty if nameInParent takes only
boolean values (for example in the case IsNormalInParent),
and DeclareAttribute otherwise.
For example, to set up the three objects Index, 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 and IndexInParent.
Chapter Group Actions of the Reference Manual
and, in particular, the Section About Group Actions
explain that certain operations such as Orbits (see Orbits),
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
group, meaning the natural action on the set of its moved points.
The definition of Orbits says that a method should be a function
with arguments G, D, gens, oprs, and opr,
as in the case of the operation ExternalSet when specified via gens
and oprs (see External Sets in the Reference Manual).
All other syntax variants allowed for Orbits (e.g., leaving
out gens and oprs) are handled by default methods.
The default methods for Orbits support the following behaviour.
HasOrbits( xset ) returns true,
the stored value of that attribute is returned.
Pcgs( G ) if CanEasilyComputePcgs( G )
is true, and to GeneratorsOfGroup( G ) otherwise;
oprs is set to gens.
OnPoints.
MovedPoints( G ) via OnPoints,
if the attribute tester HasOrbits( G ) returns true,
the stored attribute value is returned.
:= Orbits( G, D, gens,
oprs, opr ).
The declaration of operations that match the above pattern is done as follows.
OrbitsishOperation( name, reqs, usetype, NewAttribute ) F
OrbitsishOperation( name, reqs, usetype, NewProperty ) F
declares an attribute op as described above, 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 (cf. step 6 above).
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 in functions like
ExternalOrbits( xset ),
which call ExternalOrbit( xset, pnt ) for several values of pnt.)
For property testing functions such as IsTransitive,
the fourth argument is NewProperty,
otherwise it is NewAttribute.
For example, to set up the operation Orbits,
the declaration file ``lib/oprt.gd'' contains the following line of code:
OrbitsishOperation( "Orbits", OrbitsishReq, false, NewAttribute );The variable
OrbitsishReq contains the standard requirements
OrbitsishReq := [ IsGroup, IsList, IsList, IsList, IsFunction ];which are usually entered in calls to
OrbitsishOperation.
A similar mechanism is provided for operations such as Orbit that do
not have an associated attribute but still need a wrapper function to
standardize the arguments for the associated operation.
OrbitishFO( name, reqs, famrel, usetype ) F
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, elm ).
For example, in the call Orbit( G, D, pnt ),
pnt must be an element of D, so famrel = IsCollsElms is
appropriate, and in the call Blocks( G, D, seed ),
seed must be a subset of D,
and the family relation is IsIdenticalObj.
The fourth argument usetype serves the same purpose as in the case of
OrbitsishOperation.
For example, to setup the function Orbit and its operation OrbitOp,
the declaration file ``lib/oprt.gd'' contains the following line of code:
OrbitishFO( "Orbit", OrbitishReq, IsCollsElms, false );The variable
OrbitishReq contains the standard requirements
OrbitishReq := [ IsGroup, IsList, IsObject, IsList, IsList, IsFunction ];which are usually entered in calls to
OrbitishFO.
The relation test via famrel is used to provide a uniform construction
of the wrapper functions created by OrbitishFO,
in spite of the different syntax of the specific functions.
For example, Orbit admits the calls Orbit( G, D, pnt, opr )
and Orbit( G, pnt, opr ), i.e., the second argument D may be
omitted;
Blocks 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 and MaximalBlocks),
also the following form is supported.
OrbitishFO( name, reqs, famrel, attr ) F
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.
This attribute is considered by a call Blocks( G, D, opr )
(i.e., without seed) in the same way as Orbits 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 );
And this extraordinary FOA triple works as follows:
gap> s4 := Group((1,2,3,4),(1,2));; 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 ] ]
[Top] [Up] [Previous] [Next] [Index]
GAP 4 manual
March 2006