312 views

Skip to first unread message

May 25, 2018, 2:08:45 AM5/25/18

to sage-devel

`sage: G = MatrixGroup([Matrix(GF(17),2,[1,1,1,0])])`

Matrix group over Finite Field of size 17 with 1 generators (

[1 1]

[1 0]

)

sage: H = MatrixGroup([Matrix(GF(17),2,[1,1,1,0])])

sage: G is H

False

The reason is probably that there is no unique representation in gap.

Is this intended or to be considered a bug?

May 25, 2018, 2:40:56 AM5/25/18

to sage-devel

Update:

Since the same is true for subgroups of permutation groups, I wonder if this is intended?

The reason I am asking is that I implemented abelian groups and their automorphisms with gap

using unique representations for subgroups. I did I miss something?

`sage: S = SymmetricGroup(4)`

sage: S1 = S.subgroup(S.gens()[:1])

sage: S2 = S.subgroup(S.gens()[:1])

sage: S1 is S2

False

Since the same is true for subgroups of permutation groups, I wonder if this is intended?

The reason I am asking is that I implemented abelian groups and their automorphisms with gap

`sage.groups.abelian_gps.abelian_group_gap sage.groups.abelian_gps.abelian_aut`

using unique representations for subgroups. I did I miss something?

May 25, 2018, 4:00:22 AM5/25/18

to sage-devel

I believe the matrix and permutation groups are quite old code, so UniqueRepresentation may not have been available at that time. The permutation group code does need updating; in particular, it is still an old-style parent:

`sage: S.__class__.__mro__`

