General question on the kind of things we want in Sage
Nathann Cohen
I was just wondering about the kind of algorithms we want in Sage. For example, if someone in my lab finds out a brand new algorithm to compute a brand-new invariant for a pretty restrictive ( but brand-new, too ) class of graphs, do we want to have it included in Sage ?
My answer, for the moment, is no... I was thinking we only wanted to see in Sage things that may be useful to everybody, and let people write their own functions, but...
- There are many NP-complete problems that are known to be polynomial on restrictive class of instances. Does that mean we will only use the "general" ( and inefficien ) algorithms to solve these problems in Sage for instances that are known to be easy ?
- When I try to promote Sage around me, I never forget to mention the fact that it would be a pretty good way to exchange implementation of algorithms in a "common" lamguage, as there are ( or there will be ) libraries dealing with every structure ( or Category ? ^^; I am quite ignorant on that field ) the mathematical world can create.
Could it be good for sage to.... I do not know, perhaps become some kind of library of published algorithms ? Should we be thinking about ways to let used find "the algorithm described in paper XXX for journal XXX number XX pages XX-XX" ?
The thing is that I am tempted ( for the Graph class ) to write many functions I find useful, but these functions would very quickly crowd the list of Graph methods... For example I am interested in computing orientations of graphs, and there may be many functions needed... For example, how could I include 10 or 20 functions dealing with one particular problem of graphs without quickly transforming this already quite crowded class in something impossible to browse ?
These may be questions to ask in several years... But Sage is growing pretty quickly, though O_o
Thanks !!!
Nathann
Rob Beezer
> Could it be good for sage to.... I do not know, perhaps become some kind of
> library of published algorithms ? Should we be thinking about ways to let
> used find "the algorithm described in paper XXX for journal XXX number XX
> pages XX-XX" ?
idea of Sage as a repository of mathematical knowledge. For example,
docstrings can contain citations to articles or monographs. Sometimes
doctests can be based on theorems - create some object randomly, then
test if two seemingly unrelated computations are equal, as guaranteed
according to a theorem. Having two algorithms implemented for
something, and then a discussion of cases when one is superior, or
even hard-coding the choice is another piece of knowledge embedded in
Sage. Having docstrings close to the code, being open source, and
making docstrings and source code so easy to access, makes it easy to
explain, accumulate and organize a wealth of mathematical knowledge as
a side-effect, and I think this is another big advantage to an open
source approach to this class of software.
I know I've learned lots of mathematics that is new to me since
becoming involved, and in my contributions I've tried when possible to
reflect the above philosophy.
Rob
Minh Nguyen
On Fri, Sep 18, 2009 at 1:00 AM, Nathann Cohen <nathan...@gmail.com> wrote:
<SNIP>
> The thing is that I am tempted ( for the Graph class ) to write many
> functions I find useful, but these functions would very quickly crowd the
> list of Graph methods... For example I am interested in computing
> orientations of graphs, and there may be many functions needed... For
> example, how could I include 10 or 20 functions dealing with one particular
> problem of graphs without quickly transforming this already quite crowded
> class in something impossible to browse ?
Spending some time to think about design issues would help you in
organizing your functions, methods, and classes. Before start coding,
I would spend hours or a few days designing my function, method, or
class. This process would include:
* A meaningful name for the function, method, or class.
* Document what that function, method or class does. This should
include references to published work where appropriate. Remember that
in a few weeks or months, you would likely forget what your code does.
But people would still want to maintain your code. You code and write
documentation in order to minimize the learning curve of people who
would need to use your code, expand on it, or debug it.
* Give a high level explanation of the algorithm you're using, not
just the reference where one can read up on the algorithm.
* Clearly explain both the input and output.
* Write pseudo code to get a feel for the structure of the function,
method or class.
With proper designing, the name of your module (if you're going to
write a separate module on some area of graph theory) would give an
indication of its content. If you think that the graph theory
functions you will implement would be within a narrow area of graph
theory, you might want to consider making them into a separate module.
Or better yet, figure out if you can organize those 10 to 20 functions
into a number of modules, and put all of those specialized modules
within a subdirectory.
For example, when I first started on expanding the crypto stuff, I
wanted to implemented a number of block functions. Man, there are
dozens of them around these days. So I created a subdirectory under
crypto called "block_cipher". I then implemented various block ciphers
in different modules, organizing them under
"sage/crypto/block_cipher". If people want to use those block ciphers,
they can import them.
> These may be questions to ask in several years... But Sage is growing pretty
> quickly, though O_o
A problem with open source software projects like Sage is a lack of
reviewer time. There are about 100 tickets at the moment needing
review, but people who are interested in getting them in don't have
time to spare or don't have the necessary maths background to properly
review. The upcoming review day next week should cut down on the
number of tickets needing review. Small changes (a few new functions
per ticket) are usually easier to review than big changes (a few new
modules per ticket).
In any case, feel free to ask more questions if you want
clarification. Or am I missing the point you want to make?
--
Regards
Minh Van Nguyen
Jason Grout
> Hello !!!
>
> I was just wondering about the kind of algorithms we want in Sage. For
> example, if someone in my lab finds out a brand new algorithm to compute
> a brand-new invariant for a pretty restrictive ( but brand-new, too )
> class of graphs, do we want to have it included in Sage ?
Yes!
It would probably take, say, 300K of code to make Sage the expert in
what you need it to do? That's a no-brainer---do it! In fact, we also
encourage people to submit books they are writing to be included in
Sage, so that we have an entire book's worth of code as doctests.
In the next few months, I am going to submit a file of functions to
calculate the minimum rank of a graph. Probably less than 100 people in
the world work on this, but once Sage has it, Sage will be the defacto
software for working with minimum rank. That will be very, very nice.
> My answer, for the moment, is no... I was thinking we only wanted to see
> in Sage things that may be useful to everybody, and let people write
> their own functions, but...
Suppose someone, "John", submits his special function to Sage. It takes
up about 10K worth of space. Well, now John's code is guaranteed to
work with future versions of Sage (his doctests *must* pass before a new
release), at least as long as someone is willing to tweak it to port it
to new versions. Also, now John knows how to submit things and knows
how to review patches. So next time he needs something done, he's more
likely to do it himself and submit a patch.
We *need* developers and reviewers. You know that. I think 10K of code
that maybe only he uses for the time being is well worth getting another
person capable of developing and reviewing patches.
Besides, you said it was a lab? It sounds like the code is valuable to
more than just one person.
That said, I would also pay attention to what Minh said, and organize
things. That's the only reason the minimum rank code isn't submitted to
Sage already---I haven't sat down and organized it as much as it should be.
> The thing is that I am tempted ( for the Graph class ) to write many
> functions I find useful, but these functions would very quickly crowd
> the list of Graph methods... For example I am interested in computing
> orientations of graphs, and there may be many functions needed... For
> example, how could I include 10 or 20 functions dealing with one
> particular problem of graphs without quickly transforming this already
> quite crowded class in something impossible to browse ?
That's a question of organization. Sage is largely developed by people
"scratching their own itch", making the software the best possible for
the work they are doing.
Thanks again for all of the work you are doing. Your flurry of patches
is part of the reason we are having a Review day next Tuesday!
Jason
--
Jason Grout
Simon King
On Sep 17, 4:00 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
[...]
"must"!) be addressed before implementing any details.
By the way, as Rob and Minh pointed out, documentation helps a lot,
and (if it helps to convince you...) new code in Sage *must* be fully
covered by documentation *including* tests. I think nobody here would
give a positive review on anything that is not properly documented.
Cheers,
Simon
Jason Grout
I should add that Tim Daly takes this a step further and has all of the
Axiom documentation actually be books about mathematics, a "true"
repository of information, in volume form.
Jason
--
Jason Grout