- Many different algorithms may be used to ``multiply'' two algebraic objects, or to compute a property such as ``Size'' or ``Derived Subgroup'', depending on what the objects are
- How do we represent all these, and make the correct decisions, while retaining modularity and efficiency?

**Overloading**- Use of one name to refer to multiple functions (or
objects)
- The `+' operation in most programming languages
- In mathematics, the Centre of a group and the Centre of a Lie algebra are defined differently

**Polymorphism**- Use of the same code to compute with different
types of data
- a function to reverse a list of objects of any type
- a function to test whether a group (given by generators) is abelian - relies on overloading of `*' (and perhaps `=')

- One option is to give each algorithm a separate name:
`IntMult`,`RatMult`,`FPGroupEltWithRWSMult`,`PermutationMult`, etc. - Programmer then chooses method
- Prevents polymorphic programming - need a version of ``power by repeated squaring'' for every type of object
- Also prevents nice syntax - can't write
`a := b*c`

- A single function
`Multiply`which ``knows about'' every form of multiplication in the system - Can easily be invoked by infix `*'
- Allows polymorphic programming
- Makes the system hard to extend/maintain - every new kind of multipliable object required changes to this one procedure (and probably also procedures for `=', `+', etc.
- Possible performance problems

- Every object (actually or implicitly) carries with it the functions (methods) that apply to it
- The operations (actually or implicitly) look inside the object for methods
- Gather objects into ``classes'' - objects in a class have the same methods
- Establish relationships between classes - inheritance
- Polymorphism is fine - abstract classes make it safe(r)
- Overloading is OK if you are careful
- This is done in C++, Java, GAP3, Magma, Axiom, ¼

GAP3 experience found two main limitations.

- which object gets to supply the method
- that method has to choose an algorithm based on the other argument(s)
- Risk of infinite recursion

1 Operations may have more than one argument

- Forcing computation of the information
- Ignoring the information, even when it was, in fact, already there
- Messy non-polymorphic
*ad hoc*tests for the presence of information - Messily changing the class of an object when information is discovered

2 We may learn or compute new information about an object during its life, which we would like to use effectively

In GAP3, we had a choice between

- An
*Operation*is a mathematically well-defined function for arguments from some domain(s) - A
*Method*is a GAP function capable of computing the result of an operation, for some (but possibly not all) relevant argument objects - In GAP4 Methods are associated to Operations, not Objects
- Two Methods for an Operation should agree, where they are both valid - one may be much faster
- An Operation is created once, and then any number of Methods may be installed for it - each installation specifies the domain of validity of the Method
- These domain specifications can include ``non-mathematical issues'' - representation of an object, what is already known about it, etc.
- When the Operation is invoked with particular arguments, the most specialised applicable Method is determined and applied

MyExponent := NewOperation("MyExponent",[IsGroup]); InstallMethod(MyExponent, "Abelian method based on generators", true, [HasGeneratorsOfGroup and IsAbelian and IsGroup], 0, function(g) return Lcm(List(GeneratorsOfGroup(g),Order)); end); InstallMethod(MyExponent, "Default method", true, [IsGroup], 0, function(g) local e,x; e := 1; for x in g do e := Lcm(e,Order(x)); od; return e; end);

gap> gps := [SmallGroup(7,1),SmallGroup(9,1),SmallGroup(9,2)]; [ Group( [ f1 ], ... ), Group( [ f1, f2 ], ... ), Group( [ f1, f2 ], ... ) ] gap> TraceMethods(MyExponent); gap> List(gps,MyExponent); #I MyExponent: Abelian method based on generators #I MyExponent: Default method #I MyExponent: Default method [ 7, 9, 3 ] gap> HasIsAbelian(gps[2]); false gap> IsAbelian(gps[2]); true gap> MyExponent(gps[2]);; #I MyExponent: Abelian method based on generators

- The general format of
`NewOperation`is`NewOperation( ánameñ, árequirementsñ)` - The general format of
`InstallMethod`is`InstallMethod( áoperationñ, [ádescriptionñ,] áfampredñ, árequirementsñ, árankñ, ámethodñ)` - Requirements for a method and an operation are expressed in
terms of
*filters*

- A filter is a Boolean quality of an object such as:
**IsMagmaWithInverses**- The object represents a set whose elements
can be combined with * and which support
`^0`and`^-1`providing an identity and inverse **HasSize**- The result of the
`Size`operation for the object is stored (or otherwise very quickly available) **IsListHashTable**- The object is a hash table represented in a particular way
**HasIsAbelian**- The object knows whether or not it is abelian
**IsAbelian**- The object knows that it is abelian

