Call for vote about ticket #10963: axioms and more functorial constructions

[Nicolas M. Thiery]

Dear Sage developers,

This is a call for vote about the ticket:

#10963: axioms and more functorial constructions [1]

Sorry this post is long; it's trying to give a fair summary of the
huge discussion on [1]. Here is the table of contents:

- What is the ticket about
- Relevance
- History
- Debate
- Personal opinion
- Call for vote


What is the ticket about
------------------------

The main feature implemented by #10963 is an infrastructure for axioms
which enriches the current category infrastructure. Namely, if you
have a category, you can now ask for the (full) subcategory of the
objects satisfying a given axiom. For example:

sage: Groups().Finite()
Category of finite groups

Of course, this can be iterated:

sage: Magmas().Associative().Commutative().Unital().Inverse()
Category of commutative groups

By itself this is a little improvement, since it gives for example a
single entry point for all the variants of groups (or of magmas, ...);
in particular this will allow, as a later step, to remove a lot of
stuff from the global name space. This is in line with what we already
have for functorial constructions:

sage: Groups().CartesianProducts()
Category of cartesian products of groups

What's really new is that axioms play nicely with intersection:

sage: Groups() & Magmas().Commutative() & Sets().Finite()
Category of finite commutative groups

sage: (CommutativeAdditiveGroups() & Monoids()).Distributive()
Category of rings

sage: Rings().Division() & Sets().Finite() # Wedderburn's theorem
Category of finite fields

Fine, this is cute, but why is this relevant?

Relevance
---------

As time passes, the hierarchy of abstract classes for parents,
elements, and morphisms in Sage is getting larger and larger. From the
beginning, the purpose of categories in Sage has been to exploit the
strong semantic provided by the math to keep such large hierarchies
maintainable. The key is to fight hard against duplication and toward
single point of truth. Just as a trivial example, Sage deduces
automatically from the above that the abstract class for finite groups
(Groups().Finite().parent_class) should inherit from the abstract
class of groups and the abstract class of finite monoids.

Axioms are an important step to scale further by controling the
potential combinatorial explosion of the number of classes and
categories. For details, see the section on axioms in the primer [2].

History
-------

The work on this ticket started three years ago, growing up out of
strong immediate needs for the hierarchies of categories appearing in
the representation theory of semigroups or Hopf algebras. But the
infrastructure is also beneficial for non exotic categories like the
ones we have seen in the examples above. For example, it made it
practical to implement categories for the many variants of algebras
(unital or not, associative or not, commutative or not, ...)

For the design of the category infrastructure, we had some strong
source of inspiration from other systems like Axiom, MuPAD, or
Magma. As far as I know, no other system has a non trivial axiom
infrastructre like this one. Which means that it took a long time --
three years -- to analyse the needs, explore potential idioms, and
implement and reimplement the infrastructure until it felt right. It
also took as a prerequisite to fix a bunch of technical hurdles, in
particular #11935 and #13589 (thank you by the way to all who worked
and helped on those tickets, and in particular Simon and Nils).

In those three years, this ticket benefited from continuous
discussions with the other category fans, and in particular Florent
Hivert and Simon King. I also presented the framework at the occasion
of several Sage days to see how natural it would feel to new users and
developers. Most importantly, the framework was put to intensive use
in actual code to test whether the approach was sensible, viable, and
practical.

The undesirable consequence of this long history is that the ticket
has become large: it contains the axiom infrastructure, the
reorganization of the Sage categories using that infrastructure, a
bunch of new categories, and quite some related stuff that aggregated
to it along the way and would be painful to separate away (mostly
improvements to the existing functorial constructions).

Status
------

All test passes. The code is 100% doctested. All dependencies are
merged. Much time was spent on performance too, in particular checking
that the Sage startup time did not increase non trivially. Simon King
completely reviewed the code three months ago (thanks!!!) and gave a
positive review back then.

