  
  [1X78 [33X[0;0YMethod Selection[133X[101X
  
  [33X[0;0YThis chapter explains how [5XGAP[105X decides which function to call for which types
  of  objects.  It  assumes  that  you  have  read  the chapters about objects
  (Chapter [14X12[114X) and types (Chapter [14X13[114X).[133X
  
  [33X[0;0YAn  [13Xoperation[113X is a special [5XGAP[105X function that bundles a set of functions, its
  [13Xmethods[113X.[133X
  
  [33X[0;0YAll  methods  of  an  operation  compute the same result. But each method is
  installed for specific types of arguments.[133X
  
  [33X[0;0YIf  an  operation is called with a tuple of arguments, one of the applicable
  methods is selected and called.[133X
  
  [33X[0;0YSpecial cases of methods are partial methods, immediate methods, and logical
  implications.[133X
  
  
  [1X78.1 [33X[0;0YOperations and Methods[133X[101X
  
  [33X[0;0YOperations are functions in the category [2XIsOperation[102X ([14X78.1-1[114X).[133X
  
  [33X[0;0YSo  on  the  one  hand,  [13Xoperations[113X  are [5XGAP[105X functions, that is, they can be
  applied to arguments and return a result or cause a side-effect.[133X
  
  [33X[0;0YOn  the other hand, operations are more. Namely, an operation corresponds to
  a set of [5XGAP[105X functions, called the [13Xmethods[113X of the operation.[133X
  
  [33X[0;0YEach  call  of an operation causes a suitable method to be selected and then
  called.  The choice of which method to select is made according to the types
  of  the  arguments,  the  underlying mechanism is described in the following
  sections.[133X
  
  [33X[0;0YExamples  of  operations  are  the  binary  infix  operators  [10X=[110X, [10X+[110X etc., and
  [2XPrintObj[102X  ([14X6.3-5[114X) is the operation that is called for each argument of [2XPrint[102X
  ([14X6.3-4[114X).[133X
  
  [33X[0;0YAlso  all  attributes  and  properties  are operations. Each attribute has a
  special  method  which  is  called if the attribute value is already stored;
  this method of course simply returns this value.[133X
  
  [33X[0;0YThe setter of an attribute is called automatically if an attribute value has
  been  computed.  Attribute  setters are operations, too. They have a default
  method that ignores the request to store the value. Depending on the type of
  the  object,  there  may  be another method to store the value in a suitable
  way, and then set the attribute tester for the object to [9Xtrue[109X.[133X
  
  [1X78.1-1 IsOperation[101X
  
  [33X[1;0Y[29X[2XIsOperation[102X( [3Xobj[103X ) [32X Category[133X
  
  [33X[0;0Yis  the  category of operations. Every operation is a function, but not vice
  versa.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XMinimalPolynomial;[127X[104X
    [4X[28X<Operation "MinimalPolynomial">[128X[104X
    [4X[25Xgap>[125X [27XIsOperation(MinimalPolynomial);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsFunction(MinimalPolynomial);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XFactorial;[127X[104X
    [4X[28Xfunction( n ) ... end[128X[104X
    [4X[25Xgap>[125X [27XIsOperation(Factorial);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X78.1-2 TypeOfOperation[101X
  
  [33X[1;0Y[29X[2XTypeOfOperation[102X( [3Xobject[103X ) [32X function[133X
  
  [33X[0;0Yreturns  a  string  from  the  list  [10X[ "Attribute", "Operation", "Property",
  "Category",  "Representation",  "Filter", "Setter"][110X reflecting which type of
  operation [3Xop[103X is.[133X
  
  [33X[0;0Y(see [14X13.3[114X, [14X13.4[114X, [14X13.5[114X, [14X13.6[114X, [14X13.7[114X, [14X13.8[114X)[133X
  
  [1X78.1-3 ShowDeclarationsOfOperation[101X
  
  [33X[1;0Y[29X[2XShowDeclarationsOfOperation[102X( [3Xoper[103X ) [32X function[133X
  
  [33X[0;0YDisplays information about all declarations of the operation [3Xoper[103X, including
  the location of each declaration and the argument filters.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XShowDeclarationsOfOperation(IsFinite);[127X[104X
    [4X[28XAvailable declarations for operation <Property "IsFinite">:[128X[104X
    [4X[28X  1: GAPROOT/lib/coll.gd:1451 with 1 argument, and filters [ IsListOrCollection ][128X[104X
    [4X[28X  2: GAPROOT/lib/float.gd:212 with 1 argument, and filters [ IsFloat ][128X[104X
    [4X[28X  3: GAPROOT/lib/ctbl.gd:1195 with 1 argument, and filters [ IsNearlyCharacterTable ][128X[104X
  [4X[32X[104X
  
  [1X78.1-4 NewOperation[101X
  
  [33X[1;0Y[29X[2XNewOperation[102X( [3Xname[103X, [3Xargs-filts[103X ) [32X function[133X
  
  [33X[0;0Y[2XNewOperation[102X  returns  an  operation [3Xopr[103X with name [3Xname[103X. The list [3Xargs-filts[103X
  describes  requirements  about  the  arguments  of [3Xopr[103X, namely the number of
  arguments  must  be equal to the length of [3Xargs-filts[103X, and the [22Xi[122X-th argument
  must lie in the filter [3Xargs-filts[103X[22X[i][122X.[133X
  
  [33X[0;0YEach  method  that  is  installed  for  [3Xopr[103X  via [2XInstallMethod[102X ([14X78.3-1[114X) must
  require that the [22Xi[122X-th argument lies in the filter [3Xargs-filts[103X[22X[i][122X.[133X
  
  [33X[0;0YOne  can  install  methods  for other argument tuples via [2XInstallOtherMethod[102X
  ([14X78.3-2[114X),  this  way  it is also possible to install methods for a different
  number of arguments than the length of [3Xargs-filts[103X.[133X
  
  [1X78.1-5 DeclareOperation[101X
  
  [33X[1;0Y[29X[2XDeclareOperation[102X( [3Xname[103X, [3Xfilters[103X ) [32X function[133X
  
  [33X[0;0Ydoes  the  same as [2XNewOperation[102X ([14X78.1-4[114X) and then binds the new operation to
  the  global  variable [3Xname[103X. The variable must previously be writable, and is
  made read-only by this function.[133X
  
  
  [1X78.1-6 [33X[0;0YTag Based Operations[133X[101X
  
  [33X[1;0Y[29X[2XNewTagBasedOperation[102X( [3Xname[103X, [3Xrequirements[103X ) [32X function[133X
  [33X[1;0Y[29X[2XDeclareTagBasedOperation[102X( [3Xname[103X, [3Xrequirements[103X ) [32X function[133X
  [33X[1;0Y[29X[2XInstallTagBasedMethod[102X( [3Xoper[103X[, [3Xtag[103X], [3Xmeth[103X ) [32X function[133X
  
  [33X[0;0Y[2XNewTagBasedOperation[102X returns an operation with name [3Xname[103X that is declared as
  [13Xtag  based[113X  w.r.t. the list [3Xrequirements[103X of filters for its arguments. If an
  operation  with name [3Xname[103X exists already before the call then this operation
  is returned, otherwise a new operation gets created.[133X
  
  [33X[0;0Y[2XDeclareTagBasedOperation[102X  does  the same and additionally binds the returned
  operation to the global variable [3Xname[103X if the operation is new.[133X
  
  [33X[0;0YDeclaring  the  operation  [3Xoper[103X  as tag based w.r.t. [3Xrequirements[103X means that
  [2XInstallTagBasedMethod[102X  can  be  used  to install the method [3Xmeth[103X for [3Xoper[103X, a
  function whose arguments satisfy [3Xrequirements[103X, with the following meaning.[133X
  
  [30X    [33X[0;6YThe  method  [3Xmeth[103X  is  applicable if the first argument of the call to
        [3Xoper[103X  is  identical (in the sense of [2XIsIdenticalObj[102X ([14X12.5-1[114X)) with the
        tag [3Xtag[103X that has been specified in the [2XInstallTagBasedMethod[102X call.[133X
  
  [30X    [33X[0;6YIf  none of the tag based methods for [3Xoper[103X has a [3Xtag[103X that is identical
        with  the  first  argument  of  the call to [3Xoper[103X and if there is a tag
        based  method for [3Xoper[103X for which no [3Xtag[103X was specified then this method
        is applicable.[133X
  
  [33X[0;0YThus  at  most  [13Xone[113X tag based method for [3Xoper[103X is applicable, and if a method
  without [3Xtag[103X has been installed then it serves as the default method. This is
  in  contrast  to  the situation with constructors (see [14X78.2[114X) where the first
  argument  is  a  filter  that  is  used as a tag, but several methods can be
  applicable in a call to a constructor and one cannot define a default method
  for it.[133X
  
  [33X[0;0YTypical  use cases for tag based operations are operations that shall create
  objects  in  particular  internal  representations;  the filters that define
  these  representations  are  then  used as the first argument, and one wants
  that  either  the  unique  method  that  belongs to this filter or a default
  method is called.[133X
  
  [33X[0;0YCurrently  it  is possible to declare an operation as tag based only for [13Xone[113X
  list of requirements.[133X
  
  [33X[0;0YInstalling  methods with [2XInstallMethod[102X ([14X78.3-1[114X) for a tag based operation is
  possible. However, installing such methods with the same requirements as the
  ones  for  the tag based methods will have no effect because the handling of
  tag  based  methods gets installed with [2XInstallEarlyMethod[102X ([14X78.3-3[114X) and thus
  has higher priority.[133X
  
  
  [1X78.2 [33X[0;0YConstructors[133X[101X
  
  [33X[0;0YConstructors  are  a special type of operation used to make new objects. The
  key difference compared to regular operations is that method selection works
  slightly differently for them: The first argument in a call to a constructor
  must  always  be a filter [14X13.2[114X. The result of a method is expected to lie in
  that  filter.  Moreover, while normally method selection matches on the type
  of   each  argument,  for  a  constructor  the  first  argument  is  treated
  differently:  instead  of matching its type, the argument itself (which is a
  filter)  must  be  a  subset  of the filter specified by the method which is
  being  tested  for match. In other words, the argument filter must imply the
  method filter.[133X
  
  [33X[0;0YAlso,  method  ranking works differently: instead of the sum of the ranks of
  the  types  of  all  arguments,  only  the rank of the filter given as first
  argument  is  considered;  and for it, the normal ranking order is reversed.
  This  ensures  that  if multiple constructor methods match, the [21Xmost general[121X
  method is selected.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDeclareConstructor("XCons",[IsMagma,IsInt]);[127X[104X
    [4X[25Xgap>[125X [27XInstallMethod(XCons, [IsGroup, IsInt], function(t,x) return CyclicGroup(x); end);[127X[104X
    [4X[25Xgap>[125X [27XInstallMethod(XCons, [IsPermGroup, IsInt], function(t,x) return SymmetricGroup(x); end);[127X[104X
    [4X[25Xgap>[125X [27XInstallMethod(XCons, [IsSemigroup, IsInt], function(t,x) return FullTransformationMonoid(x); end);[127X[104X
    [4X[25Xgap>[125X [27XXCons(IsGroup,3);[127X[104X
    [4X[28X<pc group of size 3 with 1 generator>[128X[104X
    [4X[25Xgap>[125X [27XXCons(IsPermGroup,3);[127X[104X
    [4X[28XSym( [ 1 .. 3 ] )[128X[104X
    [4X[25Xgap>[125X [27XXCons(IsSemigroup,4);[127X[104X
    [4X[28X<full transformation monoid of degree 4>[128X[104X
    [4X[25Xgap>[125X [27X# if multiple methods match, the most general is selected:[127X[104X
    [4X[25Xgap>[125X [27XXCons(IsMagma,3);[127X[104X
    [4X[28X<full transformation monoid of degree 3>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  example  above  shows  some  basic examples (usually a constructor will
  produce  isomorphic  objects  in  different  representations,  not different
  objects as in this case).[133X
  
  [33X[0;0YIf  no  method  has  been  installed  which guarantees to produce a suitable
  objecty, a "No Method Found" error will be returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XXCons(IsFullTransformationMonoid,4);[127X[104X
    [4X[28XError, no method found! For debugging hints type ?Recovery from NoMethodFound[128X[104X
    [4X[28XError, no 1st choice method found for `XCons' on 2 arguments[128X[104X
    [4X[28Xcalled from read-eval loop at *stdin*:8[128X[104X
    [4X[28Xtype 'quit;' to quit to outer loop[128X[104X
    [4X[26Xbrk>[126X [27Xquit;[127X[104X
    [4X[25Xgap>[125X [27XXCons(IsNilpotentGroup,4);[127X[104X
    [4X[28XError, no method found! For debugging hints type ?Recovery from NoMethodFound[128X[104X
    [4X[28XError, no 1st choice method found for `XCons' on 2 arguments[128X[104X
    [4X[28Xcalled from read-eval loop at *stdin*:8[128X[104X
    [4X[28Xtype 'quit;' to quit to outer loop[128X[104X
    [4X[26Xbrk>[126X[104X
  [4X[32X[104X
  
  [33X[0;0YNote  that  in  both  these  cases  there  are methods that actually produce
  results  of  the  required types, but they have not been installed with this
  information, so are not selected.[133X
  
  [1X78.2-1 NewConstructor[101X
  
  [33X[1;0Y[29X[2XNewConstructor[102X( [3Xname[103X, [3Xargs-filts[103X ) [32X function[133X
  
  [33X[0;0Y[2XNewConstructor[102X   returns  a  constructor  [3Xcons[103X  with  name  [3Xname[103X.  The  list
  [3Xargs-filts[103X  describes  requirements  about the arguments of [3Xcons[103X. Namely the
  number  of arguments must be equal to the length of [3Xargs-filts[103X, and the [22Xi[122X-th
  argument  must  lie  in  the  filter  [3Xargs-filts[103X[22X[i][122X for [22Xi ≠ 1[122X. A constructor
  expects  the  first argument to be a [13Xfilter[113X instead of an object and it must
  be a subset of the filter [3Xargs-filts[103X[22X[1][122X.[133X
  
  [33X[0;0YEach  method  that  is  installed  for  [3Xcons[103X via [2XInstallMethod[102X ([14X78.3-1[114X) must
  require  that  the [22Xi[122X-th argument lies in the filter [3Xargs-filts[103X[22X[i][122X for [22Xi ≠ 1[122X.
  Its  first  argument  is  a  filter  and  must  be  a  subset  of the filter
  [3Xargs-filts[103X[22X[1][122X.[133X
  
  [33X[0;0YOne  can  install  methods  for other argument tuples via [2XInstallOtherMethod[102X
  ([14X78.3-2[114X),  this  way  it is also possible to install methods for a different
  number of arguments than the length of [3Xargs-filts[103X.[133X
  
  [33X[0;0YNote  that  the method selection for constructors works slightly differently
  than  for  usual  operations.  As  stated  above,  applicabilty to the first
  argument  in  an  argument  tuple  is  tested  by  determining  whether  the
  argument-filter is a [13Xsubset[113X of [3Xargs-filts[103X[22X[1][122X.[133X
  
  [33X[0;0YThe  rank  of  a  method installed for a constructor is determined solely by
  [3Xargs-filts[103X[22X[1][122X  of  the  method.  Instead  of  taking the sum of the ranks of
  filters  involved  in its [3Xargs-filts[103X[22X[1][122X, the sum of [22X-1[122X times these values is
  taken.  The  result  is  added  to  the  number  [3Xval[103X  used  in  the  call of
  [2XInstallMethod[102X ([14X78.3-1[114X).[133X
  
  [33X[0;0YThis  has the following effects on the method selection for constructors. If
  [3Xcons[103X  is  called  with  an argument tuple whose first argument is the filter
  [3Xfilt[103X,  any  method  whose  first  argument  is  [13Xmore[113X  specific  than [3Xfilt[103X is
  applicable  (if  its  other [3Xargs-filts[103X also match). Then the method with the
  [21Xmost  general[121X  filter [3Xargs-filts[103X[22X[1][122X is chosen, since the rank is computed by
  taking  [22X-1[122X  times  the ranks of the involved filters. Thus, a constructor is
  chosen  which  returns  an  object  in  [3Xfilt[103X  using  as few extra filters as
  possible,  which  presumably  is  both  more  flexible  to use and easier to
  construct.[133X
  
  [33X[0;0YThe  following  example  showcases  this  behaviour.  Note that the argument
  [3Xfilter[103X is only used for method dispatch.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28XDeclareFilter( "IsMyObj" );[128X[104X
    [4X[28XDeclareFilter( "IsMyFilter" );[128X[104X
    [4X[28XDeclareFilter( "IsMyOtherFilter" );[128X[104X
    [4X[28XBindGlobal( "MyFamily", NewFamily( "MyFamily" ) );[128X[104X
    [4X[28X[128X[104X
    [4X[28XDeclareConstructor( "NewMyObj", [ IsMyObj ] );[128X[104X
    [4X[28X[128X[104X
    [4X[28XInstallMethod( NewMyObj,[128X[104X
    [4X[28X[ IsMyObj ],[128X[104X
    [4X[28Xfunction( filter )[128X[104X
    [4X[28X    local type;[128X[104X
    [4X[28X    Print("General constructor\n");[128X[104X
    [4X[28X    type := NewType( MyFamily, IsMyObj );[128X[104X
    [4X[28X    return Objectify( type, [] );[128X[104X
    [4X[28Xend );[128X[104X
    [4X[28XInstallMethod( NewMyObj,[128X[104X
    [4X[28X[ IsMyObj and IsMyFilter and IsMyOtherFilter ],[128X[104X
    [4X[28Xfunction( filter )[128X[104X
    [4X[28X    local type;[128X[104X
    [4X[28X    Print("Special constructor\n");[128X[104X
    [4X[28X    type := NewType( MyFamily, IsMyObj and IsMyFilter and IsMyOtherFilter );[128X[104X
    [4X[28X    return Objectify( type, [] );[128X[104X
    [4X[28Xend );[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  only  IsMyObj  is  given,  both  methods  are applicable and the general
  constructor  is  called.  If  also  IsMyFilter  is  given,  only the special
  constructor is applicable.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xa := NewMyObj( IsMyObj );;[127X[104X
    [4X[28XGeneral constructor[128X[104X
    [4X[25Xgap>[125X [27XIsMyOtherFilter(a);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xb := NewMyObj( IsMyObj and IsMyFilter );;[127X[104X
    [4X[28XSpecial constructor[128X[104X
    [4X[25Xgap>[125X [27XIsMyOtherFilter(b);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xc := NewMyObj( IsMyObj and IsMyFilter and IsMyOtherFilter );;[127X[104X
    [4X[28XSpecial constructor[128X[104X
    [4X[25Xgap>[125X [27XIsMyOtherFilter(c);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X78.2-2 DeclareConstructor[101X
  
  [33X[1;0Y[29X[2XDeclareConstructor[102X( [3Xname[103X, [3Xfilters[103X ) [32X function[133X
  
  [33X[0;0Ydoes  the  same  as [2XNewConstructor[102X ([14X78.2-1[114X) and then binds the result to the
  global  variable [3Xname[103X. The variable must previously be writable, and is made
  read-only by this function.[133X
  
  [33X[0;0YNote  that  for operations which are constructors special rules with respect
  to  applicability  and  rank of the corresponding methods apply (see section
  [2XNewConstructor[102X ([14X78.2-1[114X)).[133X
  
  
  [1X78.3 [33X[0;0YMethod Installation[133X[101X
  
  [33X[0;0YIn  order  to  describe what it means to select a method of an operation, we
  must describe how the methods are connected to their operations.[133X
  
  [33X[0;0YFor attributes and properties there is [2XInstallImmediateMethod[102X ([14X78.7-1[114X).[133X
  
  [33X[0;0YFor   declaring  that  a  filter  is  implied  by  other  filters  there  is
  [2XInstallTrueMethod[102X ([14X78.8-1[114X).[133X
  
  [1X78.3-1 InstallMethod[101X
  
  [33X[1;0Y[29X[2XInstallMethod[102X( [3Xopr[103X[, [3Xinfo[103X][, [3Xfamp[103X], [3Xargs-filts[103X[, [3Xval[103X], [3Xmethod[103X ) [32X function[133X
  
  [33X[0;0Yinstalls  a  function method [3Xmethod[103X for the operation [3Xopr[103X; [3Xargs-filts[103X should
  be  a  list of requirements for the arguments, each entry being a filter; if
  supplied  [3Xinfo[103X  should  be a short but informative string that describes for
  what  situation  the  method  is  installed, [3Xfamp[103X should be a function to be
  applied  to  the  families  of  the arguments. [3Xval[103X should be an integer that
  measures  the  priority  of  the method, or a function of no arguments which
  should  return  such an integer and will be called each time method order is
  being recalculated (see [2XInstallTrueMethod[102X ([14X78.8-1[114X)).[133X
  
  [33X[0;0YThe  default  values  for  [3Xinfo[103X,  [3Xfamp[103X,  and  [3Xval[103X  are the empty string, the
  function [2XReturnTrue[102X ([14X5.4-1[114X), and the integer zero, respectively.[133X
  
  [33X[0;0YThe exact meaning of the arguments [3Xfamp[103X, [3Xargs-filts[103X, and [3Xval[103X is explained in
  Section [14X78.4[114X.[133X
  
  [33X[0;0Y[3Xopr[103X  expects its methods to require certain filters for their arguments. For
  example,  the  argument of a method for the operation [2XZero[102X ([14X31.10-3[114X) must be
  in  the  category [2XIsAdditiveElementWithZero[102X ([14X31.14-5[114X). It is not possible to
  use [2XInstallMethod[102X to install a method for which the entries of [3Xargs-filts[103X do
  not  imply the respective requirements of the operation [3Xopr[103X. If one wants to
  override  this  restriction,  one  has  to  use  [2XInstallOtherMethod[102X ([14X78.3-2[114X)
  instead.[133X
  
  [1X78.3-2 InstallOtherMethod[101X
  
  [33X[1;0Y[29X[2XInstallOtherMethod[102X( [3Xopr[103X[, [3Xinfo[103X][, [3Xfamp[103X], [3Xargs-filts[103X[, [3Xval[103X], [3Xmethod[103X ) [32X function[133X
  
  [33X[0;0Yinstalls  a function method [3Xmethod[103X for the operation [3Xopr[103X, in the same way as
  for  [2XInstallMethod[102X  ([14X78.3-1[114X), but without the restriction that the number of
  arguments  must  match a declaration of [3Xopr[103X and without the restriction that
  [3Xargs-filts[103X imply the respective requirements of the operation [3Xopr[103X.[133X
  
  [1X78.3-3 InstallEarlyMethod[101X
  
  [33X[1;0Y[29X[2XInstallEarlyMethod[102X( [3Xopr[103X, [3Xmethod[103X ) [32X function[133X
  
  [33X[0;0Yinstalls  a special "early" function method [3Xmethod[103X for the operation [3Xopr[103X. An
  early  method  is special in that it bypasses method dispatch, and is always
  the first method to be called when invoking the operation.[133X
  
  [33X[0;0YThis  can  be  used  to  avoid method selection overhead for certain special
  cases,  i.e.,  as an optimization. Overall, we recommend to use this feature
  very sparingly, as it is tool with sharp edges: for example, any inputs that
  are  handled  by an early method can not be intercepted by a regular method,
  no  matter  how  high  its  rank  is;  this  can  preclude  other  kinds  of
  optimizations.[133X
  
  [33X[0;0YAlso,  unlike regular methods, no checks are performed on the arguments. Not
  even  the  required  filters  for the operation are tested, so early methods
  must  be  careful  in  validating  their  inputs.  This  also means that any
  operation  can  have at most one such early method for each arity (i.e., one
  early method taking 1 argument, one early method taking 2 arguments, etc.).[133X
  
  [33X[0;0YIf  an  early  method  determines  that  it is not applicable, it can resume
  regular method dispatch by invoking [2XTryNextMethod[102X ([14X78.5-1[114X).[133X
  
  [33X[0;0YFor  an  example  application  of  early  methods,  they  are  used by [2XFirst[102X
  ([14X21.20-21[114X)  to  deal with internal lists, for which computing the exact type
  (needed for method selection) can be very expensive.[133X
  
  [1X78.3-4 InstallMethodWithRandomSource[101X
  
  [33X[1;0Y[29X[2XInstallMethodWithRandomSource[102X( [3Xopr[103X, [3Xinfo[103X[, [3Xfamp[103X], [3Xargs-filts[103X[, [3Xval[103X], [3Xmethod[103X ) [32X function[133X
  [33X[1;0Y[29X[2XInstallOtherMethodWithRandomSource[102X( [3Xopr[103X, [3Xinfo[103X[, [3Xfamp[103X], [3Xargs-filts[103X[, [3Xval[103X], [3Xmethod[103X ) [32X function[133X
  
  [33X[0;0YThese  functions  are  designed  to  simplify  adding new methods for [2XRandom[102X
  ([14X30.7-1[114X),  [2XPseudoRandom[102X ([14X30.7-2[114X), and [2XRandomize[102X ([14X26.6-4[114X) to [5XGAP[105X which can be
  called both with, and without, a random source.[133X
  
  [33X[0;0YThey   accept   the   same   arguments   as   [2XInstallMethod[102X   ([14X78.3-1[114X)   and
  [2XInstallOtherMethod[102X  ([14X78.3-2[114X),  with  the  extra  requirement  that the first
  member  of [3Xargs-filts[103X must be [2XIsRandomSource[102X ([14X14.7-1[114X), and the [3Xinfo[103X argument
  is compulsory and must begin 'for a random source and'.[133X
  
  [33X[0;0YThis  function  then  installs  two  methods:  first  it calls [2XInstallMethod[102X
  ([14X78.3-1[114X)  (or [2XInstallOtherMethod[102X ([14X78.3-2[114X)) with unchanged arguments. Then it
  calls  [2XInstallMethod[102X ([14X78.3-1[114X) (or [2XInstallOtherMethod[102X ([14X78.3-2[114X)) a second time
  to  install  another  method which lacks the initial random source argument;
  this   additional   method   simply   invokes   the  original  method,  with
  [2XGlobalMersenneTwister[102X ([14X14.7-4[114X) added as first argument.[133X
  
  
  [1X78.4 [33X[0;0YApplicable Methods and Method Selection[133X[101X
  
  [33X[0;0YA  method  installed  as  above  is [13Xapplicable[113X for an arguments tuple if the
  following conditions are satisfied.[133X
  
  [33X[0;0YThe  number  of arguments equals the length of the list [3Xargs-filts[103X, the [22Xi[122X-th
  argument  lies  in  the  filter  [3Xargs-filts[103X[22X[i][122X,  and  [3Xfamp[103X returns [9Xtrue[109X when
  applied  to  the  families of the arguments. The maximal number of arguments
  supported  for  methods  is  six,  one gets an error message if one tries to
  install a method with at least seven arguments.[133X
  
  [33X[0;0YSo  [3Xargs-filt[103X  describes  conditions for each argument, and [3Xfamp[103X describes a
  relation between the arguments.[133X
  
  [33X[0;0YFor  unary  operations  such  as attributes and properties, there is no such
  relation  to  postulate,  [3Xfamp[103X is [2XReturnTrue[102X ([14X5.4-1[114X) for these operations, a
  function that always returns [9Xtrue[109X. For binary operations, the usual value of
  [3Xfamp[103X is [2XIsIdenticalObj[102X ([14X12.5-1[114X), which means that both arguments must lie in
  the same family.[133X
  
  [33X[0;0YNote  that  any  properties which occur among the filters in the filter list
  will  [13Xnot[113X be tested by the method selection if they are not yet known. (More
  exact:  if  [3Xprop[103X  is a property then the filter implicitly uses not [3Xprop[103X but
  [10XHas[3Xprop[103X[10X  and  [3Xprop[103X[10X[110X.)  If  this is desired you must explicitly enforce a test
  (see section [14X78.6[114X) below.[133X
  
  [33X[0;0YIf no method is applicable, the error message [21Xno method found[121X is signaled.[133X
  
  [33X[0;0YOtherwise,  the  applicable  method  with  highest [13Xrank[113X is selected and then
  called. This rank is usually given by the sum of the ranks of the filters in
  the  list  [3Xargs-filt[103X, [13Xincluding involved filters[113X. This value can be modified
  by  the optional [3Xval[103X argument used in the call of [2XInstallMethod[102X ([14X78.3-1[114X), as
  follows.[133X
  
  [30X    [33X[0;6YIf [3Xval[103X is an integer then add this value to the rank computed from the
        filters.[133X
  
  [30X    [33X[0;6YIf  [3Xval[103X  is a function with zero arguments then add the value returned
        by this function to the rank computed from the filters.[133X
  
  [30X    [33X[0;6YIf  [3Xval[103X  is  a list of the form [10X[ filters ][110X or [10X[ filters, abs ][110X, where
        [10Xfilters[110X  is  a  list of filters and [10Xabs[110X, if given, is an integer, then
        ignore  the filters in [3Xargs-filt[103X for the rank computation, and instead
        take  the  sum  of the filters in [10Xfilters[110X (including involved filters)
        plus [10Xabs[110X.[133X
  
  [33X[0;0YSo  the  argument [3Xval[103X can be used to raise or lower the priority of a method
  relative  to  other methods for [3Xopr[103X. The variant where [3Xval[103X is a function can
  be  useful  if  one  wants  to  shift  the rank of the method by the rank of
  certain  filters;  note  that  such  ranks need not be constant during a [5XGAP[105X
  session,  they can grow due to implications, see [2XInstallTrueMethod[102X ([14X78.8-1[114X).
  The  variant where [3Xval[103X is a list can be useful for example if one wants that
  certain  filters  that  are involved in [3Xargs-filt[103X are required but shall not
  count for the rank of the method.[133X
  
  [33X[0;0YNote  that  for operations which are constructors special rules with respect
  to   applicability   and  rank  of  the  corresponding  methods  apply  (see
  [2XNewConstructor[102X ([14X78.2-1[114X)).[133X
  
  [33X[0;0YNote  that  from  the applicable methods an efficient one shall be selected.
  This  is  a  method  that  needs  only  little  time  and  storage  for  the
  computations.[133X
  
  [33X[0;0YIt  seems to be impossible for [5XGAP[105X to select an optimal method in all cases.
  The  present  ranking  of  methods  is based on the assumption that a method
  installed  for  a special situation shall be preferred to a method installed
  for a more general situation.[133X
  
  [33X[0;0YFor example, a method for computing a Sylow subgroup of a nilpotent group is
  expected  to  be  more  efficient than a method for arbitrary groups. So the
  more  specific  method will be selected if [5XGAP[105X knows that the group given as
  argument is nilpotent.[133X
  
  [33X[0;0YOf  course  there  is  no  obvious  way  to decide between the efficiency of
  incommensurable  methods. For example, take an operation with one method for
  permutation  groups,  another method for nilpotent groups, but no method for
  nilpotent  permutation  groups,  and  call this operation with a permutation
  group known to be nilpotent.[133X
  
  
  [1X78.5 [33X[0;0YPartial Methods[133X[101X
  
  [1X78.5-1 TryNextMethod[101X
  
  [33X[1;0Y[29X[2XTryNextMethod[102X(  ) [32X function[133X
  
  [33X[0;0YAfter  a  method has been selected and called, the method may recognize that
  it   cannot   compute   the   desired   result,   and  give  up  by  calling
  [10XTryNextMethod()[110X.[133X
  
  [33X[0;0YIn  effect,  the  execution  of  the  method  is  terminated, and the method
  selection  calls  the  next  method  that  is applicable w.r.t. the original
  arguments.  In  other  words,  the  applicable  method  is  called  that  is
  subsequent  to  the  one  that called [2XTryNextMethod[102X, according to decreasing
  rank of the methods.[133X
  
  [33X[0;0YFor  example,  since  every  finite  group of odd order is solvable, one may
  install  a  method  for  the  property [2XIsSolvableGroup[102X ([14X39.15-6[114X) that checks
  whether  the size of the argument is an odd integer, returns [9Xtrue[109X if so, and
  gives up otherwise.[133X
  
  [33X[0;0YCare  is  needed  if  a  partial  method might modify the type of one of its
  arguments,  for  example  by  computing  an  attribute  or property. If this
  happens,  and  the  type has really changed, then the method should not exit
  using  [10XTryNextMethod()[110X  but  should  call  the  operation  again, as the new
  information   in   the   type  may  cause  some  methods  previously  judged
  inapplicable  to  be  applicable.  For  example,  if  the  above  method for
  [2XIsSolvableGroup[102X  ([14X39.15-6[114X)  actually  computes  the  size, (rather than just
  examining  a  stored size), then it must take care to check whether the type
  of the group has changed.[133X
  
  
  [1X78.6 [33X[0;0YRedispatching[133X[101X
  
  [33X[0;0YAs mentioned above the method selection will not test unknown properties. In
  situations,  in  which  algorithms  are  only  known  (or implemented) under
  certain conditions, however such a test might be actually desired.[133X
  
  [33X[0;0YOne  way  to  achieve  this  would  be  to  install  the method under weaker
  conditions   and   explicitly   test   the  properties  first,  exiting  via
  [2XTryNextMethod[102X  ([14X78.5-1[114X) if some of them are not fulfilled. A problem of this
  approach  however  is  that such methods then automatically are ranked lower
  and that the code does not look nice.[133X
  
  [33X[0;0YA  much  better  way is to use redispatching: Before deciding that no method
  has  been  found  one tests these properties and if they turn out to be true
  the method selection is started anew (and will then find a method).[133X
  
  [33X[0;0YThis can be achieved via the following function:[133X
  
  [1X78.6-1 RedispatchOnCondition[101X
  
  [33X[1;0Y[29X[2XRedispatchOnCondition[102X( [3Xoper[103X[, [3Xinfo[103X], [3Xfampred[103X, [3Xreqs[103X, [3Xcond[103X, [3Xval[103X ) [32X function[133X
  
  [33X[0;0YThis  function installs a method for the operation [3Xoper[103X under the conditions
  [3Xfampred[103X  and  [3Xreqs[103X  which  has absolute value [3Xval[103X; that is, the value of the
  filters  [3Xreqs[103X  is  disregarded.  [3Xcond[103X  is  a list of filters. If not all the
  values  of properties involved in these filters are already known for actual
  arguments  of  the  method,  they  are  explicitly  tested  and  if they are
  fulfilled  [13Xand[113X  stored  after  this test, the operation is dispatched again.
  Otherwise  the  method  exits with [2XTryNextMethod[102X ([14X78.5-1[114X). If supplied, [3Xinfo[103X
  should  be  a  short but informative string that describes these conditions.
  This  can be used to enforce tests like [2XIsFinite[102X ([14X30.4-2[114X) in situations when
  all  existing  methods require this property. The list [3Xcond[103X may have unbound
  entries  in  which  case  the  corresponding argument is ignored for further
  tests.[133X
  
  
  [1X78.7 [33X[0;0YImmediate Methods[133X[101X
  
  [33X[0;0YUsually a method is called only if its operation has been called and if this
  method has been selected, see [2XInstallMethod[102X ([14X78.3-1[114X).[133X
  
  [33X[0;0YFor attributes and properties, one can install also [13Ximmediate methods[113X.[133X
  
  [1X78.7-1 InstallImmediateMethod[101X
  
  [33X[1;0Y[29X[2XInstallImmediateMethod[102X( [3Xopr[103X[, [3Xinfo[103X], [3Xfilter[103X, [3Xrank[103X, [3Xmethod[103X ) [32X function[133X
  
  [33X[0;0Y[2XInstallImmediateMethod[102X installs [3Xmethod[103X as an immediate method for [3Xopr[103X, which
  must  be  an  attribute or a property, with requirement [3Xfilter[103X and rank [3Xrank[103X
  (the rank can be omitted, in which case 0 is used as rank). The rank must be
  an  integer  value  that measures the priority of [3Xmethod[103X among the immediate
  methods  for [3Xopr[103X. If supplied, [3Xinfo[103X should be a short but informative string
  that describes the situation in which the method is called.[133X
  
  [33X[0;0YAn  immediate  method  is called automatically as soon as the object lies in
  [3Xfilter[103X,  provided  that the value is not yet known. Afterwards the attribute
  setter  is  called  in order to store the value, unless the method exits via
  [2XTryNextMethod[102X ([14X78.5-1[114X).[133X
  
  [33X[0;0YNote  the  difference  to  [2XInstallMethod[102X  ([14X78.3-1[114X)  that no family predicate
  occurs  because [3Xopr[103X expects only one argument, and that [3Xfilter[103X is not a list
  of requirements but the argument requirement itself.[133X
  
  [33X[0;0YImmediate methods are thought of as a possibility for objects to gain useful
  knowledge.  They  must  not  be  used  to  force  the  storing  of  [21Xdefining
  information[121X  in  an  object.  In  other  words,  [5XGAP[105X should work even if all
  immediate   methods   are   completely  disabled.  Therefore,  the  call  to
  [2XInstallImmediateMethod[102X  installs  [3Xmethod[103X  also as an ordinary method for [3Xopr[103X
  with requirement [3Xfilter[103X.[133X
  
  [33X[0;0YNote  that  in  such  a case [5XGAP[105X executes a computation for which it was not
  explicitly  asked  by  the user. So one should install only those methods as
  immediate  methods  that  are  [13Xextremely cheap[113X. To emphasize this, immediate
  methods  are  also  called  [13Xzero  cost methods[113X. The time for their execution
  should really be approximately zero.[133X
  
  [33X[0;0YFor example, the size of a permutation group can be computed very cheaply if
  a  stabilizer chain of the group is known. So it is reasonable to install an
  immediate method for [2XSize[102X ([14X30.4-6[114X) with requirement [10XIsGroup and Tester( [3Xstab[103X[10X
  )[110X, where [3Xstab[103X is the attribute corresponding to the stabilizer chain.[133X
  
  [33X[0;0YAnother  example  would  be  the implementation of the conclusion that every
  finite  group  of  prime  power  order  is  nilpotent. This could be done by
  installing  an immediate method for the attribute [2XIsNilpotentGroup[102X ([14X39.15-3[114X)
  with  requirement  [10XIsGroup  and Tester( Size )[110X. This method would then check
  whether  the  size  is  a  finite  prime power, return [9Xtrue[109X in this case and
  otherwise  call  [2XTryNextMethod[102X  ([14X78.5-1[114X).  But this requires factoring of an
  integer,  which  cannot  be  guaranteed  to be very cheap, so one should not
  install this method as an immediate method.[133X
  
  [1X78.7-2 IsNoImmediateMethodsObject[101X
  
  [33X[1;0Y[29X[2XIsNoImmediateMethodsObject[102X( [3Xobj[103X ) [32X filter[133X
  
  [33X[0;0YIf this filter is set immediate methods will be ignored for [3Xobj[103X. This can be
  crucial  for  performance for objects like pcgs (see Section [14X45.1[114X), of which
  many  are  created, which are collections, but for which all those immediate
  methods  for  [2XIsTrivial[102X  ([14X30.4-3[114X)  et cetera do not really make sense. Other
  examples of objects in [2XIsNoImmediateMethodsObject[102X are compressed vectors and
  matrices over small finite fields, see the sections [14X23.3[114X and [14X24.14[114X.[133X
  
  
  [1X78.8 [33X[0;0YLogical Implications[133X[101X
  
  [1X78.8-1 InstallTrueMethod[101X
  
  [33X[1;0Y[29X[2XInstallTrueMethod[102X( [3Xnewfil[103X, [3Xfilt[103X ) [32X function[133X
  
  [33X[0;0YIt  may happen that a filter [3Xnewfil[103X shall be implied by another filter [3Xfilt[103X,
  which  is usually a meet of other properties, or the meet of some properties
  and  some  categories.  Such  a  logical  implication can be installed as an
  [21Ximmediate method[121X for [3Xnewfil[103X that requires [3Xfilt[103X and that always returns [9Xtrue[109X.
  (This   should   not   be   mixed   up   with   the  methods  installed  via
  [2XInstallImmediateMethod[102X  ([14X78.7-1[114X), which have to be called at runtime for the
  actual objects.)[133X
  
  [33X[0;0Y[2XInstallTrueMethod[102X  has  the  effect that [3Xnewfil[103X becomes an implied filter of
  [3Xfilt[103X, see [14X13.2[114X.[133X
  
  [33X[0;0YFor  example,  each  cyclic  group  is  abelian, each finite vector space is
  finite  dimensional,  and each division ring is integral. The first of these
  implications is installed as follows.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28XInstallTrueMethod( IsCommutative, IsGroup and IsCyclic );[128X[104X
  [4X[32X[104X
  
  [33X[0;0YContrary  to  the  immediate  methods  installed with [2XInstallImmediateMethod[102X
  ([14X78.7-1[114X), logical implications cannot be switched off. This means that after
  the  above  implication  has  been  installed, one can rely on the fact that
  every  object  in  the  filter  [10XIsGroup and IsCyclic[110X whose type gets created
  after  the  installation  of  the  implication  will  also  be in the filter
  [2XIsCommutative[102X  ([14X35.4-9[114X).  In  particular, it may happen that an object which
  existed  already  before the installation of the implication lies in [10XIsGroup
  and  IsCyclic[110X  but  not  in  [2XIsCommutative[102X ([14X35.4-9[114X). Thus it is advisable to
  install  all  implications between filters before one starts creating (types
  of) objects lying in these filters.[133X
  
  [33X[0;0YAdding  logical  implications can change the rank of filters (see [2XRankFilter[102X
  ([14X13.2-1[114X)) and consequently the rank, and so choice of methods for operations
  (see  [14X78.4[114X).  By default [2XInstallTrueMethod[102X adjusts the method selection data
  structures  to take care of this, but this process can be time-consuming, so
  functions   [2XSuspendMethodReordering[102X   ([14X78.8-2[114X)   and  [2XResumeMethodReordering[102X
  ([14X78.8-2[114X) are provided to allow control of this process.[133X
  
  [1X78.8-2 SuspendMethodReordering[101X
  
  [33X[1;0Y[29X[2XSuspendMethodReordering[102X(  ) [32X function[133X
  [33X[1;0Y[29X[2XResumeMethodReordering[102X(  ) [32X function[133X
  [33X[1;0Y[29X[2XResetMethodReordering[102X(  ) [32X function[133X
  
  [33X[0;0YThese  functions  control whether the method reordering process described in
  [2XInstallTrueMethod[102X  ([14X78.8-1[114X)  is  invoked  or  not. Since this process can be
  comparatively  time-consuming,  it  is  usually  suspended  when  a  lot  of
  implications are due to be installed, for instance when loading the library,
  or  a  package.  This  is  done  by calling [2XSuspendMethodReordering[102X once the
  installations are done, [2XResumeMethodReordering[102X should be called. These pairs
  of  calls  can  be  nested.  When  the  outermost  pair  is complete, method
  reordering   takes  place  and  is  enabled  in  [2XInstallTrueMethod[102X  ([14X78.8-1[114X)
  thereafter.  [2XResetMethodReordering[102X effectively exits all nested suspensions,
  resuming  reordering immediately. This function is mainly provided for error
  recovery and similar purposes and is called on quitting from a break loop.[133X
  
  
  [1X78.9 [33X[0;0YOperations and Mathematical Terms[133X[101X
  
  [33X[0;0YUsually  an operation stands for a mathematical concept, and the name of the
  operation  describes  this  uniquely.  Examples  are  the  property [2XIsFinite[102X
  ([14X30.4-2[114X) and the attribute [2XSize[102X ([14X30.4-6[114X). But there are cases where the same
  mathematical  term  is used to denote different concepts, for example [10XDegree[110X
  is  defined  for polynomials, group characters, and permutation actions, and
  [10XRank[110X  is  defined  for  matrices,  free  modules,  [22Xp[122X-groups,  and transitive
  permutation actions.[133X
  
  [33X[0;0YIt  is  in principle possible to install methods for the operation [10XRank[110X that
  are  applicable  to  the  different types of arguments, corresponding to the
  different  contexts.  But this is not the approach taken in the [5XGAP[105X library.
  Instead  there  are  operations  such  as  [2XRankMat[102X ([14X24.7-1[114X) for matrices and
  [2XDegreeOfCharacter[102X   ([14X72.8-4[114X)  (in  fact  these  are  attributes)  which  are
  installed as methods of the [21Xambiguous[121X operations [10XRank[110X and [10XDegree[110X.[133X
  
  [33X[0;0YThe idea is to distinguish between on the one hand different ways to compute
  the  same  thing  (e.g. different  methods  for [2X\=[102X ([14X31.11-1[114X), [2XSize[102X ([14X30.4-6[114X),
  etc.),  and on the other hand genuinely different things (such as the degree
  of a polynomial and a permutation action).[133X
  
  [33X[0;0YThe  former is the basic purpose of operations and attributes. The latter is
  provided  as a user convenience where mathematical usage forces it on us [13Xand[113X
  where  no conflicts arise. In programming the library, we use the underlying
  mathematically  precise  operations  or attributes, such as [2XRankMat[102X ([14X24.7-1[114X)
  and [2XRankAction[102X ([14X41.10-3[114X). These should be attributes if appropriate, and the
  only role of the operation [10XRank[110X is to decide which attribute the user meant.
  That  way, stored information is stored with [21Xfull mathematical precision[121X and
  is less likely to be retrieved for a wrong purpose later.[133X
  
  [33X[0;0YOne  word  about  possible  conflicts. A typical example is the mathematical
  term  [21Xcentre[121X,  which  is  defined as [22X{ x ∈ M | a * x = x * a ∀ a ∈ M }[122X for a
  magma  [22XM[122X,  and as [22X{ x ∈ L | l * x = 0 ∀ l ∈ L }[122X for a Lie algebra [22XL[122X. Here it
  is  [13Xnot[113X possible to introduce an operation [2XCentre[102X ([14X35.4-5[114X) that delegates to
  attributes  [10XCentreOfMagma[110X  and  [10XCentreOfLieAlgebra[110X, depending on the type of
  the  argument.  This  is  because any Lie algebra in [5XGAP[105X is also a magma, so
  both  [10XCentreOfMagma[110X  and  [10XCentreOfLieAlgebra[110X  would  be  defined  for  a Lie
  algebra,  with  different meaning if the characteristic is two. So we cannot
  achieve  that  one  operation  in  [5XGAP[105X  corresponds to the mathematical term
  [21Xcentre[121X.[133X
  
  [33X[0;0Y[21XAmbiguous[121X  operations  such  as  [10XRank[110X  are  declared  in  the  library  file
  [11Xlib/overload.g[111X.[133X
  