(<class 'sage.groups.perm_gps.permgroup_named.SymmetricGroup_with_category'>,

<class 'sage.groups.perm_gps.permgroup_named.SymmetricGroup'>,

<class 'sage.groups.perm_gps.permgroup_named.PermutationGroup_symalt'>,

<class 'sage.groups.perm_gps.permgroup_named.PermutationGroup_unique'>,

<class 'sage.structure.unique_representation.CachedRepresentation'>,

<class 'sage.groups.perm_gps.permgroup.PermutationGroup_generic'>,

<type 'sage.groups.old.FiniteGroup'>,

<type 'sage.groups.old.Group'>,

<type 'sage.structure.parent_gens.ParentWithGens'>,

<type 'sage.structure.parent_base.ParentWithBase'>,

<type 'sage.structure.parent_old.Parent'>,

<type 'sage.structure.parent.Parent'>,

...

(Side note: We also should not be importing things like PermutationGroup_generic and PermutationGroupMorphism_id into the global namespace.)

I don't see a reason off-hand why these should not be UniqueRepresentation subclasses.

Best,

Travis

May 25, 2018, 12:55:38 PM5/25/18

to sage-devel

There is a very good reason why they should NOT'. Equality between subgroups is not uniquely determined by the construction parameters. It's part of the API of UniqueRepresentation that equality is identity on them.

Also, UniqueRepresentation objects make it much harder to write predictable code: because they're global objects they really MUST be immutable. No cheating! That's often quite inconvenient. Also, the processing of the construction parameters is possibly more expensive than the construction itself, so they may degrade performance. Furthermore, they have proven time and again to be very prone to memory leaks, to the point where I'd now work on the assumption that if you change an object to UniqueRepresentation, you're introducing memory leaks various places.

Also, UniqueRepresentation objects make it much harder to write predictable code: because they're global objects they really MUST be immutable. No cheating! That's often quite inconvenient. Also, the processing of the construction parameters is possibly more expensive than the construction itself, so they may degrade performance. Furthermore, they have proven time and again to be very prone to memory leaks, to the point where I'd now work on the assumption that if you change an object to UniqueRepresentation, you're introducing memory leaks various places.

May 25, 2018, 3:17:35 PM5/25/18

to sage-...@googlegroups.com

Hi!

On 2018-05-25, Nils Bruin <nbr...@sfu.ca> wrote:

>> I don't see a reason off-hand why these should not be UniqueRepresentation

>> subclasses.

>>

>

> There is a very good reason why they should NOT'. Equality between

> subgroups is not uniquely determined by the construction parameters. It's

> part of the API of UniqueRepresentation that equality is identity on them.

But they could still be CachedRepresentation. Then, if the same subgroup

is given by the same generators, it is identical, but if the same

subgroup is given by different generators, it is just equal but not

identical.

Best regards,

Simon

On 2018-05-25, Nils Bruin <nbr...@sfu.ca> wrote:

>> I don't see a reason off-hand why these should not be UniqueRepresentation

>> subclasses.

>>

>

> There is a very good reason why they should NOT'. Equality between

> subgroups is not uniquely determined by the construction parameters. It's

> part of the API of UniqueRepresentation that equality is identity on them.

is given by the same generators, it is identical, but if the same

subgroup is given by different generators, it is just equal but not

identical.

Best regards,

Simon

May 25, 2018, 3:53:15 PM5/25/18

to sage-devel

On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote:

But they could still be CachedRepresentation. Then, if the same subgroup

is given by the same generators, it is identical, but if the same

subgroup is given by different generators, it is just equal but not

identical.

But before doing so, you would need to show that in common scenarios it produces a benefit. It has three significant draw-backs:

- you'd slow down the creation of matrix groups in general, because you're requiring the system to first go and look if there already is an object like it.

- because the object you get *may* be shared with other code, you're at the mercy of that other code to not mutate it. (and you have to behave yourself too)

- it would likely introduce memory leaks (because it's the CachedRepresentation part of UniqueRepresentation that makes these leaks likely).

- you'd slow down the creation of matrix groups in general, because you're requiring the system to first go and look if there already is an object like it.

- because the object you get *may* be shared with other code, you're at the mercy of that other code to not mutate it. (and you have to behave yourself too)

- it would likely introduce memory leaks (because it's the CachedRepresentation part of UniqueRepresentation that makes these leaks likely).

May 26, 2018, 12:24:10 AM5/26/18

to sage-devel

MatrixGroups are immutable and their comparison is by checking the generators (and not isomorphism), which are essentially the construction parameters (in reality, they are the corresponding GAP group). For permutation groups, the equality seems to be isomorphism. So there is no problem for MatrixGroups being UniqueRepresentation in terms of behavior.

Best,

Travis

May 28, 2018, 7:56:35 AM5/28/18

to sage-devel

On Sat, May 26, 2018 at 6:24 AM, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:

> MatrixGroups are immutable and their comparison is by checking the

> generators (and not isomorphism), which are essentially the construction

> parameters (in reality, they are the corresponding GAP group). For

> permutation groups, the equality seems to be isomorphism. So there is no

> problem for MatrixGroups being UniqueRepresentation in terms of behavior.

+1 in principle. Nils has said to me as well that UniqueRepresention
> MatrixGroups are immutable and their comparison is by checking the

> generators (and not isomorphism), which are essentially the construction

> parameters (in reality, they are the corresponding GAP group). For

> permutation groups, the equality seems to be isomorphism. So there is no

> problem for MatrixGroups being UniqueRepresentation in terms of behavior.

(or even simply CachedRepresentation) is known for introducing memory

leaks. I certainly believe that--one doesn't come to such a

conclusion without hard-earned experience. But I'm skeptical that

that's something inherent to its design that can't be overcome with

correct use. Obviously it should not be used with classes that are

not truly immutable. I think Sage could use a better way to keep

track of and/or enforce immutability of classes (that is, instances of

classes). For example, have some base class which can be used as a

mix-in (or an ABC) that designates something as immutable, and

disallow assigning any attributes to its dict that aren't also

immutable (including of course support for all the common built-in

types).

Of course, getting something like that right is not completely trivial

and would require a lot of overhaul. I'm just surprised that it isn't

already something that is considered more systematically.

> On Saturday, May 26, 2018 at 5:53:15 AM UTC+10, Nils Bruin wrote:

>>

>>

>>

>> On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote:

>>>

>>> But they could still be CachedRepresentation. Then, if the same subgroup

>>> is given by the same generators, it is identical, but if the same

>>> subgroup is given by different generators, it is just equal but not

>>> identical.

>>>

>> But before doing so, you would need to show that in common scenarios it

>> produces a benefit. It has three significant draw-backs:

>> - you'd slow down the creation of matrix groups in general, because

>> you're requiring the system to first go and look if there already is an

>> object like it.

>> - because the object you get *may* be shared with other code, you're at

>> the mercy of that other code to not mutate it. (and you have to behave

>> yourself too)

>> - it would likely introduce memory leaks (because it's the

>> CachedRepresentation part of UniqueRepresentation that makes these leaks

>> likely).

>>

>

> You received this message because you are subscribed to the Google Groups

> "sage-devel" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-devel+...@googlegroups.com.

> To post to this group, send email to sage-...@googlegroups.com.

> Visit this group at https://groups.google.com/group/sage-devel.

> For more options, visit https://groups.google.com/d/optout.

May 28, 2018, 10:24:31 AM5/28/18

to sage-...@googlegroups.com

Hi Erik

On 2018-05-28, Erik Bray <erik....@gmail.com> wrote:

> I think Sage could use a better way to keep

> track of and/or enforce immutability of classes (that is, instances of

> classes). For example, have some base class which can be used as a

> mix-in (or an ABC) that designates something as immutable, and

> disallow assigning any attributes to its dict that aren't also

> immutable (including of course support for all the common built-in

> types).

I don't think this could possibly work. But actually that's not a Sage

problem but a Python problem: Perhaps somewhere in the Python ecosystem

such a mix-in class exists?

However, I find your notion of immutability ("do not allow assigning

attributes and make all existing attributes immutable") far too narrow.

IIRC, immutable means that once the object is created, its equivalence

class with respect to the "==" operator will be preserved no matter what

of its (no-underscore?) methods are called.

Thus, I believe it must be allowed to assign to an attribute of object X,

as long as the behaviour of X==Y remains unchanged for all objects Y

(and of course hash(X) doesn't change either).

Best regards,

Simon

On 2018-05-28, Erik Bray <erik....@gmail.com> wrote:

> I think Sage could use a better way to keep

> track of and/or enforce immutability of classes (that is, instances of

> classes). For example, have some base class which can be used as a

> mix-in (or an ABC) that designates something as immutable, and

> disallow assigning any attributes to its dict that aren't also

> immutable (including of course support for all the common built-in

> types).

problem but a Python problem: Perhaps somewhere in the Python ecosystem

such a mix-in class exists?

However, I find your notion of immutability ("do not allow assigning

attributes and make all existing attributes immutable") far too narrow.

IIRC, immutable means that once the object is created, its equivalence

class with respect to the "==" operator will be preserved no matter what

of its (no-underscore?) methods are called.

Thus, I believe it must be allowed to assign to an attribute of object X,

as long as the behaviour of X==Y remains unchanged for all objects Y

(and of course hash(X) doesn't change either).

Best regards,

Simon

May 28, 2018, 12:11:41 PM5/28/18

to sage-devel

On Monday, May 28, 2018 at 7:24:31 AM UTC-7, Simon King wrote:

However, I find your notion of immutability ("do not allow assigning

attributes and make all existing attributes immutable") far too narrow.

IIRC, immutable means that once the object is created, its equivalence

class with respect to the "==" operator will be preserved no matter what

of its (no-underscore?) methods are called.

Thus, I believe it must be allowed to assign to an attribute of object X,

as long as the behaviour of X==Y remains unchanged for all objects Y

(and of course hash(X) doesn't change either).

That's a definition of "immutable" that suffices for using things as keys in dictionaries. However, if the object you created might be referenced elsewhere, in totally unrelated code (because that code happens to have called PolynomialRing(Rationals(),names=['x','y']) as well) then you need to be a *lot* more careful. I'm not sure that locking some objects completely from mutation would be a feasible solution (it will be nearly impossible to enforce in python, and we might not be able to get proper performance with it), but if programmers don't take this very seriously we'll end up with a code base that is very difficult to reason about.

The conflation of the two notions of immutability, and the different levels of enforcement required for them, is what worries me about UniqueRepresentation. Originally, the use of UniqueRepresentation was required to ensure the system could *repeatedly* produce identical objects automatically, based on input parameters, see https://trac.sagemath.org/ticket/25388#comment:10 . It has the side-effect of allowing quick equality-by-identity checking. So it may *look* like UniqueRepresentation is a great way of speeding up "==" and "hash" for things that are immutable, but it requires a much higher level of immutability than required for hash.

(and in practice, the memory leaks caused by UniqueRepresentation bite us with clockwork regularity)

May 29, 2018, 7:01:51 AM5/29/18

to sage-devel

As a simple-minded user I stumbled over exactly this last week. I don't understand much of what this thread is discussing, but I know what a simple-minded user wants.

sage: G = GL(2,13)

sage: G = G.as_matrix_group()

sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ])

sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ])

sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ])

I expect H == H3 to say True as they are the same subgroup.

I expect H = H2 to say False, since they are not the same subgroup, even though they are isomorphic.

Instead

sage: H == H3

False

sage: matrix(GF(13),[[1,0],[1,1]]) in H3

True

sage: matrix(GF(13),[[1,0],[2,1]]) in H

True

sage: H.is_isomorphic(H3)

True

sage: H.is_isomorphic(H2)

True

sage: matrix(GF(13),[[1,0],[1,1]]) in H2

False

I though of working around it by checking if they are the same as sets, but to my surprise:

sage: Set( h for h in H ) == Set( h for h in H3 )

False

sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 )

True

In short: I consider this a bug. No matter how this is done at the back, the user expects == to mean mathematical equality, here equality of subgroups. Otherwise the function should be called subgroups_with_given_generators.

Chris

May 29, 2018, 7:15:30 AM5/29/18

to SAGE devel

This is not the only place in Sage where there is hidden structure which equality testing uses.

sage: QuadraticField(2) == QuadraticField(8)

False

This looks wrong if you naively think that you are defining a subset of CC or RR. But number fields in Sage are all defined with a fixed generating element, i.e. they are not just QQ-algebras but QQ[X]-algebras.

In the matrix subgroup case it is hard to see how H and the other subgroups are intended to be viewed if not as subsets of G. (By the way, your code raises an error for me in the assignment to H I get

AttributeError: 'sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float' object has no attribute 'gap'

)

Chris

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscribe@googlegroups.com.

May 29, 2018, 8:34:07 AM5/29/18

to sage-devel

Python that is impossible. I'm just talking about bookkeeping

indicating that objects of a class should be considered immutable, and

this fact discoverable through introspection (possibly with a small

amount of intelligence where possible, but certainly not guaranteeing

protection from programmer error).

May 30, 2018, 2:14:20 AM5/30/18

to sage-devel

I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here.

Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

Best,

Travis

May 30, 2018, 4:07:06 AM5/30/18

to SAGE devel

We should then admit that users will regularly be surprised. Perhaps this is similar to the situation for evaluating boolean expressions, where (I seem to remember) False is returned in case of "don't know". Any subgroup constructor (e.g. from generators) which results in a subgroup for which testing membership is impossible (or worse, silently returns False for every element of the ambient group) is surely not going to be very useful; and if there is a membership test then testing two subgroups for equality is easy (though of course possibly slow).

In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time.

Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

+1 to that.

Best,Travis

May 30, 2018, 4:30:04 AM5/30/18

to SAGE devel

> In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time.

I've run into this issue before (that two subgroups of the same ambient matrix group can compare as unequal, despite having the same elements). See https://trac.sagemath.org/ticket/24301, where there is some discussion between Travis and me whether this should be considered a bug.

(Of course, however one feels about that matter, there is no question that testing Set( h for h in H ) == Set( h for h in H3 ) should return True and anything else is a definite bug.)

David

May 30, 2018, 4:35:43 AM5/30/18

to sage-devel

I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here.

I am strongly in favour of changing all the other instances of wrong ==; or, at least, that they are well documented aberations. Or that we rename things (like subgroups_with_generator) to make it mathematically correct again.

If ever a user wants to check that the two subgroups were given by the same generators then he will check if .gens() are equal. Otherwise he will know that it may take time to test equality, just like with any other function.

I am happy with John's example of quadratic fields. The QQ-algebras QuadraticField(2) and QuadraticField(8) are not equal in any canonical thing they are contained in as there are two isomorphisms between them.

Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

Yes, fully agree. In fact elements should not have a "matrix" at all, since they are matrices by definition to the user. The element class, like many other group things, may want to be worked over completely. I am also often unhappy about PGL, which returns a permutation group, by the way.

Chris

May 30, 2018, 12:10:35 PM5/30/18

to sage-devel

On Wednesday, May 30, 2018 at 1:35:43 AM UTC-7, chris wuthrich wrote:

I am also often unhappy about PGL, which returns a permutation group, by the way.

Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with).

May 30, 2018, 12:26:54 PM5/30/18

to sage-devel

> Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with).

