find_stat in Sage, the combinatorial_map decorator and its consequences

[Nathann Cohen]

Hellooooooooo everybody !

I just noticed in today's release the presence of two tickets that I had missed while they were being reviewed, and I really regret it.

Those two tickets are #14734 and #14732. Each of them adds to Graph and Poset a one-line method which I personnally find totally useless. Of course, while I don't see the point of these methods, I don't expect to find everything that Sage can do meaningful, as I have after all my own personnal restricted field of interest, *but* the fact that these functions could be written in 30 characters really makes me think harder.

And after having thought for a loooooong time, I have reached the staggering conclusion that the only reason why these things have been added to Sage is not because they provide a useful addition to Sage's features *BUT* mainly because they provide a nice addition to find_stat. Now I really have nothing against find_stat, I actually rather like what it does. But it is a website and an independent project, and I don't see why on earth Sage should now be developped according to find_stat's needs.

Right now, find_stat seems to work with decorators over Sage's functions. It is all very nice. But then whenever some addition must be made to find_stat's combinatorial maps there must be a corresponding Sage function, and I think that adding functions to Sage just because find_stat needs them is really going too far. More than that, the @combinatorial_map decorator replaces the method that it decorates with a CombinatorialMap object which contains the decorated function. This means that a call to what used to be a function is replaced by a call to the new object, which is then forwarded to the first method.

And all this to solve find_stat's own problems.

Once more I like what find_stat is and what it tries to do. But it's a nice independent project, not an invasion. Sage is about building a software to run mathematical computations, and there's obviously no problem if find_stat uses it to build the database or whenever it wants to, but on the other hand Sage has no reason to run find_stat's code unless we want it to.

Christian invited me to be noisy about that and ask what you guys think of it. I believe that any information that find_stat needs could be added in the method's docstrings at zero cost (find_stat would then parse it and gather the data it needs) or in an independent module when there is no corresponding Sage function. There are actually many workarounds.

Sooooooooooooooooo please find_stat guys, let's talk about this but do not give your opinions while totally ignoring some elementary facts. There are very factual things like 

- "Why should we lose *ANY* computations on an existing Sage function because of find_stat", or

- "why does your development model means that you are forced to add function to Sage's objects if you want to add a map" ? To me #14734 is a patch that improves find_stat and find_stat only. Not Sage. Your development model just forces you to add stuff to Sage when you want it on your website, and that's a very factual problem.

Please, at the very least please tell me if you ACKNOWLEDGE that these things are problems. And if not, please tell me why.

Oh, and I'm sorry for constantly complaining. I hate to complain. I hate to always fight against everybody. Especially because I do that constantly. But it's not because I hate it that I am about to shut up whenever everybody around agree together that black is white and that it has always been like that.

See you !

Nathann

[Volker Braun]

What exactly is your objection?

* Is the to_partition() method too obscure that nobody / too few people have a use for it?

* Is the decorator overhead (which is just a constant factor, that is, the same complexity) too much?

* Do you object, in principle, to anything that uses more than the absolute minimum of machine instructions? Why are you using and interpreted language and not a compiled language? Or better, why not hand-crafted assembler?

[Nathann Cohen]

Hellooooooo !

> What exactly is your objection?

Mainly, that the addition of a code in Sage could be justified by saying that "it is needed by a third-party software, even though it has no use in Sage". That's my main objection.

> * Is the to_partition() method too obscure that nobody / too few people have a use for it?

Well. I find the name *REALLY* vague for a start. Especially when we already have one thousand "connected components" functions with very explicit names.

Then, I obviously cannot say that nobody needs that. I dont, that's for sure, but that's only me. This being said, as far as I can tell the only reason for adding this function is to create a map for find_stat. And I can't stand this way of doing things.

Then there is the problem of the manyyyyyyy methods we already have in those two classes, and the related comment I added to the ticket.

> * Is the decorator overhead (which is just a constant factor, that is, the same complexity) too much?

Come on Volker. You don't just read about computers, you use them too. How can you talk about "constant factors" ? Everything is a constant, even the different between Cython and Python, and between Cython and C.

I object to that because it does not appear to be necessary at all, and because it can eventually be added to functions to which it will add a non-negligible factor. So why should we pay anything for that when we can do it for free ? It does not make sense to pay *anything* for find_stat even when the code you run has nothing to do with it !

> * Do you object, in principle, to anything that uses more than the absolute minimum of machine instructions? 

If I see a code that does unnecessary computations and if there is a way to improve it, I try to make this improvement. In this case, the development of find_stat impacts many functions and there is no justification for that. Why should we keep it this way ?

> Why are you using and interpreted language and not a compiled language? 

Well, I need stuff that is in Sage, and Sage is written in Python. So I write Python.

When I can, I write Cython code. More generally, the dirtiness of my personal code is my own problem. The dirtiness of what I put into Sage is everybody's problem, so I try to keep it to a minimum.

> Or better, why not hand-crafted assembler?

Jeroen would refuse the patch because it wouldn't be platform-independent, and I hate to make Jeroen angry. Otherwise I would obviously rewrite everything I see in assembly.

Nathann

[Volker Braun]

On Wednesday, June 19, 2013 12:37:03 PM UTC-7, Nathann Cohen wrote:

> What exactly is your objection?
Mainly, that the addition of a code in Sage could be justified by saying that "it is needed by a third-party software, even though it has no use in Sage". That's my main objection.

If that is the case then why are you writing a rambling page-long post about speed penalty of decorators? 

How about we ask somebody who actually works on combinatorics whether this is a useful method. If not, remove it.

[Nathann Cohen]

> If that is the case then why are you writing a rambling page-long post about
> speed penalty of decorators?

>_<

Volker, did you fail to notice that an email can make several points at once ? I mean, how come you reduced my 1000 lines to one sentence saying something that I never claimed ? Decorators have their own interests. I played with "@parallel" yesterday. But I am pretty sure that my point was mostly that decorators are not adapted in this situation, and that it can apparently be rewritten more efficiently.

That was for the "speed" part.

For the "development model" part, I claimed that it was not very sound to require that any map that is useful in find_stat should become a method in Sage. I'm pretty sure that I mentionned that too.

> How about we ask somebody who actually works on combinatorics whether this
> is a useful method. If not, remove it.

Well, I do work on graphs from time to time. 

But even if my opinion was of any importance, or if I reached on your scale the height of somebody who actually works on combinatorics, it would not be sufficient to say that a function should be removed. I can't prove that something is useless, what I can do is say that it has been added for wrong reasons.

Hmmmm.....

Nathann

[Volker Braun]

On Wednesday, June 19, 2013 1:25:22 PM UTC-7, Nathann Cohen wrote:

But I am pretty sure that my point was mostly that decorators are not adapted in this situation, and that it can apparently be rewritten more efficiently.

Everything can be rewritten more efficiently, just at a cost in code size / maintainability and human effort. Much like Python itself, decorators are a way to make code smaller and easier to read for humans, at a certain performance penalty. Don't optimize for speed until profiling showed that this is a performance bottleneck.

[Nathann Cohen]

> Everything can be rewritten more efficiently, just at a cost in code size /
> maintainability and human effort. Much like Python itself, decorators are a
> way to make code smaller and easier to read for humans, at a certain
> performance penalty. Don't optimize for speed until profiling showed that
> this is a performance bottleneck.

I am glad to know that there is a general-purpose rule to tell me that
I should refrain from thinking. I guess that this also answers my
other points about the development model.

Thank you very much,

Nathann

[John Cremona]

I confess that I did not understand Nathan's objection, not being
familiar with find_stat or the kind of decorator used in that added
function. But I myself have added functions to Sage to help a
separate project which uses Sage, namely the lmfdb (see
http://www.lmfdb.org/). The cost to Sage users who never work with
elliptic curves and their labels seems trivial, and it never occurred
to me that anyone would object to such functionality.

Perhaps I completely misunderstood though.

John

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[tom d]

Indeed, the whole reason many of us do any work on Sage is to help our research projects.  The principle of helping Sage to help our individual mathematical pursuits is actually what makes it consistently stronger as a system.

Find Stat is a great tool for the community, and I think there are other contexts even inside of Sage where identifying maps between combinatorial objects could be quite helpful.  (We were thinking today about objects with representations as different kinds of combinatorial objects, with different algorithms available in the different representations; having an explicit list of maps between such objects could be useful for some type-switching or coercion.)

cheers!

[kcrisman]

Having read this (and the tickets), I guess I have three questions.

1) Does this really slow things down in any significant way, or could a universal implementation of it in many objects do so? (Where significant might have different tolerances for different people.)

2) Does the change to making certain things be CombinatorialMap class substantially (negatively) change Sage functionality (including available methods, introspection and tab-completion)?

3) Would it make more sense for this to be a patch applied to Sage by the FindStat folks?  It doesn't seem like it would exactly be a really hard one, nor one that would need frequent rebasing.

Usually we are in the position of downstream, and we don't ask upstream projects to do things unique to Sage (for instance, Maxima and Pari have their own design decision that would make this annoying); at the same time, helping a downstream project without any substantial effort has some merit for consideration, though I'd be worried about precedent.

[Volker Braun]

On Wednesday, June 19, 2013 1:57:11 PM UTC-7, Nathann Cohen wrote:

I am glad to know that there is a general-purpose rule to tell me that
I should refrain from thinking. 

Au contraire, I'm trying to encourage you to think. And the most important rule about building fast software is to find the place where it matters to spend your effort on, instead of going off on tangents about how this or that could have been done more efficiently.

If you don't want to listen to me how about the Cython tutorial (http://docs.cython.org/src/tutorial/profiling_tutorial.html#profiling-tutorial): "Never optimize without having profiled. Let me repeat this: Never optimize without having profiled your code. Your thoughts about which part of your code takes too much time are wrong. At least, mine are always wrong."

[Florent Hivert]

On Wed, Jun 19, 2013 at 03:02:27PM -0700, kcrisman wrote:
> Having read this (and the tickets), I guess I have three questions.
>
> 1) Does this really slow things down in any significant way, or could a
> universal implementation of it in many objects do so? (Where significant
> might have different tolerances for different people.)

First of all, before ranting about speed someone should measure the slow
down. If I remember correctly, we already did it once with Christian and the
slow down was less than 10% which is in my opinion perfectly acceptable. If an
error was made, it is that we didn't keep any trace of that experiment.

If there is a significant slow down, I'm pretty sure that the functionality
can be achieved with close to zero and maybe even zero slow down. The
combinatorial map decorator create a new class only for adding a few attribute
to a function. On can directly add attribute to a function without creating a
new class. There is *ZERO* slow down while calling the function, and a
decorator is certainly the good way to do it:

sage: def add_bla(f):
....: f.is_combinatorial_bla = True
....: return f
sage: @add_bla
....: def toto(x):
....: return x+1
sage: toto.is_combinatorial_bla
True
sage: toto(x)
x + 1
sage: def tata(x):
....: return x+1
sage: %timeit toto(x)
100000 loops, best of 3: 17.4 us per loop
sage: %timeit tata(x)
100000 loops, best of 3: 17.5 us per loop

And even if this trick doesn't solve the problem, Cythonizing properly the
decorator should reduce the slow down in a vast amount.

> 2) Does the change to making certain things be CombinatorialMap class
> substantially (negatively) change Sage functionality (including available
> methods, introspection and tab-completion)?

It certainly will change Sage positively completely independently from
find_stat. We definitely need to tag combinatorial maps to know for example
whether they are injective surjective of bijective..

> 3) Would it make more sense for this to be a patch applied to Sage by the
> FindStat folks? It doesn't seem like it would exactly be a really hard
> one, nor one that would need frequent rebasing.

