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.