Add gappy as a standard package and use for sage's libgap interface

[embray]

Update: The successor to this ticket is #31404 which offers a different approach by using gappy directly in Sage rather than providing Sage-specific wrappers. I think it is overall a better approach for now.

Package tarball: see checksums.ini; use ./configure --enable-download-from-upstream-url to test.

gappy is a new !Python/Cython package providing a Python interface to GAP using its public "libgap" API (to the extent possible).

It is the result of extracting Sage's sage.libs.gap package into a standalone package without a dependency on Sage, so it still bears some of the legacy of that package (which will continue to be cleaned up and improved on).

One particular improvement is the help system for GAP functions--as before it is possible to extract documentation (when it exists) from the GAP docs, but this is faster now (previously the pexpect interface was still required) and can usually extract only the documentation for the queried function (previously it would also append the entire rest of the documentation chapter). It may also introduce some minor performance improvements in some areas, but it will be interesting to test this with some non-trivial examples.

This ticket is to attempt to convert sage.libs.gap to a wrapper around gappy (rather than replace it entirely). The main reason a wrapper is still needed, is in order to participate in Sage's coercion model.

The GAP interpreter wrapper class sage.libs.gap.libgap.Gap is a Parent, and its elements are instances of GapElement and subclasses thereof which are subclasses of Element.

This presents a challenge which makes wrapping gappy less straightforward than one would hope: Because the classes gappy.Gap and gappy.GapObj (its equivalent of GapElement) are cdef classes, as well as Parent and Element, it is not possible to use multiple inheritance like

class GapElement(GapObj, Element):
    ...

because their base structs are incompatible. The current workaround to this is that GapElement is a wrapper for a GapObj (which in turn wraps C-level GAP Obj pointers). This creates a bit of unfortunate overhead, albeit not much; by using cdef and cpdef methods, Cython can make the call to wrapped objects reasonably fast in many cases.

TODO

• Rework the sage.libs.gap.assigned_names and sage.libs.gap.all_documented_functions modules.

• Fix more uses within sage of the deprecated Gap.function_factory method.

• Fix more tests; all test are passing in sage.libs.gap as well as all in sage.groups.perm_gps, but some tests elsewhere are failing.

• There are miscellaneous other functions in sage.libs.gap that can probably be deprecated or removed.

Food for thought...

There are some other possible workarounds to this issue I would like to explore in the future.

The first is to change how gappy works: Rather than Gap and GapObj being cdef classes, they could be pure-Python wrappers around some cdef classes. This would again create some overhead, but hopefully not too much. Then they can participate in multiple inheritance with Sage's Parent and Element classes.

The other two, which would be much more disruptive, but also possibly useful for other packages that would like to integrate with Sage without explicitly depending on it, and have been discussed before:

1. Create a relatively Sage "base" package with little to no mathematical functionality but that provides base classes for some of Sage's structural classes such as SageObject, Parent, and Element (maybe also CategoryObject?). These base classes need not replicate the full functionality found in Sage, but just enough to provide some bootstrapping. If the package is relatively small and easily pip-installable, packages like gappy can use it as a dependency without requiring all of Sage. See Modularization of sagelib: Break out separate packages sagemath-objects, sagemath-categories #29865 for an in-progress viable prototype of this.

2. A similar but subtly different option is to make classes like SageObject, Parent, and Element into Abstract Base Classes. Classes in other packages can then be registered as psuedo-subclasses of these ABCs without directly subclassing them, so long as they implement the necessary interfaces. This option is appealing to me since it means classes from other packages can more easily interface with Sage without requiring any additional dependencies. However, it is potentially more disruptive: There isn't a way to ensure that classes which register to an ABC to provide the same C-level interface (C methods and attributes). So Cython-level code that types variables as Parent or Element won't work here, and would have to provide a separate (typically slower) code path for handle ABC pseudo-subclasses. Fortunately there is not a ton of code like this in Sage, but there is some, especially in code related to the coercion model, unsurprisingly.

CC: @tscrim @dimpase @videlec

Component: interfaces

Keywords: gap libgap gappy

Work Issues: release gappy 0.1.0 final and update spkg version before merging