Agree, but it would be nice to say G = PGL(2,13) and then G(some matrix) to get its class or backwards to represent an element by a matrix, etc. But that is a different stroy than what this tread was about.

May 31, 2018, 6:05:26 AM5/31/18

to sage-devel

they exist but I'm still not clear on how this happens. I suspect it

could be improved, and I would like to look into how...

May 31, 2018, 6:07:11 AM5/31/18

to sage-devel

many possible definitions thereof. Are we talking equality up to

isomorphism? Etc...

May 31, 2018, 11:40:38 AM5/31/18

to sage-devel

On Thursday, May 31, 2018 at 3:07:11 AM UTC-7, Erik Bray wrote:

"mathematical equality" is also a red herring being that there are

many possible definitions thereof. Are we talking equality up to

isomorphism? Etc...

In this case it is not: presenting a group as a matrix groups means giving the group as a subgroup of GL(n,k). you could argue over WHICH GL(n,k) because we could have many isomorphic copies of those lying around, but we don't:

sage: G1=GL(2,GF(7))

sage: G2=GL(2,GF(7))

sage: G1 is G2

True

sage: G2=GL(2,GF(7))

sage: G1 is G2

True

so in Sage there is one copy of GL(n,k) that is canonized. After that it is completely clear what equality must mean: equality as subgroup. Of course, we can look at conjugacy and (for the GL's that have outer automorphisms) more generally isomorphism, but those are different questions. Presently, matrix groups are really just "generator lists" for their equality test:

sage: H1=G1.subgroup([G1.1,G1.1^2])

sage: H2=G1.subgroup([G1.1^2,G1.1])

sage: H1 == H2

sage: H2=G1.subgroup([G1.1^2,G1.1])

sage: H1 == H2

False

I'm suspicious that, although defining equality like that makes it easy to do some basic algorithmic stuff with them, such as stuffing them in a set etc., it doesn't actually help with actually working with the objects. But perhaps there are convincing examples that show that having a very cheap but wrong equality test must available for infrastructure reasons.

May 31, 2018, 11:41:55 AM5/31/18

to SAGE devel

On 31 May 2018 at 11:07, Erik Bray <erik....@gmail.com> wrote:

"mathematical equality" is also a red herring being that there are

many possible definitions thereof. Are we talking equality up to

isomorphism? Etc...

In the example posted by Chris Wuthrich, all the objects invoved were, by construction, subgroups of a common ambient group (in this case G = GF(2, 13)). In this case there is one and only one notion of equality which makes sense, and that is "having the same elements".

David

May 31, 2018, 12:24:57 PM5/31/18

to sage-devel

On Thursday, May 31, 2018 at 3:05:26 AM UTC-7, Erik Bray wrote:

Could you actually point me to one of those memory leaks? I'm sure

they exist but I'm still not clear on how this happens. I suspect it

could be improved, and I would like to look into how...

https://trac.sagemath.org/ticket/17008#comment:13 (prediction)

https://trac.sagemath.org/ticket/23851

https://trac.sagemath.org/ticket/23807#comment:14 (explanation)

https://trac.sagemath.org/ticket/14549#comment:6

https://trac.sagemath.org/ticket/18426

https://trac.sagemath.org/ticket/14356

https://trac.sagemath.org/ticket/17360

https://trac.sagemath.org/ticket/18905#comment:26

https://trac.sagemath.org/ticket/23851

https://trac.sagemath.org/ticket/23807#comment:14 (explanation)

https://trac.sagemath.org/ticket/14549#comment:6

https://trac.sagemath.org/ticket/18426

https://trac.sagemath.org/ticket/14356

https://trac.sagemath.org/ticket/17360

https://trac.sagemath.org/ticket/18905#comment:26

The main thing that strikes me is how reasonable the code that introduces the memory leak appears. That is why I expect this is a trap people will keep falling in again and again.

Jun 1, 2018, 5:24:01 AM6/1/18

to sage-devel

Suggestion:

(1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e), QQ^n).