See my previous remark !

Florent

[kcrisman]

On Wednesday, June 19, 2013 6:35:42 PM UTC-4, fhivert wrote:

On Wed, Jun 19, 2013 at 03:02:27PM -0700, kcrisman wrote:
> Having read this (and the tickets), I guess I have three questions.
>
> 1) Does this really slow things down in any significant way, or could a
> universal implementation of it in many objects do so? (Where significant
> might have different tolerances for different people.)

First of all, before ranting about speed someone should measure the slow
down.

I didn't rant, just asked, since Nathann ranted :-)

> 2) Does the change to making certain things be CombinatorialMap class
> substantially (negatively) change Sage functionality (including available
> methods, introspection and tab-completion)?

It certainly will change Sage positively completely independently from
find_stat. We definitely need to tag combinatorial maps to know for example
whether they are injective surjective of bijective..

Right, but will it change any functionality?  I assume it inherits from something in a nice way, but I could imagine this to be annoying.  Other decorators, at least at one time, made command-line introspection not that useful, if I recall correctly.  But that might be irrelevant here.

I don't really have a horse in the running here, but it is a nice opportunity for the community to think about its relation to downstream projects, of which there are now several.

[Andrew Mathas]

I agree with Nathan's comments: if the find_stat decorators are adding significant overhead then they need to be looked at.

As Volker said, however, before we start this conversation we should profile them to find out what the cost is (unlike Floent I would not find a 10% slow-down acceptable:).

On the question whether the find_stat people should be adding decorators for their own (nefarious?:) purposes, well, every bit of sage code that I have written has been for use in my own own independent research projects - or to make sage more the way I would like it. I think that this is not uncommon, so I don't see an issue here. The real question is whether the find_stat group are adding functionality which other sage uses find useful. I think that having "indepdent" applications of sage is also very advantageous to the sage project.

Andrew

[Robert Dodier]

On 2013-06-19, kcrisman <kcri...@gmail.com> wrote:

> Usually we are in the position of downstream, and we don't ask upstream
> projects to do things unique to Sage (for instance, Maxima and Pari have
> their own design decision that would make this annoying);

For the record, I would be interested to hear about stuff that the Sage
developers would like to see in Maxima. No guarantees that it would be
implemented, as I'm sure you understand. Can't speak for anyone else,
but I have a personal interest in interoperability between Maxima and
other software, so I'd be interested to know what kinds of problems
other developers have run into.

There are at least two venues for such discussions, the Maxima mailing
list, which is more widely read but any proposals are not easy to find
after the fact, and the feature request tracker at Sourceforge. Take
your pick.

best

Robert Dodier

[kcrisman]

> Usually we are in the position of downstream, and we don't ask upstream
> projects to do things unique to Sage (for instance, Maxima and Pari have
> their own design decision that would make this annoying);

For the record, I would be interested to hear about stuff that the Sage
developers would like to see in Maxima. No guarantees that it would be
implemented, as I'm sure you understand.

Way more robust assumptions framework! Lots and lots more indefinite integrals!  Really really awesome solving that beats the proprietary M's!  :-) 

[Jason Grout]

On 6/19/13 10:20 AM, Nathann Cohen wrote:
> But then whenever some addition must be made to find_stat's
> combinatorial maps there must be a corresponding Sage function, and I
> think that adding functions to Sage just because find_stat needs them is
> really going too far.

As a hypothetical, what if Sage absorbed the findstat database as
another spkg?

(okay, I'm going back to coding...)

Jason

[Andrey Novoseltsev]

On Jun 19, 12:37 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> If I see a code that does unnecessary computations and if there is a way to
> improve it, I try to make this improvement.

Sorry, could not resist remembering lines from you patch on #13747
like

(e for e in level)

later replaced with

iter(level)

when the correct version was definitely

level

;-)

[Nathann Cohen]

Helloooooooooo !

> 1) Does this really slow things down in any significant way, or could a universal implementation of it in many objects do so? (Where significant might have different tolerances for different people.)

I don't think that it currently does slow anything down very much, but what I claim is that this code should not even been run in mathematical parts of Sage by persons who do not care about find_stat. I will post a timing in answer to Florent's very dishonest message.

> 2) Does the change to making certain things be CombinatorialMap class substantially (negatively) change Sage functionality (including available methods, introspection and tab-completion)?

No, I don't think so and I never claimed it. What it does, however, is encourage the creation of new methods that have no interest for Sage users and only matter to find_stat, which is why it should be implemented on their side, not on ours.

> 3) Would it make more sense for this to be a patch applied to Sage by the FindStat folks?  It doesn't seem like it would exactly be a really hard one, nor one that would need frequent rebasing.

I"m obviously all for it.

> Usually we are in the position of downstream, and we don't ask upstream projects to do things unique to Sage (for instance, Maxima and Pari have their own design decision that would make this annoying); at the same time, helping a downstream project without any substantial effort has some merit for consideration, though I'd be worried about precedent.

Yep. Feature request is something, but "rewrite what they have to solve our problems" definitely isn't respectful.

Nathann

[Nathann Cohen]

Hello !

> First of all, before ranting about speed someone should measure the slow
> down. If I remember correctly, we already did it once with Christian and the
> slow down was less than 10% which is in my opinion perfectly acceptable. If an
> error was made, it is that we didn't keep any trace of that experiment.

Okay. Then welcome to the graph code where a 10% speedup is not acceptable. I just slept in my office because I want to rewrite 14535 properly, without any slowdown.

But that's not the point. Why would you accept a 10% slowdown in exchange for NOTHING ? What is the added value for Sage of configuring find_stat's database using decorators when we could do it in a different way that does not put find_stat's code between Sage code and its users ?

10% is what I was told to accept on #14535 in exchange for the mutability of graphs. This would slow ALL graphs down, not only immutable one. Why is it so easy for you to slow down other people's code in exchange for the features you want ? Some people sweat for the percents !

> If there is a significant slow down, I'm pretty sure that the functionality
> can be achieved with close to zero and maybe even zero slow down. The
> combinatorial map decorator create a new class only for adding a few attribute
> to a function. On can directly add attribute to a function without creating a
> new class. There is *ZERO* slow down while calling the function, and a
> decorator is certainly the good way to do it:
>
> sage: def add_bla(f):
> ....:     f.is_combinatorial_bla = True
> ....:     return f
> sage: @add_bla
> ....: def toto(x):
> ....:     return x+1
> sage: toto.is_combinatorial_bla
> True
> sage: toto(x)
> x + 1
> sage: def tata(x):
> ....:     return x+1
> sage: %timeit toto(x)
> 100000 loops, best of 3: 17.4 us per loop
> sage: %timeit tata(x)
> 100000 loops, best of 3: 17.5 us per loop

How dishonnest is that ? Why on earth did not you make the test using the actual combinatorial_map decorator ?


sage: from sage.combinat.combinatorial_map import combinatorial_map
sage: class C:
....:         @combinatorial_map
....:         def a(self,x):
....:                 return x+1
....:         def b(self,x):
....:                 return x+1
....:    
sage: c = C()
sage: %timeit c.a(5)
1000000 loops, best of 3: 1.03 us per loop
sage: %timeit c.b(5)
1000000 loops, best of 3: 343 ns per loop

That's a 3x in a non-existing case, which make it almost negligible for any application, and that is not even my point. WHY should this thing be implemented like that when there are non-intrusive ways to make find_stat work ?

> It certainly will change Sage positively completely independently from
> find_stat. We definitely need to tag combinatorial maps to know for example
> whether they are injective surjective of bijective..

You do, and I said in a previous email that something like that could be achieved by adding information to the docstrings. Zero cost, and it even adds the information to the documentation. I NEVER F******** claimed that this information was useless. I said that it should be rewritten in such a way that we never have to pay for it when we run computations, as it seems possible.

Nathann

[Nathann Cohen]

> > It certainly will change Sage positively completely independently from
> > find_stat. We definitely need to tag combinatorial maps to know for example
> > whether they are injective surjective of bijective..
>
> You do, and I said in a previous email that something like that could be achieved by adding information to the docstrings. Zero cost, and it even adds the information to the documentation. I NEVER F******** claimed that this information was useless. I said that it should be rewritten in such a way that we never have to pay for it when we run computations, as it seems possible.

And I can also add to this comment that you can actually implement this feature using decorators at no cost, because you can do this without changing the function at all. If you want a decorator that does that

@find_stat_properties(surjective = True, from=whatever, to=whatever2)

and registers the method in some database in Sage, then the decorator can return the very function it has been given and there is nothing wrong with that. Right now there is a class in the middle, though.

Nathann

[Simon King]

Hi!

On 2013-06-20, Nathann Cohen <nathan...@gmail.com> wrote:
> And I can also add to this comment that you can actually implement this
> feature using decorators at no cost, because you can do this without
> changing the function at all. If you want a decorator that does that
>
> @find_stat_properties(surjective = True, from=whatever, to=whatever2)
>
> and registers the method in some database in Sage, then the decorator can
> return the very function it has been given and there is nothing wrong with
> that. Right now there is a class in the middle, though.

+1

From what we heard at SD49, this is about registering certain methods as
"being useful to apply when exploring combinatorial statistics".

*Registering*

And this should really not be done on the level of the method being
registered. There should be a database of "useful combinatorial maps", and
the decorator should do nothing more than adding a method to this database.

Actually, I can imagine that this would make life *easier* for the find_stat
people.

Best regards,
Simon

[Dima Pasechnik]

On 2013-06-19, Nathann Cohen <nathan...@gmail.com> wrote:
> --20cf301ee7a5191d5204df850b33
> Content-Type: text/plain; charset=ISO-8859-1

>
> Hellooooooooo everybody !
>
> I just noticed in today's release the presence of two tickets that I had
> missed while they were being reviewed, and I really regret it.
>
> Those two tickets are #14734 and #14732. Each of them adds to Graph and
> Poset a one-line method which I personnally find totally useless. Of
> course, while I don't see the point of these methods, I don't expect to
> find everything that Sage can do meaningful, as I have after all my own
> personnal restricted field of interest, *but* the fact that these functions
> could be written in 30 characters really makes me think harder.

Deliberately ignoring the decorator technicalities, I think both #14734
and #14732 have been wrongly designed. (Throw rotten tomatoes at me
now).

Regarding #14734: well, if one adds to Graph a grow_bushy_tail() method
indeed this goes too far. I personally don't get why Bushy_Tail cannot
get a constructor from Graph instead. This would only be justified if
growing bushy tails inside Graph is more efficient than doing it outside
of it.

Same applies to #14732: why on Earth it makes Posets vomit ((c) V.Braun)
Graphs all of a sudden? Shouldn't rather Graph get a constructor from
Posets?

Having said that, the gals and guys responsible for #14734 and #14732 are at
Sagedays 49 now, go and buy them the necessary amount of beer to have
all this sorted out :-)

Dima

[Dima Pasechnik]

On 2013-06-20, Simon King <simon...@uni-jena.de> wrote:
> Hi!
>
> On 2013-06-20, Nathann Cohen <nathan...@gmail.com> wrote:
>> And I can also add to this comment that you can actually implement this
>> feature using decorators at no cost, because you can do this without
>> changing the function at all. If you want a decorator that does that
>>
>> @find_stat_properties(surjective = True, from=whatever, to=whatever2)
>>
>> and registers the method in some database in Sage, then the decorator can
>> return the very function it has been given and there is nothing wrong with
>> that. Right now there is a class in the middle, though.
>
> +1
>
> From what we heard at SD49, this is about registering certain methods as
> "being useful to apply when exploring combinatorial statistics".
>
> *Registering*
>
> And this should really not be done on the level of the method being
> registered. There should be a database of "useful combinatorial maps", and
> the decorator should do nothing more than adding a method to this database.

