Species In Sage

[Martin Rubey]

I put my code species code that I've written so far based on your work up on
the sage-combinat patch server. I made a blog posting about it which you can
find at http://blog.phasing.org . I also put up syntax-highlighted versions
http://blog.phasing.org/static/species/ , and there is a static demo page
http://sage.math.washington.edu/home/mhansen/CombinatorialSpeciesDemo.html

Many thanks. Is there a documented version available? I tried to understand
what happens for isomorphismtypes of (usual) composition, but I failed...

I guess, the code in question is

def _isomorphism_types(self, s):
"""
EXAMPLES:
sage: from sage.combinat.species.species import SetSpecies, CycleSpecies, PermutationSpecies
sage: E = SetSpecies(); C = CycleSpecies()
sage: L = E(C)
sage: len(L.isomorphism_types([1,2,3]).list())
3
"""
return self._composition_aux("isomorphism_types", s)

def _composition_aux(self, attr, s):
structure_class = self._structure_class
from sage.combinat.cartesian_product import CartesianProduct
P = PartitionSpecies()
for pi in getattr(P, attr)(s):
gs = CartesianProduct(*[getattr(self._G,attr)(part) for part in pi])
fs = getattr(self._F,attr)(pi)
for res in CartesianProduct(fs, gs):
yield structure_class(self, *res)

This looks deceptively simple. Are you sure it's correct?

In particular, I couldn't find Knuth's multipartitions anywhere. Were you able
to do without? Help is much appreciated.

I was wondering if you'd be willing to release Aldor-Combinat to me under GPL
v2 or later since that is the license I'd like to release my code under to be
compatible with the rest of Sage.

I cannot answer that one, but I guess it shouldn't be a problem. It's not a
problem for me, at least.

I'm going to be doing some work with Robert Miller in upcoming weeks on
generating isomorphism class representatives for functorial composition. He
wrote a clean-room implementation of the algorithms in nauty for graph
isomorphism testing and generating non-isomorphic simple graphs. This summer
he's working on generalizing that code to work with other types of
combinatorial objects.

Wow.

I'll probably be working on the multisort case later on. Due to lack of
funds, I can't make it out to RISC this summer, but I'd be more than happy to
join in your discussions about multisort species.

I did most of the maths involved (i.e., how to generate isotypes of a
composition of multisort species), it's mainly a problem of representation.
The trouble is, so far I did not find a reasonable way to do composition such
that the output are *representatives* of isomorphismtypes -- the approach taken
in the trunk version of Ralf's code and mine. But if your code above solves
this problem, then there is little left to do!

In iso-experiment, which is the branch implementing proper isotypes of
composition, the labels are replaced by all ones. But obviously, that won't
work for functorial composition...

Martin


-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Ralf Hemmecke]

Post by Martin Rubey
Many thanks. Is there a documented version available?

Martin, when I looked at that code, I was asking myself the same
question. I guess Mike might answer: the documentation is at
http://www.risc.uni-linz.ac.at/people/hemmecke/aldor/combinat/index.html
I find that very unsatisfying. I've put *a lot* of energy in the
documentation which probably caused that Mike was able to implement that
stuff so quickly. Now, if in the future we would like to transfer some
ideas from sage-combinat to aldor-combinat. We are in a very bad
situation. That's somehow unfair and I hope that people working on
sage-combinat will do a bit more than writing doc-strings. Mike, just
imagine I had not documented the way I deal with 'approximateOrder'. I
guess you would have had very hard times to understand my code.

Where is all your background information and your design decisions. You
probably could not follow the Aldor approach exactly. Where do I find a
documentation of the different design?

[snip]

Post by Martin Rubey

I was wondering if you'd be willing to release Aldor-Combinat to me under GPL
v2 or later since that is the license I'd like to release my code under to be
compatible with the rest of Sage.

I cannot answer that one, but I guess it shouldn't be a problem. It's not a
problem for me, at least.

So, before I say yes, what does that actually mean? And why do you need
it? You are not using Aldor-code anyway.

My position is actually as follows. AC is under GPL2, because GPL3 was
not available when we started. Now I am not really against adding "and
later versions" to our GPL license. But first explain, why you need that.

Post by Martin Rubey

I'll probably be working on the multisort case later on. Due to lack of
funds, I can't make it out to RISC this summer, but I'd be more than happy to
join in your discussions about multisort species.