(2) Do not use unique representation for subobjects.

(3) Give the .subobject(self, gens) method a (weak?) cache.

(4) Modify == to test equality as subobjects/subsets.

(1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e), QQ^n).

(2) Do not use unique representation for subobjects.

(3) Give the .subobject(self, gens) method a (weak?) cache.

(4) Modify == to test equality as subobjects/subsets.

Jun 3, 2018, 3:58:41 AM6/3/18

to sage-...@googlegroups.com

Hi Simon,

On 2018-06-01, Simon Brandhorst <sbran...@web.de> wrote:

> (1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e),

> QQ^n).

+1, unless you say that each set (including a subset of something)

is an ambient object.

> (2) Do not use unique representation for subobjects.

+1, except for subobjects that can be considered "ambient" themselves

(such as: The set of prime numbers in the set of integers; or GL(n,k) in

MatrixSpace(k,n))

> (3) Give the .subobject(self, gens) method a (weak?) cache.

+1, provided that it doesn't add memory leaks.

> (4) Modify == to test equality as subobjects/subsets.

-1, as I tend to think of "==" as a QUICK test.

If testing equality has a potential to hit decision problems (which

certainly is the case for subgroups), then "==" should give a swift

"True" if the two objects are easily seen to be equal (by equality of

the set of generators, say), and should return "False" otherwise.

