Sage Patch Review

I just spent a lot of time during the last few days refereeing Sage patches in the Sage trac server. Basically, we got behind and had something like nearly a 100 patches in there that were marked as "[with patch; needs review]", which means that the patch is done, and is just waiting on review. Some of the patches in this state hadn't been commented on since August! In many cases they had "bit rotted", which means that they are broken, since related parts of Sage had changed after the batches had been posted.

In June 2008 at Sage Days 8.5 we had a long meeting and setup a patch referee editor system, but it turned out to be a total failure. Our system was setup to be like a journal editor system, except with the addition of a weekly meeting. Even in person, our one and only meeting was an inefficient experience, and it never worked over irc or email.

Review is a Generic Problem

Robert Bradshaw recently went to a Google Summer of Code Mentors summit, and told me that the number one problem open source projects have that was discussed a lot at the summit is with patch review, in particular, with patches not getting reviewed in a timely fashion.

Review is also a big problem with mathematics journals, though with journals the turnaround time is expected to be months. Or even years -- I have one paper that's been in the review process at Mathematics of Computation for 3 years now, and I've almost never gotten a first referee report back from that journal in less than a year from submission time! But for some reason math journals tend to work. That said, I had some discussions with a prominent publisher about a journal that had fallen apart because the chief editor had seriously dropped the ball, and said publisher had to spend a massive amount of his own time fixing the situation.

Patch Review and Paper Review