Author: Erik Bray

Branch/Commit: u/embray/gappy @ 82e7e56

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/31297

[embray]

New commits:

ce1a235

Add gappy as a standard SPKG and dependency of sagelib.

[embray]

Branch: u/embray/gappy

[embray]

Author: Erik Bray

[embray]

Commit: ce1a235

[sagetrac-git]

Changed commit from ce1a235 to a8aab2a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a8aab2a

Initial work to convert sage.libs.gap to use gappy.

[mkoeppe]

Replying to @embray:

1. Create a relatively Sage "base" package with little to no mathematical functionality but that provides base classes for some of Sage's structural classes such as SageObject, Parent, and Element (maybe also CategoryObject?). These base classes need not replicate the full functionality found in Sage, but just enough to provide some bootstrapping. If the package is relatively small and easily pip-installable, packages like gappy can use it as a dependency without requiring all of Sage.

See #29865 for this

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

45b175e	Don't use the string evaluation construction for libgap permutation
197290f	Fix miscellaneous tests that broke due to different group iteration
9f621e9	Update gappy to v0.1.0a1 with some fixes for matrices and gap_function.
4839316	Miscellaneous updates to not use deprecated interfaces, particularly

[sagetrac-git]

Changed commit from a8aab2a to 4839316

[embray]

comment:10

Replying to @mkoeppe:

See #29865 for this

Thanks for pointing it out. I thought I remembered there being a ticket for that. I didn't realize you already had a prototype in the works.

[embray]

comment:11

Travis, I'm curious about your take on this, especially on the impact to permutation groups, since this partly reverts #25609, which I see you worked on. AFAICT this makes some minor performance improvements in construction of permutation groups from Sage -> GAP, but might be a little slower for going from GAP -> Sage.

[embray]

Work Issues: release gappy 0.1.0 final and update spkg version before merging

[mkoeppe]

comment:14

Big +1 on this work (but I know too little about GAP to review)

[sagetrac-git]

Changed commit from 4839316 to baa0f61

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

baa0f61

Update gappy to v0.1.0a2 which adds MacOS and Cygwin fixes.

[mkoeppe]

comment:16

A quick remark on install-requires: For prerelease versions, it's best to use the exact version; version ranges may not work (see
#30913 comment:81),
so it should be gappy ==0.1.0a0

[videlec]

comment:17

gappy is an excellent news!

I would like to bring the attention to cypari2 that played the role of gappy at the time the PARI/GP interface in Sage became an independent Cython module. In particular, if any design decision has to be made, it would be weird if they would be different for both interfaces.

First of all, two things that seem different from the rough description of the ticket

• there is no extra layer between cypari2 and Sage. Sage deals with cypari2.gen.Gen objects directly.
• cypari2 is completely agnostic to Sage and its coercion system

There was no need for coercion because the most basic possible happen : in any mixture, everything is converted to a cypari2 Gen object. Here with integers

sage: type(1 + pari(1))
<class 'cypari2.gen.Gen'>
sage: type(pari(1) + 1)
<class 'cypari2.gen.Gen'>

Here with matrices

sage: type(pari("[1, 2; 3, 4]") + matrix(2, [1,1,1,1]))
<class 'cypari2.gen.Gen'>
sage: type(matrix(2, [1,1,1,1]) + pari("[1, 2; 3, 4]"))
<class 'cypari2.gen.Gen'>

I do not see the difference here with the GAP interface. In what sort of construction the interaction with categories/coercion has to be handled? I would like a more concrete description if possible.

On a related note, cypari2 introduced the standardized name __pari__ for the method that would provide a conversion of any object to its cypari2 equivalent. That way, any Python library could make interaction with cypari2.

For the cypari2 -> Sage conversion, there is sage.libs.pari.convert_sage.gen_to_sage which is a partial but efficient converter. It introduced a slowdown in conversions PARI/GP -> Sage because the sage method on cypari2.gen.Gen (which was kept) became