In these cases, there ought to be a special method that the user will only

call if s/he really is prepared to wait for the answer for a couple of hours.

Note that in a way it would be nice if "==" had a ternary logic

"True/False/Unknown". But Python isn't there yet (although I do recall

that there used to be a PEP for it).

Best regards,

Simon

On 2018-06-01, Simon Brandhorst <sbran...@web.de> wrote:

> (1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e),

> QQ^n).

is an ambient object.

> (2) Do not use unique representation for subobjects.

(such as: The set of prime numbers in the set of integers; or GL(n,k) in

MatrixSpace(k,n))

> (3) Give the .subobject(self, gens) method a (weak?) cache.

> (4) Modify == to test equality as subobjects/subsets.

If testing equality has a potential to hit decision problems (which

certainly is the case for subgroups), then "==" should give a swift

"True" if the two objects are easily seen to be equal (by equality of

the set of generators, say), and should return "False" otherwise.

In these cases, there ought to be a special method that the user will only

call if s/he really is prepared to wait for the answer for a couple of hours.

Note that in a way it would be nice if "==" had a ternary logic

"True/False/Unknown". But Python isn't there yet (although I do recall

that there used to be a PEP for it).

Best regards,

Simon

Jun 3, 2018, 4:54:48 AM6/3/18

to sage-devel