Since then, Simon, Nils, and Volker spotted and tracked down a bug
which is fixed now. I am super grateful to them because it was tricky:
the code was actually too paranoid! It did an assertion check too
early during some initialization, which caused a recursion loop
involving imports, and ended up with a silent garbage collection
issue.

This triggered a long discussion on trac where basically each and
every design choice was put again to trial, a good thing in itself!
Based on this discussion (thanks by the way to all the participants),
I added a 1500-lines overview text about axioms, including rationale
for the design decisions, the specification of the infrastructure, and
a detailed sketch of proof of correctness. This text, and some further
little improvements, are under review by Simon. There are also a few
further small suggestions from the reviewer's that I have offered to
implement, against my own opinion, if they really cared about
them. It's a matter of days before this is done.

This ticket is holding up a bunch of other tickets that depend on it,
either because they implement themselves new categories with axioms,
or use features from the ones implemented here. This includes:

- #14102: Non symmetric Macdonald polynomials. This is one of the main
outcomes of last year's ICERM semester. Up to one glitch that
appeared when merging with recent versions of Sage, it has been
ready to go since last June. It's an important feature and end users
are waiting for it.

- Work by PhD students (Jean-Baptiste Priez, ...) on Hopf algebras, a
large piece of which could go in very soon once #10963 is in. This
code is one of the major pieces of their PhD work, and they deserve
to get credit for it.

- #11111 and follow-ups on representation theory of finite dimensional
algebras and semigroups by Saliola, Aladin, Florent, myself, ...

- Further work on categories (support for morphisms, ...)

- A bunch of further stuff in the former Sage-Combinat queue

Taking this in consideration, since last June, basically all the
energy I could spend on Sage-development was devoted to finalizing
this ticket and getting it merged.

Debate
------

In my view, the most non obvious point about this ticket is whether
the general approach just makes any sense and is viable. De facto, it
took me three years to convince myself! Now I am convinced :-) And I
tried to be convincing in the documentation. Now, if you wonder about
this point, which is legitimate, actually sane, please read [2] and
decide for yourself. Comments and opinions are very welcome. Just
please create a new thread so that we don't mix the discussions.

As far as I can tell from the long trac discussion, there is a
reasonable consensus about this first point; I might be biased though.