Reviewing a math paper is a much different experience from reviewing a software patch. When one reviews a math paper, you basically get a potentially very interesting paper that is at the cutting edge of research, which you would be crazy to not want to read anyways (or you're just going to easily not recommend it for publication). When you review the paper, you excitedly read it, and if things don't make sense -- or the style is bad, or whatever -- you get to ask the author to explain clearly any point that troubles you, and the author definitely will. It's a lot of work, but it is mathematical research.

Reviewing a patch is different than reviewing a math paper. First, very often a patch fixes a subtle bug in Sage or introduces some new functionality. If the patch fixes a subtle bug, then of course the fix itself could easily introduce a new subtle bug, or maybe not really fix the bug correctly, and the referee has to figure this out. If the patch introduces new functionality, it could easily contain bugs, often bugs that the author of the patch hasn't thought about testing for. Often when refereeing a patch, I bounce it back with a use case that exhibits a bug. Some of the most common and dangerous patches are the ones that speed up existing code. These are often some slight changes in a few places, which seem safe enough, and make some code a bit faster. Last time I looked at one of these, I decided to loop over the first 100 obvious test cases -- about the 90th input crashed the new code (the old code worked fine on that example). I would have never noticed that problem had I just read the patch and tried the tests included with it; it was thus critical for me to creatively think of new tests.

Of course, when refereeing a math paper one also looks for subtle flaws and tests theorems for consistency, but still it has a different feel than refereeing a patch.
And with refereeing patches there is also a time window, which also a huge problem. Patches stop working because the rest of the Sage system evolves past them -- math papers don't just stop working because somebody out there proves more theorems.

What Should We Do?

As I said above, I believe that patch review is a major problem for the Sage project. I think the best solution is that there be one person at any given time who acts as the "patch review manager". This person could vary from month to month. This position would be the analogue of release manager or more directly of the chief editor at a traditional journal. Every few days, this person looks at the list of all patches that need review and goes through every single one, either pinging people about them, or refereeing them if possible. Said person, must be bold enough to be able to understand code anywhere in Sage, and have a good sense of who can look at what. If a person did that, I believe our patch review problem would be solved.

If we don't do this, the Sage project will operate at reduced efficiency and new and experienced developers alike will get needlessly frustrated. (NOTE: We currently do have Michael Abshoff who does pretty much what I describe above, but he has other things he should be doing, since he is release manager.) The Sage project will have a harder time reaching its goal to be a viable alternative to Magma, Maple, Mathematica, and Matlab. We have to work smarter and do a better job, for the sake of all the people out there currently forced to use Magma, Maple, Mathematica, or Matlab, instead of an open source peer reviewed scientifically viable system like Sage aims to be.

Magma and Sage

I spent the weekend working on making Sage and Magma talk to each other more robustly. Getting different math software systems to talk to each other is a problem that the OpenMath project tried to tackle since the 1990s, but they failed. Sage has out of necessity made real (rather than theoretical) progress toward this problem over the years, and what I did this weekend was a little step in the right direction for Sage.

First, I designed with Michael Abshoff a new feature for our testing framework, so we can test only optional doctests that depend on a certain component or program being present. Without a usable, efficient, and flexible testing system it is impossible to develop good code, so we had to do this. Next, I worked on fixing the numerous issues with the current Sage/Magma interface, as evidenced by many existing doctests failing. It was amusing because some of the doctests had clearly never ever succeeded, e.g., things like

 sage: magma.eval('2')       # optional
 sage: other stuff

was in the tree, where the output was simply missing.

Anyway, in fixing some of the much more interesting issues, for example, things like this that involve nested polynomial rings, I guess I came to understand better some of the subtleties of getting math software to talk with other math software.

sage: R.<x,y> = QQ[]; S.<z,w> = R[]; magma(x+z)
boom

The first important point is that one often thinks that the problem with interfacing between systems is given an object X in system (say Sage), finding a string s such that s evaluates in another system (say Magma) to something that "means the same thing" as X. This is the problem that OpenMath attempt to solve (via XML and content dictionaries), but it is not quite the right problem. Instead, given a particular mathematical software system (e.g., Magma) in a particular state, and a view of that state by another system (e.g, Sage), the problem is to then come up with a string that evaluates to the "twin image" of X in the running Magma system.

To do this right involves careful use of caching. Unless X is an atomic element (e.g., a simple thing like an integer) it's important to cache the version of X in Magma as an attribute of X itself. Let's take an example where this caching is very important and subtle. Consider our example above, which has the following Sage code as setup.

sage: R.<x,y> = QQ[]
sage: S.<z,w> = R[]

This creates the nested polynomial ring (QQ[x,y])[z,w]. The new code in sage-3.2.1 (see #4601) does the following to convert x + z to a particular Magma session. Note that the steps to convert x+z to Magma depend on the state of a particular Magma session! Anyway, Sage first gets the Magma version of S, then askes for the generator names of that object in the given Magma session. These are definitely not z,w:

sage: m = magma(S)
sage: m.gen_names()
('_sage_[4]', '_sage_[5]')

The key point is the strings returned by the gen_names command are strings that are valid in Magma and evaluate to each of the generators we're after. They depend on time -- if you did stuff in the interface earlier you would get back different numbers (not 4 and 5). Note that it's very important that the Python objects in Sage that _sage_[4] and _sage_[5] point to do not get garbage collected, since if they do then _sage_[4] and _sage_[5] also become invalid, which is not good. So it's important that the magma version (m above) of S is cached.

Next Sage gets the magma string version of each of the coefficients of the polynomial x+z (over the base ring R) using a similar process. It all works very well without memory leaks, but only because of careful track of state and caching.
And the resulting string expression involves the _sage_[...]'s.

sage: (x+z)._magma_init_(magma)
'((1/1)*1)*_sage_[4]+((1/1)*_sage_[7])*1'
sage: magma(x+z)
z + x

Notice that _magma_init_ -- the function that produces the string that evaluates to something equal to x+z in magma -- now takes as input a particular Magma session (there can be dozens of these in a given Sage session, with different Magma's running on different computers all over the world). This is a change to _magma_init_ that makes the implementation of what's described above easy. It's an API change that might also be carried over to many of the other interfaces (?).

Sage-3.2 and Mathematica 7.0

We just released sage-3.2! W00t! See for the tickets closed in this release.

There's been a lot of hyperbole due to Mathematica 7.0's recent release. A colleague of mine got a personal email from Stephen Wolfram himself, asking him to try out Mathematica 7.0, and instead my colleague forwarded the message to me and remarked that it was too late, since he had switched to Sage.

I looked over the Mathematica 7.0 release notes... and noticed that they added support for computing with Dirichlet characters. I implemented the code in Magma and Sage, and wrote a chapter in my modular forms book about computing with Dirichlet characters. So I followed the "what's new" to this Mathematica page about their new functionality for Dirichlet characters. It's sad. They give no way of specifying a character, except to give the "ith character", which is meaningless and random (and they say so) -- that's like giving a matrix over a finite field at random. All they give is a function to evaluate characters at numbers -- they don't give functions for arithmetic with them, or computing invariant such as the conductor, which is where all the real fun comes in. Boggle. Sage is light years ahead of Mathematica here.

The Mathematica release notes also brag about finally having something for finite groups, but again it is very minimal compared to what Sage provides (via GAP). Basically all they have is a bunch of tables of groups, but no real algorithms or functionality. The whole approach seems all backwards -- first one should implement algorithms for computing with groups, then use them to make tables in order to really robustify the algorithms, then compare those tables to existing tables, etc. I wonder whether the group theory data in Mathematica was computed using Gap or Magma?

I'm back from Sage Days 11 (UT Austin), which was very intense as are all Sage Days. It was a great workshop, and kickstarted many things, I hope. One very obvious big plus that came out of it was Craig Citro and Gonzalo Tornaria's work on massively optimizing the Cython-related dependency checking code in setup.py. The current implementation was some crappy thing I literally did in an hour, which has really bogged down as the Sage core library has gotten massive. Also, there's now a lot of momentum behind implementing Dokchitser's L-functions algorithm natively in Sage, which I'm greatly looking forward to -- Sourav San Gupta did much work on this at Sage Days 11, and has done a lot since too (in addition to his heavy load of grad courses). Mike Rubinstein and Rishi are wrapping Rubinstein's Lcalc using Cython as well, so Sage will soon go from the best system for computing with L-functions to even better!!

Yesterday I thought a bunch about the Sage/Magma interface and wrote several demos and test code. I'm still not 100% sure about how I want to do this -- there are numerous interesting subtleties with Magma. For example, if you create QQ[x,y] in Magma, then create QQ[x,y][z,q], the variables x,y from the first ring will *not* play nicely with the variables x,y in the second ring, which is surprising, since it is different than what happens with Sage. Anyway, this and many other problems are solvable and I'll be working on this again a lot tomorrow.

Sage Days 11 in Austin Texas is tomorrow

I'm in Seattle, it's 6pm, and Sage Days 11 is in Austin, Texas tomorrow. I'm very excited, and I'm flying there over night. On the one hand, a red eye might make me "totally exhausted" for the conference tomorrow. On the other hand, I slept an average of 2-3 hours per night for a week during Sage Days 8 last time I was in Austin, and I'm reasonably caught up on sleep.

My main goal for the workshop is to continue work of Tim Dokchitser and Jennifer Balakrishnan to create a native implementation of Dokchiter's algorithm for computing L(f,s). Having this is suddenly incredibly important to my number theory research, so I'm finally motivated to want to get it into Sage.

I'll post about the workshop in my blog here.