%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  foa.tex                   GAP documentation            Heiko Thei\3en
%%
%H  @(#)$Id: foa.tex,v 4.20 2002/10/09 12:32:13 gap Exp $
%%
%Y  Copyright 1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,   Germany
%%
\Chapter{Function-Operation-Attribute Triples}

{\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~"tut:Attributes"  in the   tutorial. In   this  chapter  we  will
describe further mechanisms that  allow storage of  results that  are not
values of attributes.

\index{FOA triples}
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
*f*unction-*o*peration-*a*ttribute 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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Key Dependent Operations}

% see the text in the declaration of `KeyDependentOperation';
% eventually one would like to use the manual builder also for the `ext'
% manual

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~"prg: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 `<name>Op', respectively, and an attribute with name 
and the attribute as described above,
with names <name>, `<name>Op', and `Computed<name>s'.
<dom-req> and <key-req> specify the required filters for the first and
second argument of the operation `<name>Op',
which are needed to create this operation with `NewOperation'
(see~"prg:NewOperation").
<dom-req> is also the required filter for the corresponding attribute
`Computed<name>s'.
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.
\begintt
KeyDependentOperation( "SylowSubgroup", IsGroup, IsPosInt, "prime" );
\endtt
In this example, <key-test> has the value `"prime"',
which is silently replaced by a function that tests whether its argument
is a prime.

\beginexample
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(()) ]
\endexample

%notest
\beginexample
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;
\endexample

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{In Parent Attributes}

This section describes how you can add  new ``in parent attributes''
(see~"ref:Constructing Subdomains" and "ref: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~"ref:Attributes" in the Reference Manual),
namely `D -> IndexOp( Parent( D ), D )'.

The operation `Index' proceeds as follows.
\beginlist%unordered
\item{$\bullet$}
  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.
\item{$\bullet$}
  Otherwise, `IndexOp' is called with the same arguments that `Index' was
  called with, and the result is returned.
\endlist
(Note that it is in principle possible to install even `Index' and
`IndexOp' methods for a number of arguments different from two,
with `InstallOtherMethod',
see~"prg: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>, `<name>Op', and `<name>InParent'.
<super-req> and <sub-req> specify the required filters for the first and
second argument of the operation `<name>Op',
which are needed to create this operation with `NewOperation'
(see~"prg:NewOperation").
<sub-req> is also the required filter for the corresponding attribute
`<name>InParent';
note that `HasParent' is *not* required for the argument <U> of
`<name>InParent', because even without a parent stored,
`Parent( <U> )' is legal, meaning <U> itself
(see~"ref:Parents" in the Reference Manual).
The fourth argument is `DeclareProperty' if `<name>InParent' 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.
\begintt
InParentFOA( "Index", IsGroup, IsGroup, DeclareAttribute );
\endtt

Note that no methods need be installed for `Index' and `IndexInParent'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operation Functions}

\indextt{ExternalSet}\atindex{G-sets}{@$G$-sets}\indextt{Orbits}
Chapter~"ref:Group Actions"  of  the  Reference Manual
and, in particular, the Section~"ref:About Group Actions"
% currently in `abattoir/group.tex', `abattoir/permgrp.tex',
% `abattoir/solvgrp.tex' ...
explain that certain operations such as `Orbits' (see~"ref: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~"ref: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.
\beginlist%ordered
  \item{1.}
    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.
  \item{2.}
    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>.
  \item{3.}
    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>.
  \item{4.}
    The default value of <opr> is `OnPoints'.
  \item{5.}
    In the case of an operation of a permutation group <G>
    on `MovedPoints( <G> )' via `OnPoints',
    if the attribute tester `HasOrbits( <G> )' returns `true',
    the stored attribute value is returned.
  \item{6.}
    The operation is called as `<result>:= Orbits( <G>, <D>, <gens>,
    <oprs>, <opr> )'.
  \item{7.}
    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>.
  \item{8.}
    <result> is returned.
\endlist

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:
\begintt
OrbitsishOperation( "Orbits", OrbitsishReq, false, NewAttribute );
\endtt
The variable `OrbitsishReq' contains the standard requirements
\begintt
OrbitsishReq := [ IsGroup, IsList,
		  IsList,
		  IsList,
		  IsFunction ];
\endtt
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 `<name>Op'.
The second argument <reqs> specifies the list of required filters for the
operation `<name>Op'.

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:
\begintt
OrbitishFO( "Orbit", OrbitishReq, IsCollsElms, false );
\endtt
The variable `OrbitishReq' contains the standard requirements
\begintt
OrbitishReq  := [ IsGroup, IsList, IsObject,
		  IsList,
		  IsList,
		  IsFunction ];
\endtt
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:
\begintt
DeclareAttribute( "BlocksAttr", IsExternalSet );
OrbitishFO( "Blocks",
    [ IsGroup, IsList, IsList,
      IsList,
      IsList,
      IsFunction ], IsIdenticalObj, BlocksAttr );
\endtt
And this extraordinary FOA triple works as follows:
\beginexample
gap> s4 := Group((1,2,3,4),(1,2));; Blocks( s4, MovedPoints(s4), [1,2] );
[ [ 1, 2, 3, 4 ] ]
gap> Tester( BlocksAttr )( s4 );
false
\endexample

\beginexample
gap> Blocks( s4, MovedPoints(s4) );       
[ [ 1, 2, 3, 4 ] ]
gap> Tester( BlocksAttr )( s4 );  BlocksAttr( s4 );
true
[ [ 1, 2, 3, 4 ] ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E