There is also a consensus about a certain number of desirable further
features (see the TODO's in the documentation) that are best postponed
to follow-up tickets since this one is already way too large! One such
feature is to improve and make the overview text more concise, as it
matures thanks to the feedback from more and more developers reading
it.

Now, as often, there can be variants on how the approach is
implemented. And diverging opinions about those variants. Volker
dislikes some syntactical and implementation choices, and would like
to change some them. I dislike his counter propositions.

The difficulty in this discussion is that this is more about wild
guesses about the future; at this point, we lack concrete amo to back
up clear cut decisions; we just have forged different intuitions about
the right balances between different principles. That's fine by
itself: I like that developpers have opinions; it's a richness for the
Sage community. However we are stuck in an endless discussion with no
consensus emerging. And a lot of time is wasted on it when there is so
much else to do.

I think the divergence points are essentially about:

(1) The usage of nested classes: currently if Cs() is a category which
implements stuff for its subcategory Cs().A() of the objects
satisfying the axiom A, then that stuff is to be put in a class
Cs.A

Typically this class can be a nested class, or it can be put
elsewhere, e.g. in a lazily imported module, with a link from Cs;
this is very flexible.

(2) The "header" for categories with axioms

{{{
class Blah(Category):
# The currently implemented syntax
class Finite(CategoryWithAxiom):
...

# Volker's proposal, something like:
class ChooseYourName(axioms.Finite.Category):
...
}}}

plus possibly some attribute setting.

(3) Internal implementation points.


There is also a preexisting performance issue in some special
situations which is made worse by this ticket (see #15801). We have a
plan to fix it, and I am happy to settle this with Simon shortly after
#10963 is merged.

Personal opinion
----------------

About (1): we have been using the same syntax for functorial
constructions ever since the initial implementation of categories back
in 2009. It has proven a very practical way to structure the code, we
never had a problem with it, and developers learned it all right. I
don't see why we should deviate from this syntax for axioms given that
axioms are of the same nature as functorial construction, just with
more properties. If we decide for another syntax, then we should
change the syntax as well for functorial constructions. I am *not*
undertaking this change myself.

About (2): I had considered something similar earlier on, and
practical usage told me to drop it. In any cases, it's a rather small
change to the interface (one line or two per new category with
axiom). It can be implemented in a follow up ticket. Even in a couple
months there won't be hundreds of new categories with axioms
implemented out there. If we convince ourselves that we should really
change the interface, the categories with axioms in the Sage library
will be easy to fix. And we can warn and help the couple developpers
that will have implemented some in their private code.

About (3): the code is already functional. It certainly can be further
improved, but this can be postponned at no cost to followup tickets.


Conclusion: In such a situation where it comes to opinion against
opinion, I believe that decisions that have been battlefield tested
for sanity and practicality over a non trivial period (years) on a non
trivial body of code (50 categories just in the Sage library itself)
are as good as any other. The ticket is already way too big (I take my
share of the blame for it) and this is holding up the work of
many. Hence further development should go in follow up tickets,
especially if it's unclear whether they actually improve the
situation.

Let's not deviate even more from incremental development and the usual
"release early, release often".

Call for vote
-------------

[ ] Merge this ticket, and move on with further improvements in follow
up tickets
[ ] This ticket should be held up until everybody is happy
[ ] This ticket does not make any sense

Let me conclude by thanking everybody who has been involved in this
ticket. And also those who worked so hard on the new Sage development
workflow! It's been a life saver in the last months, and the previous
workflow has some responsibilities on the size of this ticket.

Cheers,
Nicolas

PS: I have tried hard to make a fair account of the situation. Yet
please read everything with a grain of salt, for this has been the
most frustrating development experience I ever had.

[1] http://trac.sagemath.org/ticket/10963
[2] http://sage.math.washington.edu/home/nthiery/sage-6.0/src/doc/output/html/en/reference/categories/sage/categories/primer.html

[Volker Braun]

First of all, Nicolas has done a lot of work on this ticket and I very much agree with his goal of providing a mixin framework for categories (called "axioms" on the ticket) so that you don't have to, say, separately write a FiniteCategory for each Category. Its also the hardest for me to say "No" since I generally want to make progress and push things forward. But I really feel uncomfortable with the syntax which IMHO deviates too much (and unnecessarily so) from normal Python.

I also think we agree that the implementation where a recursive computation is done on startup is not ideal. Relatively simple implementation mistakes in new category/axioms end up with an infinite recursion on startup, which I think is rather unhelpful for developers. There is also no way to doctest this recursion beyond "sage manages to start up". This is related to the fact that adding an assertion in the wrong place can easily lead to hard-to-debug infinite recursions, as Nicolas already mentioned. But then, this could all be improved on a later ticket.

What really bothers me with the ticket is the reliance on implicit magic over explicitly specifying relations between categories. From the ticket, this example:

sage: class Cs(Category):

....:     def super_categories(self):

....:         return [Sets()]

....:     class Finite(CategoryWithAxiom):

....:         class ParentMethods:

....:             def foo(self):

....:                 print "I am a method on finite C's"

implements

sage: P = Parent(category=Cs().Finite())

sage: P.foo()           # ok, nice

I am a method on finite C's

sage: P.is_finite()     # Where does that come from?

True

The theory here is that Sets defines a Finite axiom, and by some metaclass magic the inner class Cs.Finite ends up being a subcategory of Sets.Finite. But none of that is apparent from reading the code, you can pretty much only figure it out through reading the sage/categories/sets_cat.py or introspection if your Sage install manages to start up. It is well documented, which is nice but IMHO it would be even nicer if you could understand what is going on by just reading the code. Nicolas thinks this amount of breverity is a desirable feature, and I think we should make Cs.Finite be explicit about which axiom it implements (and, therefore, not require that it is named Cs.Finite if you don't want to). We've explored various ways to implement this syntax, either through inheritance or a class attribute, but Nicolas doesn't like any.

Nicolas keeps saying that we can change the syntax later, but I think that should be done right or not at all on this ticket (one can easily implement the axiom functionality without introducing the subclass syntax).

[Nicolas M. Thiery]

Dear Volker,

Thanks much for your time on expressing here your opinion! Hopefully
this will help others have a synthetic view of the situation and bring
in their opinion so that we can reach quickly a consensus.

Just two micro-notes.

On Fri, Mar 07, 2014 at 05:25:12AM -0800, Volker Braun wrote:
> I also think we agree that the implementation where a recursive
> computation is done on startup is not ideal. Relatively simple
> implementation mistakes in new category/axioms end up with an infinite
> recursion on startup, which I think is rather unhelpful for developers.
> There is also no way to doctest this recursion beyond "sage manages to
> start up".

To be precise, the recursion error occurs on startup only if you
fiddle with those fundamental categories that are created upon Sage's
startup. And you can already run into a similar problem without this
ticket if you screw up your implementation of the super_categories
methods (I did a bunch of times!). Recursion errors are not unusual
when you apply an algorithm for acyclic graphs on a graph that
accidently contains a cycle :-)

But yes we certainly agree that one has to be a bit more careful
because of the deduction rules, and that there is room for improvement
in the error reporting.

My point being that you can infer this information from the code by
using the math:

P is a finite Cs. A Cs is a set. Therefore P is a finite set.

This indeed requires to learn, beyond standard Python, that Cs.Finite
implements the category of finite Cs, that super_categories specifies
the relation between Cs and Sets, and that Sage will do this kind of
deduction. But that's not a whole lot of documentation to digest
either.

Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Andrew]

On Friday, 7 March 2014 23:14:44 UTC+11, Nicolas M. Thiéry wrote:

        Dear Sage developers,

This is a call for vote about the ticket:

     #10963: axioms and more functorial constructions [1]

 

Dear Nicolas,

I think that it is good that this is being done (thank you!) but, like some others, I'm not fond of the use of implicit code and black magic whenever this makes it hard to track down the real source of some of the code. If everything is well documented and explained then this is probably OK, although I feel that one of the problems with python/sage documentation is that we are encouraged to write good documentation for methods but there is little emphasis of writing a self-contained general overview of what is going on -- I've even had reviewers take this out when I have tried to write it.

To take the category framework as an example, I have fought with it and won on several occasions but it is always been a painful experience because I find that the documentation is not very helpful. Of course, perhaps it is just me but I find that most of the example code in the documentation is artificial and treats only simplified situations and that many little "secrets" are not documented at all. To be fair good documentation is hard to write, especially when you have a complex piece of code. Even so, in my experience there is quite a lot of undocumented magic in the category framework.

I hope that the documentation for the functorial constructions patch is more helpful.

Andrew

[Nicolas M. Thiery]

On Sun, Mar 09, 2014 at 05:50:29AM -0700, Andrew wrote:
> I think that it is good that this is being done (thank you!) but, like
> some others, I'm not fond of the use of implicit code and black magic
> whenever this makes it hard to track down the real source of some of the
> code.

I belong to the "some others":-) I am the first one to be struck when
this happens!

