<html><head><title>[prg] 4 Examples of Extending the System</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>4 Examples of Extending the System</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP004.htm#SECT001">Addition of a Method</a>
<li> <A HREF="CHAP004.htm#SECT002">Extending the Range of Definition of an Existing Operation</a>
<li> <A HREF="CHAP004.htm#SECT003">Enforcing Property Tests</a>
<li> <A HREF="CHAP004.htm#SECT004">Adding a new Operation</a>
<li> <A HREF="CHAP004.htm#SECT005">Adding a new Attribute</a>
<li> <A HREF="CHAP004.htm#SECT006">Adding a new Representation</a>
<li> <A HREF="CHAP004.htm#SECT007">Components versus Attributes</a>
<li> <A HREF="CHAP004.htm#SECT008">Adding new Concepts</a>
<li> <A HREF="CHAP004.htm#SECT009">Example: M-groups</a>
<li> <A HREF="CHAP004.htm#SECT010">Example: Groups with a word length</a>
<li> <A HREF="CHAP004.htm#SECT011">Example: Groups with a decomposition as semidirect product</a>
<li> <A HREF="CHAP004.htm#SECT012">Creating Own Arithmetic Objects</a>
</ol><p>
<p>
This chapter gives a few examples of how one can extend the functionality of
<font face="Gill Sans,Helvetica,Arial">GAP</font>.
<p>
They are arranged in ascending difficulty. We show how to install new
methods, add new operations and attributes and how to implement new features
using categories and representations. (As we do not introduce completely
new kinds of objects in these example it will not be necessary to declare
any families.)
Finally we show a simple way how to create new objects with an own
arithmetic.
<p>
The examples given are all very rudimentary -- no particular error checks
are performed and the user interface sometimes is quite clumsy.
<p>
Even more complex examples that create whole classes of objects anew will be
given in the following two chapters <a href="CHAP005.htm">An Example -- Residue Class Rings</a> and
<a href="CHAP006.htm">An Example -- Designing Arithmetic Operations</a>.
<p>
<p>
<h2><a name="SECT001">4.1 Addition of a Method</a></h2>
<p><p>
The easiest case is the addition of a new algorithm as a method for an
existing operation for the existing structures.
<p>
For example, assume we wanted to implement a better method for computing the
exponent of a nilpotent group (it is the product of the exponents of the
Sylow subgroups).
<p>
The first task is to find which operation is used by <font face="Gill Sans,Helvetica,Arial">GAP</font> (it is <code>Exponent</code>)
and how it is declared. We can find this in the reference manual (in our
particular case in section <a href="../ref/CHAP037.htm#SECT016">Numerical Group Attributes</a>) and the
declaration in the library file <code>lib/grp.gd</code> (The easiest way to find the
place of the declaration is usually to <code>grep</code> over all <code>.gd</code> and <code>.g</code> files,
see section <a href="../ext/CHAP003.htm">Library Files</a> of ``Extending Gap''.)
<p>
In our example the declaration in the library is:
<pre>
DeclareAttribute("Exponent",IsGroup);
</pre>
<p>
Similarly we find that the filter <code>IsNilpotentGroup</code>
represents the concept of being nilpotent.
<p>
We then write a function that implements the new algorithm which takes the
right set of arguments and install it as a method. In our example this
installation would be:
<pre>
InstallMethod(Exponent,"for nilpotent groups",
[IsGroup and IsNilpotent],
function(G)
[function body omitted]
end);
</pre>
<p>
We have left out the optional rank argument of <code>InstallMethod</code>,
which normally is a wise choice -- <font face="Gill Sans,Helvetica,Arial">GAP</font>
automatically uses an internal ranking based on the filters that is only
offset by the given rank. So our method will certainly be ``better'' than
a method that has been installed for mere groups or for solvable groups but
will be ranked lower than the library method for abelian groups.
<p>
That's all. Using <code>ApplicableMethod</code> (see <a href="../ref/CHAP007.htm#SSEC002.1">ApplicableMethod</a>) we can
check for an nilpotent group that indeed our new method will be used.
<p>
When testing, remember that the method selection will not check for
properties that are not known. (This is done internally by checking the
property tester first.) Therefore the method would not be applicable
for the group <code>g</code> in the following definition but only for the --
mathematically identical but endowed with more knowledge by <font face="Gill Sans,Helvetica,Arial">GAP</font> -- group
<code>h</code>. (Section <a href="CHAP004.htm#SECT003">Enforcing Property Tests</a> shows a way around this.)
<pre>
gap> g:=Group((1,2),(1,3)(2,4));;
gap> h:=Group((1,2),(1,3)(2,4));;
gap> IsNilpotentGroup(h); # enforce test
true
gap> HasIsNilpotentGroup(g);
false
gap> HasIsNilpotentGroup(h);
true
</pre>
<p>
<p>
Lets now look at a slightly more complicated example:
We want to implement a better method for computing
normalizers in a nilpotent permutation group.
(Such an algorithm can be found for example in <a href="biblio.htm#luksrakocziwright97"><cite>luksrakocziwright97</cite></a>.)
<p>
We already know <code>IsNilpotentGroup</code>, the filter <code>IsPermGroup</code>
represent the concepts of being a group of permutations.
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> uses <code>Normalizer</code> to compute normalizers, however the declaration is
a bit more complicated. In the library we find
<pre>
InParentFOA( "Normalizer", IsGroup, IsObject, NewAttribute );
</pre>
<p>
The full mechanism of <code>InParentFOA</code> is described in
chapter <a href="../ext/CHAP006.htm">Function-Operation-Attribute Triples</a> of ``Extending <font face="Gill Sans,Helvetica,Arial">GAP</font>'',
however for our purposes it is sufficient to know that for such a function
the actual work is done by an operation <code>NormalizerOp</code> (and all the
complications are just there to be able to remember certain results) and that
the declaration of this operation is given by the first arguments, it would
be:
<pre>
DeclareOperation( "NormalizerOp", [IsGroup, IsObject] );
</pre>
<p>
This time we decide to enter a non-default family predicate in the call to
<code>InstallMethod</code>.
We could just leave it out as in the previous call;
this would yield the default value, the function <code>ReturnTrue</code> of arbitrary
many arguments which always returns <code>true</code>.
However, then the method might be called in some cases of inconsistent input
(for example matrix groups in different characteristics) that ought to fall
through the method selection to raise an error.
<p>
In our situation, we want the second group to be a subgroup of the first, so
necessarily both must have the same family and we can use <code>IsIdenticalObj</code>
as family predicate.
<p>
Now we can install the method. Again this manual is lazy and does not show
you the actual code:
<pre>
InstallMethod(NormalizerOp,"for nilpotent permutation groups",IsIdenticalObj,
[IsPermGroup and IsNilpotentGroup,
IsPermGroup and IsNilpotentGroup],
function(G,U)
[ function body omitted ]
end);
</pre>
<p>
<p>
<h2><a name="SECT002">4.2 Extending the Range of Definition of an Existing Operation</a></h2>
<p><p>
It might be that the operation has been defined so far only for a set of
objects that is too restrictive for our purposes (or we want to install a
method that takes another number of arguments). If this is the case,
the call to <code>InstallMethod</code> causes an error message. We can avoid this by
using <code>InstallOtherMethod</code> instead of <code>InstallMethod</code>.
<p>
<p>
<h2><a name="SECT003">4.3 Enforcing Property Tests</a></h2>
<p><p>
As mentioned above, <font face="Gill Sans,Helvetica,Arial">GAP</font> does not check unknown properties to test whether
a method might be applicable. In some cases one wants to enforce this,
however, because the gain from knowing the property outweighs the cost of
its determination.
<p>
In this situation one has to install a method <strong>without</strong> the additional
property (so it can be tried even if the property is not yet known) and at high
rank (so it will be used before other methods). The first thing to do in the
actual function then is to test the property and to bail out with
<code>TryNextMethod()</code> (see <a href="CHAP002.htm#SSEC004.1">TryNextMethod</a>) if it turns out to be <code>false</code>.
<p>
The above <code>Exponent</code> example thus would become:
<pre>
InstallMethod(Exponent,"test abelianity", [IsGroup],
50,# enforced high rank
function(G)
if not IsAbelian(G) then
TryNextMethod();
fi;
[remaining function body omitted]
end);
</pre>
<p>
The value ``50'' used in this example is quite arbitrary. A better way is to
use values that are given by the system inherently: We want this method
still to be ranked as high, <strong>as if it had</strong> the <code>IsAbelian</code> requirement. So
we have <font face="Gill Sans,Helvetica,Arial">GAP</font> compute the extra rank of this:
<pre>
InstallMethod(Exponent,"test abelianity", [IsGroup],
# enforced absolute rank of `IsGroup and IsAbelian' installation: Subtract
# the rank of `IsGroup' and add the rank of `IsGroup and IsAbelian':
SIZE_FLAGS(FLAGS_FILTER(IsGroup and IsAbelian))
-SIZE_FLAGS(FLAGS_FILTER(IsGroup)),
function(G)
</pre>
the slightly complicated construction of addition and subtraction is
necessary because <code>IsGroup</code> and <code>IsAbelian</code> might imply the <strong>same</strong>
elementary filters which we otherwise would count twice.
<p>
<p>
A somehow similar situation occurs with matrix groups. Most methods for
matrix groups are only applicable if the group is known to be finite.
<p>
However we should not enforce a finiteness test early (someone else later might
install good methods for infinite groups while the finiteness test would be
too expensive) but just before <font face="Gill Sans,Helvetica,Arial">GAP</font> would give a ``no method found''
error. This is done by redispatching, see <a href="CHAP002.htm#SECT005">Redispatching</a>. For example to
enforce such a final finiteness test for normalizer calculations could be
done by:
<pre>
RedispatchOnCondition(NormalizerOp,IsIdenticalObj,
[IsMatrixGroup,IsMatrixGroup],[IsFinite,IsFinite],0);
</pre>
<p>
<p>
<h2><a name="SECT004">4.4 Adding a new Operation</a></h2>
<p><p>
The next step is to add own operations. As an example we take the Sylow
normalizer in a group of a given prime. This operation gets two arguments,
the first has to be a group, the second a prime number.
<p>
There is a function <code>IsPrimeInt</code>, but no property for being prime (which
would be pointless as integers cannot store property values anyhow). So the
second argument gets specified only as positive integer:
<pre>
SylowNormalizer:=NewOperation("SylowNormalizer",[IsGroup,IsPosInt]);
</pre>
(Note that we are using <code>NewOperation</code> (see <a href="CHAP003.htm#SSEC005.1">NewOperation</a>) instead of
<code>DeclareOperation</code> (see <a href="CHAP003.htm#SSEC017.3">DeclareOperation</a>) as used in the library.
The only difference other than that <code>DeclareOperation</code> saves some typing,
is that it also protects the variables against overwriting.
When testing code (when one probably wants to change things)
this might be restricting. If this does not bother you, you can use
<pre>
DeclareOperation("SylowNormalizer",[IsGroup,IsPosInt]);
</pre>
as well.)
<p>
The filters <code>IsGroup</code> and <code>IsPosInt</code> given are <strong>only</strong> used to test that
<code>InstallMethod</code> (see <a href="CHAP002.htm#SSEC002.1">InstallMethod</a>) installs methods with suitable
arguments and will be completely ignored when using <code>InstallOtherMethod</code>
(see <a href="CHAP002.htm#SSEC002.2">InstallOtherMethod</a>). Technically one could
therefore simply use <code>IsObject</code> for all arguments in the declaration. The
main point of using more specific filters here is to help documenting with
which arguments the function is to be used (so for example a call
<code>SylowNormalizer(5,G)</code> would be invalid).
<p>
Of course initially there are no useful methods for newly declared
operations; you will have to write and install them yourself.
<p>
If the operation only takes one argument and has reproducible results
without side effects, it might be worth declaring it as an attribute
instead; see the next section (<a href="CHAP004.htm#SECT005">Adding a new Attribute</a>).
<p>
<p>
<h2><a name="SECT005">4.5 Adding a new Attribute</a></h2>
<p><p>
<a name = "I0"></a>
<a name = "I0"></a>
<a name = "I1"></a>
Now we look at an example of how to add a new attribute. As example we
consider the set of all primes that divide the size of a group.
<p>
First we have to declare the attribute:
<pre>
PrimesDividingSize:=NewAttribute("PrimesDividingSize",IsGroup);
</pre>
(See <a href="CHAP003.htm#SSEC003.1">NewAttribute</a>).
This implicitly declares attribute tester and setter, it is convenient
however to assign these to variables as well:
<pre>
HasPrimesDividingSize:=Tester(PrimesDividingSize);
SetPrimesDividingSize:=Setter(PrimesDividingSize);
</pre>
Alternatively, there is a declaration command
<code>DeclareAttribute</code> (see <a href="CHAP003.htm#SSEC017.2">DeclareAttribute</a>) that executes all three
assignments simultaneously and protects the variables against overwriting:
<pre>
DeclareAttribute("PrimesDividingSize",IsGroup);
</pre>
<p>
Next we have to install method(s) for the attribute that compute its value.
(This is not strictly necessary. We could use the attribute also without
methods only for storing and retrieving information, but calling it for objects
for which the value is not known would produce a ``No method found'' error.)
For this purpose we can imagine the attribute simply as an one-argument
operation:
<pre>
InstallMethod(PrimesDividingSize,"for finite groups",
[IsGroup and IsFinite],
function(G)
if Size(G)=1 then return [];
else return Set(Factors(Size(G)));fi;
end);
</pre>
<a name = "I2"></a>
The function installed <strong>must</strong> always return a value (or call
<code>TryNextMethod</code>; see <a href="CHAP002.htm#SSEC004.1">TryNextMethod</a>). If the object is in the representation
<code>IsAttributeStoringRep</code> this return value once computed will be automatically
stored and retrieved if the attribute is called a second time. We don't have
to call setter or tester ourselves. (This storage happens by <font face="Gill Sans,Helvetica,Arial">GAP</font>
internally calling the attribute setter with the return value of the
function. Retrieval is by a high-ranking method which is installed under the
condition <code>HasPrimesDividingSize</code>. This method was installed automatically
when the attribute was declared.)
<p>
<p>
<h2><a name="SECT006">4.6 Adding a new Representation</a></h2>
<p><p>
<a name = "I3"></a>
<a name = "I3"></a>
<a name = "I4"></a>
<a name = "I5"></a>
<a name = "I5"></a>
<a name = "I6"></a>
Next, we look at the implementation of a new representation of existing
objects. In most cases we want to implement this representation only for
efficiency reasons while keeping all the existing functionality.
<p>
For example, assume we wanted (following <a href="biblio.htm#wielandt69"><cite>wielandt69</cite></a>)
to implement permutation groups defined by relations.
<p>
Next, we have to decide a few basics about the representation. All existing
permutation groups in the library are attribute storing and we probably want
to keep this for our new objects. Thus the representation must be a
subrepresentation of <code>IsComponentObjectRep and IsAttributeStoringRep</code>.
Furthermore we want each object to be a permutation group and we can imply
this directly in the representation.
<p>
We also decide that we store the degree (the largest point that might be
moved)
in a component <code>degree</code> and the defining relations in a component
<code>relations</code> (we do not specify the format of relations here. In an actual
implementation one would have to design this as well, but it does not affect
the declarations this chapter is about).
<pre>
IsPermutationGroupByRelations:=NewRepresentation(
"IsPermutationGroupByRelations",
IsComponentObjectRep and IsAttributeStoringRep and IsPermGroup,
["degree","relations"]);
</pre>
(If we wanted to implement sparse matrices we might for example rather
settle for a positional object in which we store a list of the nonzero
entries.)
<p>
We can make the new representation a subrepresentation of an existing one.
In such a case of course we have to provide all structure of this ``parent''
representation as well.
<p>
Next we need to check in which family our new objects will be. This will be
the same family as of every other permutation group, namely the
<code>CollectionsFamily(PermutationsFamily)</code> (where the family
<code>PermutationsFamily=FamilyObj((1,2,3))</code> has been defined already in the
library).
<p>
Now we can write a function to create our new objects. Usually it is helpful
to look at functions from the library that are used in similar situations (for
example <code>GroupByGenerators</code> in our case) to make sure we have not forgotten
any further requirements in the declaration we might have to add here.
However in most cases the function is straightforward:
<pre>
PermutationGroupByRelations:=function(degree,relations)
local g
g:=Objectify(NewType(CollectionsFamily(PermutationsFamily),
IsPermutationGroupByRelations),
rec(degree:=degree,relations:=relations));
end;
</pre>
<p>
It also is a good idea to install a <code>Print</code> (possibly also a <code>View</code>) method
-- otherwise testing becomes quite hard:
<pre>
InstallMethod(PrintObj,"for perm grps. given by relations",
[IsPermutationGroupByRelations],
function(G)
Print("PermutationGroupByRelations(", G!.degree,",",G!.relations,")");
end);
</pre>
<p>
Next we have to write enough methods for the new representation so that the
existing algorithms can be used. In particular we will have to implement
methods for all operations for which library or kernel provides methods for
the existing (alternative) representations. In our particular case there are
no such methods. (If we would have implemented sparse matrices we
would have had to implement methods for the list access and assignment
functions, see <a href="../ref/CHAP021.htm#SECT002">Basic Operations for Lists</a> in the reference manual.)
However the existing way permutation groups are represented is by
generators. To be able to use the existing machinery we want to be able to
obtain a generating set also for groups in our new representation. This can
be done (albeit not very effectively) by a stabilizer calculation in the
symmetric group given by the <code>degree</code> component. The operation function to
use is probably a bit complicated and will depend on the format of the
<code>relations</code> (we have not specified in this example). In the following
method we use <code>operationfunction</code> as a placeholder;
<pre>
InstallMethod(GeneratorsOfGroup,"for perm grps. given by relations",
[IsPermutationGroupByRelations],
function(G)
local S,U;
S:=SymmetricGroup(G!.degree);
U:=Stabilizer(S,G!.relations, operationfunction );
return GeneratorsOfGroup(U);
end);
</pre>
This is all we <strong>must</strong> do. Of course for performance reasons one might want
to install methods for further operations as well.
<p>
<p>
<h2><a name="SECT007">4.7 Components versus Attributes</a></h2>
<p><p>
In the last section we introduced two new components, <code>G!.degree</code> and
<code>G!.relations</code>. Technically, we could have used attributes instead.
There is no clear distinction which variant is to be preferred: An attribute
expresses part of the functionality available to certain objects (and thus
could be computed later and probably even for a wider class of objects), a
component is just part of the internal definition of an object.
<p>
So if the data is ``of general interest'', if we want the user to have
access to it, attributes are preferable. They provide a clean interface and
their immutability makes it safe to hand the data to a user who potentially
could corrupt a components entries.
<p>
On the other hand more ``technical'' data (say the encoding of a sparse
matrix) is better hidden from the user in a component, as declaring it as an
attribute would not give any advantage.
<p>
Resource-wise, attributes need more memory (the attribute setter and
tester are implicitly declared, and two filter bits are required), the
attribute access is one further function call in the kernel, thus components
might be an immeasurable bit faster.
<p>
<p>
<h2><a name="SECT008">4.8 Adding new Concepts</a></h2>
<p><p>
Finally we look how to implement a new concept for existing objects and fit
this in the method selection. Three examples that will be made more explicit
below would be groups for which a ``length'' of elements (as a word in
certain generators) is defined, groups that can be decomposed as a
semidirect product and M-groups.
<p>
In each case we have two possibilities for the declaration. We can either declare it
as a property or as a category. Both are eventually filter and in this way
indistinguishable for the method selection. The distinction is rather
conceptual and mainly reflects whether we want existing objects to be part
of our new concept or not.
<p>
<p>
<dl compact>
<dt>Property:<dd>
Properties also are attributes:
If a property value is not known for an object, <font face="Gill Sans,Helvetica,Arial">GAP</font> tries to find a
method to compute the property value. If no suitable method is found, an
error is raised.
<p>
<dt>Category:<dd>
An object is in a category if it has been created in it. Testing the
category for an object simply returns this value. Existing objects cannot
enter a new category later in life. This means that in most cases one has to
write own code to create objects in a new category.
<p>
<dt><dd>If we want to implement a completely new concept so that new
operations are defined only for the new objects -- for example bialgebras
for which a second scalar multiplication is defined -- usually a category is
chosen.
<p>
<dt><dd>Technically, the behaviour of the category <code>IsXYZ</code>, declared as subcategory
of <code>IsABC</code> is therefore exactly the same as if we would declare <code>IsXYZ</code> to
be a property for <code>IsABC</code> and install the following method:
<pre>
InstallMethod(IsXYZ,"return false if not known",[IsABC],ReturnFalse);
</pre>
<dt><dd>(The words <code>category</code> also has a
well-defined mathematical meaning, but this does not need to concern us at
this point.
The set of objects which is defined to be a (<font face="Gill Sans,Helvetica,Arial">GAP</font>)-category does
not need to be a category in the mathematical sense, vice versa not every
mathematical category is declared as a (<font face="Gill Sans,Helvetica,Arial">GAP</font>) category.)
</dl>
Eventually the choice between category and property often becomes a matter of
taste or style.
<p>
Sometimes there is even a third possibility (if you have <font face="Gill Sans,Helvetica,Arial">GAP</font> 3 experience
this might reflect most closely ``an object whose operations record is
<code>XYOps</code>''): We might want to indicate this new concept simply by the fact
that certain attributes are set. In this case we could simply use the
respective attribute tester(s).
<p>
The examples given below each give a short argument why the
respective solution was chosen, but one could argue as well for other
choices.
<p>
<p>
<h2><a name="SECT009">4.9 Example: M-groups</a></h2>
<p><p>
M-groups are finite groups for which all irreducible complex
representations are induced from linear representations of subgroups, it
turns out that they are all solvable and that every supersolvable group is
an M-group. See <a href="biblio.htm#Isa76"><cite>Isa76</cite></a> for further details.
<p>
Solvability and supersolvability both are testable properties. We therefore
declare <code>IsMGroup</code> as a property for solvable groups:
<pre>
IsMGroup:=NewProperty("IsMGroup",IsSolvableGroup);
</pre>
The filter <code>IsSolvableGroup</code> in this declaration <strong>only</strong> means that methods
for <code>IsMGroup</code> by default can only be installed for groups that are (and
know to be) solvable (though they could be installed for more general
situations using <code>InstallOtherMethod</code>). It does not yet imply that M-groups
are solvable. We must do this deliberately via an implication and we use the
same technique to imply that every supersolvable group is an M-group.
<pre>
InstallTrueMethod(IsSolvableGroup,IsMGroup);
InstallTrueMethod(IsMGroup,IsSupersolvableGroup);
</pre>
<p>
Now we might install a method that tests for solvable groups whether they
are M-groups:
<pre>
InstallMethod(IsMGroup,"for solvable groups",[IsSolvableGroup],
function(G)
[... code omitted. The function must return `true' or `false' ...]
end);
</pre>
<p>
<p>
<h2><a name="SECT010">4.10 Example: Groups with a word length</a></h2>
<p><p>
Our second example is that of groups for whose elements a <code>word length</code>
is defined. (We assume that the word length is only defined in the context
of the group with respect to a preselected generating set
but not for single elements alone. However we will not delve into any
details of how this length is defined and how it could be computed.)
<p>
Having a word length is a feature which enables other operations (for
example a ``word length'' function). This is exactly what categories are
intended for and therefore we use one.
<p>
First, we declare the category. All objects in this category are groups and
so we inherit the supercategory <code>IsGroup</code>:
<pre>
DeclareCategory("IsGroupWithWordLength",IsGroup);
</pre>
<p>
We also define the operation which is ``enabled'' by this category, the word
length of a group element, which is defined for a group and an element
(remember that group elements are described by the category
<code>IsMultiplicativeElementWithInverse</code>):
<pre>
DeclareOperation("WordLengthOfElement",[IsGroupWithWordLength,
IsMultiplicativeElementWithInverse]);
</pre>
We then would proceed by installing methods to compute the word length in
concrete cases and might for example add further operations to get shortest
words in cosets.
<p>
<p>
<h2><a name="SECT011">4.11 Example: Groups with a decomposition as semidirect product</a></h2>
<p><p>
<a name = "I7"></a>
The third example is groups which have a (nontrivial) decomposition as a
semidirect product. If this information has been found out, we want to be
able to use it in algorithms. (Thus we do not only need the fact <strong>that</strong>
there is a decomposition, but also the decomposition itself.)
<p>
We also want this to be applicable to every group and not only for groups
which have been explicitly constructed via <code>SemidirectProduct</code>.
<p>
Instead we simply declare an attribute <code>SemidirectProductDecomposition</code> for
groups.
(again, in this manual we don't go in the details of how such an
decomposition would look like).
<pre>
DeclareAttribute("SemidirectProductDecomposition",IsGroup);
</pre>
If a decomposition has been found, it can be stored in a group using
<code>SetSemidirectProductDecomposition</code>. (At the moment all groups in <font face="Gill Sans,Helvetica,Arial">GAP</font> are
attribute storing.)
<p>
Methods that rely on the existence of such a decomposition then get
installed for the tester filter <code>HasSemidirectProductDecomposition</code>.
<p>
<p>
<h2><a name="SECT012">4.12 Creating Own Arithmetic Objects</a></h2>
<p><p>
Finally let's look at a way to create new objects with a user-defined
arithmetic such that one can form for example groups, rings or vector spaces
of these elements. This topic is discussed in much more detail in
chapter <a href="CHAP006.htm">An Example -- Designing Arithmetic Operations</a>, in this section we
present a simple approach that may be useful to get started but does not
permit you to exploit all potential features.
<p>
The basic design is that the user designs some way to represent her objects
in terms of <font face="Gill Sans,Helvetica,Arial">GAP</font>s built-in types, for example as a list or a record.
We call this the ``defining data'' of the new objects.
Also provided are functions that perform arithmetic on this ``defining
data'', that is they take objects of this form and return objects that
represent the result of the operation. The function
<code>ArithmeticElementCreator</code> then is called to provide a wrapping such that
proper new <font face="Gill Sans,Helvetica,Arial">GAP</font>-objects are created which can be multiplied etc. with the
default infix operations such as <code>\*</code>.
<p>
<a name = "SSEC012.1"></a>
<li><code>ArithmeticElementCreator( </code><var>spec</var><code> ) F</code>
<p>
offers a simple interface to create new arithmetic elements by providing
functions that perform addition, multiplication and so forth, conforming to
the specification <var>spec</var>. <code>ArithmeticElementCreator</code>
creates a new category, representation and family for the new arithmetic
elements being defined, and returns a function which takes the
``defining data'' of an element and returns the corresponding new
arithmetic element.
<p>
<var>spec</var> is a record with one or more of the following components:
<p>
<dl compact>
<dt><code>ElementName</code><dd>a string used to identify the new type of object. A global
identifier <code>Is</code><var>ElementName</var><code></code> will be defined to indicate a category for
these now objects. (Therefore it is not clever to have blanks in the
name). Also a collections category is defined. (You will get an error
message if the identifier <code>Is</code><var>ElementName</var><code></code> is already defined.)
<p>
<code>Equality</code>, <code>LessThan</code>, <code>One</code>, <code>Zero</code>, <code>Multiplication</code>, <code>Inverse</code>,
<dt><code>Addition</code>, <code>AdditiveInverse</code><dd> functions defining the arithmetic
operations. The functions interface on the level of ``defining data'',
the actual methods installed will perform the unwrapping and wrapping as
objects. Components are optional, but of course if no multiplication is
defined elements cannot be multiplied and so forth.
<p>
<dt><dd>There are default methods for <code>Equality</code> and <code>LessThan</code> which simply
calculate on the defining data. If one is defined, it must be ensured
that the other is compatible (so that <i>a</i> < <i>b</i> implies not(<i>a</i> = <i>b</i>))
<p>
<dt><code>Print</code> <dd> a function which prints the object. By default, just
the defining data is printed.
<p>
<dt><code>MathInfo</code> <dd> filters determining the
mathematical properties of the elements created. A typical value is for
example <code>IsMultiplicativeElementWithInverse</code> for group elements.
<p>
<dt><code>RepInfo</code> <dd> filters determining the representational
properties of the elements created. The objects created are always
component objects, so in most cases the only reasonable option is
<code>IsAttributeStoringRep</code> to permit the storing of attributes.
</dl>
All components are optional and will be filled in with default values
(though of course an empty record will not result in useful objects).
<p>
Note that the resulting objects are <strong>not equal</strong> to their defining data
(even though by default they print as only the defining data). The
operation <code>UnderlyingElement</code> can be used to obtain the defining
data of such an element.
<p>
As the first example we look at subsets of {1…,4} and define an
``addition'' as union and ``multiplication'' as intersection.
These operations are both commutative and we want the resulting elements to
know this.
<p>
We therefore use the following specification:
<pre>
gap> # the whole set
gap> w := [1,2,3,4];
[ 1, 2, 3, 4 ]
gap> PosetElementSpec :=rec(
> # name of the new elements
> ElementName := "PosetOn4",
> # arithmetic operations
> One := a -> w,
> Zero := a -> [],
> Multiplication := function(a, b) return Intersection(a, b); end,
> Addition := function(a, b) return Union(a, b); end,
> AdditiveInverse := a -> Filtered(w, x->(not x in a)),
> # Mathematical properties of the elements
> MathInfo := IsCommutativeElement and IsAdditivelyCommutativeElement
> );;
gap> mkposet := ArithmeticElementCreator(PosetElementSpec);
function( x ) ... end
</pre>
<p>
Now we can create new elements, perform arithmetic on them and form domains:
<pre>
gap> a := mkposet([1,2,3]);
[ 1, 2, 3 ]
gap> CategoriesOfObject(a);
[ "IsExtAElement", "IsNearAdditiveElement", "IsNearAdditiveElementWithZero",
"IsNearAdditiveElementWithInverse", "IsExtLElement", "IsExtRElement",
"IsMultiplicativeElement", "IsMultiplicativeElementWithOne",
"IsAdditivelyCommutativeElement", "IsCommutativeElement", "IsPosetOn4" ]
gap> a=[1,2,3];
false
gap> UnderlyingElement(a)=[1,2,3];
true
gap> b:=mkposet([2,3,4]);
[ 2, 3, 4 ]
gap> a+b;
[ 1, 2, 3, 4 ]
gap> a*b;
[ 2, 3 ]
gap> s:=Semigroup(a,b);
<semigroup with 2 generators>
gap> Size(s);
3
</pre>
<p>
The categories <code>IsPosetOn4</code> and <code>IsPosetOn4Collection</code> can be used to
install methods specific to the new objects.
<pre>
gap> IsPosetOn4Collection(s);
true
</pre>
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
119