- Filters are combined with
`and`to produce flag lists -`IsGroup`is constructed as`IsMagmaWithInverses and IsAssociative`. - Certain (combinations of) filters automatically imply certain other filters. When an object acquires one, the others are filled in.

- Every filter has a rank, usually 1.
- Every method has a rank (sum of ranks of filters required, plus
the
*rank*parameter) - Every object carries a flags list (sometimes implicitly)
- When an operation is invoked on actual arguments, the highest rank method whose requirements they meet is called
- A method can exit with
`TryNextMethod()`

- Any unary Operations with no side-effects (eg
`Exponent`) may be an Attribute - It has an associated filter (tester) usually called
`HasXxx`(eg`HasSize`) and another operation (setter) usually called`SetXxx` - The setter is called with the attribute value whenever it is computed
- Methods for setters may store the attribute value in the object and set the tester
- A high-rank method requiring the tester is installed to recover the stored object
- A Boolean attribute is a Property (eg
`IsAbelian`). - A Property is a filter in its own right

These distinctions have no effect on method selection, but alter the way filters are created and set

**Categories**- These are fixed when an object is created, and
control what basic operations are defined for the object (a bit like
abstract classes in C++) (eg
`IsAdditiveElement`implies that a + is defined) **Representations**- Fixed when an object is created, describe how the object is stored, used to select low-level access methods
**Attribute testers**- Set when an attribute value is stored
(eg
`HasIsAbelian`) **Properties**- Set when a property is known to hold (eg
`IsAssociative`) **Others**- A small number of special filters
( eg
`CanEasilyComputePcgs`)

- The filters are essentially static - the complete set of filters is created when the libraries are read
- This does not allow relationships between objects to be captured
- For example
InstallMethod(Comm, "generic method", true, [IsMultiplicativeElementWithInverse, IsMultiplicativeElementWithInverse], 0, function(x,y) return x^-1*y^-1*x*y; end);

might get called with a permutation x and a free group element y - To handle this in the method would add the kind of tedious checking that we are trying to avoid
- There are infinitely many different kinds of group elements - for example elements of different fp groups

- These relationships are captured by the
*family* - Every object has a family (equal objects are in the same family)
- Families can be created dynamically - for example the elements of each fp group form a family
- The
*fampred*argument of`InstallMethod`is passed the families of the arguments. If it returns`true`then the method is applicable - Potential performance problem, but common cases (like family equality) are optimized
- The flags lists and family of an object together make up its
*Type*, which determines the methods that will be applied to it

- Where a name is used for mathematically different meanings (eg Centre of a group { x Î G : xg = gx "g Î G}, Centre of a Lie Algebra {x Î L : xl = 0 "l Î L}
- Have two Attributes:
`CentreOfGroup`and`CentreOfLieAlgebra` - For the user supply an Operation
`Centre`, with methods that call the appropriate Attribute - If there is ever an object which both a group and a LA, there
*must*be a method to decide (or object) - This doesn't happen too often

**Kernel objects**- Objects like permutations have an implicit
type, which cannot change. For basic operations (`+', `*',
`PrintObj`, etc.) the kernel selects the method. Other operations see the implicit type. **Constructors**- A few functions, like
`AbelianGroup`take a flags list as first argument. The method selected is one that will return an object with at least those flags (contravariant) **OperationArgs**- No method selection for functions of variable
numbers of arguments - just one method allowed
Often these functions can call an underlying method with fixed number of args -

`Print`,`PrintObj`

**TryNextMethod()**- This does what it says. If you have two logically different methods whose applicability is NOT captured by the method selection, one can try to solve the problem and then fall through to the other.
**Caching and Hashing**- Various caches are used to ensure
that two equal families are always identical (same memory location)
and two equal types usually are. This costs time when they are
created but saves time and space later.
Each operation caches the most recent (sets of) types it was called with (currently five) and the method selected (including next methods). Most calls hit this cache.

Also cache the result of

`and`for flags lists and a few other things

**Immediate Methods**- Also called ``Zero Cost Methods'' These one-argument methods are run
*whenever*an object acquires the required filters. They are used to ``fill in'' cheap consequences of new information **Virtual Lists and Records**- The list access and assignment
operators
`\[\]`,`\[\]\:\=`and related things are Operations. An object can have the IsList filter and methods installed for these operations and be a ``virtual'' list (possibly infinite). **Iterators**- In a similar way, the
`for`statement will call the`Iterator`operation to obtain a way fo running through an object.

File translated from T

On 10 May 2004, 09:34.