for this one does not even need a decorator put anywhere in the code...

[Stefan]

> First of all, before ranting about speed someone should measure the slow
> down. If I remember correctly, we already did it once with Christian and the
> slow down was less than 10% which is in my opinion perfectly acceptable. If an
> error was made, it is that we didn't keep any trace of that experiment.

Question: is this a slowdown only in the function call under scrutiny, or a slowdown in the construction of the object? The acceptability of the former depends on whether the function is likely to be used in time-critical applications, the second is definitely unacceptable for an object like Graph.

Nathann's complaint about the out-of-control growth of methods of the Graph object is a very valid issue. In fact, I wonder if it's time to do some redesign and cleanup? Maybe have a graph algorithm database, just like you've got a graph construction database? Like

graphs.algorithms.conversions.to_partition(G)

Cheers,

Stefan.

[Volker Braun]

On Thursday, June 20, 2013 7:37:07 AM UTC-7, Stefan wrote:

Nathann's complaint about the out-of-control growth of methods of the Graph object is a very valid issue

I think we talked about that a few months ago. One should first evaluate whether all / most methods really make sense for all graphs. If not, they should probably be factored out into mixin classes that are dynamically added if the graph has the requisite property. In any case, thats another thread.

[Volker Braun]

On Thursday, June 20, 2013 12:17:48 AM UTC-7, Simon King wrote:

And this should really not be done on the level of the method being
registered. There should be a database of "useful combinatorial maps", and
the decorator should do nothing more than adding a method to this database.

But that is just an implementation detail, once you have the decorator in place in the sources you can change its behavior. For performance-critical paths, one should definitely use an implementation that registers it once. E.g. during doctesting one can then check that the methods labelled with the decorator are exactly the ones in the registry of maps.

Contrary to what Nathan believes, creating the same map again and again in a tight loop is not a case that needs to be optimized. In fact, this special case could be optimized best by maintaining a cache in the decorator if it were relevant. 

[Volker Braun]

On Wednesday, June 19, 2013 11:20:39 PM UTC-7, Nathann Cohen wrote:

sage: from sage.combinat.combinatorial_map import combinatorial_map
sage: class C:
....:         @combinatorial_map
....:         def a(self,x):
....:                 return x+1

Thats not a benchmark, thats masturbating over the call overhead. Unless you can think of a use case where generating the map repeatedly in a tight loop is even remotely useful you'll have to accept the fact that one will want to create the graph and do something with the output. So a sane comparison would be something like this:

sage: def doit_method():

....:         g = Graph({0:{1:'x',3:'a'}, 2:{5:'out'}})

....:         part = g.to_partition()

....:         part.is_empty()

....:     

sage: def doit_manually():

....:         g = Graph({0:{1:'x',3:'a'}, 2:{5:'out'}})

....:         part = Partition(sorted([len(y) for y in g.connected_components()], reverse=True))

....:         part.is_empty()

....:     

sage: 

sage: timeit('doit_manually()')

625 loops, best of 3: 108 µs per loop

sage: timeit('doit_method()')

625 loops, best of 3: 114 µs per loop

Which means that the extra method call and decorator add perhaps 5% overhead in a ridiculously simple graph.

[Nathann Cohen]

> Thats not a benchmark, thats masturbating over the call overhead.

Volker, could you please read aloud the sentence which followed
immediately this example of code ?

"That's a 3x in a non-existing case, which make it almost negligible
for any application, and that is not even my point. WHY should this
thing be implemented like that when there are non-intrusive ways to
make find_stat work ?"

Nathann

[Volker Braun]

On Thursday, June 20, 2013 8:33:47 AM UTC-7, Nathann Cohen wrote:

WHY should this
thing be implemented like that when there are non-intrusive ways to
make find_stat work ?" 

Please propose a mechanism that

  * Only occupies a single line of code

  * Outside of the method body, so it is separated from the actual implementation

  * But not in a separate file, since that is hard to keep in sync

  * If it appears in the documentation, it must be doctestable and flag syntax errors

[Christian Stump]

Dear all,

