Opened 6 years ago
Closed 6 years ago
#17573 closed enhancement (fixed)
Wrap Gap Structure Description
Reported by:  kcrisman  Owned by:  

Priority:  minor  Milestone:  sage6.5 
Component:  group theory  Keywords:  
Cc:  Merged in:  
Authors:  Sergey Bykov  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  294041b (Commits)  Commit:  294041b72adf4b10f44f913d7439c33c96524eee 
Dependencies:  Stopgaps: 
Description
G.gap().StructureDescription?()
Change History (41)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
To make it work on the example given on math.sx, you have to first build the associated permutation group.
sage: F.<x, y> = FreeGroup() sage: G=F / [x^2*y^1, x^3*y^2, x*y*x^1*y^1] sage: G.as_permutation_group().structure_description() 'C7'
It should probably be exposed in F
directly. As an alias to .as_permutation_group().structure_description()
if we have to, but it seems that gap does not actually need to build the permutation group in order to compute that.
Nathann
comment:3 Changed 6 years ago by
 Branch set to u/captaintrunky/wrap_gap_structure_description
comment:4 Changed 6 years ago by
 Commit set to b88e7a5c17a8e564852bef7d1a80580c04d0f114
 Status changed from new to needs_review
New commits:
b88e7a5  Added shortcut for structure_description() procedure

comment:5 Changed 6 years ago by
Hello,
The method does not look reasonable: if you ask the structure description of the free group, it will not answer. I am pretty sure that there are things to analyze structure of finitely generated groups in GAP. Moreover why 4096000 for finite groups? it is quite huge!
Vincent
comment:6 followup: ↓ 8 Changed 6 years ago by
Hello again,
It seems that it is not necessary to turn the group into a permutation group in order to get this information from gap
sage: F.<x, y> = FreeGroup() sage: G=F / [x^2*y^1, x^3*y^2, x*y*x^1*y^1] sage: G._gap_().StructureDescription() "C7"
Thus there should be no problem with a limit argument or anything.
There remains some work to do in this ticket, however, for the code of structure_description
defined in PermutationGroup
does not only return GAP's answer: there is some string rewriting going on (as well as a latex output available), and it would be better to not copy/paste it here.
Nathann
comment:7 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:8 in reply to: ↑ 6 ; followup: ↓ 9 Changed 6 years ago by
Hi, Nathan. Thanks for the feedback. I've ended up today with exactly the same solution like yours. I'll add Latex output and proper string formatting in a couple of days.
Replying to ncohen:
Hello again,
It seems that it is not necessary to turn the group into a permutation group in order to get this information from gap
sage: F.<x, y> = FreeGroup() sage: G=F / [x^2*y^1, x^3*y^2, x*y*x^1*y^1] sage: G._gap_().StructureDescription() "C7"Thus there should be no problem with a limit argument or anything.
There remains some work to do in this ticket, however, for the code of
structure_description
defined inPermutationGroup
does not only return GAP's answer: there is some string rewriting going on (as well as a latex output available), and it would be better to not copy/paste it here.Nathann
comment:9 in reply to: ↑ 8 Changed 6 years ago by
Yoooooooo !
I've ended up today with exactly the same solution like yours. I'll add Latex output and proper string formatting in a couple of days.
Great! Thanks for working on that.
Nathann
comment:10 Changed 6 years ago by
 Commit changed from b88e7a5c17a8e564852bef7d1a80580c04d0f114 to 3afe347685ec8ccf777c633f9c91bd6f334b1c83
Branch pushed to git repo; I updated commit sha1. New commits:
3afe347  Added direct call to the _gap_.StructureDescription and Latex formatting