I did most of the maths involved (i.e., how to generate isotypes of a
composition of multisort species), it's mainly a problem of representation.
The trouble is, so far I did not find a reasonable way to do composition such
that the output are *representatives* of isomorphismtypes -- the approach taken
in the trunk version of Ralf's code and mine. But if your code above solves
this problem, then there is little left to do!

Mike, actually, I'd like to follow your code using mercurial, but I've
no experience with it. If you could give some hint on what to do exactly
to be always up-to-date with your latest sage-combinat and what to do to
actually run it.

BTW, I haven't looked into Multisort species for some time.
Theoretically that is not too difficult. Why I don't go on with it is,
because Aldor doesn't let me do the definition as nicely as I want it.

Basically, I'd like to write

F(G,H,K)

similar to what is done in the univariate case (see
http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatsu26.html#x40-580008.13

Actually that is not a problem for bi- tri-, ... n-variate species.
But that would mean n implementations of basically equivalent code.
As you might guess, I don't want to double code and rather write generic
code for that situation. Aldor doesn't let me specify this at compile
time. Since Python is interpreted, you might be more lucky.

Best regards

Ralf

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Mike Hansen]

Post by Martin Rubey
Many thanks. Is there a documented version available?

Martin, when I looked at that code, I was asking myself the same question. I
guess Mike might answer: the documentation is at
http://www.risc.uni-linz.ac.at/people/hemmecke/aldor/combinat/index.html
I find that very unsatisfying. I've put *a lot* of energy in the
documentation which probably caused that Mike was able to implement that
stuff so quickly. Now, if in the future we would like to transfer some ideas
from sage-combinat to aldor-combinat. We are in a very bad situation. That's
somehow unfair and I hope that people working on sage-combinat will do a bit
more than writing doc-strings. Mike, just imagine I had not documented the
way I deal with 'approximateOrder'. I guess you would have had very hard
times to understand my code.

Yes, there were places where the documentation was very helpful.
There were also places where the actual Aldor code was the most
helpful.

Where is all your background information and your design decisions. You
probably could not follow the Aldor approach exactly. Where do I find a
documentation of the different design?

I guess my first priority was to get code out for people to play
around with and to get feedback on the design since it is definitely
not set in stone. Code is much easier to refactor than documentation.
I'll write more big picture documentation when I know that things
have settled down. Why types of questions would be the most useful
for you to have answers to?

So, before I say yes, what does that actually mean? And why do you need it?
You are not using Aldor-code anyway.
My position is actually as follows. AC is under GPL2, because GPL3 was not
available when we started. Now I am not really against adding "and later
versions" to our GPL license. But first explain, why you need that.

If you don't view my code as a derived work, then there is no issue
and nothing needs to be done. If you do view it as a derived work,
then I can't release it under GPL v2 or later (which is the license
for Sage code since it is the GPL license compatible with the most
software). You could release a copy just to me under v2 or later, and
I wouldn't distribute your code under that license. You could leave
the version on the web under GPLv2.

Post by Martin Rubey

I'll probably be working on the multisort case later on. Due to lack of
funds, I can't make it out to RISC this summer, but I'd be more than happy to
join in your discussions about multisort species.

I did most of the maths involved (i.e., how to generate isotypes of a
composition of multisort species), it's mainly a problem of
representation.
The trouble is, so far I did not find a reasonable way to do composition such
that the output are *representatives* of isomorphismtypes -- the approach taken
in the trunk version of Ralf's code and mine. But if your code above solves
this problem, then there is little left to do!

Mike, actually, I'd like to follow your code using mercurial, but I've no
experience with it. If you could give some hint on what to do exactly to be
always up-to-date with your latest sage-combinat and what to do to actually
run it.

If you have a copy of Sage right now, you can download this script
http://wiki.sagemath.org/combinat/Mercurial?action=AttachFile&do=get&target=sage-combinat,
make it executable, make sure sage is in your current path, and run
"./sage-combinat install". This will clone a copy of your sage
repository, make one for combinat, and apply our patches there. The
next time you start up sage, it will be with the combinat/ branch and
have our patches applied. If you do "./sage-combinat update", it will
update to our latest patches. To make them active, you run "sage -br
combinat"

There is a fairly thorough overview of our development process at
http://wiki.sagemath.org/combinat/Mercurial