Thanks Nathann for starting the discussion (though I sometimes think that being a little less aggressive wouldn't hurt).

Let me start with what the positive sides of a combinatorial_map decorator are for us (and I think several of the combinat people do agree here):

- we obtain a better image of which maps between combinatorial collections exist (see in particular the graph at the bottom of http://www.findstat.org/, and the linked more detailed pdf, this is not only interesting for FindStat but provides a nice visualization of how many combinatorial objects in Sage are linked together),

- we can thus easier work on completing the picture. Indeed, we implemented many (~20-30 would be my guess, but I don't know) new maps between combinatorial objects that are interesting for combinatorialists (even those not interested in FindStat).

- we can automatize checks if maps do indeed map to the proper codomain (e.g., StandardTableau.conjugate
returned a Tableau, and not a StandardTableau as desired, see #14258),

- we can automatize many corner case checks (of course, such checks should as well go into the doctests, but if
we automatically apply all these maps on hundreds of elements including corner cases, we already found various bugs in the pre-existing code that were not captured by the doc tests, see e.g. #14724, #14718, #13624).

- we would like more mathematical information to the decorator (though this is not yet done). This would provide more refined automated requests like "Which bijections between Dyck paths and NoncrossingSetPartitions are implemented?". Currently, we can only ask "Which maps from Dyck paths to NoncrossingSetPartitions are implemented?", but I think that is nice to get as well.

Some words on the current implementation:

- I implemented the decorator word by word following the (old) cached_method decorator, this might have been good or not, but it was the best I was able to do.

- Nathann himself tested that the cost of the wrapper when calling the method is very much negligible, here is a test when creating the object

sage: class A:

....:     def a(self,x):
....:         return x

....:    

sage: class B:
....:     @combinatorial_map

....:     def b(self,x):
....:         return x

....:    

sage: %timeit AA = A()
1000000 loops, best of 3: 250 ns per loop

sage: %timeit BB = B()
1000000 loops, best of 3: 249 ns per loop

if there is any better test to check this issue, please do so.

Anyway, the current implementation might be good enough to use, or someone might provide a better implementation, but this is not the point for me, and - if I understand it right - it's not the point for Nathann either. Two of his point are yet to be answered/discussed a bit further:

"Right now, find_stat seems to work with decorators over Sage's functions. It is all very nice. But then whenever some addition must be made to find_stat's combinatorial maps there must be a corresponding Sage function, and I think that adding functions to Sage just because find_stat needs them is really going too far. "

My answer: it is right that - in the current implementation - we need to implement a map between combinatorial collections in Sage and decorate it with @combinatorial_map in order to use this map in FindStat. But we only want to use maps in FindStat that are interesting for mathematicians, and if this is the case, then it should be very valid to have this map as well in Sage. If anyone is interested I could provide a list with methods we implemented for (or better in) Sage because we wanted to have them in FindStat. We can then see if it would have better to implement all these maps in a different project without allowing Sage users to use them as well.

"But it is a website and an independent project, and I don't see why on earth Sage should now be developped according to find_stat's needs."

My answer: All we do is to decorate maps between certain combinatorial collections to provide further information about this map. We then use this information in FindStat, but this information is not only useful for FindStat (at least in my opinion), see as well my comments above about the "positive sides". There might be something not perfect in the actual implementation, but the so far discussed drawbacks seem to be very little, compared to the advantage that a user is e.g. not annoyed anymore that the conjugate of a StandardTableau is not standard anymore, or that there are now all these new maps between the objects implemented. Anyway, if there is a better way of achieving such possibilities I am very positive of doing so (though this will again use someone's time that she might want to use differently). And: we are Sage users and/or developers, so if we want Sage to do sth for us that doesn't hurt (@Nathann: except for philosophical reasons), I don't see the point of not getting Sage doing it for us (as others did similar things before, according to John Cremona and others comments earlier on this thread) and for the combinat community.

Finally, I think that the combinat part of Sage would have been less explored without the implementations done in the context of FindStat, and several combinatorialists only started implementing some maps or new combinatorial objects because FindStat uses them. So imho, the advantages outweigh the drawbacks by far, though there might be the point in minimizing the drawbacks even further.

Best, Christian

[kcrisman]

Having said that, the gals and guys responsible for #14734 and #14732 are at
Sagedays 49 now, go and buy them the necessary amount of beer to have
all this sorted out :-)

Or other beverage as appropriate :)  The shrillness level has gotten a little higher than really necessary, certainly than customary on this list.  

 

[Christian Stump]

On Thursday, June 20, 2013 5:59:55 PM UTC+2, kcrisman wrote:

Or other beverage as appropriate :)  The shrillness level has gotten a little higher than really necessary, certainly than customary on this list.

 Does your comment apply in particular to my last post? I certainly did not want to be shrill - sorry if that was your impression when reading my post.

[Nathann Cohen]

Hellooooooooooooooooooooooo !!

> Thanks Nathann for starting the discussion (though I sometimes think that
> being a little less aggressive wouldn't hurt).

Yes, sorry about that. But it takes a lifetime to get people to admit the most elementary things. I mean, my first message contained two lines of which I said "please tell me if you acknowledge this or not", and so far nobody cared even to answer "no" to them.

> Let me start with what the positive sides of a combinatorial_map decorator
> are for us (and I think several of the combinat people do agree here):

Hmm.... I probably agree with all advantages, what find_stat does is nice and useful. But a decorator is not to me a clean way to do it. That' s really the only thing I have been defending all along. Wrapping the method into classes instead of just registering them somewhere, and requiring the addition of new Sage methods just because find_stat needs them.

Those are really the only points that I try to make. But I probably agree with all advantages that you list below, it's just totally unrelated.

> - we obtain a better image of which maps between combinatorial collections
> exist (see in particular the graph at the bottom of
> http://www.findstat.org/, and the linked more detailed pdf, this is not only
> interesting for FindStat but provides a nice visualization of how many
> combinatorial objects in Sage are linked together),

That's cool.
+1

> - we can thus easier work on completing the picture. Indeed, we implemented
> many (~20-30 would be my guess, but I don't know) new maps between
> combinatorial objects that are interesting for combinatorialists (even those
> not interested in FindStat).

That's cool.
+1

> - we can automatize checks if maps do indeed map to the proper codomain
> (e.g., StandardTableau.conjugate
> returned a Tableau, and not a StandardTableau as desired, see #14258),

That's cool.
+1

> - we can automatize many corner case checks (of course, such checks should
> as well go into the doctests, but if
> we automatically apply all these maps on hundreds of elements including
> corner cases, we already found various bugs in the pre-existing code that
> were not captured by the doc tests, see e.g. #14724, #14718, #13624).

That's cool.
+1

> - we would like more mathematical information to the decorator (though this
> is not yet done). This would provide more refined automated requests like
> "Which bijections between Dyck paths and NoncrossingSetPartitions are
> implemented?". Currently, we can only ask "Which maps from Dyck paths to
> NoncrossingSetPartitions are implemented?", but I think that is nice to get
> as well.

That's cool.
+1

But still totally unrelated to the points I try to make.

> - I implemented the decorator word by word following the (old) cached_method
> decorator, this might have been good or not, but it was the best I was able
> to do.

Well, just returning the function as it is while registering the decorator's information somewhere seems to be nice.

The decorator could even add some information to the docstring so that this information would automatically appear in the doc !

> - Nathann himself tested that the cost of the wrapper when calling the
> method is very much negligible, here is a test when creating the object

The correct phrasing for this changed since, and will from now on be called masturbation.

> if there is any better test to check this issue, please do so.

Well, I called the methods while you created the class, but really it's pretty much for free. Only the code has no reason at all to be run when the function is called. And if you want to improve your decorator perhaps you will add more stuff to it, and if you do it like that then it means that the stuff that you will add in the decorator necessarily stays free, from fear that it would add a non-negligible amount of computations when the function is called.
Honestly, if you just register the functions somewhere else and do not change them at all I would be very happy.

Besides, it would mean that there is a way to add more functions and information to your database WITHOUT creating additional Sage methods, and this would be nice because as Dima said here, Graph(my_poset) makes much more sense that my_poset.to_graph().
And there is this .to_partition() method too, which to me was only added because of find_stat.

> Anyway, the current implementation might be good enough to use, or someone
> might provide a better implementation, but this is not the point for me, and
> - if I understand it right - it's not the point for Nathann either. Two of
> his point are yet to be answered/discussed a bit further:
>
>
> "Right now, find_stat seems to work with decorators over Sage's functions.
> It is all very nice. But then whenever some addition must be made to
> find_stat's combinatorial maps there must be a corresponding Sage function,
> and I think that adding functions to Sage just because find_stat needs them
> is really going too far. "
>
> My answer: it is right that - in the current implementation - we need to
> implement a map between combinatorial collections in Sage and decorate it
> with @combinatorial_map in order to use this map in FindStat. But we only
> want to use maps in FindStat that are interesting for mathematicians, and if
> this is the case, then it should be very valid to have this map as well in
> Sage.

In the particular case of .to_partition(), I do not think so. In the particular case of .to_graph() I do not think so either, because Graph(my_poset) makes more sense according to Sage's syntax. Is that a valid objection to the idea that all maps should correspond to Sage methods ?

> If anyone is interested I could provide a list with methods we
> implemented for (or better in) Sage because we wanted to have them in
> FindStat. We can then see if it would have better to implement all these
> maps in a different project without allowing Sage users to use them as well.

This last sentence ignores the possibility of Graph(my_poset) instead of .to_graph().

> "But it is a website and an independent project, and I don't see why on
> earth Sage should now be developped according to find_stat's needs."
>
> My answer: All we do is to decorate maps between certain combinatorial
> collections to provide further information about this map. We then use this
> information in FindStat, but this information is not only useful for
> FindStat (at least in my opinion), see as well my comments above about the
> "positive sides". There might be something not perfect in the actual
> implementation, but the so far discussed drawbacks seem to be very little,
> compared to the advantage that a user is e.g. not annoyed anymore that the
> conjugate of a StandardTableau is not standard anymore, or that there are
> now all these new maps between the objects implemented. Anyway, if there is
> a better way of achieving such possibilities I am very positive of doing so
> (though this will again use someone's time that she might want to use
> differently). And: we are Sage users and/or developers, so if we want Sage
> to do sth for us that doesn't hurt (@Nathann: except for philosophical
> reasons), I don't see the point of not getting Sage doing it for us (as
> others did similar things before, according to John Cremona and others
> comments earlier on this thread) and for the combinat community.

What you do on the math level is nice, find_stat is nice, using Sage to do that too, and Sage benefits from it. Agreed. Now :

1) Is there any need to wrap the methods instead of returning them as they are, while registering the information somewhere. If not, could it be changed ?
2) If you agree that not all find_stat maps should be Sage function (and if you don't please tell me why the two examples above are invalid), could we remove those .to_poset() and .to_partition() things and add the entries to the find_stat database without touching those classes ?

> Finally, I think that the combinat part of Sage would have been less
> explored without the implementations done in the context of FindStat, and
> several combinatorialists only started implementing some maps or new
> combinatorial objects because FindStat uses them. So imho, the advantages
> outweigh the drawbacks by far, though there might be the point in minimizing
> the drawbacks even further.

The advantages outweigh the drawbacks, and it may even be possible to have only advantages and no drawbacks. What do you think ?

Nathann

[Nathann Cohen]

Hello !

> Please propose a mechanism that
>   * Only occupies a single line of code

I propose that we immediately strip Sage's sources of all its `\n`

>   * Outside of the method body, so it is separated from the actual implementation

I propose that we shuffle the lines of each file, and keep it running until everything that is find_stat related lies outside of the related method.

>   * But not in a separate file, since that is hard to keep in sync

Let us also put all Sage's code in a unique file.

>   * If it appears in the documentation, it must be doctestable and flag syntax errors

We should also implement something that screams when the names of the variables used in the doctests are french words. I do this mistake often.

More seriously, wouldn't changing the decorator to something that registers the method and not change it do the trick ? We could also add entries manually to the database, that is without creating the corresponding method.

It's highly probable that these two ideas may have been mentionned in this mailing list already.

Nathann

[kcrisman]

Or other beverage as appropriate :)  The shrillness level has gotten a little higher than really necessary, certainly than customary on this list.

 Does your comment apply in particular to my last post? I certainly did not want to be shrill - sorry if that was your impression when reading my post.

I was just referring to the general level; it wasn't aimed at any one post in particular.  Your last post and Nathann's post immediately following the post I'm replying to both seem very much in the spirit of a good discussion :-)

[Volker Braun]

On Thursday, June 20, 2013 9:34:48 AM UTC-7, Nathann Cohen wrote:

More seriously, wouldn't changing the decorator to something that registers the method and not change it do the trick

There decorator performs two functions currently:

 1) label the method as a combinatorial map

 2) transform the output into a special "map" class

Both are potentially useful. Having a map instead of just the image enables you to attach more functionality in the future, e.g. composition of maps. Right now there is not really anything, thats a question of what the find_stat roadmap is.

One could add a special keyword argument to disable the wrapping in CombinatorialMap and just use the decorator to add it to the registry. Its a viable optimization. But I don't see a need for that unless there is any need for it.

[leif]

Volker Braun wrote:
> Right now there is not really anything, thats a question of
> what the find_stat roadmap is.
>

> But I don't see a need for that unless there
> is any need for it.

+1


-leif

--
() The ASCII Ribbon Campaign
/\ Help Cure HTML E-Mail

[leif]

kcrisman wrote:
> The shrillness level has gotten a
> little higher than really necessary, certainly than customary on this list.

We haven't seen illustrations of the effect of the @bushy_tail
decorators yet... :P

[Nathann Cohen]

> One could add a special keyword argument to disable the wrapping in CombinatorialMap and just use the decorator to add it to the registry. Its a viable optimization. But I don't see a need for that unless there is any need for it.

Sooooooooo, let me sum it up, and correct me if I am wrong somewhere :

* You don't know why this class is wrapped, and the code would be simpler if it were not wrapped

* Useless code is run each time the function is run and it can be removed

* The one who originally implemented it like that seems to say (and it would be nice if he could confirm that) that the class was just created like that because of a copy and paste, and there was no intent behind this wrapping

As a result, nobody knows why it is implemented like that, yet you call a simplification "optimization", and we should keep code even though nobody has any clue what it is there for. 

Because it is (quote) "potentially useful", and of course nobody can guess in which way (please prove me wrong and tell me why).

And there is also this problem of forcing us to add Sage method for each find_stat map which will stand for as long as there will not be a manual way to add a map in the database, and even though I asked this question in my first email, so far it is systematically ignored by the defenders of the current implementation.

And yet my preacher tells me that God's cosmic plan makes sense. This guy's crazy.

Nathann

[Volker Braun]

I did read the source before posting on the subject, and your message makes no sense in that context. 

  * Decorators have their place. 

  * A non-decorator way to add maps to the database should be added eventually.

  * Premature optimizations are bad.

[Florent Hivert]

On Fri, Jun 21, 2013 at 09:48:32AM +0200, Nathann Cohen wrote:
> And yet my preacher tells me that God's cosmic plan makes sense. This guy's
> crazy.

You should add:

* Don't mess with the missionary man ;-) !

Cheers,

Florent

[Dima Pasechnik]

On 2013-06-20, Volker Braun <vbrau...@gmail.com> wrote:
> ------=_Part_2218_21876941.1371741153226
> Content-Type: text/plain; charset=ISO-8859-1

>
> On Thursday, June 20, 2013 12:17:48 AM UTC-7, Simon King wrote:
>
>> And this should really not be done on the level of the method being
>> registered. There should be a database of "useful combinatorial maps", and
>> the decorator should do nothing more than adding a method to this
>> database.
>>
>
> But that is just an implementation detail, once you have the decorator in
> place in the sources you can change its behavior. For performance-critical

Why does one even need a decorator in Simon's proposal?
I think a decorator like this makes the code unreadable, and if it can
be avoided then it should be avoided.
To me it's akin to graffity saying "XYZ was here" sprayed over the code
for no clear purpose (except known to XYZ only)...

[Volker Braun]

http://www.python.org/dev/peps/pep-0318/

On Friday, June 21, 2013 1:43:13 PM UTC-7, Dima Pasechnik wrote:

Why does one even need a decorator in Simon's proposal?

http://www.python.org/dev/peps/pep-0318/

I think a decorator like this makes the code unreadable, and if it can
be avoided then it should be avoided.

That is not the general consensus

[Dima Pasechnik]

On 2013-06-22, Volker Braun <vbrau...@gmail.com> wrote:
> ------=_Part_5_26369588.1371859450149
> Content-Type: text/plain; charset=ISO-8859-1

>
> http://www.python.org/dev/peps/pep-0318/
>
> On Friday, June 21, 2013 1:43:13 PM UTC-7, Dima Pasechnik wrote:
>>
>> Why does one even need a decorator in Simon's proposal?
>>
>
> http://www.python.org/dev/peps/pep-0318/

Thanks Volker, I started writing code generating code 30+ years ago...

>
> I think a decorator like this makes the code unreadable, and if it can
>> be avoided then it should be avoided.
>>
>
> That is not the general consensus

I don't think it's general consensus that if project B needs something
from classes A0, A1, ... it must directly modify classes A0, A1,...
(already full of methods), just because it's the 1st thought the crossed
the designer's minds, and because they have the numbers to muscle this
design in. IMHO B could very well derive from classes A0, A1,... and
place its extra methods in these derivations. Using decorators or
schmuckerators or whatever it sees fit.

One advantage of such design is that the code of B is located in one
place, instead of being all over the A0, A1,...


>

[Nathann Cohen]

Helloooooo Christian.

I was thinking of our find_stat battle from one week ago, and I
wondered if you could answer the questions I raised in my answer to
your post. In particular (but not only) about the methods added to
Graph and Poset ?...

Thanks,

Nathann

[Christian Stump]

Hi Nathan --

> I was thinking of our find_stat battle from one week ago, and I
> wondered if you could answer the questions I raised in my answer to
> your post. In particular (but not only) about the methods added to
> Graph and Poset ?...

Given the level of "shrillness" to which you certainly contributed, I
didn't actually plan to answer again. But okay...

I keep voting for having the methods added to Graphs and to Posets. I
just looked again at the list of methods for graphs, and there are 280
of them. For me (and some others, whichever reason we might have)
these two methods are useful for our "mathematics research" and that
makes it already a strong case for keeping them. If you feel like
there are too many methods, why not deleting "am" as a shortcut for
"adjacency_matrix", or replacing the almost 50 "is_???" by
"has_property(???)", including "antisymmetric" which should rather be
"is_antisymmetric", or replacing all "to_???" by a single method. If
there is a majority to delete them, or a particular reason why exactly
these methods out of the 280 should be deleted (I do not see either of
the two in this discussion currently), I would certainly be okay with
doing so. Simply "you want these methods for a 3rd party project, and
I don't like that" is not convincing to me.


Concerning the general design of the combinatorial_map decorator: I
implemented it in a way which did not interfere with other peoples
code or usage of Sage AND it made Sage better for several users. I
think that makes it a valid contribution.

It might have downsides. But you basically wrote "I don't like it the
way it is done" without giving any reason. An example: You mentioned
that it does run code each time the method is called, and this cannot
be avoided in the current implementation. This is true for ANY method
in Sage, with or without this decorator.
You and others asked if it slows down the methods or the
initialization of objects, and we did disprove both.
You said that you do not like decorators, that's okay but your
personal preference.
You do not like that the method gets a thin layer around, but you did
not argue why this is (or might become) a problem - so far, the
infected methods seemed to be doing okay.

If you do not like its design (for whatever reason), feel free to
provide improvements and discuss your improvements (I did ask about
the combiatorial_map decorator at various occasions, including the
mailing list, and no one complained). However such improvements might
look like, I want to stay able to ask which methods for a
"combinatorial set" are maps to "combinatorial sets" (see the method
combinat.combinatorial_map.combinatorial_maps_in_class), and (though
this would only come in a little while in the current implementation)
I want to tag such maps with mathematical information (okay, the
docstring could be used for such information, but this could become
complicated since the docstring is then used to provide the user with
infos, and to be (partially) machine interpretable at the same time).

Cheers, Christian

[Nathann Cohen]

Hello !

> I keep voting for having the methods added to Graphs and to Posets. I
> just looked again at the list of methods for graphs, and there are 280
> of them. For me (and some others, whichever reason we might have)
> these two methods are useful for our "mathematics research" and that
> makes it already a strong case for keeping them.

The function Poset.to_graph() can be replaced by Graph(the_poset) as Dima pointed out, which makes much more sense in Sage's usual syntax than Poset.to_graph(). You can still do the operation that you need for your research, and this seems to be a much more natural way to implement it in Sage. What do you think ?

My comment about your .to_partition() method is that its name does not give the slightest idea of what it does. Do you agree that this objection is valid ? At the very least I think that it should be renamed.

> If you feel like
> there are too many methods, why not deleting "am" as a shortcut for
> "adjacency_matrix", 

It's a good idea. 

> or replacing the almost 50 "is_???" by
> "has_property(???)",

It breaks tab-completion, and it becomes harder to find the list of such properties.

> including "antisymmetric" which should rather be

> "is_antisymmetric",

Oh, good idea. Do you create the patch, or do I write it ?

> or replacing all "to_???" by a single method.

Tab completion again.

> If
> there is a majority to delete them, or a particular reason why exactly
> these methods out of the 280 should be deleted (I do not see either of
> the two in this discussion currently), I would certainly be okay with
> doing so.

Yeah, I agree with you about antisymmetric and adjacency matrix.

> Simply "you want these methods for a 3rd party project, and

> I don't like that" is not convincing to me.

I pointed out many, many, many times other problems. For instance I relayed Dima's comment that Graph(my_poset) makes more sense. I am pretty sure I wrote that at least 5 times in the emails.

But yes, of course, knowing that you add these things in Sage just because you need them for a third party software is something that I do not like at all. I don't consider Sage to be a dependence of find_stat.

> Concerning the general design of the combinatorial_map decorator: I

> implemented it in a way which did not interfere with other peoples
> code or usage of Sage AND it made Sage better for several users. I
> think that makes it a valid contribution.

Once more, the decorator can stay a decorator and not create a class between the former method and Graph, by just registering the method somewhere else and returning the function it received without changing it.

> It might have downsides. But you basically wrote "I don't like it the
> way it is done" without giving any reason.

Christian please. I made the comment above many many many times. You CAN change your decorator this way, and you have to find a way to add methods to your database without creating method in Sage. If only to be able to add to find_stat all the coercions that exist in our constructors and that do not correspond to methods. 

For instance if you want to have a map from a binary matrix to a Digraph, or something like that. You cannot think of adding a .to_graph() method to matrices for such a thing !

>  An example: You mentioned
> that it does run code each time the method is called, and this cannot
> be avoided in the current implementation. 

It *CAN*, if the decorator returns the method exactly as it found it. It can do whatever it wants and register the function and all informations needed in a find_stat module in Sage, i.e. wherever you want but without modifying the method itself.

> This is true for ANY method

I don't understand that.

> You and others asked if it slows down the methods or the
> initialization of objects, and we did disprove both.

Indeed. And it was obviously necessary to ask this question. I am pretty sure that you did it yourself before you implemented this decorator.

> You said that you do not like decorators, that's okay but your
> personal preference.

Thank you.

> You do not like that the method gets a thin layer around, but you did
> not argue why this is (or might become) a problem - so far, the
> infected methods seemed to be doing okay.

Can you tell me why you need this layer ? If you don't, you can simplify your code by removing it.

> If you do not like its design (for whatever reason),

1) it forces you to create methods for your maps which is not always justified