comment:11 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:12 followup: ↓ 13 Changed 6 years ago by
Hello again,
I thought for a while about how we could avoid some copy/pate meant to handle the GAP output, then ended up using a trick. I wrote a couple of commits which do the following:
1) Move structure_description
from permgroup.py
to generic.py
without doing any modification to it
2) Update it a bit (change 'self' into 'G', add a couple of examples) then bind this function to the permutation_group
and finitely_presented_group
classes. And also to Matrix_group
while I was at it.
I had to find a workaround for this .sage()/.str()
problem you must have met yourself while you were working on this patch. This code works but there is definitely something fishy there.
Tell me what you think,
Nathann
P.S.: Those two commits can be found at: public/17573
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 6 years ago by
Hi, Nathann!
StructureDescription
routine seems to be very general, so I agree that it should be moved from a special object like permutation_group
somewhere else. I found your solution in these 2 commits reasonable for the whole problem.
Yes, I have already struggled with sage()/str()
. Maybe we should open a ticket for this? I was very surprised that such basic stuff works in different (and not obvious) ways under the same cover due to several APIs to GAP.
In conclusion, I think that this ticket may be closed  the goal is achieved.
Replying to ncohen:
Hello again,
I thought for a while about how we could avoid some copy/pate meant to handle the GAP output, then ended up using a trick. I wrote a couple of commits which do the following:
1) Move
structure_description
frompermgroup.py
togeneric.py
without doing any modification to it2) Update it a bit (change 'self' into 'G', add a couple of examples) then bind this function to the
permutation_group
andfinitely_presented_group
classes. And also toMatrix_group
while I was at it.I had to find a workaround for this
.sage()/.str()
problem you must have met yourself while you were working on this patch. This code works but there is definitely something fishy there.Tell me what you think,
Nathann
P.S.: Those two commits can be found at:
public/17573
comment:14 in reply to: ↑ 13 Changed 6 years ago by
 Branch changed from u/captaintrunky/wrap_gap_structure_description to public/17573
 Commit changed from 3afe347685ec8ccf777c633f9c91bd6f334b1c83 to 294041b72adf4b10f44f913d7439c33c96524eee
 Reviewers set to Nathann Cohen
Hello!
StructureDescription
routine seems to be very general, so I agree that it should be moved from a special object likepermutation_group
somewhere else.
Indeed.
I found your solution in these 2 commits reasonable for the whole problem.
Thanks.
Yes, I have already struggled with
sage()/str()
. Maybe we should open a ticket for this? I was very surprised that such basic stuff works in different (and not obvious) ways under the same cover due to several APIs to GAP.
To be honest I would be glad to see it fixed, but I really did not understand where the problem came from. For some reason that I do not get, calling str(x)
is not equivalent to x.__str__()
on some objects O_o
In conclusion, I think that this ticket may be closed  the goal is achieved.
Well, then you can switch the ticket's status to positive_review
and it will make it in the next release :)
Nathann
New commits:
a2d8ade  trac #17573: Move structure_description from permgroup.py to generic.py

294041b  trac #17573: update structure_descriptions and bind it to the classes

comment:15 Changed 6 years ago by
 Status changed from needs_review to positive_review
I'll try to investigate the troubles with str()/sage()
.
comment:16 followup: ↓ 17 Changed 6 years ago by
Argh, monkey patching classes to inherit your methods? Really? Am I the only one who finds this hideously ugly?
The plan is to
 get rid of
Group_old
, ie. switch permutation group to libgap  get rid of all users of the old gap pexpect interface
comment:17 in reply to: ↑ 16 ; followup: ↓ 19 Changed 6 years ago by
Argh, monkey patching classes to inherit your methods? Really? Am I the only one who finds this hideously ugly?
Where do you think that this method should be implemented in order to be only inherited by classes on which it will actually work?
Nathann
comment:18 followup: ↓ 20 Changed 6 years ago by
 Status changed from positive_review to needs_work