> (4) Modify == to test equality as subobjects/subsets.

-1, as I tend to think of "==" as a QUICK test.

If testing equality has a potential to hit decision problems (which

certainly is the case for subgroups), then "==" should give a swift

"True" if the two objects are easily seen to be equal (by equality of

the set of generators, say), and should return "False" otherwise.

In these cases, there ought to be a special method that the user will only

call if s/he really is prepared to wait for the answer for a couple of hours.

Note that in a way it would be nice if "==" had a ternary logic

"True/False/Unknown". But Python isn't there yet (although I do recall

that there used to be a PEP for it).

I am also generally in favor of having == being a (generally) fast check. However, the symbolics code takes the opposite approach: it has the method is_trivial_equal() for quick checks but == fires up the proof engine. In terms of surprise, the fast == is clearly worse, but using is_trivially_equal() makes the code harder to read and maintain (often because of inconsistent use in regards to speed regressions).

Best,

Travis

Travis

Jun 3, 2018, 6:11:23 AM6/3/18

to sage-...@googlegroups.com

On 26/05/2018 06:24, Travis Scrimshaw wrote:

> MatrixGroups are immutable and their comparison is by checking the

> generators (and not isomorphism), which are essentially the construction

> parameters (in reality, they are the corresponding GAP group). For

> permutation groups, the equality seems to be isomorphism. So there is no

> problem for MatrixGroups being UniqueRepresentation in terms of behavior.

Jun 3, 2018, 6:26:46 AM6/3/18

to sage-...@googlegroups.com

That is

1. what Python `==` means in Sage and state it clearly in the

developer's guide and documentation

2. alternative function/operator for other kind of equalities