2) Currently it adds useless computations to some methods, which does not cost any time but is definitely a bad design ....

> feel free to

> provide improvements and discuss your improvements 

Now that you have read them, please give me your opinion on them.

> However such improvements might
> look like, I want to stay able to ask which methods for a
> "combinatorial set" are maps to "combinatorial sets" (see the method
> combinat.combinatorial_map.combinatorial_maps_in_class), and (though
> this would only come in a little while in the current implementation)
> I want to tag such maps with mathematical information (okay, the
> docstring could be used for such information, but this could become
> complicated since the docstring is then used to provide the user with
> infos, and to be (partially) machine interpretable at the same time).

Christian : at the very very very least, and unless there is a way to query find_stat in Sage (and a meaning to that), what you can easily do is make the @combinatorial_map in Sage do *NOTHING*, that is return its input immediately, and patch your own installation of Sage with a definition of a more complex behaviour of combinatorial_map.

This way, nobody has to run your find_stat code and you are free to do whatever you want.

Otherwise, please consider registering your function into some module and writing decorators which return the functions exactly as it got them.

Nathann

[Nicolas M. Thiery]

Dear all,

Let me try to draw a consensus (in fact I believe it's already there),
so that we can ignore the irrelevant historical details of the
discussion and move forward toward what we can do to improve the
situation.

Here are a couple statements that might be agreed upon by everybody:

(1) Per se, adding semantic information to Sage is a good thing (e.g.
function XXX is actually an isomorphism). Of course this good
thing is to be put into balance with other good things, among
which is performance.

(1') It's interesting to explore what can possibly be done with such
semantic information; it's great that findstat is doing that.
And we will certainly find other use cases.

(2) Using a decorator on the function XXX is one possible syntax for
achieving (1). Another alternative is to add the info to the
documentation string. Another is to have a separate "database".
Etc.

(3) There are some advantages in using a decorator:

- It's checked by the Python parser; so the odds of a syntax error
not getting detected is low.

- Code locality: information about XXX is close to XXX.

- Part of the Sage library is already tagged using this syntax.

(4) The overhead of the combinatorial_map decorator upon loading a
Python file is negligible.

(5) The overhead of the combinatorial_map decorator upon calling the
function is currently non trivial. But it could be made to zero by
having the decorator return the decorated function as is.

findstat would just need to instrument the Sage code to have the
decorator register the function to its database.

Volunteers?

(6) The name of some of the recently added methods could be improved:

- Graph.to_partition is ambiguous: there are many ways to make a
partition out of a graph (degree sequence, size of connected
components, ...).

Suggestions for improvements?

- Poset.to_graph is ambiguous: there are several ways to make an
unoriented graph out of a poset (e.g. hasse diagram or its
transitive closure). Note that the alternative syntax
Graph(poset) has the same problem.

My personal recommendation would be:

- Add a combinatorial map decorator on Poset.hasse_diagram
- Add a combinatorial map from oriented to non oriented graph
(which possibly calls for a syntax to declare that a
constructor implements a combinatorial map between two sets)
- Use transitivity

Volunteers?

(7) It would be nice for the findstat project to have an alternative
mean to declare some of the combinatorial maps either in its own
source code or database. Two use cases:

- As a temporary mean to move forward quicker than Sage when needed.

- For some methods that are so trivial that their addition to Sage
is subject to controversy.

Please let me know (concisely) in case of disagreement on one of the
points above or if I left out some important point in the discussion.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Volker Braun]

On Wednesday, June 26, 2013 10:19:52 AM UTC-4, Christian Stump wrote:

or replacing the almost 50 "is_???" by
"has_property(???)", including "antisymmetric" which should rather be
"is_antisymmetric"

I think this is a terrible pattern. There is nothing wrong with having lots of methods, Python works just fine. Whereas a monolithic has_property(foo) method is difficult to write, document, and maintain precisely because it goes against the OOP spirit---its a procedural design shoehorned into Python. 

If we want to improve the user experience when tab-expanding then we should improve the tab expansion and not bend over backwards in the class layout. In particular, the tab expansion could easily collect bar.is_...() methods and just print a summary bar.is_(99 further methods) if there is a large number.

[Nathann Cohen]

> Let me try to draw a consensus (in fact I believe it's already there),

The day I learn how to say things like that with a straight face I will enter politics :-P

> (1) Per se, adding semantic information to Sage is a good thing (e.g.

+1

> (1') It's interesting to explore what can possibly be done with such semantic information

+1

> (2) Using a decorator on the function XXX is one possible syntax for
>     achieving (1). Another alternative is to add the info to the
>     documentation string. Another is to have a separate "database".
>     Etc.

+1

> (3) There are some advantages in using a decorator:

+1

> (4) The overhead of the combinatorial_map decorator upon loading a
>     Python file is negligible.

+1

> (5) The overhead of the combinatorial_map decorator upon calling the
>     function is currently non trivial.

Well. I would say that is *is* trivial, but that it is not a good design.

>  But it could be made to zero by
>     having the decorator return the decorated function as is.
>
>     findstat would just need to instrument the Sage code to have the
>     decorator register the function to its database.

I think that I wrote that in each of my last 1000 emails.

>     Volunteers?

If I patch find_stat there will be side-effects :-P

> (6) The name of some of the recently added methods could be improved:

+1

>     - Graph.to_partition is ambiguous: there are many ways to make a
>       partition out of a graph (degree sequence, size of connected
>       components, ...).
>
>       Suggestions for improvements?

If I had a method like that to code and if I were unable to find a good name for it, I just wouldn't include it. Because this function can be written in three lines, so it's not very bad if it is not already written.

sizes = {}
for cc in g.connected_components():
    sizes[len(cc)] = sizes.get(len(cc),0) + 1

>     - Poset.to_graph is ambiguous: there are several ways to make an

+1

I have 4 lines of Sage to add to that :

sage: posets.PentagonPoset().hasse_diagram()
Digraph on 5 vertices
sage: posets.PentagonPoset().hasse_diagram().transitive_closure()
Transitive closure of : Digraph on 5 vertices
sage: Graph(posets.PentagonPoset().hasse_diagram())                    
Graph on 5 vertices
sage: Graph(posets.PentagonPoset().hasse_diagram().transitive_closure())
Transitive closure of : Graph on 5 vertices

Honestly. They are all one-liners already. What's the problem with that ?

> (7) It would be nice for the findstat project to have an alternative
>     mean to declare some of the combinatorial maps either in its own
>     source code or database.

+1

Nathann

[Nathann Cohen]

> If I had a method like that to code and if I were unable to find a good name for it, I just wouldn't include it. Because this function can be written in three lines, so it's not very bad if it is not already written.
>
> sizes = {}
> for cc in g.connected_components():
>     sizes[len(cc)] = sizes.get(len(cc),0) + 1

My mistake, this code does something more complicated that what #14734 does. #14734 is actually another one-liner.

Nathann

[Christian Stump]

Thanks Nicolas for clearing up the discussion! in general, I agree
with your statements, though

to (5): I do still find the overhead here negligible, so I am not
volunteering in the very near future.

to (6) and as well to Nathann's similar complaint: agreed, what about
size_of_connected_components or connected_component_sizes (to have it
close to connected_components in tab completion). I don't agree on the
situation for Poset, identifying a (finite) poset with its Hasse
diagram is very natural, so "to_directed_graph" seems to be very
natural to me.

to (7): this is true, and we already do that. So what about deleting
the method Poset.to_graph again from Sage (and we just keep it applied
as a patch on top of Sage - as we already do e.g. with a common parent
for all finite Cartan types).

Concerning Nathann's last mail:

> The function Poset.to_graph() can be replaced by Graph(the_poset) as Dima
> pointed out, which makes much more sense in Sage's usual syntax than
> Poset.to_graph().

> ...

> What do you think ?

Where do I find this description of the "Sage's usual syntax"? greping
"def to_" yields tons of other examples where this is used: it is
actually used all over combiantorics (to_composition, to_permutation,
to_matrix, to_graph, to_dyck_word, to_binary_tree, +100 others). Did
you even implement "to_directed"/"to_undirected" for (Di)Graphs
yourself? Why does your antipathy not apply there as well?

I am totally okay with replacing the methods in your suggested way,
once this becomes common sense and we do the same for the other
examples as well.

Moreover, I wonder why you do not apply comment "this breaks tab
completion" here as well.

> I pointed out many, many, many times other problems. For instance I relayed
> Dima's comment that Graph(my_poset) makes more sense. I am pretty sure I
> wrote that at least 5 times in the emails.

And without Dima's comment? Other objections that particularly apply
to our new methods (rather than being general comments for many
methods, just applied to this situation)?

> But yes, of course, knowing that you add these things in Sage just because
> you need them for a third party software is something that I do not like at
> all. I don't consider Sage to be a dependence of find_stat.

What do you mean by "consider Sage to a dependence of FindStat"? Being
dependent as it depends on say GAP? This is not the case, and we did
not implement anything that we do not consider valuable for Sage. If
we agree that it would be better for Sage to not have e.g.
Poset.to_graph, then we do not put it in (or rather remove it again).

> Once more, the decorator can stay a decorator and not create a class between
> the former method and Graph, by just registering the method somewhere else
> and returning the function it received without changing it.

How do I do that explicitly? How do I register all combinatorial maps
in a given class at once? I could start playing with this a bit -
though I still do not see ANY problem with the current implementation
(I only see that @Nathann doesn't like it).

> Christian please. I made the comment above many many many times. You CAN
> change your decorator this way, and you have to find a way to add methods to
> your database without creating method in Sage.

This is not about FindStat. I want to have all combinatorial map in a
given class in Sage, so I can start playing with them! And I do want
to do that automatically. I have quite some code for that, just like
others have code for their research that does depend on methods and
functions in Sage.

> For instance if you want to have a map from a binary matrix to a Digraph, or
> something like that. You cannot think of adding a .to_graph() method to
> matrices for such a thing !

This is right, and we do not plan to do so! But we do now have a class
AlternatingSignMatrix for which we do want to implement and use such
methods.

> 1) it forces you to create methods for your maps which is not always justified

it doesn't force you to do so, simply don't use the decorator. If I
want to add this decorator afterwards, I want to create these methods
and find them useful.

> 2) Currently it adds useless computations to some methods, which does not cost any time but is definitely a bad design ....

> Now that you have read them, please give me your opinion on them.

As written above, how would you do it, so that the function
combinatorial_maps_in_class(cls) can provide the desired information?

It seems to be an often used behaviour when providing a patch for
Sage: do provide a first implementation that fits your needs (without
disturbing others), and then you or someone else provides an
improvement after a while. This is just happening here.

> Christian : at the very very very least, and unless there is a way to query
> find_stat in Sage (and a meaning to that), what you can easily do is make
> the @combinatorial_map in Sage do *NOTHING*

That is wrong, I do want to use the above method in my code, as I
already do for more than a year.

--
Christian Stump

christi...@gmail.com
www.stump.tv

[Christian Stump]

I think this is a terrible pattern. There is nothing wrong with having lots of methods, Python works just fine. Whereas a monolithic has_property(foo) method is difficult to write, document, and maintain precisely because it goes against the OOP spirit---its a procedural design shoehorned into Python.

 
I didn't actually want to suggest these changes. These are just as good or as bad as deleting a method others find useful in order to have the tab completion not being overloaded...

[Dima Pasechnik]

On 2013-06-26, Christian Stump <christi...@gmail.com> wrote:
> Hi Nathan --
>
>> I was thinking of our find_stat battle from one week ago, and I
>> wondered if you could answer the questions I raised in my answer to
>> your post. In particular (but not only) about the methods added to
>> Graph and Poset ?...
>
> Given the level of "shrillness" to which you certainly contributed, I
> didn't actually plan to answer again. But okay...
>
> I keep voting for having the methods added to Graphs and to Posets. I
> just looked again at the list of methods for graphs, and there are 280
> of them. For me (and some others, whichever reason we might have)
> these two methods are useful for our "mathematics research" and that
> makes it already a strong case for keeping them.

it seems to be some kind of ongoing project
which might be very important for you, but outsiders have no clue
what it is, it seems. Indeed, check out
http://en.wikipedia.org/wiki/Combinatorial_map :-)

Moreover, your methods are little more than some kinds of tags,
hidden in the decorator.

> If you feel like
> there are too many methods, why not deleting "am" as a shortcut for
> "adjacency_matrix", or replacing the almost 50 "is_???" by
> "has_property(???)", including "antisymmetric" which should rather be
> "is_antisymmetric", or replacing all "to_???" by a single method. If
> there is a majority to delete them, or a particular reason why exactly
> these methods out of the 280 should be deleted (I do not see either of
> the two in this discussion currently), I would certainly be okay with
> doing so. Simply "you want these methods for a 3rd party project, and
> I don't like that" is not convincing to me.

it is however might sound convincing that you basically pollute the codebase with
stuff that only you and your collaborators know about.

Imagine NSA got interested in certain maths stuff,
wrote little @PRISM_map decorator and put it all over Sage ;-)

> Concerning the general design of the combinatorial_map decorator: I
> implemented it in a way which did not interfere with other peoples
> code or usage of Sage AND it made Sage better for several users. I
> think that makes it a valid contribution.
>
> It might have downsides. But you basically wrote "I don't like it the
> way it is done" without giving any reason.

the reason is as stated above, it seems - polluting the codebase with strange stuff...

> An example: You mentioned
> that it does run code each time the method is called, and this cannot
> be avoided in the current implementation. This is true for ANY method
> in Sage, with or without this decorator.
> You and others asked if it slows down the methods or the
> initialization of objects, and we did disprove both.
> You said that you do not like decorators, that's okay but your
> personal preference.
> You do not like that the method gets a thin layer around, but you did
> not argue why this is (or might become) a problem - so far, the
> infected methods seemed to be doing okay.
>
> If you do not like its design (for whatever reason), feel free to
> provide improvements and discuss your improvements (I did ask about
> the combiatorial_map decorator at various occasions, including the
> mailing list, and no one complained).

Did you? The first time combinatorial_map features in the subject line
of sage-devel is this very thread. Just googling combinatorial_map
doesn't seem to produce meaningful hits either.

> However such improvements might
> look like, I want to stay able to ask which methods for a
> "combinatorial set" are maps to "combinatorial sets" (see the method
> combinat.combinatorial_map.combinatorial_maps_in_class), and (though
> this would only come in a little while in the current implementation)
> I want to tag such maps with mathematical information (okay, the
> docstring could be used for such information, but this could become
> complicated since the docstring is then used to provide the user with
> infos, and to be (partially) machine interpretable at the same time).

Well, again, are you sure it's OK to liberally tag library code for your own
projects? Do you make marks on pages of library books just because it is
convenient for you?

Dima


>
> Cheers, Christian
>

[Sébastien Labbé]

On Friday, June 21, 2013 10:43:13 PM UTC+2, Dima Pasechnik wrote:
> I think a decorator like this makes the code unreadable, and if it can
> be avoided then it should be avoided.

+1

My opinion is very close to the one of Dima in this thread. I believe we should avoid to spread such decorator in the Sage code base.

Results of computations made by FindStat shoud not depend on the number of combinatorial map decorators that are in the Sage code. There might be some interesting results that FindStat could find but does not just because there is no decorators for it. In the long term, the actual design tends to add decorators to more and more methods in Sage to improve FindStat and I do not agree with this. I think FindStat should return the best results possible no matter the presence/absence of decorators.

Sébastien

[Nicolas M. Thiery]

Hi Dima,

On Thu, Jun 27, 2013 at 10:40:07PM +0000, Dima Pasechnik wrote:
> it seems to be some kind of ongoing project
> which might be very important for you, but outsiders have no clue
> what it is, it seems. Indeed, check out
> http://en.wikipedia.org/wiki/Combinatorial_map :-)

As I mentioned in my other e-mail, I think this adds interesting
semantic information which could be useful outside of findstat. On the
other hand, from your e-mail I am reading that maybe we should try to:

- Give a good definition of what a "combinatorial map" is supposed to be
- Find a better name?

[Christian Stump]

>it is however might sound convincing that you basically pollute the codebase with
> stuff that only you and your collaborators know about.

This is not quite right, see https://groups.google.com/d/topic/sage-combinat-devel/a7wq0ksV2fY/discussion the initial discussion on this topic on sage-combinat-devel (and so far, we only decorated methods the combinat folder, except for the two methods for graphs which we already discuss to remove again.

So the combinat people seem to be happy with the decorator and its usage, including its value for them as well.

 
> the reason is as stated above, it seems - polluting the codebase with strange stuff...

I don't find a way to tell if a method is a map between combinatorial collections very strange.

> Did you? The first time combinatorial_map features in the subject line
> of sage-devel is this very thread. Just googling combinatorial_map
> doesn't seem to produce meaningful hits either.

See the link above, we moved from the initial idea of a combinatorial_statistic decorator.

> Well, again, are you sure it's OK to liberally tag library code for your own
> projects? Do you make marks on pages of library books just because it is
> convenient for you?

I do agree that it would be not very nice to do so if I were doing it silently and/or everywhere. But as said above, we only did it in the combinat part after multiple on- and offline discussions with many of the Sage-Combinat developers.

[Nathann Cohen]

Helloooooooooooo !

> I don't agree on the
> situation for Poset, identifying a (finite) poset with its Hasse
> diagram is very natural, so "to_directed_graph" seems to be very
> natural to me.

What could possibly be wrong with the existing Poset.hasse_diagram() method ?

> Where do I find this description of the "Sage's usual syntax"? greping
> "def to_" yields tons of other examples where this is used: it is
> actually used all over combiantorics (to_composition, to_permutation,
> to_matrix, to_graph, to_dyck_word, to_binary_tree, +100 others).

Well. It's a bit hard to grep the conversions that can be obtained from the constructors, though :-P

But converting an object, when the function is very natural, through the image's constructor is rather widespread..

n = Integer(5)
nn = int(n)
n = Integer(nn)

Same with floats, algebras and modules I guess, and with pretty much everything when we can actually modify the image's class. Graphs accept one thousand of different inputs, but I guess that this is only done when there is no ambiguity over what the expected result is. There is no way to fo that for

graphs.PetersenGraph().sparse6_string() # outputs a string

or for .to_dictionary().

> Did
> you even implement "to_directed"/"to_undirected" for (Di)Graphs
> yourself?

I don't think I did O_o

Actually, I did not !

~/sage/sage/graphs$ hg blame graph.py | grep "def to_undirected"
 8830:     def to_undirected(self):
~/sage/sage/graphs$ hg log -r 8830
changeset:   8830:dbe53cb3e5f7
user:        Robert L. Miller <r...@rlmiller.org>
date:        Sat Mar 08 21:43:17 2008 -0800
summary:     Flattened patch for ticket #2433

http://trac.sagemath.org/sage_trac/ticket/2433

I don't think I even new that Sage existed at that time. I probably did not know what a graph was at that time, for the matter :-P

> Why does your antipathy not apply there as well?

My antipathy is boundless. I even hate myself for being so antipathic.

Joke apart Christian, I'm just discussing code there. There is nothing personal at all, you are definitely a cool guy and I really have nothing against you. It's just code problems O_o

> I am totally okay with replacing the methods in your suggested way,
> once this becomes common sense and we do the same for the other
> examples as well.

Your post actually made me think about it for a while, and I cannot say that I like very much to have all these conversions written in the Constructor after all. For the developpers it mostly means that totally unrelated code will be gathered in the same place (conversions from very different objects to a common one), though for users it does make a big difference. MyObject(MyOtherObject) is a cool thing to write when there is no doubt as to how the object should be converted.
And as you said yourself, saying that the digraph associated with a graph is its hasse diagram is very natural.
Though we already have a P.hasse_diagram() for that.

> Moreover, I wonder why you do not apply comment "this breaks tab
> completion" here as well.

Because to me tab completion is useful to find out new functions, new things that the object can do. Things that you would not think that the object can do otherwise. Or if you don't know the name.
Trying DiGraph(my_poset) to get its associated digraph (hasse diagram) is rather sensible to me, while Partition(my_graph) to get your partition would be totally crazy because there is no natural partition associated with a graph.

The point is that if you begin to create a method whose name is precisely "MyClass.to_<image_class>", there are to me two alternatives
* If the conversion is natural it should rather be called ImageClass(my_class_object)
* If it is not natural, and if you don't think useful to rename the function to something that actually gives a hint of what it does, to me it screams "I don't care what the function does, all that matters to me is that there is a function from A to B and that's another map for find_stat"

> And without Dima's comment? Other objections that particularly apply
> to our new methods (rather than being general comments for many
> methods, just applied to this situation)?

Well, I just know two of these methods, the ones I named above. To me the Poset.to_graph() can be obtained through the very natural Graph(Poset.hasse_diagram()), and can become Graph(your_poset) if you think that it realler matters somehow (though I don't see how). For the .to_partition like I said above, to me it screams "I don't care what the function actually does, I'm just adding a map for find_stat".

> What do you mean by "consider Sage to a dependence of FindStat"? Being
> dependent as it depends on say GAP?

GAP is a software of its own, and we don't change GAP's code to help with Sage's interface to it. Sage is a software of its own, and find_stat shouldn't change Sage's code to help with its interface to it.

> This is not the case, and we did
> not implement anything that we do not consider valuable for Sage.

It's just my personal advice, but I do think that this .to_partition() and .to_graph() are not valuable to Sage, and that you added them only because it is useful for find_stat. And as I understand why it would be useful for find_stat (you want to add maps, and you can only do so with decorators on functions, i.e. not on constructors) I think that this explanation is right :-P

> If

> we agree that it would be better for Sage to not have e.g.
> Poset.to_graph, then we do not put it in (or rather remove it again).

+1

> How do I do that explicitly? How do I register all combinatorial maps
> in a given class at once? I could start playing with this a bit -
> though I still do not see ANY problem with the current implementation
> (I only see that @Nathann doesn't like it).

Well, I don't know what you actually need to store in these combinatorial map things.

def my_new_decorator(f, domaine, bijection = None, surjection = None, codomain=None, ...):
    import sage.combinat.find_stat_stuff as find_stat
    find_stat.all_combinatorial_methods.append("New function from "+str(f.im_class.__name__)+" to somewhere, which is "+("" if bijective else "not ")+"bijective")
    return f

I mean.. What do you need to know ?

> This is not about FindStat. I want to have all combinatorial map in a
> given class in Sage, so I can start playing with them! And I do want
> to do that automatically.

O_o
Well, don't want to be forced to run that code when I work on graphs. Is that a problem ? O_o

With the decorator above I wouldn't have to run your code as soon as I call a method which bears your decorator. But it looks like some other persons do not like decorators in this case either (and I surely don't say that I do).... Why don't you just find out a way to add stuff to your collection of maps without using decorators ? You DO need that anyway, for the conversions that are stored in constructors. And there are even methods which return difference types depending on their arguments ! Python is not typed and we can perfectly do that... It's not compatible with how combinatorial_map was designed, is it ?

> I have quite some code for that, just like
> others have code for their research that does depend on methods and
> functions in Sage.

We just don't put it in Sage if it's a hassle for others. I even have very good routines to plot symmetric graphs, but so far I have no idea how to make it easy to use for a Sage user... So it stays on my computer, until I have a good design in mind :-P

> This is right, and we do not plan to do so! But we do now have a class
> AlternatingSignMatrix for which we do want to implement and use such
> methods.

The example still shows that you need ways to add map to find_stat without creating decorated methods in Sage.

> As written above, how would you do it, so that the function
> combinatorial_maps_in_class(cls) can provide the desired information?

With the short code I provided above, it looks like you can add to a list in a find_stat module whatever information you want. Later on you can just query this database to tell you what you want to know, can't you ?

> It seems to be an often used behaviour when providing a patch for
> Sage: do provide a first implementation that fits your needs (without
> disturbing others), and then you or someone else provides an
> improvement after a while. This is just happening here.

Hmmm. Well, if I proved nothing here I hope I proved that it did disturb others. Even if it is only me :-P

> > Christian : at the very very very least, and unless there is a way to query
> > find_stat in Sage (and a meaning to that), what you can easily do is make

> > the @combinatorial_map in Sage do *NOTHING*
>
> That is wrong, I do want to use the above method in my code, as I
> already do for more than a year.

There is absolutely nothing that I can do to prevent you from doing what you want with a GPL software on your own computer.
And even if I could, I certainly would not.
But it would be a bit greedy to require that your own code is included in Sage if you are the only one who can use it O_o

Is there any example of how one can use all the find_stat methods in Sage, by the way ?

Oh yes there is !
http://www.sagemath.org/doc/reference/combinat/sage/combinat/combinatorial_map.html

Well, you could keep the same features by having a dictionary in a find_stat module which associates <whatever you want> to a class.

sage: g = Graph()            
sage: f=g.connected_components
sage: {f.im_class:"whatever you want"}
{sage.graphs.graph.Graph: 'whatever you want'}

Nathann

[Christian Stump]

What could possibly be wrong with the existing Poset.hasse_diagram() method ?

Nothing.
 

Well. It's a bit hard to grep the conversions that can be obtained from the constructors, though :-P

All I wanted to show is that we didn't invent the "to_???" methods which you call "unusual Sage syntax".

> MyObject(MyOtherObject) is a cool thing to write when there is no doubt as to how the object should be converted.

This becomes a little problematic if the user is not aware that "MyObject" even exists, while she is seeing it in tab completion with the "to_???" method.

> Though we already have a P.hasse_diagram() for that.

This is not a bad example, DiGraph(P) might be okay to come up with, but would a given user figure out that he should do HasseDiagram(P) in order to get the Hasse diagram (and to import it first, since it's not in the global namespace?

> Trying DiGraph(my_poset) to get its associated digraph (hasse diagram) is rather sensible to me, while Partition(my_graph) to get your partition would be totally crazy because there is no natural partition associated with a graph.

As I wrote above, DiGraph sounds reasonable to me as well, HasseDiagram much less reasonable, while Partition would indeed be stupid.

> all that matters to me is that there is a function from A to B and that's another map for find_stat"

Let me emphasize this once more here, if it where only to get it in findstat, there would be no problem at all to patch everything we need, and apply it on top of a fresh Sage - we do that already for other stuff we do not think to be valuable for Sage itself.

All I do is arguing that I consider the changes to be valuable for Sage, or equivalently, for other people who use Sage.

> but I do think that this .to_partition() and .to_graph() are not valuable to Sage

My impression is that you only care because it is "your" graph code. But nevertheless, several people wrote in this thread that they do not like these maps, so I'd suggest to remove them again (I wouldn't call it a majority but I do understand that it is arguable to say "we have a method that provides the connected components, so why should we add another giving their sizes").

> And as I understand why it would be useful for find_stat (you want to add maps, and you can only do so with decorators on functions, i.e. not on constructors) I think that this explanation is right :-P

It would have taken me 30 min to undo the changes, and patch them for myself on top of Sage, while this discussion took certainly more time. So I must have had another reason to discuss...

> Well, don't want to be forced to run that code when I work on graphs. Is that a problem ? O_o

Somehow yes since you consider your negligible disadvantage (as you said yourself) more important than advantages for others.

> With the decorator above I wouldn't have to run your code as soon as I call a method which bears your decorator.

I'll see if I gonna try to change the implementation, but currently I think of asking if the combinat people want to keep it as it is (and remove the two methods from graphs), or if I just patch it - I don't see why I should spend more time on that...

Christian

[Nathann Cohen]

Hellooooooo !

>> but I do think that this .to_partition() and .to_graph() are not valuable
>> to Sage
>
> My impression is that you only care because it is "your" graph code.

I think that I would have said the same if you had patched any other class, but I look closely at what happens to graphs in Sage, of course, and did not notice it before. The reason why I looked at these decorators in the first place was because of a question I asked during the last Sage Days in Orsay, about find_stat. I said that I had a "not very kind" question, and asked how the decorators were implemented because I had been scared by the immutability decorators before. At that time I had no idea that Graphs were somehow involved.

>> Well, don't want to be forced to run that code when I work on graphs. Is

>> that a problem ? O_o
>
> Somehow yes since you consider your negligible disadvantage (as you said
> yourself) more important than advantages for others.

It's a pity that I gave this impression, for I really do not think that this is how I behave. I really tried to say that there were alternatives. We were even discussing how it could be replaced by a non-intrusive decorator in the last post !

> I'll see if I gonna try to change the implementation, but currently I think
> of asking if the combinat people want to keep it as it is (and remove the
> two methods from graphs), or if I just patch it - I don't see why I should
> spend more time on that...

Because one always feels responsible of what one puts into Sage. That's actually a nice thing ! :-P

Anyway I am glad that this fight is now over. And I'm sorry that you found me aggressive. When I talk about maths or coding it's just about what is right or wrong. It's just about technical things. And I would have been pleased to go get a beer with you anytime during this exchange, and it can still happen whenever we will meet again :-P

Good evening :-)

Nathann

[Dima Pasechnik]

On 2013-06-28, Christian Stump <christi...@gmail.com> wrote:
> ------=_Part_74_1772145.1372424392980
> Content-Type: text/plain; charset=ISO-8859-1

>
>>it is however might sound convincing that you basically pollute the
> codebase with
>> stuff that only you and your collaborators know about.
>
> This is not quite right, see
> https://groups.google.com/d/topic/sage-combinat-devel/a7wq0ksV2fY/discussion
> the initial discussion on this topic on sage-combinat-devel (and so far, we
> only decorated methods the combinat folder, except for the two methods for
> graphs which we already discuss to remove again.
>
> So the combinat people seem to be happy with the decorator and its usage,
> including its value for them as well.

Do the sage-combinat people now 0wn Sage codebase? :-)
Mind you, not everyone reads sage-combinat-devel...

>
>> the reason is as stated above, it seems - polluting the codebase with
> strange stuff...
>
> I don't find a way to tell if a method is a map between combinatorial
> collections very strange.

I do not question the intent, I question the implementation. If more projects
start tagging Sage classes left and right, like you do, then it will become a
bloody mess...

>
>> Did you? The first time combinatorial_map features in the subject line
>> of sage-devel is this very thread. Just googling combinatorial_map
>> doesn't seem to produce meaningful hits either.
>
> See the link above, we moved from the initial idea of a
> combinatorial_statistic decorator.
>
>> Well, again, are you sure it's OK to liberally tag library code for your
> own
>> projects? Do you make marks on pages of library books just because it is
>> convenient for you?
>
> I do agree that it would be not very nice to do so if I were doing it
> silently and/or everywhere. But as said above, we only did it in the
> combinat part after multiple on- and offline discussions with many of the
> Sage-Combinat developers.

Graph lives in sage.graphs, not in sage.combinat.

Best,
Dima

[Thierry]

Hi,

i first want to say that i love you all, i am not deeply involved in
sage-graphs nor sage-combinat, nor representing any community. Just my
two cents about this thread and the related tickets.

- I disagree that this thread reached a consensus.

- I disagree that functionalities in Sage can not be added in relation
with external purposes. Actually, the success of Sage over both faster
and more reliable other free mathematical software (don't feed the
troll) is, imho, due to its social ability to easily include people's
contribution. Somehow, its "poor" but inclusive design allow everyone
to share its piece of code there, and i like to promote this.

The main issue is about design, not about the right to exist.


First hint
----------

I like how Sebastien explains how to design classes and i think it could
help here : http://trac.sagemath.org/sage_trac/ticket/10519#comment:4

Shortly, we write algorithms. They answer questions. Identifying classes
containing them as methods is identifying the entities to which you ask
the question.

Let us have a look at the .to_partition() method introduced in the Graph
class.
http://trac.sagemath.org/sage_trac/attachment/ticket/14734/graph_to_partition.patch

Its name may make sense from the algebraic combinatorialist point of
view, but is definitely more cryptic than
`.connected_component_sizes_partition()`, which corresponds to its
one-line implementation. Here, the semantics about what you precisely
ask to the given graph is removed.

With such a name, one could imagine that `G.to_partition()` groups the
vertices by degrees. Each map g whose domain is the set of vertices of a
graph naturally creates a partition (the partition associated to the
equivalence relation f(u) == f(v)). We can imagine tons of such maps,
e.g. the number of triangles v belongs to, or the maximal number of
disjoint path from v to v, or the cardinal of the connected components
of its first neighborhood, such objects are not so artificial as they
actually appear in graph theory.

All those maps are interesting, but the name `.to_partition()` itself
states that this is not such a question you ask to a graph G, and that
there is a design issue (and changing the name will not solve the
issue). The name of the method `.to_partition()` is quite clear: it ask
"give me a map from the set of graphs to the set of partitions".


Let us have a look to the .to_poset() method,
http://trac.sagemath.org/sage_trac/attachment/ticket/14732/posets_to_graph.patch,
In particular, the comments
http://trac.sagemath.org/sage_trac/ticket/14732#comment:5
http://trac.sagemath.org/sage_trac/ticket/14732#comment:14 state:

<<From a pure Sage point of vue, I think it is actually a nice shortcut:
not everyone thinks of transforming the poset into a Hasse diagram.>>

<<I actually think it it makes it better, because I for example would
never think of doing Graph(P.hasse_diagram()) to transform the Poset
into a Graph.>>

If a user want the Hasse diagram of a poset, she asks the question "what
is your Hasse diagram" to the given poset. Here, the user is assumed not
to think of transforming the poset into a Hasse diagram, the user is
asking (again) the question "Is there a natural map from the class of
posets to the class of graphs?"

This is a legitimate question, some class in Sage should answer it.

To whom should the user ask those questions ? Not to a graph or to a
poset, but to a quiver (in a board sense: an organized set of arrows).
This entity knows which arrows exist between posets and graphs, between
graphs and partitions, and so on.

The current implementation asks this question to a given poset "Hey you,
3-element poset, could you tell me what maps are there from your whole
family and the set of graphs ?".

In this thread, you plan to ask the question <<Which bijections between
Dyck paths and NoncrossingSetPartitions are implemented?>>, should you
ask this question to a length-2 Dyck path ?

The same holds for the `to_partition` method : it is not assumed to
answer the question "what is the sequence of cardinals of connected
components of G", it aims to answer the question "give me an arrow
between graphs and partitions".

A class is not the domain of the method, it is the entity you ask your
question. Hence, you should not store an arrow into its domain, you
should store it into a quiver.


Second hint.
------------

- <<All we do is to decorate maps between certain combinatorial
collections to provide further information about this map.>>.

- <<I don't find a way to tell if a method is a map between
combinatorial collections very strange.>>

- <<As a simple example, one might want to know all the statistics that
are implemented for permutations>>

- <<by just registering the method somewhere else and returning the

function it received without changing it.>>

This nice idea does not correspond to what actually happens. De facto,
the proposed implementation is not a tagging system to add semantics in
existing methods: the current implementation implies creating artificial
methods that are of no use to the class they belong to.

When i say artificial, i mean that the method does not answer a question
that a user may ask to the associated object. If, given graph, i want to
find the partition corresponding to the list of cardinals of its
connected components, i will never look for an existing method achieving
that. The method only exists to host the decorator.

Perhaps adding a decorator to backlink from a method to its
corresponding arrow in the quiver might make sense in some very
particular cases, but having to create an artificial method to be able
to tag it with a decorator in order to construct an arrow is just
overkill.

This is a hint that decorators may not be appropriate to organize, and
especially to feed, your quiver.


Third hint
----------

If you read the code of the combinatorial_map() function, you get the
following example:

sage: p = Permutation([1,3,2,4])
sage: p.left_tableau
Combinatorial map: Robinson-Schensted insertion tableau

But `p.left_tableau` is NOT a map from Posets to Tableaux.
sage.combinat.permutation.Permutation_class.left_tableau is. Both are
different.

Example with a classical method:

sage: G = graphs.PetersenGraph()
sage: Graph.connected_components(G) == G.connected_components()
True
sage: Graph.connected_components == G.connected_components
False

Example with a decroated method:

sage: p = Permutation([1,3,2,4])
sage: q = Permutation([1,3,2,4,5])
sage: q.left_tableau == p.left_tableau
True
sage: q.left_tableau() == p.left_tableau()
False
sage: type(p).left_tableau == p.left_tableau
True
sage: type(p).left_tableau(p)
[[1, 2, 4], [3]]
sage: p.left_tableau(p)
...
TypeError: left_tableau() takes exactly 1 argument (2 given)

Hence, the decorator identifies object.method with type(object).method,
which are two different things (in particular their number of entries
differ by 1). There seems to be a confusion between the class of
permutationss and a given single permutation.

Also, this may confuse Python users, since it contradicts the following
paragraph :
http://docs.python.org/2/tutorial/classes.html#method-objects

You won't add a decorator @taylor_expansion to the .cos() method of a
real number.


Fourth hint.
------------

Your quiver will benefit of having more and more maps. So, it needs to
be scalable.

In the current implementation, it implies writing artificial methods for
each new map, easy to write, easy to review, easy to spread, therefore
flooding Sage code.

On the other hand, maintaining a small and coherent set of methods for a
given class asks for more work. You need to merge methods, deprecate
code, etc.

No doubt that the "be fruitful, and multiply" strategy will win. Not
sure Sage code will benefits from this.

Also, non-essential Sage features tend to be lazy_imported. It may be
hard to lazy_import each artificial method along the whole sage code,
where it will be easy to lazy_import a quiver. In the future, one may
want to build specialized parts of Sage "the_software", what about code
modularity ?

Let me give a provocative example: i am currently interested in integer
sequences, and i want to collect them.

Sage has a fibonacci() function. To add semantics, i could add an
@integer_sequence() decorator on it, and even
@integer_sequence('A000045') to improve the interface with OEIS,
therefore providing more information.

I could do this for prime numbers as well, tagging
sage.rings.arith.nth_prime() with @integer_sequence('A000040')
decorator, then posets with @integer_sequence('A000112').

I could also add @integer_sequence('A001203') for the continued fraction
expansion of pi. CFF and pi are there, so i will just add an artificial
pi_continued_fractions() function to host the decorator.

I will get stuck at some point with existing Sage functions, but the
collection benefits on being as complete as possible, so i will need to
have 'A005408' as well, the odd numbers are so natural, and indeed
important, this may be useful for some Sage users. So i will add a
trivial function odd() into Sage whose decorator will be
@integer_sequence('A005408'). OEIS currently offers me a potential of
226576 sequences. Winning strategy. People will start complaining, but
we are close to a consensus: improving semantics is good, perhaps could
changing the name of the "odd()" function be a solution, volunteers ?

Sage aims at being inclusive. There is a place for implementation of
integer sequences. But not as tagged functions spread along Sage code
for proximity.


So what ?
---------

Changing or removing two artificial methods might be sufficient to stop
a flame. But i think that everyone, and especially people interested in
combinatorial maps, could benefit in a redesign of the implementation of
combinatorial maps (not its removal).

Precise details will depends on the mid-term goal of combinatorial maps
(which questions do you plan to ask), so you may have to ask to some
sage-combinat developpers about this design.

But even a very basic implementation with tuples of the form
(domain, codomain, map, additional_information_dict)
where map could point to an existing method or be a locally defined
lambda function, seem to make more sense than the current
decorator-based implementation.

It will speed up queries, remove the need to create (and doctest) an
articifial method representing the map into the class representing the
domain, therefore making addition of new maps easier, give more symetry
between domain and codomain (then you could ask for all maps with Posets
as codomain, without having to browse the whole Sage code), is scalable
(could easily become a SQL database at some point), does not pollute
namespace, etc.

Ciao,
Thierry

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[vdelecroix]

Hi,

I do like the project find_stat but do not like the way it intends to do it. In that sense, I mostly agree with Nathann objections.

Following Thierry, why combinatorial maps are not implemented as morphisms between two proper parents ? We could add some semantic to morphisms (injectivity/surjectivity/bijectivity, ...) which is definitely useful. Note that some semantic is already there as a morphism might be a map between sets or a map between between graded objects. It is possible to implement a decorator that actually creates a morphism from a method (@morphism_from_method) and cache it somewhere. I think that it should not transform a method to a combinatorial map (which was one of the main Nathann's objection) but it might be useful that such decorator exists. Then, the problem is what method is not an actual morphism between two parents (do we want decorators everywhere) ? Where do we register the morphisms (in the parent, in a database) ?

Another problem is that given a parent, it is not possible to determine all the morphisms from or to that parent ("possible" here means that such function will never exists, because most of the objects and morphisms are dynamically created with the coercion framework and that set of morphisms is potentially infinite). Nevertheless, coercion framework takes care about somewhat "natural" morphisms and combinatorial maps are somewhat opposite (ie non trivial transformations). But still, some semantic might be applied to coercion morphisms.

There are several obstruction to such project:
 - an object (let say the partition [3,2,1]) may have several parent (Partitions of 6, Partitions graded by the length, ...) but the combinatorial map exists somewhat independently of the parent
 - we need to convince Nathann that it would be good to have the parent Graphs ;-)

Best
Vincent

[Paul-Olivier Dehaye]

Just adding a link to a track ticket that is relevant:

http://trac.sagemath.org/ticket/16403