At the very least don't impose your idea of the degree of the dihedral group on others. Especially if your docs say that you use GAP's definititon.
comment:19 in reply to: ↑ 17 Changed 6 years ago by
Replying to ncohen:
Where do you think that this method should be implemented in order to be only inherited by classes on which it will actually work?
The standard lore is to give a generic implementation as high up as possible (e.g. in Group
) and then override it with specialized implementations where appropriate.
comment:20 in reply to: ↑ 18 Changed 6 years ago by
At the very least don't impose your idea of the degree of the dihedral group on others. Especially if your docs say that you use GAP's definititon.
None of the code that this branch contains does that. As you will find from the commits, it merely moves a function from one place to another, and the function's body has not been changed.
The standard lore is to give a generic implementation as high up as possible (e.g. in Group) and then override it with specialized implementations where appropriate.
If you do that, the function will be broken on many groups. It will not give wrong or slow results, but will just break. This is why I only added it to the classes that I found able to handle it.
I set this patch back to its original status.
Nathann
comment:21 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:22 followup: ↓ 23 Changed 6 years ago by
Fine, take a dump in our codebase.
comment:23 in reply to: ↑ 22 Changed 6 years ago by
Fine, take a dump in our codebase.
I'll be glad to improve this implementation if you eventually want to contribute some more constructive criticism.
Nathann
comment:24 followup: ↓ 25 Changed 6 years ago by
Could raising a NotImplementedError
at the highest level solve this standoff? I believe that is the usual way to deal with this.
comment:25 in reply to: ↑ 24 Changed 6 years ago by
Could raising a
NotImplementedError
at the highest level solve this standoff? I believe that is the usual way to deal with this.
This would make the function available on all groups, but then how should we make the 'real code' available in the groups that actually support it (if not by the trick used here)?
Nathann
comment:26 followup: ↓ 28 Changed 6 years ago by
Really the SX question boils down to : why is structure_description
not consistently available for every group, after all it makes sense for every group. Just monkeypatching it to yet another group addresses one particular symptom, but does nothing against the disease. I agree with KarlDieter, just raise NotImplementedError
where appropriate (e.g. there is no gap
method).
comment:27 Changed 6 years ago by
I haven't looked at the details, just trying a suggestion; perhaps in this case it isn't appropriate. There is no subclass of groups that it is available on?
Or is the problem that the code for wrapping this only should be written once, but the various subclasses it works on aren't inherited from each other, so that then one has to rewrite this code for each such class?
To Volker's point, I believe that not every group actually has this description available in gap itself, or so I read the comments and tests to imply. It isn't sufficient to have a gap method, it looks like.
comment:28 in reply to: ↑ 26 ; followup: ↓ 29 Changed 6 years ago by
Yo!
Really the SX question boils down to : why is
structure_description
not consistently available for every group, after all it makes sense for every group.
True. There are oddities in the code, however, like this MatrixGroup_gap
class whose description reads:
Matrix group over a ring that GAP understands
I took it as a hint that there will never be a working .gap()
function on all groups.
Just monkeypatching it to yet another group addresses one particular symptom, but does nothing against the disease.
Indeed. It only makes the method available on some classes where it was not.
I agree with KarlDieter, just raise
NotImplementedError
where appropriate (e.g. there is nogap
method).
Thus this patch should only move that function from one place to another. In which class do you think it should go?
Nathann
comment:29 in reply to: ↑ 28 ; followups: ↓ 30 ↓ 33 Changed 6 years ago by
Replying to ncohen:
I took it as a hint that there will never be a working
.gap()
function on all groups.
Yes. Another possible generic implementation is to call .as_permutation_group().structure_description()
, if that is available. But in some cases you'll have to raise NotImplementedError
. It is then up to author of that particular group to override structure_description
.
Thus this patch should only move that function from one place to another. In which class do you think it should go?
Evidently it should be in sage.groups.group.Group
comment:30 in reply to: ↑ 29 ; followup: ↓ 31 Changed 6 years ago by
Yes. Another possible generic implementation is to call
.as_permutation_group().structure_description()
, if that is available.
Only applies to finite groups. And will be meaningless for very large finitely presented groups.
But in some cases you'll have to raise
NotImplementedError
. It is then up to author of that particular group to overridestructure_description
.
I personally consider this bad design, and this is why I prefer to monkeypatch functions that work rather than inherit broken ones.
Evidently it should be in sage.groups.group.Group
Will you review it if I make the change?
Nathann
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 6 years ago by
Replying to ncohen:
And will be meaningless for very large finitely presented groups.
Everything is impossible to compute once you increase the problem size too far. FP groups are perhaps particularly tricky in that regard since there is no algorithm that necessarily terminates. But you should be allowed to ask the question.
I personally consider this bad design
this = consistent interfaces and specialized implementations in subclasses?
Will you review it if I make the change?
Sure
comment:32 in reply to: ↑ 31 Changed 6 years ago by
Everything is impossible to compute once you increase the problem size too far.
You are oversimplifying. Some finitely presented groups can be described very easily in either Sage or Gap, and this function can be called quickly too. Turning them into a permutation group is a very bad move.
I personally consider this bad design
this = consistent interfaces and specialized implementations in subclasses?
Calling non implemented or broken functions, and saying that "it is somebody else's problem"
It is then up to author of that particular group to override structure_description.
Nathann
comment:33 in reply to: ↑ 29 Changed 6 years ago by
Evidently it should be in sage.groups.group.Group
This change does not work: a CyclicPermutationGroup
does not inherit from Group
. If you wonder how that happens, just look at that and roll your eyes, just like me:
def is_Group(x): from sage.groups.old import Group as OldGroup return isinstance(x, (Group, OldGroup))
Nathann
comment:34 followup: ↓ 35 Changed 6 years ago by
I know. This is why I said that permutation groups need to be switched away from OldGroup.
comment:35 in reply to: ↑ 34 Changed 6 years ago by
I know. This is why I said that permutation groups need to be switched away from OldGroup.
I see. What do you propose that we do with this ticket, then? I want this feature to make it into Sage, but I cannot rewrite code that I do not understand.
Nathann
comment:36 followup: ↓ 37 Changed 6 years ago by
I would just add a method to OldGroup? that calls Group.structure_description (or whatever is appropriate) with a note that it should be removed later.
comment:37 in reply to: ↑ 36 Changed 6 years ago by
I would just add a method to OldGroup? that calls Group.structure_description (or whatever is appropriate) with a note that it should be removed later.
I am sorry to block this here, but I do not agree with this way of doing things. I can rebase this patch on another ticket if this OldGroup/Group
problem is solved soon, but otherwise I prefer this code as it is, as it does not introduce broken methods.
Nathann
comment:38 followup: ↓ 39 Changed 6 years ago by
So we'll have a consistent interface as soon as we have monkeypatched every group in Sage, excellent.
comment:39 in reply to: ↑ 38 Changed 6 years ago by
So we'll have a consistent interface as soon as we have monkeypatched every group in Sage, excellent.
Stop being difficult and let us do something useful: I am telling you that I am willing to help you or whoever will try to rewrite this code. The only thing I cannot do is rewrite it all by myself if you start taking this ticket as a hostage.
My problem is that I do not know nor understand how the group code works. I only want to add a feature, and this is the only way I found to do it without introducing broken functions (I do not want users to call a function and end up with an exception  to them that is nothing but a bug).
If you are willing to solve the root of the problem, let us do so in another ticket. I will be glad to help.
Nathann
comment:40 Changed 6 years ago by
In general I agree with ncohen here. Though:
this is the only way I found to do it without introducing broken functions (I do not want users to call a function and end up with an exception  to them that is nothing but a bug).
Well, NotImplementedError
is a special case, though. Maybe you can make the error message really really obvious that it is GAP which doesn't have this available, not that Sage has some error? Then it takes the sting away  nobody can calculate it, it's not a Sage bug at all, just the user wishing something got calculated that isn't, like an elementary integral to sin(x)/x.
comment:41 Changed 6 years ago by
 Branch changed from public/17573 to 294041b72adf4b10f44f913d7439c33c96524eee
 Resolution set to fixed
 Status changed from positive_review to closed
Something like that ?
It is in
sage.groups.perm_gps.permgroup.PermutationGroup
(relevant ticket#15128)Nathann