BTW, I haven't looked into Multisort species for some time. Theoretically
that is not too difficult. Why I don't go on with it is, because Aldor
doesn't let me do the definition as nicely as I want it.
Basically, I'd like to write
F(G,H,K)
similar to what is done in the univariate case (see
http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatsu26.html#x40-580008.13
Actually that is not a problem for bi- tri-, ... n-variate species.
But that would mean n implementations of basically equivalent code.
As you might guess, I don't want to double code and rather write generic
code for that situation. Aldor doesn't let me specify this at compile time.
Since Python is interpreted, you might be more lucky.

I see. So the issue is that Aldor classes/categories can't take
variable number of parameters? I guess I avoid the problem by having
my species be objects/elements instead of classes/domains/categories.

--Mike

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Ralf Hemmecke]

Post by Mike Hansen

Post by Ralf Hemmecke
Basically, I'd like to write
F(G,H,K)
similar to what is done in the univariate case (see
http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatsu26.html#x40-580008.13
Actually that is not a problem for bi- tri-, ... n-variate species.
But that would mean n implementations of basically equivalent code.
As you might guess, I don't want to double code and rather write generic
code for that situation. Aldor doesn't let me specify this at compile time.
Since Python is interpreted, you might be more lucky.

I see. So the issue is that Aldor classes/categories can't take
variable number of parameters?

No. There is Tuple for such issues. In fact -> is a type constructor in
Aldor with the following definition.

((A: Tuple Type) -> (R: Tuple Type)): with == add;

which later allows you to write functions of the form

f: (A, B, C) -> (D, E)

and -> is an infix type constructor that allows any numer of arguments
before and after it. So if I define

X(T: Tuple PrimitiveType): with == add;

then X is a type constructor that can be uses like

X()
X(String)
X(Integer)
X(String, Integer)
etc.

But Aldor would not allow me to write X(TextWriter) since the domain
TextWriter is not of type PrimitiveType. So there is type-safety here.

The problem actually is if you have a functor
F: PrimitiveType->PrimitiveType
which I want to apply to every element of the tuple, then there is no
way to express that in Aldor. Well, actually, there is, but it's not
nice and the compiler doesn't like it. It is basically an identification
problem. Second, the construction of elements of such a type is somehow
impossible.

Post by Mike Hansen
I guess I avoid the problem by having
my species be objects/elements instead of classes/domains/categories.

Well, somehow I seem to have seen it. You said something like
L.define(E+X*L) or something like that. I think I have to look more
closely to your define method.

Ralf

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Ralf Hemmecke]

Post by Mike Hansen
I guess my first priority was to get code out for people to play
around with and to get feedback on the design since it is definitely
not set in stone.

That's the usual way. But I don't personally like to play around with
code whose background is not nicely explained.

Post by Mike Hansen
Code is much easier to refactor than documentation.

That's an argument for not having documentation at all. I like that. ;-)

Post by Mike Hansen
I'll write more big picture documentation when I know that things
have settled down.

