Hi Tim, Thanks for posting the example. It will be more interesting to look at when it is complete, I note for example that something is missing on line 379, there is a typo on line 394 and so far the implementation essentially only defines the category that you want to work in and the algebraic rules for the objects of that category. The algorithm itself is not yet implemented. But in terms of documentation it is clear what you intend.
I note you have a very long section of a paper by Agrawal, Kayal and Saxena. This contains a description of what the algorithm does, what its input will be and what its output will be. It has a good clear specification of the algorithm itself and proofs that the algorithm works. In an ideal world, one would have the following: 1) A description of the algorithm using symbols that are also used in the code, e.g. if some quantity is called g in the description of the algorithm, it would be called g in the implementation. 2) The proofs would be provided along with the algorithm and the proofs would use the same symbols as the description of the algorithm. 3) The semantics would be well specified, for example, what exactly happens if an integer less than 2 is input to the algorithm? 4) (Actually in an ideal world one would have a system capable of formally proving that the code does what is specified, but failing that....) one would have a test suite which checks lots of random inputs in a non-trivial way, checks that numerous important cases return correct answers and perhaps checks that the output agrees with a simpler implementation of the same basic functionality. The test code should also check that the function will produce valid output when used in any of the ways that it might be used in practice. Sometimes using the function for a subordinate computation in a higher level algorithm also finds flaws that don't show up with the best intentioned test code. 5) One would have decent user documentation, written for someone who simply wants to use the function without understanding all that much about it. This would specify what the function does, what its input should look like, what its output means, various assumptions made, the action taken by the code if invalid input is supplied, something about how the function performs and/or in what regime it should/can be used and most importantly, lots of trivial and non-trivial examples of how it can be used. Of course in the real world, one rarely has the specification of an algorithm and proofs a la AKS to incorporate, so the first step in approaching this level of rigour is to write the documentation, including rewriting the original paper to include a decent algorithm, changing all the symbols, perhaps including a more self contained and formal proof, etc. Things become much more complicated if you want your algorithm to make certain assumptions for performance reasons. In the end you might not end up implementing precisely the algorithm specified in the original paper. There might also be lots of performance hacks which make it difficult or impossible to use the same notation in the implementation as in the paper. Given that the world is not ideal one wonders what the best compromise is. I can't say much about the standard in SAGE, since the only code I looked at in detail for a patch review was Martin Albrecht's Coppersmith root finding code (though I guess I do have a *perception* of what happens in SAGE, which I attempt to comment on below). Regarding Martin's code, I found it easy to follow what the code did. Original papers were cited and symbols in the code corresponded in a fairly obvious way with the original paper. A number of examples of how to use the code were included, the code (after it had some minor fixes) did what was specified, and on the whole I felt that anyone with access to the original papers could easily understand how the code did what it did. I suppose that one quibble was that I had to look up the documentation for the LLL function in SAGE to determine how to specify some of the inputs to the function if I wanted to use more exotic functionality. But on the whole one didn't need alien intelligence to figure it out. If that code is indicative of the standard of SAGE overall, then I feel it isn't doing too badly. The test code for this module, I did not see. If I understand correctly, the examples documented with the implementation actually specify the correct results and these are tested by some automated script. I personally find this to be wholly inadequate as a testing regime for code. That sort of approach for example would not find any of the bugs I recently reported to the Magma group, nor the ones reported to the Pari group. I think the rationale for this in SAGE is that bugs show up when functions are used subordinately by higher level functions and this happens often. Perhaps there is a more comprehensive test suite which I am unaware of though. I can say more about FLINT, since I am completely familiar with most aspects of the code base. Most of what I say below is theory not practice. :-) FLINT is implemented as a series of modules, e.g. there is a major module for polynomial arithmetic over multiprecision ZZ called fmpz_poly. We made the decision a long time ago to have only a few files associated with each module. There would be a .h file for the headers and inline functions and a .c file for the implementation. Then there would be a -test.c file for the test code and a -profile.c file for profiling code. We vaguely settled on -tuning.c for automatic tuning code and -tuning.h for data specifying tuning parameters, though the standard is less well defined there. Sometimes there is a - timing.c file for producing ad hoc timings which are do not produce output in the format that our graphing code uses. 0 The choice to have a whole module in relatively few files is similar to the way NTL is constructed and does not follow the GMP standard of having a separate file for each *function* that is implemented.This choice informs the way things like documentation and testing are done. As the file for an entire module can become very large (more than 10,000 lines in some cases) it becomes necessary to be careful about what gets included in that file. I found it most convenient to include (only) a basic description of what the function does, assumptions about its inputs and outputs, semantics, etc, etc, at the point where the function was implemented. In some cases the implementation is in the .c file, in the case of inlines, it is in the .h file. It is convenient to be able to look at the documentation at the same time as looking at the implementation. (David Harvey I think encouraged documentation to be all in the same file, i.e. all in the .h file or all in the .c file, whicjh is also a sensible choice, and so these standards are applied inconsistently and many functions, especially ones I wrote, have poor or nonexistant documentation. I'm not so bothered about this, since much of what I wrote needs to be cleaned up, a process I've been working on sporadically.) User documentation is in no way contained in the code, but is handwritten and placed in a doc directory. This has advantages and disadvantages. The test code primarily compares the output of the code with a more naive implementation of the same functionality. In cases where this is not possibility, the action of a function is reversed by an inverse operation which should return the original values. The most important part of the testing strategy is that very large numbers of test cases over a wide parameter range are examined for each function. In most cases, thousands or tens of thousands of random inputs are computed. The code is written in such a way as to highlight corner cases where possible. The stategy of using sparse data (used in GMP test code) is used where possible. This has turned up an amazing number of corner cases over the months. I have seen cases where one million random inputs are given to a function and then a single corner case arises, returning the wrong answer, but not crashing the program! In recent days I have become concerned with branch level testing. This is the concept of writing test code in such a way as to give a very high probability of testing every single branch in the implementation of a function. I do this now by writing the test code and putting traces in to every branch. I check that all branches are taken often in a single test run, then remove the traces. In combination with the above stategies, this turns up vastly more corner cases!! With regard to documentation of algorithms, the aim (not the current practice) is to document these in human readable files (latexed) with a description of the algorithms used in each module, and where literature does not exist with proofs, proofs will be given of the correctness. Though really, if I have an algorithm which is not documented anywhere, I am pretty keen to just publish it. I won't say much about profiling except that we profile millions of data points against other packages and ensure FLINT is uniformly faster where possible. When it is not, we go back and write more code until it is. This is very time consuming. So does all of this work? No, not really. Someone in the SAGE group or from elsewhere will ask me, "does FLINT do X"? There will be a whole lot of enthusiasm and volunteer effort available and so I'll get enthused to implement functionality X under the assumption that someone will actually use it. I go through some small subset of the above, which takes ages, especially the debugging amd ensuring the performance of FLINT doesn't suck in comparison with alternatives. By the time all this is done and I have made an annoucement, the volunteer effort to incorporate it in SAGE or use it elsewhere has become interested in other projects, no one is interested any longer in actually using the new functionality, and/or functionality y is now found to be missing from FLINT and use of the FLINT code base becomes impractical until *that* function is implemented. On the other hand, in the mean time, SAGE has become an enormous project (and quite a success story). The breadth of coverage is staggering as are all the neat internet tools, cython and all the other SAGE spinoffs. I do have some specific concerns about SAGE: 1) The adequacy of test code to detect corner cases. 2) The way SAGE handles exceptions and special cases when interfacing with some of the underlying packages. 3) The fact that mathematics is an expansive subject, thus there is no end in sight for what can be implemented. Thus with still far too few people working on SAGE, there is little consolidation of what is already in SAGE. New volunteer effort usually focuses on implementing new functionality and often just makes the base wider rather than improving the quality of what is there. Of course this is also a strength of SAGE. 4) The time and resources of a core group of SAGE volunteers is stretched thinner and thinner, largely on account of 3. 5) I *perceive* that there is an attitude of "I've implemented algorithm x in SAGE", when in reality all that has been done is that algorithm x was previously implemented by someone else in package K and merely *wrapped* trivially in SAGE. Please don't mistake my meaning here. There is a lot of original code in SAGE implementing actual algorithms, and I'm not criticising the attitude of the hard working volunteers who contributed that. Also understand I am not criticising the ideal of not reinventing the wheel, which is again a strength of SAGE. I'm talking about distinguishing more carefully what is wrapped and what is implemented. There is also a major difference between implementing an algorithm in SAGE which might take just a few lines, based on what is already in SAGE, and then optimising that functionality, which might take hundreds or thousands of lines. 6) The performance of some functions really sucks, and quite often this is functions that have been implemented afresh. I think Tim Daly mentioned this. There also seems to be little attempt at systematically monitoring performance and making sure that the algorithms in SAGE cover a wide range of input parameters and that the functions are not just efficient for the small examples in the doctest (which often just boil down to reducing python overhead). No one is going to do this for you. The original "implementor" must take responsibility for testing, profiling and documentation of their code (build testing is a separate matter). 7) New packages seem to be suggested for inclusion in SAGE on a regular basis. This just worries me. This conjures the image of ravening wolves who cannot wait to consume (wrap) more functionality in SAGE. This has some advantages for SAGE, but on the whole I think it starts to go too far at some point. 8) I have found the documentation somewhat unhelpful so far. From the point of view of someone who does not use python it is so far hard to get familiar with SAGE compared to a much simpler (and simplistic) package such as Pari for example, though it is probably comparable with learning how to use Magma effectively. 9) There are many bugs in the trac which will never be fixed, some have been fixed or have become irrelevant, some should have been fixed a long time ago but have not, and the list grows ever longer, which is in itself worrying. I know mabshoff does an excellent job of fixing bugs related to build testing, but numerous other bugs seem to get little attention. The main focus seems to be on fixing bugs related to failing doctests. My honest gut feeling is that these could be multiplied ad infinitum if careful tests were carried out, and this concerns me. I hope I'm wrong about this. Finally I should mention some of the strengths of SAGE, since I'm obviously invested in the success of SAGE, and so do not want to criticise in a negative way: 1) SAGE build testing is excellent and improving all the time. 2) There are some really neat development, language and UI tools developed and included as part of SAGE. 3) The enthusiasm and energy of the core group of developers is outstanding. The community is very active compared to many other packages. 4) SAGE is starting to attract the interest of large corporations/ organisations. 5) The coverage of SAGE is quite good, though thin and spotty at points. 6) The regular SAGE days, developer meetings, conferences and bug/doc days are fantastic. Apologies for the long anal response. I guess in summary I share some of Tim's concerns, but I have a different perspective. I'm also no expert in these things, essentially learing about them at the same time as the other younger SAGE developers, and discussion helps focus my own ideas. Bill. On 1 May, 04:49, root <[EMAIL PROTECTED]> wrote: > >I do believe that computational mathematics needs to become a more > >rigorous subject. In fact, I'd like to see a piece of code written by > >Tim upholding the standards he is advocating, where someone has "taken > >the time", because I would like to compare it to my own code and get > >some ideas. > > >However, I think that a vast number of mathematical papers are written > >to a vastly lower standard than a lot of code. Much of what is > >written, you really do need a fields medal to understand it and papers > >are absolutely full of errors, omissions, handwaving, unchecked > >assertions, statements which have come from the mouths of other people > >but never formally proved, etc, etc. > > >Just this morning I read a note in which an important new result was > >mentioned. There was no indication of who the result was due to, what > >year they published it, or any other clues. I eventually tracked down > >another paper which mentioned it. But that paper also did not mention > >the authors of the original result. I eventually established that it > >was one or more of the authors of the very paper I was reading! They > >couldn't even reference their own work properly. Not only that, it > >appears to be an unpublished result, and may have been "proved" using > >a computer. I did however manage to find out which month they > >discovered their result, but this didn't help me recover the proof. > > >On the up side, I also read a paper which was somewhat comprehensible, > >where all the terms were defined, references were given for omitted > >proofs (and they weren't in obscure papers in Russian) and the paper > >was really doing something interesting which was not written down in a > >textbook somewhere. I have to say though, that kind of paper is about > >as rare as the code you are referring to. > > The "canonical example" which is in-plan to write is based on the > paper in src/doc/primesp.spad.pamphlet > <http://github.com/daly/axiom/tree/master/src/doc/primesp.spad.pamphlet> > I obtained permission from the authors to use this paper in Axiom as > the basis for a canonical example. It is not yet complete and fully > integrated into Axiom so I don't talk about it much but it is > "in process". > > Tim --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