The question is whether this ticket makes things worse in
practice. After having used it quite some, I believe not, especially
since I tweaked things to this end. But I'd love to have more feedback
arising from concrete use.

> If everything is well documented and explained then this is probably
> OK, although I feel that one of the problems with python/sage
> documentation is that we are encouraged to write good documentation for
> methods but there is little emphasis of writing a self-contained general
> overview of what is going on -- I've even had reviewers take this out when
> I have tried to write it.

I agree: we need more overview documents in Sage!

> To take the category framework as an example, I have fought with it and
> won on several occasions but it is always been a painful experience
> because I find that the documentation is not very helpful. Of course,
> perhaps it is just me but I find that most of the example code in the
> documentation is artificial and treats only simplified situations and that
> many little "secrets" are not documented at all.
> To be fair good documentation is hard to write, especially when
> you have a complex piece of code. Even so, in my experience there
> is quite a lot of undocumented magic in the category framework.

Concrete examples would be helpful so that we can see if it was
actually due to "black magic in the infrastructure" as is discussed
here. Or "just" a problem of navigating the large body of generic code
implemented in the categories; problem that we would have as well with
plain abstract classes. Of course in both cases we should seek to
improve things! In particular, each areas (modules, algebras, groups,
...) should have overview documents.

> I hope that the documentation for the functorial constructions patch is
> more helpful.