cdef class Gen:
    def sage(self, locals=None):
        r"""
        Return the closest SageMath equivalent of the given PARI object.

        INPUT:

        - ``locals`` -- optional dictionary used in fallback cases that
          involve ``sage_eval``

        See :func:`~sage.libs.pari.convert_sage.gen_to_sage` for more information.
        """
        from sage.libs.pari.convert_sage import gen_to_sage
        return gen_to_sage(self, locals)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c9160c1

Further rework of 45b175e43621795f890204a9cdfb30b524f961fa which

[sagetrac-git]

Changed commit from a07f20e to c9160c1

[mkoeppe]

comment:32

Replying to @embray:

For now I could add a special case in the Integer constructor but I agree it's not ideal.

Just a quick note that the compile-time dependency of sage.rings.integer on various libraries will be a major obstacle to modularization (#29705), see #30022. This will become relevant later (perhaps in the Sage 9.5 cycle according to current plans), but it won't block immediate development, so I have no objections.

[videlec]

comment:33

Replying to @mkoeppe:

Replying to @embray:

For now I could add a special case in the Integer constructor but I agree it's not ideal.

Just a quick note that the compile-time dependency of sage.rings.integer on various libraries will be a major obstacle to modularization (#29705), see #30022. This will become relevant later (perhaps in the Sage 9.5 cycle according to current plans), but it won't block immediate development, so I have no objections.

Good point. The remark applies equally to gappy and cypari2 (and possibly other libraries).

In the same vein that Erik proposed in [comment:26] we could introduce a way to register conversions to Sage so that ZZ(my_cypari2_object) (construction from the parent) works. One would then drop the support for Integer(my_cypari2_object) (construction from the element class). There will be some time penalty in doing this. But fast conversion functions would remain available in sage.libs.pari.

On the other hand, Integer does implement a __pari__ method for conversion to cypari2. That should be changed at the same time.

[videlec]

comment:34

Replying to @videlec:

Replying to @mkoeppe:

Replying to @embray:

For now I could add a special case in the Integer constructor but I agree it's not ideal.

Just a quick note that the compile-time dependency of sage.rings.integer on various libraries will be a major obstacle to modularization (#29705), see #30022. This will become relevant later (perhaps in the Sage 9.5 cycle according to current plans), but it won't block immediate development, so I have no objections.

Good point. The remark applies equally to gappy and cypari2 (and possibly other libraries).

In the same vein that Erik proposed in [comment:26] we could introduce a way to register conversions to Sage so that ZZ(my_cypari2_object) (construction from the parent) works. One would then drop the support for Integer(my_cypari2_object) (construction from the element class). There will be some time penalty in doing this. But fast conversion functions would remain available in sage.libs.pari.

On the other hand, Integer does implement a __pari__ method for conversion to cypari2. That should be changed at the same time.

Beyond conversions, many methods of Integer depend exlicitely on __pari__

• perfect_power
• is_prime_power
• is_prime
• next_probable_prime
• next_prime
• previous_prime
• etc
  Given that, I don't see how we could make Integer independent of cypari2 without removing most of it functionalities.

[mkoeppe]

comment:35

These are just Python methods, not cdef's, right?
I think they can just be patched into the class in the same way that https://pypi.org/project/recursive-monkey-patch/ does

Crucial for the modularization is really just that the compiled Cython module no longer has such compile-time dependencies.

[videlec]

comment:36

Replying to @mkoeppe:

These are just Python methods, not cdef's, right?
I think they can just be patched into the class in the same way that https://pypi.org/project/recursive-monkey-patch/ does

Crucial for the modularization is really just that the compiled Cython module no longer has such compile-time dependencies.

Not really. Integer is an extension class, hence not extensible by any mean.

[mkoeppe]

comment:37

Thanks, you are right, of course.

[mkoeppe]

comment:38

On the other hand Element.__getattribute__ already dispatches fairly dynamically via getattr_from_category, so...

[tscrim]

comment:39

Replying to @mkoeppe:

On the other hand Element.__getattribute__ already dispatches fairly dynamically via getattr_from_category, so...

The problem with that is it is relatively slow IIRC. It might be better to have a Python subclass of Integer that can be monkey patched.

[embray]

comment:40

Replying to @mkoeppe:

Replying to @embray:

For now I could add a special case in the Integer constructor but I agree it's not ideal.

Just a quick note that the compile-time dependency of sage.rings.integer on various libraries will be a major obstacle to modularization (#29705), see #30022. This will become relevant later (perhaps in the Sage 9.5 cycle according to current plans), but it won't block immediate development, so I have no objections.

I wonder if a minimal Integer base type wouldn't also be helpful here. Again all we need are base classes that have the same struct layout, and maybe a minimum of methods defined.

[embray]

comment:41

Replying to @videlec:

Replying to @mkoeppe:

These are just Python methods, not cdef's, right?
I think they can just be patched into the class in the same way that https://pypi.org/project/recursive-monkey-patch/ does

Crucial for the modularization is really just that the compiled Cython module no longer has such compile-time dependencies.

Not really. Integer is an extension class, hence not extensible by any mean.

No, but a plain Python subclass of it is.

[embray]

comment:42

Another important example that doesn't work without coercion support which did before is evaluation of polynomials on GAP objects:

sage: from gappy import gap
sage: R.<x> = PolynomialRing(ZZ)                                                                                                                                                                 
sage: x = R.gen()                                                                                                                                                                                
sage: x(gap(1))                                                                                                                                                                               
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-20-815f7921111e> in <module>
----> 1 x(libgap(Integer(1)))

~/src/sagemath/sage/local/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_integer_dense_flint.pyx in sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint.__call__ (build/cythonized/sage/rings/polynomial/polynomial_integer_dense_flint.cpp:7957)()
    463                 return acb_z
    464 
--> 465         return Polynomial.__call__(self, *x, **kwds)
    466 
    467     cpdef Integer content(self):

~/src/sagemath/sage/local/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.__call__ (build/cythonized/sage/rings/polynomial/polynomial_element.c:9488)()
    775         # polynomial's base ring (e.g., for evaluations at integers).
    776         if not have_same_parent(a, cst):
--> 777             cst, aa = coercion_model.canonical_coercion(cst, a)
    778             # Use fast multiplication actions like matrix × scalar.
    779             # If there is no action, replace a by an element of the

~/src/sagemath/sage/local/lib/python3.6/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.canonical_coercion (build/cythonized/sage/structure/coerce.c:13758)()
   1393                 self._record_exception()
   1394 
-> 1395         raise TypeError("no common canonical parent for objects with parents: '%s' and '%s'"%(xp, yp))
   1396 
   1397 

TypeError: no common canonical parent for objects with parents: 'Integer Ring' and '<class 'gappy.gapobj.GapInteger'>'

This doesn't work with PARI gens either unless you convert the polynomial to PARI explicitly first.

[embray]

comment:43

TIL: The coercion model does in fact already support a _sage_ magic method, though it wasn't so easy for me to find: https://doc.sagemath.org/html/en/reference/coercion/sage/structure/coerce.html?highlight=_sage_#sage.structure.coerce.CoercionModel.canonical_coercion

Adding this to GapObj makes it work:

sage: one = libgap(1)                                                                                                                                                                            
sage: one._sage_()                                                                                                                                                                               
1
sage: R.<x> = PolynomialRing(ZZ)                                                                                                                                                                 
sage: x = R.gen()                                                                                                                                                                                
sage: x(one)                                                                                                                                                                                     
1
sage: a, b = coercion_model.canonical_coercion(one, x)                                                                                                                                           
sage: type(a)                                                                                                                                                                                    
<class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
sage: type(b)                                                                                                                                                                                    
<class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>

I wonder why pari_gen doesn't support this too.

[embray]

comment:44

Hrm, the problem with the above example though is that with GapElement the result of evaluating a polynomial on a GapElement is another GapElement, whereas here it just converts it to the appropriate Sage type and evaluates the polynomial on that.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0ae791e

Update gappy to v0.1.3a3 with the requisite changes needed to adapt to

[sagetrac-git]

Changed commit from c9160c1 to 0ae791e

[sagetrac-git]

Changed commit from 0ae791e to 82e7e56

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

82e7e56

A few minor test fixes:

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:49

let's do this the other way: #31404