Constructors

[stevelinton]

I think there is a bug in the way constructors are implemented.

I spotted this looking at the AbelianGroupCons constructor, which, when called with IsGroup as first argument does not consider the constructor installed for IsFpGroup. If it did the function AbelianGroup could be considerably simplified.

The problem is that when the methods are installed the implications of the first argument need to be filled in before it is stored (or possibly during method selection). Without implications IsFpGroup does not actually have all the filters set for IsGroup (they are implied but not explicit).

I'll take a look.

[stevelinton]

Thinking more about the method selection problem for constructors. Let us consider a constructor call

XCons( <filter>, <arg> )

It doesn't make any real difference if there are more arguments.

It is fairly easy to determine which methods are applicable,

Something installed with

InstallMethod( XCons, [<filter2>, <filter3>], foo)

applies provided that <filter2> implies <filter1> and <arg> lies in <filter3>.

The hard question is when another method installed with

InstallMethod( XCons, [<filter4>, <filter3>], bar)

is also applicable, which should we prefer?

At the moment we prefer the most general method, ie the one that promises the least about the object created. Technically we choose the lowest ranked of <filter2> and <filter4>. This is vaguely associated with the idea that such a method is least widely applicable, since it can only be used if the caller is willing to accept a wide range of objects. For normal operations we use the least widely applicable method that applies to the arguments.

I am coming to the view that this was a mistake (mine, I think), confusing applicability with selection. I think we should actually do the exact opposite, use the method that promises most about the object created (the highest ranked filter), since this is likely to produce the best-performing object.

In the example that started this discussion, and with the libraries we have, we should make AbelianGroupCons( IsGroup, [0]) return a PCP group rather than a general FP Group.

[stevelinton]

I just found this email from Martin Schonert which seems relevant. At that time what are now called "types" where called "kinds". This email clearly just represents one point in the discussion, since, in particular it proposes constructors that do not take the desired type as the first argument.

About Constructors

This document describes some of my thoughts about constructors in GAP 4 as of 1996/09/09.

A constructor is an operation that constructs objects. The constructor and its methods assemble the object and then call Objectify

Methods for other operations should in general not directly assemble objects and call Objectify. The reason is that other methods should in general not determine the representation of the result, but leave this decision to the constructor and its methods.

What we want (in the order of importance)

1) local correctness implies global correctness

2) constructors and their methods can select representation

3) new representations can be added without changing existing code

The current mechanism

The current mechanism uses the NewObject operation. The first argument of this operation is the kind of thing that should be constructed. NewObject is a kind-arg1 operation, i.e., dispatching is not done based on the kind of the first argument, but on the first argument itself.

One problem is, that a method is applicable if the promised kind for the result (this is basically how the reuirements for the first argument for NewObject methods should be interpreted) is a superkind of the wanted kind (this is how the first argument to NewObject should be interpreted). That means that a method is applicable if it promises less than what is wanted.

The ranking mechanism implies (in the absence of explicit adjustments) that among the applicable methods the one that promises most will be called. In many cases this will probably be a method that promises exactey what is wanted. But this will already fail, if a method promises less but requires more from the other arguments.

For example a method that promises a vectorspace and requires that the other argument is a list of cyclotomics may take precedence over a more generic method that constructs a field from a list of scalars. In this case the result would be a vectorspace, when a field was asked for.

In this case the correct result can only be guaranteed if a method promising exactely what is wanted is installed with high enough ranking. This cleary violates the rule that local correctness implies global correctness (all methods do what they claim to do, yet the result is incorrect).

An improved mechanism

The obvious improvement after the previous discussion would be to change the selection such that a method is applicable if it promises more than what is wanted.

The problem with this approach is that the interpretation of the other arguments may not be uniform among all the applicable methods.

For example assume that that we again have two methods, one to construct a vectorspace from a number of generators, and the other to construct a field from a number of generators. If a vectorspace is constructed, then both methods are applicable (since every field is a vectorspace). If the second method is selected, then the second argument is interpretated as a list of field generators. Thus one gets a vectorspace containing the generators, but very likely not the smallest one.

Again this is a problem with the rule that local correctness should imply global correctness (all methods to what they claim to do, yet the result is incorrect).

More than one constructor

The main problem above is that there is a single constructor ('NewObject'), for which no uniform interpretation of the arguments can be defined. The solution is to introduce more than one constructor, each with a well defined interpretation of the arguments. Thus there would be a constructor that constructs a vectorspace from a list of vectorspace generators, and another constructor that constructs a field from a list of field generators.

Since each constructor defines an interpretation of the arguments and each method belongs to a unique constructor, no accidently misinterpretation of the arguments can happen. Thus local correctness guarantees global correctness.