Well, you know, I'd like to learn about design ideas as they develop.
There might be errors in the docs, but it might lead to discussion and
finally makes everything better faster. If I have to interpret Python
code (a language that I don't yet know), it just costs me a lot of time
to understand the language and your design ideas from the code.

Of course, documentation is a waste of time for you and for the current
code. But look at yourself in 2 years and other now. By documentation
you help them. (For example, I would, myself, have hard times to believe
that this 'approximateOrder' think works as expected in AC. That would
could me certainly more time now to find a bug (without documentation)
than it costed me to write down my ideas one year ago.

Post by Mike Hansen

So, before I say yes, what does that actually mean? And why do you need it?
You are not using Aldor-code anyway.
My position is actually as follows. AC is under GPL2, because GPL3 was not
available when we started. Now I am not really against adding "and later
versions" to our GPL license. But first explain, why you need that.

If you don't view my code as a derived work, then there is no issue
and nothing needs to be done.

Oh, interesting. It would not have come to my mind that one can consider
a python translation of an aldor program a 'derived work'. Could you
point me to the section of the GPL2 that speaks about it? Maybe my
English is not good enough to understand a text that is more written for
lawyers than for ordinary people. And you perhaps know that certain
sections of the GPL are not applicaple in Europe (or Germany in particular)?

Post by Mike Hansen
If you have a copy of Sage right now

I don't have at the moment.

, you can download this script

Post by Mike Hansen
http://wiki.sagemath.org/combinat/Mercurial?action=AttachFile&do=get&target=sage-combinat,
make it executable, make sure sage is in your current path, and run
"./sage-combinat install". This will clone a copy of your sage
repository, make one for combinat, and apply our patches there. The
next time you start up sage, it will be with the combinat/ branch and
have our patches applied. If you do "./sage-combinat update", it will
update to our latest patches. To make them active, you run "sage -br
combinat"

So assume I have mercurial installed, could you give the list of
commands that get's the sage repository to my computer so that I could
say "./configure && make && make install".

From that I should be able to get sage-combinat from above. Hmmm, if I
look at that, I would then have two complete copies of the sage
repository on my computer, one with the patches and one without. Is that
true?

Post by Mike Hansen
There is a fairly thorough overview of our development process at
http://wiki.sagemath.org/combinat/Mercurial

Shouldn't there be a command like

hg clone <<URL to original sage repository>>

or something like that? I've never worked with hg. :-(

Ralf

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Mike Hansen]

Well, you know, I'd like to learn about design ideas as they develop. There
might be errors in the docs, but it might lead to discussion and finally
makes everything better faster. If I have to interpret Python code (a
language that I don't yet know), it just costs me a lot of time to
understand the language and your design ideas from the code.
Of course, documentation is a waste of time for you and for the current
code. But look at yourself in 2 years and other now. By documentation you
help them. (For example, I would, myself, have hard times to believe that
this 'approximateOrder' think works as expected in AC. That would could me
certainly more time now to find a bug (without documentation) than it costed
me to write down my ideas one year ago.

Yes, yes, I understand the literate programming mantra, but I don't
fully buy into it. Anyways, if you're seriously interested in
spending time looking at my code, I'll write more documentation for
you. Where would you like me to start? Do you have any specific
questions?

Oh, interesting. It would not have come to my mind that one can consider a
python translation of an aldor program a 'derived work'. Could you point me
to the section of the GPL2 that speaks about it? Maybe my English is not
good enough to understand a text that is more written for lawyers than for
ordinary people. And you perhaps know that certain sections of the GPL are
not applicaple in Europe (or Germany in particular)?

It's more a question of copyright law than the GPL itself so it varies
from country to country. From http://www.rosenlaw.com/lj19.htm :

"Almost everyone agrees on this: If you take the copyrighted source
code of any program and physically modify it – actually revise the
program or translate it into another computer language – you have
created a derivative work of that program. That's the simple case.
If you do such a thing with a program licensed under the GPL or the
OSL, then you must honor the reciprocity provision and publish the
source code of your derivative works that you distribute."

So assume I have mercurial installed, could you give the list of commands
that get's the sage repository to my computer so that I could say
"./configure && make && make install".

The closest thing is downloading the source tarball from
http://sagemath.org/download.html, extracting it, and typing "make".
The Sage library itself is only a small part (but important) of Sage.
The 5 or so million lines of code in the Sage distribution are not all
in one large repository.

From that I should be able to get sage-combinat from above. Hmmm, if I look
at that, I would then have two complete copies of the sage repository on my
computer, one with the patches and one without. Is that true?

Yep. You could also just apply the patches to the main branch if you wanted.

--Mike

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

[Martin Rubey]

(I hope you don't mind that I forward to aldor-combinat. But I'll describe an
idea below, that I want to archive there...)

Post by Martin Rubey
This looks deceptively simple. Are you sure it's correct?

This is just for ordinary species.

what is an "ordinary species"? You mean, it's only for the structures, not the
isotypes?

The only differences between it and your code for isomorphism types is that I
use the getattr stuff to avoid writing the same algorithm twice and that I
use CartesianProduct which I had already written elsewhere in Sage.

Are you saying that you took the algorithm from trunk? If so, then it's
incorrect. Unfortunately, I don't have an example right now, but I think there
should be an appropriate test in our testsuite (which is failing in trunk, of
course). I should make it explicit, I admit.

I'd be *very* interested in a *good* design for isotypes that works with
representatives. I think one way to do it would be to separate the structure
from it's labels. More precisely, a structure could be represented as an
"isotype" together with a bijection that gives the structure the appropriate
labelling. Of course, this representation is not unique, i.e. we can
represent, say, the binary tree

(1,(2,3))

as

isotype = (1,(2,3)) - pi = id

or as

isotype = (2,(1,3)) - pi = 2->1, 1->2, 3->3

But maybe, this wouldn't matter for the generation of compositions as long as
the representation is deterministic.

Martin


-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08