I put a lot of work into that :-) It would be helpful if you could
read the updated primer [1] and the overview documentation about
axioms [2] and report!

Cheers,
Nicolas

[1] http://sage.math.washington.edu/home/nthiery/sage-6.0/src/doc/output/html/en/reference/categories/sage/categories/primer.html
[2] http://sage.math.washington.edu/home/nthiery/sage-6.0/src/doc/output/html/en/reference/categories/sage/categories/category_with_axiom.html

[Nicolas M. Thiery]

On Fri, Mar 07, 2014 at 04:32:52AM -0800, Nathann Cohen wrote:
> This ticket, like every ticket on our trac server, will be merged when the
> reviewers will be happy with it. Period.
> Respect that. Don't attempt to short-cut the review process with polls.

Certainly. I am not trying to "vote out a reviewer". The discussion
was at a stalemate due to diverging opinions on two points (a
technical point; and a point about how to proceed). I am therefore
bringing it on sage-devel to get *more* opinions so that we can
finally get to a consensus.

This already lead to some progress since this has been the occasion
for laying out the positions and divergence points, and have a serene
discussion about it. And the discussion is serene because it's about
opinions on facts, not on people.

> > Let's not deviate even more from incremental development and the usual
> > "release early, release often".

> Is that a f*** joke ? Your ticket was created three years ago, and the
> branch is thousands of lines long. Sage-combinat is all about not
> releasing early and often. It's about keeping it all unreviewed for months
> while you work on it, before creating a patch-bomb ticket on Sage's trac
> server. If you had worked incrementally this would have been settled ages
> ago, not at the last minute.

I already broke it down and got merged a bunch of stuff that could go
in earlier. Just look at the dependency list: #11224, #8327, #10193,
#12895, #14516, #14722, #13589, #14471, #15069, #15094, #11688,
#13394, #15150, #15506, #15757, #15759 (not all are mine). The list
does not even show dependencies like #11935 or #715 by Simon, which
were developed outside of the Sage-Combinat queue, and took a *long*
time to fix because they were *hard*.

The axiom infrastructure by itself is not splitable, and could not
have gone in much earlier due to the dependencies. What makes the
ticket big is the refactoring of the library using the axiom
infrastructure. I believe it's helpful to review it at the same time
as the infrastructure anyway because it illustrates how it works at a
large scale. You don't have to agree with that, but it could not have
been released earlier anyway.

The only stuff that could potentially have been split off was about
functorial constructions (maybe 20% of the patch?), and this is what I
take the blame for.


Nicolas

[Nicolas M. Thiery]

On Mon, Mar 10, 2014 at 02:00:59PM +0100, Nathann Cohen wrote:
> Still, really. I can re-read your poll a thousand times, and all I see is
> "he does not want to change his branch despite the reviewer's remark,
> so he tries to force it with a poll".