Since the constructor now determines what should be constructed (e.g., a method installed for VectorspaceGenerators "knows'' that it should construct a vectorspace), it is no longer necessary to pass the wanted kind as first argument.

It is also possible to let the constructor and its methods select a representation.

In order to allow introduction of new representations without changing existing code, this should be done as follows. For each representation there should be a single method, that constructs objects with this representation. Applicability should be determined via the requirements for the arguments (and if this is not sufficient the method must check the arguments and if the arguments are not good enough call TryNextMethod()). Those methods should be ranked such that methods producing better representations have higher ranking (because methods producing better representations will likely require more of the arguments, this will need explicit adjustments only in the cases where TryNextMethod() is used).

As an example here is how the definition of the constructor for quarternions and some of its methods might look.

Quarternion :=
   NewConstructor( "Quarternion",
       [ IsCyclotomic, IsCyclotomic ] );

IsQuarternionRep :=
   NewRepresentation( "IsQuarternionRep",
       IsPositionalRep );

InstallMethod( Quarternion,
   IsIdentical, [ IsCyclotomic, IsCyclotomic ], 0,
   function ( a, b )
   return Objectify( NewKind(QuarternionsFamily,IsQuarternionRep), [a,b] );
   end );

IsQuarternionJ0Rep :=
   NewRepresentation( "IsQuarternionJ0Rep",
       IsPositionalRep );

InstallMethod( Quarternion,
   IsIdentical, [ IsCyclotomic, IsZeroCyc ], 0,
   function ( a, b )
   return Objectify( NewKind(QuarternionsFamily,IsQuarternionJ0Rep), [a] );
   end );

IsQuarternionJ1Rep :=
   NewRepresentation( "IsQuarternionJ1Rep",
       IsPositionalRep );

InstallMethod( Quarternion,
   IsIdentical, [ IsCyclotomic, IsCyclotomic ], 1, # better than generic
   function ( a, b )
   if b <> 1 then TryNextMethod(); fi;
   return Objectify( NewKind(QuarternionsFamily,IsQuarternionJ1Rep), [a] );
   end );

One problem with this approach is that the kind of the result is not used for the ranking. For example in the above example the IsQuarternionJ1Rep method cannot tell InstallMethod that it constructs something better than the IsQuarternionRep method. Thus in order to assure that this method is first tried, it must be installed with an explicit adjustment. That could be solved by having a ValueFilter function, and requiring that methods for constructors are installed with InstallMethod(,,,ValueFilter(),)

Restricting Representation

One wish is that the caller of a constructor should be able to restrict the choices of the representation.

I am not really certain what we want here. Do we really want to be able to specify a representation (and if so is each subrepresentation acceptable?).

Or do we rather wish to state preferences (as in AsList/Enumerator). In this case it is probably best to do this with several different constructors (because as we can see with AsList/Enumerator such a wish is not specific to constructors).

This needs more discussion.

Summary

I suggest that we take the following approach.

There is a constructor (or a small number of constructors) for to each category (resp. category-like filter, such as IsGroup).

Each constructor places a well defined interpretation on its arguments.

New constructors are created with NewConstructor, which takes a name and a list of requirements for the arguments (just like NewOperation).

Each method for a constructor should construct objects in a certain representation.

As far as possible the requirements for the arguments should express what is necessary to construct an object in this representation. Where this is not sufficient, the method may contain additional checks and calls to TryNextMethod() (remember TryNextMethod() is basically a way to extend the method selection).

The adjustment for the ranking should include ValueFilter(<result-filter>), so that methods that construct something in a more restrictive representation are preferred.

Martin.

[stevelinton]

Actually this was the start of further discussion:

constructors and families.pdf Domain Constructors.pdf Mailing list Constructors Info -2.pdf Mailing list Constructors Info .pdf Bye NewObject.pdf constructors again.pdf

[stevelinton]

I've been playing with this on and off. Figuring out the correct selection order for constructors is actually horrible,

Consider SymmetricGroupCons( IsPermGroup, <int>)

There are methods that guarantee a regular permutation group and methods that guarantee a natural symmetric group. Both of these are "stronger" guarantees than IsPermGroup and which one happens to rank higher is more or less arbitrary, however you pretty clearly don't want the regular representation of S_100. Also, if you just do SymmetricGroupCons( IsGroup, 4) do you want S_4 as a permutation group or a pc-group (or a pcp-group)?

I still think that, more often than not, the method which makes the stronger guarantee is the one you want, but we will need to rank down some methods like the regular permutation groups constructors (also to avoid an infinite recursion).

[ThomasBreuer]

(Today @fingolfin pointed me to this issue.)

Concerning the ranking of applicable methods of a constructor, the documentation of NewConstructor says that the method with the smallest promises is chosen first. The manual section is perhaps to concise. Here is another argument for the chosen definition: Suppose that there is a constructor C with three methods, one for IsGroup, one for IsMatrixGroup, one for IsFFEMatrixGroup. If the method which makes the strongest guarentee would be chosen first then this one would always be chosen first, no matter whether we call C( IsGroup ) or C( IsMatrixGroup ) or C( IsFFEMatrixGroup ); thus one would not have a chance to "choose" one of the other methods.