Note that Python == is used in non-trivial operation such as

constructing hash tables (set, dictionaries). It would be a bad

design to set == to be something else than mathematical equality

(ie equality of the subgroups).

Note also that it is perfectly fine for "==" to raise an error such as

NotImplementedError. If some algorithm is not able to decide whether

H1 and H2 are equal it can just give up.

Vincent

Jun 3, 2018, 6:38:58 AM6/3/18

to sage-...@googlegroups.com

I ask "How many apples in my basket?" to Sage I don't want an answer

like "red bikes are nicer than blue ones" because it is faster to do so.

The problem here is definitely *not* to discuss whether equality of

subgroups is decidable or fast but what "==" should be.

Jun 3, 2018, 6:45:40 AM6/3/18

to sage-devel

On Sunday, June 3, 2018 at 12:26:46 PM UTC+2, vdelecroix wrote:

Note also that it is perfectly fine for "==" to raise an error such as

NotImplementedError. If some algorithm is not able to decide whether

H1 and H2 are equal it can just give up.

The problem isn't that the computer will ever run out of things to try to show that two groups are isomorphic. In fact, quite the opposite: All RAM will be consumed while trying to show equality, and eventually the oomkiller will terminate the process.

Jun 3, 2018, 7:33:16 AM6/3/18

to sage-...@googlegroups.com

Hi Travis,

On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:

> I am also generally in favor of having == being a (generally) fast check.

> However, the symbolics code takes the opposite approach: it has the method

> is_trivial_equal() for quick checks but == fires up the proof engine.

No, that's not correct.

For symbolics, "==" only does trivial checks and leaves the equality

unevaluated otherwise, so that you need an explicit evaluation as a

bool in order to force a non-trivial computation.

Such as:

sage: (x+1)^2 == x^2+2*x+1

(x + 1)^2 == x^2 + 2*x + 1

sage: bool(_)

True

Best regards,

Simon

On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:

> I am also generally in favor of having == being a (generally) fast check.

> However, the symbolics code takes the opposite approach: it has the method

> is_trivial_equal() for quick checks but == fires up the proof engine.

For symbolics, "==" only does trivial checks and leaves the equality

unevaluated otherwise, so that you need an explicit evaluation as a

bool in order to force a non-trivial computation.

Such as:

sage: (x+1)^2 == x^2+2*x+1

(x + 1)^2 == x^2 + 2*x + 1

sage: bool(_)

True

Best regards,

Simon

Jun 3, 2018, 7:54:24 AM6/3/18

to sage-devel

Sun 2018-06-03 11:33:16 UTC, Simon King:

>

> For symbolics, "==" only does trivial checks and leaves the equality

> unevaluated otherwise, so that you need an explicit evaluation as a

> bool in order to force a non-trivial computation.

>

> Such as:

>

> sage: (x+1)^2 == x^2+2*x+1

> (x + 1)^2 == x^2 + 2*x + 1

> sage: bool(_)

> True

Actually, for symbolics, "==" always creates an equation,

and never tries to evaluate it!

A lot of confusion stems from the fact that what "==" does

depends on whether both sides are symbolic:

- if neither side is symbolic, it tests equality

- if either side is symbolic, it creates an equation

Once an equation has been created, to evaluate

whether the equation holds, one can use "bool".

Compare:

sage: 0 == 1

False

sage: SR(0) == 1

0 == 1

sage: 0 == SR(1)

0 == 1

sage: SR(0) == SR(1)

0 == 1

and never tries to evaluate it!

A lot of confusion stems from the fact that what "==" does

depends on whether both sides are symbolic:

- if neither side is symbolic, it tests equality

- if either side is symbolic, it creates an equation

Once an equation has been created, to evaluate

whether the equation holds, one can use "bool".

Compare:

sage: 0 == 1

False

sage: SR(0) == 1

0 == 1

sage: 0 == SR(1)

0 == 1

sage: SR(0) == SR(1)

0 == 1

Jun 3, 2018, 7:56:01 AM6/3/18

to sage-...@googlegroups.com

On 2018-06-03, Simon King <simon...@uni-jena.de> wrote:

> Hi Travis,

>

> On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:

>> I am also generally in favor of having == being a (generally) fast check.

>> However, the symbolics code takes the opposite approach: it has the method