Forcing? Hmm. To force anything, I would need to have coercive power
on the community, which I certainly don't. You can see from the rest
of the post that I tried very hard to *not* put a bias in the
outcome. And if you want to know the details, I did get in touch
personally with a couple developers, asking them to "read the post,
forge your own opinion and vote accordingly; or don't vote!".

A very good measure of my lack of coercive power, and in general the
resilience of our community to pressures of all sorts, is that many
people expressed opinions, but no one voted. That's fine! Actually I
expected that: I trust people in our community to only vote if they
have a strong opinion. And it's very hard to forge oneself a strong
opinion in such a situation.

A couple other notes:

- I gladly made changes when I was convinced by them.

- It's not a change I think should be done and am just lazy to
implement. It's a change I dislike (sorry to have opinions)!

> > I already broke it down and got merged a bunch of stuff that could go
> > in earlier. Just look at the dependency list: #11224, #8327, #10193,
> > #12895, #14516, #14722, #13589, #14471, #15069, #15094, #11688,
> > #13394, #15150, #15506, #15757, #15759 (not all are mine). The list
> > does not even show dependencies like #11935 or #715 by Simon, which
> > were developed outside of the Sage-Combinat queue, and took a *long*
> > time to fix because they were *hard*.
>

> Well, I regret that all those persons had to base their own work on a
> patch that it not in yet.

The list above is about tickets #10963 depended on. Not the tickets
that depend on it. I was arguing that I had indeed been doing
iterative development.

> If it is that fundamental, please don't include a piece of code
> that you A think is not good enough or will have to be changed.

For whatever it's worth, *I* think it's good enough. And don't worry
too much, it's been one of the most reviewed patch around.

Cheers,

[John H Palmieri]

On Tuesday, March 11, 2014 12:40:41 PM UTC-7, Nathann Cohen wrote:

>    On that note, I think reviewers shouldn't hold up tickets because they
> don't like the current implementation without providing a working
> alternative and can demonstrate why it's better. 

Do you think that a patch should automatically be merged when it has been waiting for a reviewer for a long time ?

With regards to #10963, the ticket had been reviewed and indeed had gotten a positive review, and then some other people looked at it and started asking questions. So Nicolas is not trying to bypass the review process, but rather trying to sort out a disagreement among the various participants on the ticket. That's probably too brief to adequately summarize what's going on, but anyway, I think your question is not really relevant to this particular ticket.

--
John

[Nicolas M. Thiery]

Hi Simon!

On Tue, Mar 11, 2014 at 09:36:02PM +0000, Simon King wrote:
> In what location would you put the specification of an axiom and in what
> location would you put the documentation of a concrete implementation of
> the specified axiom, when axioms are lists of strings?

Just as a tiny complement for those who haven't checked the details:

- The specification of an axiom `A` currently goes in the
documentation string of the method Cs().A, where Cs is the category
defining that axiom. For example, the specifications of the axiom
Associative is defined in the documentation string of
Magmas().Associative (which technically is
Magmas.SubcategoryMethods.Associative).

Oops. Actually that's where it ought to have been; but apparently I
took the definition of associative for granted. Let me fix that now.

- Documentation of an implementation of an axiom: I assume you mean
implementation of a category with axiom. The documentation of the
category of finite groups goes in Groups.Finite.

- Axioms are indeed currently modeled by strings; on the user or
category implementer interface side, this shows up in very few spots
(essentially when you ask for the axioms satisfied by a category).
So we can easily change this later.

[Nicolas M. Thiery]

On Wed, Mar 12, 2014 at 05:24:08PM +0000, Simon King wrote:
> OK. So, Cs().A?? yields the specification and Cs.A?? the implementation.

Yes, though to get the implementation, it is preferable to use
``Cs().A()?``: it works uniformly, independently of whether this
category is implemented in Cs.A or elsewhere, or is just a join
category.