Yes, please post it to sage-devel and I'll reply there.
I wasn't sure what your reply would be, so I started offlist. :)
Ondrej
On Tue, Aug 19, 2008 at 1:54 AM, Bill Page <bill...@newsynthesis.org> wrote:
> Ondrej,
>
> I would be glad (with your permission) to post this question and my
> reply on-list somewhere - sage-devel if you prefer.
>
> On Mon, Aug 18, 2008 at 6:50 PM, Ondrej Certik wrote:
>> Hi Bill,
>>
>> since you know both Python and Aldor or Axiom and now you know
>> Sage quite a bit, do you think Aldor or the Axiom style of things
>> (domains) is viable? I know it's not 100% equivalent to Python and
>> it can be fast with Aldor.
>>
>
> Yes, certainly I think Axiom domains are viable. Another way of asking
> this question is: if static strongly typed language with first-order
> polymorphic dependent types is viable? I think this has been answered
> in the positive by other experiments besides Axiom such as the ML
> series of languages and Haskell. Axiom (and Aldor) however does have a
> slightly different angle on the object-oriented part of the language
> by introducing the concept of 'category'. Categories are named subsets
> of domains. Categories allow a kind of generic programming that seems
> quite suitable to mathematical algorithms but I think this part of the
> design is less proven. So a better form of your question might be: Is
> the Axiom concept of 'category' viable? The existence of the Axiom
> library (and some of the libraries available in Aldor) provide some
> positive evidence, but I do not consider it proven.
>
> The Sage concept of 'parent' is an attempt to capture similar generic
> relationships that are represented by categories in Axiom, but I do
> not like the fact that this concept needs to be added on to Sage
> rather than being supported by some more fundamental feature of
> Python, e.g. Python meta-types.
>
>> What are your personal goals with Axiom (and forks)?
>>
>
> My personal goals do shift a little over time but currently I am
> mostly focused on the goal of using many algebraic notions from
> mathematical category theory (not the same as the notion of category
> in Axiom), in computer algebra. Ultimately, like you I want to be able
> to use computer algebra in theoretical physics but perhaps my goals
> are a little more abstract.
>
> http://axiom-wiki.newsynthesis.org/CategoryTheoryAndAxiom
>
>> I don't know how to judge it. I was looking at fricas mailinglist,
>> currently it has 59 members. Sympy list has 172 members. But
>> these numbers can easily change, so it imho doesn't say much.
>>
>
> What do you mean by "judge"? Are you trying to consider which of Sympy
> or FriCAS is more "viable"? I think you first have to define more
> exactly what you mean, e.g. viable for what purposes etc. You have
> previously argued that the simply popularity of a language like Python
> trumps any technical advantage that FriCAS may or may not have. I do
> accept that as largely true. On the other hand Python would *not* be
> my language of choice for doing more abstract things in category
> theory.
>
>> Sympy compared to fricas is really stupid, it cannot do many things.
>
> Probably it is more accurate to compare Sympy to some of the libraries
> that are available in Aldor, e.g. 'libAlgebra' and 'BasicMath'. These
> libraries also "cannot do many things" but they attempt to do at least
> a small number of things reasonably well. FriCAS likewise has the
> Axiom library but it is not so easily separable from the rest of the
> Axiom environment and interpreter (some people might call it: "the
> Axiom ecosystem"). So maybe it is better to compare FriCAS to Sage
> and/or Maxima etc. As I understand it Sympy does not attempt to become
> such an "ecosystem" but rather just a rather more lightweight library
> for Python programmers. Right?
>
>> So this means that there is a big barrier for people who would like
>> to use fricas, even its advanced features doesn't seem to track
>> attention.
>>
>
> If you mean that the type system of FriCAS is a big barrier, then I
> agree. On the other hand, depending on what you want to do with FriCAS
> this might be an essential advantage.
>
>> So I am just interested in your opinions on this.
>>
>
> Thank you. I am also interested to know other people's opinions on this issue.
>
> Regards,
> Bill Page.
>
The popularity of these examples with "end users" suggests
to me a lack of viability. Though of course it depends on one's
goals.
>> The Sage concept of 'parent' is an attempt to capture similar generic
>> relationships that are represented by categories in Axiom, but I do
>> not like the fact that this concept needs to be added on to Sage
>> rather than being supported by some more fundamental feature of
>> Python, e.g. Python meta-types.
Just to make sure credit goes where it should, the idea of
"parent" is not a Sage concept
but a Magma concept. I think the credit for it should definitely
go to John Cannon et al., and certainly not to me or Sage.
I think in Magma it is also not a part of the language but something
that is implemented on top of the Magma language. Unlike
you, I personally like that parent is not a fundamental feature
of Python, but a "design pattern" that can be implemented
on top of Python. That means one can directly use the same idea
in C/C++/etc. code.
-- William
On Tue, Aug 19, 2008 at 8:14 PM, Bill Page <bill...@newsynthesis.org> wrote:
>> Yes, certainly I think Axiom domains are viable. Another way of asking
>> this question is: if static strongly typed language with first-order
>> polymorphic dependent types is viable? I think this has been answered
>> in the positive by other experiments besides Axiom such as the ML
>> series of languages and Haskell. Axiom (and Aldor) however does have a
>> slightly different angle on the object-oriented part of the language
>> by introducing the concept of 'category'. Categories are named subsets
>> of domains. Categories allow a kind of generic programming that seems
>> quite suitable to mathematical algorithms but I think this part of the
>> design is less proven. So a better form of your question might be: Is
>> the Axiom concept of 'category' viable? The existence of the Axiom
>> library (and some of the libraries available in Aldor) provide some
>> positive evidence, but I do not consider it proven.
Thanks for answering. As William said, there are not many users of
such languges like Haskell. So while those languages have their
communities, for me personally this is not very viable. But of course
it depends what you want.
>>
>> The Sage concept of 'parent' is an attempt to capture similar generic
>> relationships that are represented by categories in Axiom, but I do
>> not like the fact that this concept needs to be added on to Sage
>> rather than being supported by some more fundamental feature of
>> Python, e.g. Python meta-types.
>>
>>> What are your personal goals with Axiom (and forks)?
>>>
>>
>> My personal goals do shift a little over time but currently I am
>> mostly focused on the goal of using many algebraic notions from
>> mathematical category theory (not the same as the notion of category
>> in Axiom), in computer algebra. Ultimately, like you I want to be able
>> to use computer algebra in theoretical physics but perhaps my goals
>> are a little more abstract.
>>
>> http://axiom-wiki.newsynthesis.org/CategoryTheoryAndAxiom
I see thanks.
>>
>>> I don't know how to judge it. I was looking at fricas mailinglist,
>>> currently it has 59 members. Sympy list has 172 members. But
>>> these numbers can easily change, so it imho doesn't say much.
>>>
>>
>> What do you mean by "judge"? Are you trying to consider which of Sympy
>> or FriCAS is more "viable"? I think you first have to define more
>> exactly what you mean, e.g. viable for what purposes etc. You have
>> previously argued that the simply popularity of a language like Python
>> trumps any technical advantage that FriCAS may or may not have. I do
>> accept that as largely true. On the other hand Python would *not* be
>> my language of choice for doing more abstract things in category
>> theory.
>>
>>> Sympy compared to fricas is really stupid, it cannot do many things.
>>
>> Probably it is more accurate to compare Sympy to some of the libraries
>> that are available in Aldor, e.g. 'libAlgebra' and 'BasicMath'. These
>> libraries also "cannot do many things" but they attempt to do at least
>> a small number of things reasonably well. FriCAS likewise has the
>> Axiom library but it is not so easily separable from the rest of the
>> Axiom environment and interpreter (some people might call it: "the
>> Axiom ecosystem"). So maybe it is better to compare FriCAS to Sage
>> and/or Maxima etc. As I understand it Sympy does not attempt to become
>> such an "ecosystem" but rather just a rather more lightweight library
>> for Python programmers. Right?
Yes, my own aim with Sympy is to just be a library to Python, that is
small and hackable, but feature full and fast. Something like numpy
but for symbolic stuff. That people can take and use in their programs
in engineering, physics, or applied math. It should have all features
of calculus in Mathematica. For example I would like to do quantum
field theory in sympy. There are many nice and interesting
calculations, that just cry out for being automated. I'd like to play
with it in python. There are some packages for it in Mathematica, but
programming in Mathematica is not fun.
Ondrej
> but
> programming in Mathematica is not fun.
And that would be the understatement of the week.
Cheers,
f
Could you remind me (yet again) of the top ten things you miss about
mathematica for symbolic calculations?
-- William
Thanks for reminding me this. It seems that people really like
Mathematica, so when I graudate, I'll try to learn it and do something
in it, so that I get a better feeling for how easy it is. Especially
its assumptions and substitution.
Ondrej
I don't think you're strange, I was just joking a bit. Caveat: it's
been years that I've *programmed* in Mathematica in a serious way
(recently I've mostly used it as a fancy calculator for quickly
computing integrals I'm too lazy to do by hand). But having said
that, what I really found Mathematica programming to be was a very
mixed experience: certain things that should be easy were
unjustifiably tricky to achieve, even after consulting with local
hard-core gurus.
But the elegance with which you can manipulate expressions
*structurally* is truly something to behold. This comes courtesy of
the lisp-like facilities you have for accessing any entity, working on
it as an expression tree you can manipulate with very powerful
transformation rules. And there are classes of problems where that
approach allows you to get pretty much exactly the solution you're
after with a minimum amount of fuss, where as in more conventional
languages it would be a lot of work.
So there, I hope this is a slightly more reasoned reply to a topic
worthy of an honest answer ;)
Cheers,
f
I need to learn Mathematica to understand what it means. In SymPy, you
can do some fancy stuff as well, e.g.:
In [1]: e = x*y+sin(x*y)**3
In [2]: print e
x*y + sin(x*y)**3
In [3]: from sympy.utilities.iterables import postorder_traversal,
preorder_traversal
In [4]: postorder_traversal(e)
Out[4]: <generator object at 0xa53376c>
In [9]: print list(postorder_traversal(e))
[x, y, x*y, sin(x*y), 3, sin(x*y)**3, x, y, x*y, x*y + sin(x*y)**3]
In [10]: print list(preorder_traversal(e))
[x*y + sin(x*y)**3, sin(x*y)**3, sin(x*y), x*y, x, y, 3, x*y, x, y]
And here is how those two functions are implemented:
def preorder_traversal(node):
yield node
for arg in node.args:
for subtree in preorder_traversal(arg):
yield subtree
def postorder_traversal(node):
for arg in node.args:
for subtree in postorder_traversal(arg):
yield subtree
yield node
So you can access all expressions uniformly and iterate over the
expression tree in 4 lines by hand, or just calling one of the
predefined functions above. I don't think this is complicated, but
maybe things can be made even easier.
Ondrej
Because of the subject of this thread I feel justified in giving the
following examples from Axiom:
http://axiom-wiki.newsynthesis.org/ManipulatingExpressions
Perhaps Sage can implement some form of pattern matching and
subsitution such is done by Axiom's rewrite rules? I think that in
many respects these provide a functionality similar to Mathematica.
There is also a similar re-writing system in Maple (applyrule).
> ...
>
> On Thu, Aug 21, 2008 at 12:50 AM, mhampton wrote:
>>
>> I really need to go to sleep so I won't do a top-ten, but here's a
>> top 2:
>>
>> 1) Powerful substitutions and rules. Sage does not have anything
>> comparable. The .subs() function is buggy even in its limited
>> domain. There have been previous posts on sage-devel that give
>> good examples of this.
>>
>
> Because of the subject of this thread I feel justified in giving the
> following examples from Axiom:
>
> http://axiom-wiki.newsynthesis.org/ManipulatingExpressions
>
> Perhaps Sage can implement some form of pattern matching and
> subsitution such is done by Axiom's rewrite rules? I think that in
> many respects these provide a functionality similar to Mathematica.
>
> There is also a similar re-writing system in Maple (applyrule).
I believe patter matching is something that GiNaC will get for us.
- Robert
> On Tue, Aug 19, 2008 at 8:14 PM, Bill Page <bill...@newsynthesis.org> wrote:
> >> The Sage concept of 'parent' is an attempt to capture similar generic
> >> relationships that are represented by categories in Axiom, but I do
> >> not like the fact that this concept needs to be added on to Sage
> >> rather than being supported by some more fundamental feature of
> >> Python, e.g. Python meta-types.
> William Stein:
> Unlike you, I personally like that parent is not a fundamental
> feature of Python, but a "design pattern" that can be implemented on
> top of Python. That means one can directly use the same idea in
> C/C++/etc. code.
Let me reuse this thread for further discussions about categories.
To start with: a disclaimer. I am a complete practitioner
here. Language design is not at all my specialty. But I do have a bit
of experience using and designing categories in MuPAD (MuPAD-Combinat
adds about 60 categories to the standard MuPAD hierarchy) as a design
pattern for organizing and factoring out generic code.
My feeling is that we need both concepts of parents *and* of
categories (more rant about this upon request). And I like the idea of
having them as design pattern not tighten too much to the language. In
particular, this means that we can progressively improve the design
pattern to increase its expressiveness in our context. We used that a
lot in MuPAD. Of course, in the long run, further and deeper support
from the language could help improve the safety.
With Florent, Mike, and Robert we spent some time discussing about
categories for Sage. I am now implementing a prototype (available in
sage-combinat), whose design differs slightly from that of:
http://trac.sagemath.org/sage_trac/ticket/4301
The idea is to let a category define generic code for parents and
elements through standard class inheritance (with some class surgery
done automatically behind the scene). It's a bit more tricky to setup
internally, but avoids messing around with getattr (that is in
practice introducing another technical way for doing multiple
inheritance; I am not speaking of cython object there, which probably
will need some getattr tricks since standard multiple inheritance does
not work).
The current design should leave the door open for those who will want
to do category theory (i.e. calculations on the categories
themselves), rather than using them to organize generic code which is
my own main goal.
See the attached files for some details.
My plan, with the help of Teresa, is to setup soon a full category
hierarchy (with most categories being dummy for the moment), as we had
discussed with Robert and others during Sage days 7 (most inspiration
coming from Axiom/MuPAD). Before we proceed, we have some questions:
- Has anyone done work in this direction lately?
- Did anyone keep a list or graph of the desired categories from sage days 7?
For reference, the hierarchy for MuPAD-Combinat is available there:
http://mupad-combinat.sourceforge.net/Papers/Categories.pdf
- Are the Sage categories currently used for anything but documenting
and testing the mathematical properties of parents?
- In particular, does anything depend on the current category
hierarchy, as defined at the end of categories/category_types.py,
or should we feel free to reorganize / extend it in any
mathematically meaningful way?
- Do we want to stick to the (possibly questionable) Axiom/MuPAD
convention to distinguish between monoids (or groups/...) written
additively or multiplicatively:
- AbelianGroup, AbelianMonoid, ...: structure for the + operation
- Monoid, Group, CommutativeGroup, ...: structure for the * operation
With this convention, a Ring is both an AbelianGroup and a Monoid
Alternatively, one could use the more verbose AdditiveMonoid
w.r.t. MultiplicativeMonoid; other suggestions are welcome.
Part of the question is whether we will ever want to have a
category for non abelian monoids written additively (I would
personnaly frown upon this, as much as I dislike using + for
concatenation of lists and strings; but that might be just me).
Best regards,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
The category hierarchy in Axiom is being documented in more detail.
The latest, nearly complete, version is at:
<http://daly.axiom-developer.org/bookvol10.2.pdf>
Note that the PDF is hyperlinked.
A (currently partial) diagram of the hierarchy can be found at:
<http://axiom-developer.org/axiom-website/dotabb.html>
Further documentation is at:
<http://axiom-developer.org/axiom-website/documentation.html>
Tim
Yes. Here is an example of one of the main ways I intended
categories to be used in practice.
sage: C = VectorSpaces(GF(5))
sage: W = (ZZ^3).span([[1,2,3],[4,5,3]])
sage: C
Category of vector spaces over Finite Field of size 5
sage: C(W)
Vector space of degree 3 and dimension 2 over Finite Field of size 5
Basis matrix:
[1 0 2]
[0 1 3]
As you can see, categories are to parents like parents
are to elements...
> - In particular, does anything depend on the current category
> hierarchy, as defined at the end of categories/category_types.py,
> or should we feel free to reorganize / extend it in any
> mathematically meaningful way?
You will probably break some code, but that's ok if you fix it.
But it will be very good to have some new work on this stuff!!
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
> The category hierarchy in Axiom is being documented in more detail.
> ...
Wow, thanks so much for all the pointers!
The key advantage of adopting the Axiom category hierarchy is the Sage
system could reuse a lot of the algorithms in Axiom. The Spad language
used in Axiom is similar in style and spirit to the Sage python language.
If the same categories were available it should be possible to use the
algorithms in Axiom's domains as written.
The temptation to re-design is very seductive but not very productive.
========================================================================
For those who don't understand Axiom's category/domain/package structure
I'll give the following very weak analogy:
You might find it useful to understand that Axiom has the algebra
divided into 3 kinds of things, Categories, Domains, and Packages.
By analogy to clothing,
Categories would be the patterns, fabrics, buttons, styles and
other things that are not specific. Mathematically these are things
like OrderedSet which specify functions like >, <=, etc.
Domains are instances of choices, like a particular dress, which
is chosen from a selection of categories by inheritance, so that
a particular domain (dress) has a certain fabric, pattern, style, etc.
Mathematically these are domains like Integer which model the
integer number system.
Packages are tools for dressmaking, such as sewing machines,
button-hole makers, ironing boards, etc.
In general, you work in domains which are particular instances of
mathematics with certain functions and properties inherited from
the categories. Every object created lives in some domain.
On Sun, Nov 9, 2008 at 1:21 PM, root <da...@axiom-developer.org> wrote:
> There are at least two possible paths toward a category hierarchy in Sage,
> adopting Axiom's version or designing a new one.
>
> The key advantage of adopting the Axiom category hierarchy is the Sage
> system could reuse a lot of the algorithms in Axiom. The Spad language
> used in Axiom is similar in style and spirit to the Sage python language.
> If the same categories were available it should be possible to use the
> algorithms in Axiom's domains as written.
>
> The temptation to re-design is very seductive but not very productive.
What is the relationship between "categories" in Axiom and the
mathematical notion of a category?
--Mike
On 11/09/2008 09:43 PM, William Stein wrote:
> On Sun, Nov 9, 2008 at 7:31 AM, Nicolas M. Thiery
> <Nicolas...@u-psud.fr> wrote:
>> - Are the Sage categories currently used for anything but documenting
>> and testing the mathematical properties of parents?
>
> Yes. Here is an example of one of the main ways I intended
> categories to be used in practice.
Similar to what you wrote...
sage: C = VectorSpaces(GF(5))
sage: C
Category of vector spaces over Finite Field of size 5
sage: W = (ZZ^3).span([[1,2,3],[4,5,3]])
sage: W
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 2 3]
[0 3 9]
sage: C(W)
Vector space of degree 3 and dimension 2 over Finite Field of size 5
Basis matrix:
[1 0 2]
[0 1 3]
That looks to me as if C is like a coercion function.
Should
sage: C(ZZ)
actually work? Currently it doesn't.
> As you can see, categories are to parents like parents
> are to elements...
Can you point me to the proper specification of a sage category concept?
The only thing I could find up to now is
http://www.sagemath.org/doc/ref/module-sage.categories.category.html
which is a rather imprecise specification.
Ralf
That's a pretty deep question that's been under debate for a while
on the Axiom mailing list. See:
<http://lists.gnu.org/archive/html/axiom-developer/>
My capsule response would be that it is a computational approximation
to the mathematical idea. Axiom's implementation was not trying to
develop category theory in full generality. However, because many of
the ideas underlie the implementation, Axiom has a very strong
"scaffold" that arranges and supports its category hierarchy.
I've found that there is a gap between traditional mathematics and
computational mathematics. Implementing the exact mathematics makes
a system extremely difficult to use. Implementing the computational
approximation makes mathematical reasoning awkward and approximate.
(Trivially, consider "Real Numbers")
I do not believe that the proper theory exists to bridge the gap.
I feel that such a theory will be the fundamental theory of
computational mathematics. And, no, I have no idea what that might be.
The point I was making is related to Nicolas's suggestion of redesigning
the category hierarchy to handle additive vs multiplicative forms in a
different way. While that may be a good idea it would have the side-effect
of changing the implementation of the algorithms. I make no claim that
Axiom's choices are better than any other possible choices, merely that
the pragmatics of the choice make life easier.
If Sage had an Axiom-style category hierarchy then the Axiom (Spad language)
algorithms for things like integration could be rewritten into python
with a local-minimum of effort. Spad uses indentation in the same way
that python does. However, this would not be "trivial" since python
does not support lisp-like macros, Sage does not seem to have a compiler,
python does not support the data==program abstraction, etc.
Tim
On Sun, Nov 09, 2008 at 04:21:56PM -0500, root wrote:
> There are at least two possible paths toward a category hierarchy in Sage,
> adopting Axiom's version or designing a new one.
>
> The key advantage of adopting the Axiom category hierarchy is the Sage
> system could reuse a lot of the algorithms in Axiom. The Spad language
> used in Axiom is similar in style and spirit to the Sage python language.
> If the same categories were available it should be possible to use the
> algorithms in Axiom's domains as written.
>
> The temptation to re-design is very seductive but not very productive.
Of course!
Don't worry: I am bound to be productive into translating code from
MuPAD to Sage :-) And the MuPAD's category hierarchy is quite similar
(since inspired from) Axiom's.
For the mathematical categories (Groups, Algebras, ...), the hierarchy
is anyway constrained by the mathematics behind. There are many
categories that are in MuPAD-Combinat but not in Axiom, and
reciprocally. So, there will be some merging of the two hierarchies
(and of others) but it should be straightforward and should not affect
the way algorithms are written.
Some other categories of Axiom are really more about computer science,
not mathematics. My feeling is that those would better be translated
into just a hierarchy of Python "abstract" classes. However we can try
to ensure compatibility whenever possible (names, hierarchy, ...), so
as to ease the translation of algorithms.
All the best,
Ah ok. Sorry if I have been unclear, I was merely asking whether
different *names* could possibly be deemed more appropriate by the
Sage community. That does not change the hierarchy itself, and a query
replace can take care of the job for code translation.
Cheers,
None. It is much better to think of categories in Axiom as multisorted
algebras. Or to make it simpler, as a first approach you can think of it
as universal algebras.
A semigroup in Axiom looks like
SemiGroup(): Category == with
*: (%, %) -> %
Monoid: Category == SemiGroup with
1: %
etc.
Programmatically, it is nothing else than the "interface" (Java-speak)
of a domain, i.e. all the exported function names and their signatures
(it's a bit oversimplified).
And I also would not too much draw a distinction between domains and
packages. A package is a domain where the special symbol % (which stands
for something like ThisDomain, old Axiom use $ instead of %) does not
appear.
The type hierarchy in Axiom is actually:
elements
domains/packages
categories
Then there is a hierarchy of domains (only single inheritance is
possible) and a hierarchy of categories (multiple inheritance allowed
since there is no conflict, because a category (usually) contains no
implementation of the signatures).
More details you find in Section 2.5 (p. 28) of
http://axiom-portal.newsynthesis.org/refs/articles/doye-aldor-phd.pdf
Regards
Ralf
Do you have information about MuPad's categories?
Tim
Wow. That's pretty orthogonal to my own goals. But this also means my
changes should not break much this part.
> As you can see, categories are to parents like parents
> are to elements...
Very much like in MuPAD. And somehow that's the part I don't like in
MuPAD. We often wanted to have parents which would simultaneously be
also elements (e.g. consider a monoid whose elements would themselves
be monoids, using cartesian product as multiplication). Being forced
to put parents of parent-element at a different level makes it harder
to share code (here, between 1st level and 2nd level monoids). And
what about monoids of monoids of monoids?
I think the parent approach has really something to say here. And
still can be combined with the category approach to have the best of
both worlds. I'll try to rant about this in the doc of my prototype
rather than on the mailing list. Otherwise I'll never have the time to
write the doc ...
> You will probably break some code, but that's ok if you fix it.
Any suggestions for which tests to run most to detect such bugs?
> But it will be very good to have some new work on this stuff!!
:-)
Hmm, way time to go to bed now ...
Nothing centralized, except from the MuPAD online doc, but you can
get the MuPAD-Combinat pieces from:
http://mupad-combinat.sourceforge.net/Papers/Categories.pdf
http://mupad-combinat.sourceforge.net/doc/en/Cat_Combinat/index.html
Cheers,
> Very much like in MuPAD. And somehow that's the part I don't like in
> MuPAD. We often wanted to have parents which would simultaneously be
> also elements (e.g. consider a monoid whose elements would themselves
> be monoids, using cartesian product as multiplication). Being forced
> to put parents of parent-element at a different level makes it harder
> to share code (here, between 1st level and 2nd level monoids). And
> what about monoids of monoids of monoids?
You know that FriCAS/Aldor does not have this drawback? Eg., the set of all
combinatorial species forms a Ring...
Martin
+1
> We used that a
> lot in MuPAD. Of course, in the long run, further and deeper support
> from the language could help improve the safety.
>
> With Florent, Mike, and Robert we spent some time discussing about
> categories for Sage. I am now implementing a prototype (available in
> sage-combinat), whose design differs slightly from that of:
>
> http://trac.sagemath.org/sage_trac/ticket/4301
>
> The idea is to let a category define generic code for parents and
> elements through standard class inheritance (with some class surgery
> done automatically behind the scene). It's a bit more tricky to setup
> internally, but avoids messing around with getattr (that is in
> practice introducing another technical way for doing multiple
> inheritance; I am not speaking of cython object there, which probably
> will need some getattr tricks since standard multiple inheritance does
> not work).
>
> The current design should leave the door open for those who will want
> to do category theory (i.e. calculations on the categories
> themselves), rather than using them to organize generic code which is
> my own main goal.
This is the "categories are bags of methods which are valid on
particular parents/elements" philosophy, which I agree is very
useful. One of the main goals is to be able to implement a ring R
and, by virtue of declaring it to belong to the category of Euclidean
Domains, a working gcd method would get attached to all the elements
of R. There are, of course, other uses for Categories but letting
them be full-featured objects allows for further flexibility.
> See the attached files for some details.
If I understand your code correctly, what you're proposing is that to
declare an Parent/Element to be a member of a category, one creates
the category and then dynamically creates classes at runtime that
need to be inherited from. Using QQ[x] as an example, I would create
the category
C = JoinCategory(EuclideanRings(), Algebras(QQ))
and then inherit from the dynamically created C.parent_class() and
C.element_class().
Actually, if I wanted to sit down and write my super-optimized QQ[x]
(say, by wrapping FLINT) I'm not even sure how I'd go about doing
that. It's also unclear how this would fit into the coercion model
(where the cdef classes Element and Parent use on c-level methods and
attributes for speed). But you do avoid needing to implement a
__getattr__ method.
> My plan, with the help of Teresa, is to setup soon a full category
> hierarchy (with most categories being dummy for the moment), as we had
> discussed with Robert and others during Sage days 7 (most inspiration
> coming from Axiom/MuPAD). Before we proceed, we have some questions:
>
> - Has anyone done work in this direction lately?
No. There's been times I've wanted to use it for stuff, but the patch
you referred to is still sitting un-refereed (as it probably should
while we hammer out our exact approach to these things).
> - Did anyone keep a list or graph of the desired categories from
> sage days 7?
> For reference, the hierarchy for MuPAD-Combinat is available there:
> http://mupad-combinat.sourceforge.net/Papers/Categories.pdf
I thought someone took a photo of it, but I don't know who.
> - Are the Sage categories currently used for anything but documenting
> and testing the mathematical properties of parents?
Not currently, which is unfortunate. I'm glad you're taking up the
banner to change this :).
> - In particular, does anything depend on the current category
> hierarchy, as defined at the end of categories/category_types.py,
> or should we feel free to reorganize / extend it in any
> mathematically meaningful way?
Yes, though the current coercion system does use morphsims (which, in
turn depends on the creation of homsets).
> - Do we want to stick to the (possibly questionable) Axiom/MuPAD
> convention to distinguish between monoids (or groups/...) written
> additively or multiplicatively:
>
> - AbelianGroup, AbelianMonoid, ...: structure for the +
> operation
> - Monoid, Group, CommutativeGroup, ...: structure for the *
> operation
>
> With this convention, a Ring is both an AbelianGroup and a Monoid
>
> Alternatively, one could use the more verbose AdditiveMonoid
> w.r.t. MultiplicativeMonoid; other suggestions are welcome.
>
> Part of the question is whether we will ever want to have a
> category for non abelian monoids written additively (I would
> personnaly frown upon this, as much as I dislike using + for
> concatenation of lists and strings; but that might be just me).
We currently do that in Sage too. Yes, I think we should, if just for
the ease of writing generic algorithms that can use inline arithmatic
rather than having to get the operation as a function and call z = op
(x,y) everywhere.
I implemented http://trac.sagemath.org/sage_trac/ticket/3999 which
mitigates the separation. I think a similar thing could be easily
written for a the parent-as-element class to cover your concern about
parents at different levels (e.g. monoids of monoids). I actually
think this distinction is good, as the behavior of an object viewed
as a parent may be different than that same object viewed as an
element (e.g. "order" has different meanings in the two contexts, and
I would expect something like "trace" to return a value for elements
and a function for parents).
- Robert
>> On Tue, Aug 19, 2008 at 8:14 PM, Bill Page wrote:
>> >> The Sage concept of 'parent' is an attempt to capture similar
>> >> generic relationships that are represented by categories in
>> >> Axiom, but I do not like the fact that this concept needs to
>> >> be added on to Sage rather than being supported by some
>> >> more fundamental feature of Python, e.g. Python meta-types.
>
>> William Stein:
>> Unlike you, I personally like that parent is not a fundamental
>> feature of Python, but a "design pattern" that can be implemented
>> on top of Python. That means one can directly use the same idea
>> in C/C++/etc. code.
On Sun, Nov 9, 2008 at 10:31 AM, Nicolas M. Thiery wrote:
>
> Let me reuse this thread for further discussions about categories.
>
> To start with: a disclaimer. I am a complete practitioner here.
> Language design is not at all my specialty. But I do have a bit
> of experience using and designing categories in MuPAD
> (MuPAD-Combinat adds about 60 categories to the standard
> MuPAD hierarchy) as a design pattern for organizing and factoring
> out generic code.
>
Thank you for "re-using" this thread. :-) I still think this subject
is important so let me start by explaining why I did not continue the
original thread. William's comment quoted above struck me as
representing a view of computer algebra systems so different than mine
that I did not think there was any chance of consensus - so merely
stating opinions seemed like an adequate closure of the subject at
that time. In spite of this I do still strongly support the idea of
Sage, including many of William's other visions of how it should/does
work. And in fact I find myself using Sage more and more these days in
spite of my continuing devotion to most other things more
Axiom-related.
The difference of opinion about parents and categories in Sage versus
Axiom probably runs rather deep. I was amused to realize that this
difference might even be summarized rather well by your choice of
title for this thread: "Categories for the working programmer". The
significance of this title might be lost on some readers who might not
know the classic text on category theory by Saunders Mac Lane:
"Categories for the working Mathematician". Not only does the term
"category" mean something very different in these titles, but also
there is a fundamental different in the point of view. It comes down
to this question: What is one really doing in computer algebra:
*programming* or *mathematics* ???
In perhaps a too terse manner, I think the difference between Axiom
and Sage can be summarized in the following anecdotal manner: The
developers of Axiom were/are largely computer scientists (aka.
programmers) attempting to implement a system for doing mathematics on
a computer. The developers of Sage on the other hand are (mostly)
mathematicians attempting to program a computer system to do
mathematics. The peculiar thing perhaps is that there is somewhat a
reversal of the usual perspective of mathematics versus computer
science: Sage is often pragmatic where Axiom is pedantic.
> My feeling is that we need both concepts of parents *and* of
> categories (more rant about this upon request). And I like the idea
> of having them as design pattern not tighten too much to the language.
> In particular, this means that we can progressively improve the design
> pattern to increase its expressiveness in our context. We used that
> a lot in MuPAD. Of course, in the long run, further and deeper support
> from the language could help improve the safety.
>
I think there is something deeper at issue here as well. Python is a
dynamically typed language while Axiom is statically typed. What this
means is that in Python it is the *values* that carry the type
information and the associated methods while in Axiom it is the
container, i.e. variable that carries the type. This distinction is
obscured somewhat by Axiom's interpreter which does try to implement a
kind of compromise (and bridge) between these two ideas about types,
but it is very obvious when one compares the Axiom library compiler
language Spad and Python. This difference has a big impact on the role
of parents in Sage and categories in Axiom. To some extent I view the
notion of "parent" in Sage as attempting to "put back" some of the
rigor (and type safely) that is lost in the dynamic approach to typing
implemented in Python. The library compiler in Axiom on the other hand
can (at least in principle) make good use of static typing to produce
type-safe and efficient machine code.
I have never spent much time with MuPAD, but my perception after some
experimentation is that MyPAD sort of "grafts" Axiom's ideas of domain
and category on top of an underlying untyped language not so different
from Maple. I have only a little more sympathy for this approach than
I have for the concept of "parent" in Sage. William Stein has said
that the notion of parent used in Sage is motivated almost entirely by
his experience with Magma. But all of these projects (MuPAD, Magma,
and Sage) seem to fit my preconceived notion of how mathematicians use
and program computers as opposed to how computer scientists might like
computers to implement mathematics.
But perhaps I am making to much of this supposed difference?
> With Florent, Mike, and Robert we spent some time discussing about
> categories for Sage. I am now implementing a prototype (available in
> sage-combinat), whose design differs slightly from that of:
>
> http://trac.sagemath.org/sage_trac/ticket/4301
>
> The idea is to let a category define generic code for parents and
> elements through standard class inheritance (with some class
> surgery done automatically behind the scene). It's a bit more tricky
> to setup internally, but avoids messing around with getattr (that is
> in practice introducing another technical way for doing multiple
> inheritance; I am not speaking of cython object there, which
> probably will need some getattr tricks since standard multiple
> inheritance does not work).
>
As some others in this thread (Tim Daly and Ralf Hemmecke) have
pointed out, there is not a complete consensus even in the Axiom
project(s) about the "true nature" of categories in Axiom. But the one
that I like the most is the one promoted by one of the early
developers of Axiom who later became the primary developer of Aldor -
the second generation library compiler for Axiom: Stephen Watt.
Stephen defines a category in Axiom (and Aldor) as a "sub-domain of
the Domain of all domains". This combines several ideas. First,
domains implement the notion of type or class in object-oriented
design. All values manipulated in Axiom are members of some domain and
the domain provides the methods by which these values are created and
accessed. One domain can be a sub-domain of another, e.g.
PositiveInteger is a sub-domain of Integer. But domains themselves are
values of a distinguished domain called Domain. Finally, categories
are sub-domains of this Domain - in other words categories are just
collections of domains.
I find this description satisfying because it is couched in terms that
should be very familiar to the mathematician. It does not invent any
new concepts of dubious intuitive value like "parent".
The reason why categories are interesting is as a means of organizing
domains into a conceptual hierarchy that corresponds in some
reasonable manner to formal concepts of interest to mathematics.
Navigating this hierarchy is an important part of learning to use the
Axiom system for any particular purpose. But it turns out that this is
also exactly the abstraction that makes generic programming possible.
When we associate properties like a list of exported operations to a
category, we will require that all domains that are members of this
category export and implement exactly these operations. Algorithms
implemented at the level of a category are available as defaults to
all the members of that category.
In comparison I find the concepts of class, meta-class, element,
parent and category in Sage overly complex and confusing - especially
to someone new to Sage. But I am clearly trumped in any argument along
these lines by the overwhelmingly greater number of people now
actively programming new functionality in Sage compared to Axiom. Of
course this is a source of considerable frustration to me. :-(
> The current design should leave the door open for those who will
> want to do category theory (i.e. calculations on the categories
> themselves), rather than using them to organize generic code which
> is my own main goal.
This strategy also conflicts strongly with my personal vision of how
mathematical category theory (as opposed to "category" as implemented
in Axiom and Sage) ought to fit into computer algebra. Category theory
has rapidly become an essential part of the toolkit of the computer
scientist. It has also gained almost universal acceptance in
mathematics as at least one of the ways in which mathematics can be
accurately and formally presented. Most aspects of category theory are
essentially algebraic in nature. So it seems peculiar in the extreme
to me that almost all computer algebra systems treat category theory
as at best a kind of "add-on" rather than a fundamental design
approach.
It seems to me that of all the existing computer algebra systems,
because of it's strong and often pedantic type system, Axiom seems
most compatible with taking category theory as a foundation.
Unfortunately in most respects Axiom does not do nearly enough to
exploit this. Magma apparently also takes a formal approach that is at
least in part motivated by category theory but I was rather
disappointed to see how little of this remains in the approach now
implemented in Sage.
>
> See the attached files for some details.
> ...
Well, it is hard to argue with working code! So to the extent that
this allows you do do things in Sage that might be awkward in a more
pedantic system like Axiom, I am very happy that you are working on
extending Sage in this manner. I do still wish however this becomes an
integral part of Sage and not just something else added on.
Regards,
Bill Page.
On Mon, Nov 10, 2008 at 9:31 PM, Bill Page <bill...@newsynthesis.org> wrote:
>> The current design should leave the door open for those who will
>> want to do category theory (i.e. calculations on the categories
>> themselves), rather than using them to organize generic code which
>> is my own main goal.
>
> This strategy also conflicts strongly with my personal vision of how
> mathematical category theory (as opposed to "category" as implemented
> in Axiom and Sage) ought to fit into computer algebra. Category theory
> has rapidly become an essential part of the toolkit of the computer
> scientist. It has also gained almost universal acceptance in
> mathematics as at least one of the ways in which mathematics can be
> accurately and formally presented. Most aspects of category theory are
> essentially algebraic in nature. So it seems peculiar in the extreme
> to me that almost all computer algebra systems treat category theory
> as at best a kind of "add-on" rather than a fundamental design
> approach.
>
> It seems to me that of all the existing computer algebra systems,
> because of it's strong and often pedantic type system, Axiom seems
> most compatible with taking category theory as a foundation.
> Unfortunately in most respects Axiom does not do nearly enough to
> exploit this. Magma apparently also takes a formal approach that is at
> least in part motivated by category theory but I was rather
> disappointed to see how little of this remains in the approach now
> implemented in Sage.
Just a quick note. Categories in Sage are modeled after the
mathematical categories rather than Ralf's universal algebra notion.
That is, you have objects, morphisms, functors, homsets, etc. They
just happen to be a convenient place to put generic methods for their
objects.
--Mike
Although I am vaguely aware that Sage does implement these notions,
even after working with Sage now for the last two years I still know
very little about what is actually implemented and what is planned.
Unless I missed it, it seems to me that there is an extreme lack of
documentation on all of this in Sage.
Also, I have some trouble reconciling your comments with the comments
of Nicolas Thiery at the start of this thread. Is Nicolas talking
about mathematical categories in Sage or something more like
categories in Axiom/MuPAD?
Finally, I should note that I do not agree with Ralf's views (quoting
Doye's article on Aldor) on the importance of universal algebra
notions to categories in Axiom. But I do think that this article is
very relevant to the subject of coercions in computer algebra and so
also important in Sage.
Regards,
Bill Page.
Maybe it belongs somewhere else, but how would you explain to someone
who is new to Aldor/panAxiom, what the concept of "category" in the
Aldor/panAxiom language is? That is a language concept.
Then comes the question whether an Axiom category is in some way related
to some known mathematical concept. For me order-sorted algebras match
quite well while (mathematical) category doesn't (even if that might
have been the original motivation for the name in Axiom).
> But I do think that this article is very relevant to the subject of
> coercions in computer algebra and so also important in Sage.
Oh, yes, good that you mention that. After I read that thesis I thought
that the language actually should somehow support that it should not
matter, which coercion path one follows to arrive at a certain type. The
result should be the same. But I guess, such a check is undecidable.
Ralf
I have nothing against functors. However, as I understand, C is a
>> Category of vector spaces over Finite Field of size 5
and that does not sound like a "functor".
> And taking this in mind I think this is a good behaviour of C(W),
> since this behaviour is for example similar to that of F5(x) in the
> example below:
> sage: F5=GF(5)
> sage: F5
> Finite Field of size 5
> sage: x=ZZ(102)
> sage: F5(x)
> 2
> That is F5() tries to make an element in F5() of 102 as C tries to
> make a vectorfield over GF(5) out of W. So maybe it is also not bad to
> have coercion functions defined for categories.
In in the above form "ZZ(102)" and "F5(x)" you basically use ZZ and F5
to denote a type cast. That is what I called "coercion" (which is
basically a function ZZ -> F5).
My question now (still being a bit unfamiliar with python) would be,
where can I find the documentation of what is allowed for x in something
like F5(x). I guess F5("some string") does not work. I'd like to be sure
that code I write does not break at runtime. A pointer to the
documentation is highly appreciated.
Thank you
Ralf
In Sage, we use the term "coercion" to denote a canonical (using the
term a bit loosely), implicit map between Parents (or objects of a
concrete category). E.g. from ZZ to F5 would be a "coercion," but
there is a "conversion" and not a "coercion" the other direction.
Coercions are invoked to do arithmetic, but conversions are not. For
example
sage: F5.coerce_map_from(ZZ)
Natural morphism:
From: Integer Ring
To: Finite Field of size 5
sage: f = F5.coerce_map_from(ZZ)
sage: f(3)
3
sage: f(943)
3
sage: ZZ.coerce_map_from(F5) # there isn't one
sage: ZZ.convert_map_from(F5)
Conversion via _integer_ method map:
From: Finite Field of size 5
To: Integer Ring
Eventually, that last one will be a lift map (that's essentially what
it is, but I haven't gotten around to moving the finite fields to the
new model yet... currently it's exposing the implementation details).
> My question now (still being a bit unfamiliar with python) would be,
> where can I find the documentation of what is allowed for x in
> something
> like F5(x). I guess F5("some string") does not work. I'd like to be
> sure
> that code I write does not break at runtime. A pointer to the
> documentation is highly appreciated.
F5(...) calls the F5.__call__ method. If F5 were a type, this
(eventually, in the basic case) calls the __init__ method on an
instance of that type. Depending on what was implemented, anything
could be valid. They are used as constructors, and the general
philosophy is "make an element of the right type if at all possible."
Thus,
sage: F5("some string")
Traceback (most recent call last):
...
TypeError: unable to convert x (=some string) to an integer
sage: F5('2')
2
Just as this casting notation works to force elements in one object
into another by invoking the appropriate morphism, it can be used to
force objects in one category into another by invoking the
appropriate functor.
- Robert
> In Sage, we use the term "coercion" to denote a canonical (using the
> term a bit loosely), implicit map between Parents (or objects of a
> concrete category). E.g. from ZZ to F5 would be a "coercion," but
> there is a "conversion" and not a "coercion" the other direction.
> Coercions are invoked to do arithmetic, but conversions are not.
Just for the record, this is *exactly* the same definition as in FriCAS.
(in case you wonder, the notation "Object::SomeType" is syntactic sugar for
"coerce(Object)@SomeType", where @ is a language builtin, that selects the
function according to return type.
Unfortunately, the contributors to NAG Axiom were sometimes a bit sloppy about
which coercions to implement.
There was one idea, which I personally like a lot, to provide to "Categories"
(in the FriCAS/Axiom sense)
CoercibleTo S, RetractableTo S and ConvertibleTo S that provide
coerce: % -> S, coerce: S -> % and retract: % -> S
respectively. One can then ask
(4) -> SquareMatrix(2, INT) has CoercibleTo Matrix INT
(4) true
Type: Boolean
Very unfortunately, currently in almost all cases the query "has CoercibleTo
Something" will return false, because the coerce function is not inherited by
the category. (I have a suspicion for the reason, but that's not important
here.)
However, I think in principle the design is *very* good. I think the design in
Sage is not so different (I did not check thoroughly, though), which comes as
confirmation.
Martin
> Just for the record, this is *exactly* the same definition as in FriCAS.
Exactly.
> (in case you wonder, the notation "Object::SomeType" is syntactic sugar for
> "coerce(Object)@SomeType", where @ is a language builtin, that selects the
> function according to return type.
And, as Robert kindly explained (thank you), it is written
"SomeType(Object)" in Sage.
The only difference between Sage and Aldor/panAxiom is that Sage checks
whether the Object can be coerced to SomeType at runtime whereas Aldor
and SPAD allow to check at compile time.
And I don't say that "some string"::Integer is impossible to succeed, it
is only a question whether the compiler sees (has in scope) a function
coerce: String->Integer that would do the job... of course at compile
time. (By the way, if one defines this coerce to be the length of the
string and takes + as the concatenation of strings then this coerce is
even a homomorphism from the String monoid into the integers considered
as an additive monoid.)
Ralf
> The only difference between Sage and Aldor/panAxiom is that Sage checks
> whether the Object can be coerced to SomeType at runtime whereas Aldor
> and SPAD allow to check at compile time.
I don't think this is the full story. As far as I can see, it is the
responsibility of the programmer to do the dispatch, i.e.,
if arg is string then do this
if arg is number then do that
etc. (please correct me if I'm wrong!!!)
If this is not properly done, the user will get *some* error message, not
necessarily informative.
In FriCAS, the message is standardized:
(5) -> 1.5::INT
Cannot convert from type Float to Integer for value
1.5
(5) -> "1213" :: Float
Cannot convert from type String to Float for value
"1213"
simply because there is no suitable function coerce: String -> Float.
(I'm cheating I tiny bit here, but I believe I got the philosophy right)
If one get's the arguments of a function wrong, the message is also
standardized - possibly it could be better, but anyway:
(7) -> D(x^2, x, x)
There are 3 exposed and 0 unexposed library operations named D
having 3 argument(s) but none was determined to be applicable.
Use HyperDoc Browse, or issue
)display op D
to learn more about the available operations. Perhaps
package-calling the operation or using coercions on the arguments
will allow you to apply the operation.
Cannot find a definition or applicable library operation named D
with argument type(s)
Polynomial(Integer)
Variable(x)
Variable(x)
Perhaps you should use "@" to indicate the required return type,
or "$" to specify which version of the function you need.
(Because in FriCAS, the syntax for differentiation is D(fun, var, how-often),
but obviously, one might believe that it is D(fun, var1, var2,...))
I think that Sage / Python could be improved here (not that I want to do it - I
hope you accept this "criticism" as constructive). For example:
sage: parametric_plot(1, x, (0,4))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/home/rubey/<ipython console> in <module>()
/opt/local/sage-3.1.2/local/lib/python2.5/site-packages/sage/plot/plot.py in
parametric_plot(funcs, tmin, tmax, **kwargs)
3786
3787 """
-> 3788 if len(funcs) == 3:
3789 raise ValueError, "use parametric_plot3d for parametric plots
in 3d dimensions."
3790 elif len(funcs) != 2:
TypeError: object of type 'sage.rings.integer.Integer' has no len()
But what I'd like to see: "x" is not a range.
Similarly:
sage: contour_plot(x^2==0, (0,4), (0,4))
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/home/rubey/<ipython console> in <module>()
/opt/local/sage-3.1.2/local/lib/python2.5/site-packages/sage/plot/plot.py in
contour_plot(f, xrange, yrange, **kwds)
2917 xy_data_array = [[g(x, y) for x in \
2918 sage.misc.misc.xsrange(xrange[0], xrange[1],
xstep)]
-> 2919 for y in sage.misc.misc.xsrange(yrange[0],
yrange[1], ystep)]
2920
2921 g = Graphics(xmin=float(xrange[0]), xmax=float(xrange[1]),
ymin=float(yrange[0]), ymax=float(yrange[1]))
/opt/local/sage-3.1.2/local/lib/python2.5/site-packages/sage/calculus/equations.py
in __call__(self, *args, **argv)
211 from sage.calculus.all import SR
212 m = matrix(SR, 1, 2, [self._left, self._right])
--> 213 left,right = m(*args, **argv)[0]
214 return self._op(left, right)
215
/home/rubey/matrix_symbolic_dense.pyx in
sage.matrix.matrix_symbolic_dense.Matrix_symbolic_dense.__call__
(sage/matrix/matrix_symbolic_dense.c:5608)()
ValueError: the number of arguments must be less than or equal to 1
But what I'd like to see: first argument has to be a function.
The dynamic typing philosophy gives more flexibility, but also more
responsibility, it seems.
Martin
Using the full resolution (zoom lens button) one can barely read every
node of the tree!
Clément
That's the idea. But I see this as an implementation detail that the
average programmer should not have to play with. So actually I have
modified the Parent.__init__ constructor to do this automatically for
you. See the Category documentation a bit lower in my patch on
sage-combinat; here is a short extract:
We now construct a parent in the usual way:
sage: from sage.categories.category import build_class
sage: class myparent(Parent):
... def __init__(self):
... Parent.__init__(self, categories=[Ds()])
... def g(self):
... return "myparent"
... class Element:
... def method(self):
... return "myparent"
sage: D = myparent()
sage: D.__class__
<class '__main__.myparent_with_categories'>
Something similar should be done for elements: the class would be
built automatically from the Element class of the categories and of
the parent itself. This is not implemented yet.
Note that the classes created dynamically are cached. So most of the
time two parents coming from the same place (e.g. VectorSpace(3, QQ)
or VectorSpace(3, RR)) would share the same underlying class.
One drawback: the current implementation uses a hack (which is well
localized but still a hack): the Parent.__init__(self) method changes
the class of self on the fly to the newly created one. How robust is
this, in particular w.r.t. cython class?
> Actually, if I wanted to sit down and write my super-optimized QQ[x]
> (say, by wrapping FLINT) I'm not even sure how I'd go about doing
> that. It's also unclear how this would fit into the coercion model
> (where the cdef classes Element and Parent use on c-level methods
> and attributes for speed). But you do avoid needing to implement a
> __getattr__ method.
Yup. I indeed don't know yet how this fits with pure cython classes
(but see my other post about subclasses of cython classes). I am
hoping that something semantically equivalent can be implemented, but
for this I need you. The main thing is: do you foresee any blocker for
this design to be adapted to cython classes one way or the other.
> Not currently, which is unfortunate. I'm glad you're taking up the
> banner to change this :).
:-)
First, thanks you so much for all the feedback you are kindly providing!
I am busy right now with some articles + habilitation + visitors, but
I am following the thread closely, and will answer soon where needed.
On Tue, Nov 11, 2008 at 01:04:12AM -0500, Bill Page wrote:
> Also, I have some trouble reconciling your comments with the comments
> of Nicolas Thiery at the start of this thread. Is Nicolas talking
> about mathematical categories in Sage or something more like
> categories in Axiom/MuPAD?
Sorry, I should have been clearer about that. Yes, I am talking about
the modeling of mathematical categories, primarily as a design pattern
to organize generic code, but leaving the door open for other uses:
- functors, possibly used as coercions
- storage of mathematical information about parents (is this a ring?
a field?), both for documentation and algorithmic decisions
- computations in category theory?
- ...
So maybe I should have taken as subject:
Mathematical categories for the working programming mathematician
(btw: this subject was also referring to the book: Categories for the
working Computer Scientist).
Independently, I am keeping an eye on the other category hierarchies
in Aldor/panAxiom, as this could give some good hints for the
organization of abstract classes in Sage.
On Tue, Nov 11, 2008 at 01:04:12AM -0500, Bill Page wrote:
> > ... Categories in Sage ...
> Although I am vaguely aware that Sage does implement these notions,
> even after working with Sage now for the last two years I still know
> very little about what is actually implemented and what is planned.
> Unless I missed it, it seems to me that there is an extreme lack of
> documentation on all of this in Sage.
I guess the current implementation was deemed as temporary and to be
refactored; so not that useful to document right away at the user
level. Of course, the "final" implementation will need extensive
documentation. I actually expect the documentation to take out most of
the code and development time, and am saving my energy for this ...
Best,
> On Mon, Nov 10, 2008 at 07:13:58PM -0800, Robert Bradshaw wrote:
>> If I understand your code correctly, what you're proposing is that to
>> declare an Parent/Element to be a member of a category, one creates
>> the category and then dynamically creates classes at runtime that
>> need to be inherited from. Using QQ[x] as an example, I would create
>> the category
>>
>> C = JoinCategory(EuclideanRings(), Algebras(QQ))
>>
>> and then inherit from the dynamically created C.parent_class() and
>> C.element_class().
>
> That's the idea. But I see this as an implementation detail that the
> average programmer should not have to play with.
Yes. Of course *I'm* very interested in the implementation details,
now that we've decided what we mean by "category" and what we want to
do with them, but I'm certainly in the minority there :).
It can't be done.
sage: L = range(10)
sage: L.__class__ = dict
Traceback (most recent call last):
...
TypeError: __class__ assignment: only for heap types
Perhaps that's for the better, as treating a list as a dict would
result in c-level incompatibilities and segfaults. Note that there
are several Parents (not just elements) that are implemented in
Cython as well. For Elements, we avoid calling the __init__ method
altogether (as in many cases that Python call may be more expensive
than the arithmetic itself).
However this is implemented behind the scenes, I fully agree with you
that the average programmer should just be able to inherit from
Parent/Element (optionally?) specifying the category the Parent
belongs to, and it should "just work" without having to know some
extra incantation.
On the note of making it easy to understand, what would people think
of renaming Parent to SetObject or even just Set? This would clear up
the very frequently asked question "what is a Parent?" to give it a
more mathematically-grounded name.
>> Actually, if I wanted to sit down and write my super-optimized QQ[x]
>> (say, by wrapping FLINT) I'm not even sure how I'd go about doing
>> that. It's also unclear how this would fit into the coercion model
>> (where the cdef classes Element and Parent use on c-level methods
>> and attributes for speed). But you do avoid needing to implement a
>> __getattr__ method.
>
> Yup. I indeed don't know yet how this fits with pure cython classes
> (but see my other post about subclasses of cython classes). I am
> hoping that something semantically equivalent can be implemented, but
> for this I need you. The main thing is: do you foresee any blocker for
> this design to be adapted to cython classes one way or the other.
Actual full multiple inheritance for cdef'd classes in Cython won't
happen for a long time, if ever. This is due to major technical
difficulties (C++ style multiple inheritance won't work, as it casts
by actually adjusting the pointer, which breaks when passing in and
out of the Python library with PyObject*, and it seems every other
way of doing it incurs much more overhead on non-multiply inherited
classes). However, if they types are compatible (e.g. one side is
pure Python), then it just might be possible to implement multiple
inheritance...
What can be simulated much more easily is a (nearly arbitrary) lookup
if nothing is found in the straight line hierarchy. This means that
if we have
A
| \
B C
| /
D
where the C-D inheritance is emulated, a method on C would not
override a method on A as desired. (One could manually manipulate the
mro, but this would change all instances of D.) But this may be
sufficient, as C and B would likely not have a common ancestor. Note
that issubclass(D, C) would be False, which might also have
implications for binding methods, though probably not too hard to get
around.
- Robert
> You know that FriCAS/Aldor does not have this drawback? Eg., the set of all
> combinatorial species forms a Ring...
Thanks for pointing this out. Could you make a quick summary here of
how this is achieved?
Each combinatorial species is a domain, right? Are they simultaneously
elements of some domain in the Ring category?
Cheers,
A semi-ring, we don't have virtual species yet.
> Thanks for pointing this out. Could you make a quick summary here of
> how this is achieved?
I don't know what Martin refers to exactly, because he could have
pointed to some code.
> Each combinatorial species is a domain, right? Are they simultaneously
> elements of some domain in the Ring category?
Well, that is not completely fleshed out. (At least not in trunk of
aldor-combinat.) But as you see at
http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatsu27.html#x41-590008.14
you are approximately right.
Elements of this CombinatorialSpeciesAlgebra domain are functions that
produce combinatorial species. The 1 is clear, addition as well, 0 would
also be simple. The X, maybe doesn't really belong there, since that
already is a step towards a polynomial (semi)algebra. But otherwise, who
cares at the moment?
Well, that is just some idea... And I don't see why that cannot work in
Aldor. I actually also don't see a big trouble that something along
these lines would be impossible in Python. Or is it? I'd be happy to
learn more how this can be achieved through python.
Ralf
Although I seriously doubt that the Sage developers would agree to
change the name of something quite this fundamental in Sage, since I
was/am one of the people who have been most critical "parent" in Sage,
it is hard to let this pass without comment. In fact we have discussed
this previously in the thread:
http://groups.google.com/group/sage-devel/msg/423c69d7f48dcd3d
David Harvey proposed what I think is a more precise definition of "parent":
>> Bill Page wrote:
>>> How does it related to the concept of "parent" - which seems equally
>>> ill-defined to me?
> On Jun 3, 2008, at 10:04 PM, Robert Bradshaw wrote:
>> A Parent is an Object in the category of Sets,
David Harvey wrote:
> huh? Don't you mean to say something more like "a parent is an object
> of a concrete category", i.e. a category C with a faithful functor
> f : C -> Set, such that the "elements" (as understood by Sage) of the
> parent P are exactly the elements of f(P)?
I rather like David's definition because it is careful to make a
connection to category theory. Unfortunately, as far as I can tell
Sage does not directly implement this notion. I mean: there is no such
identifiable concrete category in Sage as such, even if it is true
that a parent "behaves" in this manner. In any case, perhaps it would
be helpful if 'parent' was replaced with
sage: concrete_category(1)
Integer Ring
But there is a further complication since there already is some kind
of "category" associated with elements:
sage: category(1)
Category of elements of Integer Ring
I do not understand what this really is yet. It does not seem to me
that the elements of Integer Ring actually form a category as such.
Regards,
Bill Page.
The point below was discussed during Sage Days 15,
On Sun, Nov 09, 2008 at 04:31:52PM +0100, Nicolas Thiéry wrote:
>
> ... About naming conventions for categories:
>
> - Do we want to stick to the (possibly questionable) Axiom/MuPAD
> convention to distinguish between monoids (or groups/...) written
> additively or multiplicatively:
>
> - AbelianGroups, AbelianMonoids, ...: structure for the + operation
> - Monoids, Groups, CommutativeGroups, ...: structure for the * operation
>
> With this convention, a Ring is both an AbelianGroup and a Monoid
>
> Alternatively, one could use the more verbose AdditiveMonoid
> w.r.t. MultiplicativeMonoid; other suggestions are welcome.
>
> Part of the question is whether we will ever want to have a
> category for non abelian monoids written additively (I would
> personnaly frown upon this, as much as I dislike using + for
> concatenation of lists and strings; but that might be just me).
We discussed this point at Sage Days 15, and apparently the consensus
was to go for the more explicit, at the price of breaking with
historical conventions in Axiom and MuPAD (and actually also in Sage:
before the category patch, Rings inherits from AbelianGroups!).
Since this was not debated on the list, this e-mail is a last call for
comments before the things get set in stone.
So: is there a reasonable consensus on the following naming scheme:
- Structure for the + operation:
AdditiveMonoids, AdditiveGroups, CommutativeAdditiveMonoids, ...
- Structure for the * operation:
Monoids, Groups, CommutativeMonoids, CommutativeGroups
Then, a Ring would be a CommutativeAdditiveGroup and a Monoid.
Note: I personally vote against specifying Multiplicative.
CommutativeMultiplicativeGroups is unnecessary long and cumbersome.
The convention above readily breaks any ambiguity.
On a similar note, we will need conventions at some point for rings
without 1 or without 0. Here I am a totally in favor of breaking with
the historical hack which was certainly fun but not quite reasonable:
`i` stands for `identity`, and n for neutral. So:
- Ring: usual ring
- Rig: Ring without 0
- Rng: Ring without 1
- Rg: Ring without 1 and 0
Suggestions?
>> Bill Page wrote:
>>> How does it related to the concept of "parent" - which seems equally
>>> ill-defined to me?
> On Jun 3, 2008, at 10:04 PM, Robert Bradshaw wrote:
>> A Parent is an Object in the category of Sets,
David Harvey wrote:
> huh? Don't you mean to say something more like "a parent is an object
> of a concrete category", i.e. a category C with a faithful functor
> f : C -> Set, such that the "elements" (as understood by Sage) of the
> parent P are exactly the elements of f(P)?
I rather like David's definition because it is careful to make a
connection to category theory. Unfortunately, as far as I can tell
Sage does not directly implement this notion. I mean: there is no such
identifiable concrete category in Sage as such, even if it is true
that a parent "behaves" in this manner. In any case, perhaps it would
be helpful if 'parent' was replaced with
sage: concrete_category(1)
Integer Ring
But there is a further complication since there already is some kind
of "category" associated with elements:
sage: category(1)
Category of elements of Integer Ring
I do not understand what this really is yet. It does not seem to me
that the elements of Integer Ring actually form a category as such.
Why? Why do you think elements can't be objects in a category?
-- William
But none of this has much to do with category theory as such where
normally elements of some co-domain are *morphisms* with the domain
some terminal object in the category.
Regards,
Bill Page.
Sorry, if I was unclearn. I was not doubting the a consensus about this.
The question I was raising was about the names we wanted to use for
"rings" without 0 resp. 1.
> 2009/5/24 William Stein <wst...@gmail.com>:
> > For me rings always have both 1 and 0.
> > I would call a "ring without 1" an algebra.
Possibly. Although "algebra" is very often taken for a ring with a
vector space structure (and this is the current convention in
Sage/Axiom/MuPAD). Darn, no internet access to check what Wikipedia
says.
> I have not looked at the rest of what has been done in any one
> detail. But I hope that all the functionality for abelian groups
> will be available for both additive and multiplicative groups,
> something which is certainly not the case at present.
This certainly is very much desirable. The current patch is just about
setting up the overall framework. Now it needs to be filled up, in
particular by abstracting out generic code spread over the Sage library.
I will leave this to the experts, and (finally!) focus back on my
favorite topics (hopf algebras, combinatorics, representation theory, ...).
By the way: as in Axiom/MuPAD/... the current setup does not do
anything special to factor out generic code that work the same for
both additive and multiplicative groups except for the *names* of the
operations. We need good ideas for handling this nicely!
Best,
> Sorry, if I was unclearn. I was not doubting the a consensus about this.
Aha, A := 3Z (all multiples of 3) is not a (mathematical) ring!? And {0}
also doesn't count as ring?
That one fixes the convention that 'Ring' in any CAS to mean a
mathematical ring with 1 is another question.
> The question I was raising was about the names we wanted to use for
> "rings" without 0 resp. 1.
Z is also a ring without one, i.e., Ring should inherit from Rng. I
would rather say that Rng is a "ring" that *doesn't claim* the existence
of 1.
Ralf
PS: Nicolas, can you give an example of a Rg. I always thought that a
ring is a commutative group wrt + and a semigroup wrt *.
You forgot to read the line after your signature. I was speaking about
inheritance Rng ==> Ring, i.e. every Ring is a Rng.
Ralf
> That one fixes the convention that 'Ring' in any CAS to mean a
> mathematical ring with 1 is another question.
That indeed is the scope of the discussion (and btw is also the
default convention for rings in Wikipedia).
> Z is also a ring without one, i.e., Ring should inherit from Rng.
Definitely. And this is the case.
> I would rather say that Rng is a "ring" that *doesn't claim* the
> existence of 1.
Yup, it's like non-associative rings of which rings are a special case.
Now, I need a better name than RingsThatDoNotClaimExistenceOfOne().
> PS: Nicolas, can you give an example of a Rg. I always thought that a
> ring is a commutative group wrt + and a semigroup wrt *.
Well, one can certainly cook up an example. Whether we want to give it
a name that is related to the ring concept is an other question.
Cheers,
Although, when I first saw Rng in Axiom, I didn't understand why the
programmers used something that looked like an abbreviation. But, in
fact, I somehow like that name. It makes it pretty obvious that the
'identity' is somehow hidden or non-existent.
If you don't like Rng, then what about PseudoRing?
http://en.wikipedia.org/wiki/Pseudo-ring
But actually, Rng looks more intuitive. Is clear enough (or even
clearer), and shorter than PseudoRing ;-). But it seems that also
PseudoRing is quite a good name.
And I am sure you have also found the following for Rig.
http://en.wikipedia.org/wiki/Semi-ring
Looks like a Semiring/Rig is *not* what you originally described as
>>> - Rig: Ring without 0
http://groups.google.com/group/sage-devel/msg/bd5d8a5ad2103c57
Ralf
Thanks for the feedback.
PseudoRing, is pretty non informative. The NonUnitalRing they also
mention is better (though with the usual quirk that a UnitalRing is a
NonUnitalRing, but not the converse).
> And I am sure you have also found the following for Rig.
>
> http://en.wikipedia.org/wiki/Semi-ring
>
> Compare also
> http://books.google.at/books?id=roEx6lkAp10C&dq=Jonathan+S.+Golan,+Semirings+and+their+applications&printsec=frontcover&source=bl&ots=jI4yTSEBOZ&sig=CgCZ_07yz0qI_EUTLs2NAChAVYw&hl=de&ei=n_gcSqnSF4yHsAaQyOzQCg&sa=X&oi=book_result&ct=result&resnum=1
> Chapter one.
>
> Looks like a Semiring/Rig is *not* what you originally described as
>
> >>> - Rig: Ring without 0
> http://groups.google.com/group/sage-devel/msg/bd5d8a5ad2103c57
Silly me, I had never realized that Rig == SemiRing. Without neutral
element, you can't have additive inverse!
Well, SemiRing is well established (and that's what we used in
Sage-Combinat) so we have a name here.
> For me rings always have both 1 and 0.
> I would call a "ring without 1" an algebra.
It is common terminology to call a `Ring without 1' a Rng.
I'm usually not a fan of Wikipedia as reference, but here you go
http://en.wikipedia.org/wiki/Rng_(algebra)
-- Gaby