>> is_trivial_equal() for quick checks but == fires up the proof engine.

>

> No, that's not correct.

>

> For symbolics, "==" only does trivial checks

That's not correct either. "==" apparently always returns an equation,
> Hi Travis,

>

> On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:

>> I am also generally in favor of having == being a (generally) fast check.

>> However, the symbolics code takes the opposite approach: it has the method

>> is_trivial_equal() for quick checks but == fires up the proof engine.

>

> No, that's not correct.

>

> For symbolics, "==" only does trivial checks

not a bool.

Jun 3, 2018, 8:40:30 AM6/3/18

to sage-...@googlegroups.com

Travis Scrimshaw wrote:

> In terms of surprise, the fast == is clearly worse,

It is not that clear to me! (What I think I'd expect if I didn't know
> In terms of surprise, the fast == is clearly worse,

Sage would be for == to compare the representation of the objects, not

their mathematical semantics, even when that semantics is unambiguous.)

--

Marc

Jun 3, 2018, 8:47:01 PM6/3/18

to sage-devel

Sorry, I was thinking of in the context of evaluating a boolean statement (such as "if x == y"). However, when checking the truth value of an expression, it does fire up the full engine:

`sage: x = var('x')`

sage: f = sin(x)^2 + cos(x)^2

sage: f

cos(x)^2 + sin(x)^2

sage: %timeit bool(f == 1)

10 loops, best of 3: 22.2 ms per loop

sage: %timeit f.is_trivially_equal(1)

The slowest run took 11394.28 times longer than the fastest. This could mean that an intermediate result is being cached.

1000000 loops, best of 3: 1.67 µs per loop

sage: bool(f == 1)

True

sage: f.is_trivially_equal(1)

False

If it was doing something trivial, both outputs would be the same and there would be far less time taken to evaluate the bool.

Best,

Travis

Jun 3, 2018, 8:51:34 PM6/3/18

to sage-devel

> I think it is a bad thing in this case for == to be equality as sets.

> Imagine if these are two really big, equal, but differently constructed

> subgroups. This would be a really long and expensive check, whereas in most

> cases, checking the defining objects are sufficient. I believe we have

> other places in Sage where == is not strict mathematical equality for

> similar reasons. -1 on changing the == semantics here.

But what if you *do* want to compare the subgroups (as Chris does). When

I ask "How many apples in my basket?" to Sage I don't want an answer

like "red bikes are nicer than blue ones" because it is faster to do so.

The problem here is definitely *not* to discuss whether equality of

subgroups is decidable or fast but what "==" should be.

So we have moved from bikeshedding to bikecoloring? :P However, that is not the correct analogy. I would say a better analogy with the apple basket is "are the trees these apples came from the same." IMO, these two issues are coupled (in part due to limitations of Python not allowing an Unknown return). One option on the table is to allow == to check a potential undecidable or very slow test.

Best,

Travis

Jun 11, 2018, 4:10:02 PM6/11/18

to sage-devel

And to illustrate with what frequency you can expect to discover these things in our code base:

Jun 12, 2018, 11:13:54 AM6/12/18

to sage-...@googlegroups.com

On 2018-05-25 10:00, Travis Scrimshaw wrote:

> I believe the matrix and permutation groups are quite old code, so

> UniqueRepresentation may not have been available at that time. The

> permutation group code does need updating; in particular, it is still an

> old-style parent:

See https://trac.sagemath.org/ticket/24612 for that. It's sort-of on my

radar since I did that for intervals (#24371), matrix spaces (#23719)

and I'm working on multi-variate polynomials (#25558).

Unfortunately, in all 3 cases above I discovered a huge mess when

looking at the code. They all involved quite a bit of work to clean that up.

Jeroen.

> I believe the matrix and permutation groups are quite old code, so

> UniqueRepresentation may not have been available at that time. The

> permutation group code does need updating; in particular, it is still an

> old-style parent:

See https://trac.sagemath.org/ticket/24612 for that. It's sort-of on my

radar since I did that for intervals (#24371), matrix spaces (#23719)

and I'm working on multi-variate polynomials (#25558).

Unfortunately, in all 3 cases above I discovered a huge mess when

looking at the code. They all involved quite a bit of work to clean that up.

Jeroen.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu