Add an interface to Jean-Eric Pin's Semigroupe package

[nthiery]

Add an interface to Jean-Eric Pin's Semigroupe package

​http://www.liafa.jussieu.fr/~jep/semigroupes.html

An experimental spkg is now on trac; here is the patch taken from the old Sage-Combinat patch server:

:attachment:trac_8360_semigroupe-interface-nt.patch​

Status: advanced proof of concept, with interactions in both directions (building a semigroup in Semigroupe from Sage data). Main show stopper: one can only manipulate one semigroup at a time.

The following should hopefully get you started:

   sage -f http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8360/semigroupe-2.0-2.spkg
   sage -combinat update
   sage -br

   sage: semigroupe?
   sage: semigroupe.tutorial?

Beware 'sage -f an_url' does not redownload the package if sage already has a copy of it. So you may have to first do:

        rm <SAGE_ROOT>/spkg/optional/semigroupe-2.0.spkg

Update 2016-12-05: James Mitchel is reimplementing Semigroupe in C++, which will lift the main limitation (a single semigroup at a time): ​https://james-d-mitchell.github.io/semigroupsplusplus/

This could be the occasion to revive this old code.

[nthiery]

Superceedes the previous spkg

[saliola]

There seems to be a problem on a 64bit machine. After installing the spkg, the following commands will cause Sage to segfault:

sage: W = CoxeterGroup(["H",4])
sage: S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups())
sage: S.cardinality()
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in Sage.
...

The problem seems to be with compiling Semigroupe on a 64bit machine. After installing the package, the following segfaults:

karkwa: cd $SAGE_ROOT/local/bin
karkwa: Semigroupe
karkwa: ./Semigroupe
Segmentation fault
karkwa: ./SelfContainedTest 
Toto
a | 2  3  1 
b | 2  1  3 
c | 1  2  1 

Segmentation fault
karkwa: ./SemigroupeModuleTest 

a | 2  1 
b | 1  1 

Segmentation fault 

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

[aschilling]

On a 32-bit machine, I obtain the following error:

sage: S = semigroupe.AutomaticSemigroup?(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups?()) sage: S.cardinality() python(24860) malloc: * vm_allocate(size=262144) failed (error code=3) python(24860) malloc: * error: can't allocate region python(24860) malloc: * set a breakpoint in szone_error to debug memory allocation failed memory usage :

size : 2 ^{used/allocated}

0 310/312 1 21/22 2 109/109 3 73/73 4 49/50 5 5/6 6 9/9 7 3/3 8 1/1 9 1/1

10 1/2 11 0/1 12 0/0 13 0/1 14 1/1 15 25959/25959 16 0/0 17 0/0 18 0/0 19 0/0 20 0/0 21 0/0 22 0/0 23 0/0 24 0/0 25 0/0 26 0/0 27 0/0 28 0/0 29 0/0 30 0/0 31 0/0

total : 850645964/850657280 4-byte units used/allocated .../Applications/sage-4.4/devel/sage-combinat/sage/combinat/crystals$

Anne

[saliola]

In case this helps track down the issue: things seem to be working correctly in a 32bit virtual machine. I created a 32bit VirtualBox? virtual machine, installed Ubuntu 10.04, then I installed the sage-4.4.1 binary, the gap3 spkg from #8906, and the semigroupe spkg here.

[nthiery]

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

Those are little self contained test programs we had written with Florent to understand how semigroupe was working. Yes, they eventually should be turned into test suites, and run from spkg-check.

[nthiery]

Same as previous one, working on both 32bits and 64bits, but managing the patches on the semigroupe sources in a mercurial queue

[slabbe]

Note that semigroupe is now part of the experimental packages:

​http://www.sagemath.org/packages/experimental/

One can install it with the usual sage -i semigroupe-2.0-2.spkg.

next step is to make the code in sage-combinat go into sage...

[nthiery]

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch. I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

Cheers,

Nicolas

[slabbe]

Replying to nthiery:

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch.

you mean a git branch?

which patch? is it finite_semigroup-nt.patch ?

I don't see how this patch uses semigroupe.

I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360 is to make the actual semigroup into sage as it is. semigroupe was written for something no? Let's first make this available!

Then I suggest to open a ticket showing with sage command line code illustrating how the bug for creating two semigroup simultaneously is obtained. The new ticket would ask for an upstream fix.

Sébastien

[nthiery]

Replying to slabbe:

Replying to nthiery:

The next step is actually just to make a branch out of the patch.

you mean a git branch?

Yup.

which patch? is it finite_semigroup-nt.patch ? I don't see how this patch uses semigroupe.

trac_8360_semigroupe-interface-nt.patch

I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360 is to make the actual semigroup into sage as it is. semigroupe was written for something no? Let's first make this available!

Indeed, the interface was written for something. But in practice, even if I spent quite some time on it, I am actually seldom using it because that misfeature is making it relatively unusable (at least in my use-cases).

Then I suggest to open a ticket showing with sage command line code illustrating how the bug for creating two semigroup simultaneously is obtained. The new ticket would ask for an upstream fix.

That's an option. If you are convinced that:

• At some point not to far in the future the bug will be fixed upstream (upstream meaning possibly us taking the time to do the fix).

• The current code won't need serious interface change then.

Then let's go ahead. I'd love to have this code always under my fingertips. Otherwise I am a bit reluctant to put in Sage some code that we might need to remove (because unused) or change a lot later on.

At the end of the day, this would actually be best handled by putting the interface code in the spkg and not in the Sage library. I haven't checked how hard/easy it would be to handle.

Cheers,

Nicolas