Implement a "distribute" method

[EmmanuelCharpentier]

Motivation : some "obvious" transformations, sometimes helpful in routine calculations, cannot be obtained via the current methods. Some (elementary,
i. e. high-school- or undergrad-level) exemples : given the declarations :

var("a,b")
var("j,p", domain="integer")
f,g,X=function("f,g,X")

the following equalities, true under no or mild conditions, cannot be deduced currently :

sum(X(j)+Y(j),j,1,p)==sum(X(j),j,1,p)+sum(Y(j),j,1,p) ## (1)
prod(X(j)*Y(j),j,1,p)==prod(X(j),j,1,p)*prod(Y(j),j,1,p) ## (2)
integrate(f(x)+g(x),x,a,b)==integrate(f(x),x,a,b)+integrate(g(x),x,a,b) ## (3)

Similarly, if A, B and C are matrices over a suitable ring and of
suitable dimensions, the following equalities cannot be
straightforwardly obtained.

(A+B).trace()==A.trace()+B.trace() ## (4)
(A*B).det()==A.det()*B.det() ## (5)

(Curiously, (f(x)+g(x)).diff(x) does return
diff(f(x),x)+diff(g(x),x) (and a way to return to the original
expression does not seem to exist currently)).

The ability to generate the right-hand form from the left-hand form of
these various examples is sometimes useful in (low-level)
examples. The examples (1) and/or (2) arise naturally when deriving the
maximum-likelihood estimators of the mean and variance of a given
distribution. The third one is often encountered in elementary calculus
exercises.

In all cases, an operator is "distributed" over another one :
(1) : symbolic_sum is distributed over addition.
(2) : symbolic product is distributed over multiplication.
(3) : integration is ditributed over addition.
(4) : trace is distributed over (matrix) addition.
(5) : determinant is distributed over (matrix) multiplication.

Implementing (1) as an extension of the expand() method of
Expression is tempting (see #22915). However, there are situations
where this expansion is not useful. So, creating a method for such
situations seems useful.

One should note that such "distributions" are not systematically
valid : we have a collection of special cases rather than a general
mechanism. So this method shoud either limit itself to a few
recognized cases or take keyword argument(s) specifying what should be
distributed over what.

Another design choice is to know if these distributions should be
recursive or run only on the top level of a given expression
(possibly controlled by another keyword argument).

The present ticket aims at implementing this method for sage.symbolic.expression.Expression, at least in cases (1) to (3) (case (2) needs an implementation of the symbolic products, see #17505). Further suggestions for other classes are welcome...

Depends on #17505

Upstream: None of the above - read trac for reasoning.

CC: @rwst @tscrim

Component: symbolics

Author: Emmanuel Charpentier, Ralf Stephan

Branch: 7aee739

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/22937

[EmmanuelCharpentier]

comment:1

Discussion opened onsage-devel

[EmmanuelCharpentier]

Branch: u/charpent/distribute

[EmmanuelCharpentier]

comment:3

First implementation :

• Symbolic sum of a sum ==> sum of symbolic sums
• Integral (definite or not) of a sum ==> sum of integrals.

Passes ptestlong with the same errors as those reported for 8.0.beta4 and 8.0.beta5

==>neeeds_review

---

New commits:

c3bcef0

First implementation of distribute() : sums.

[EmmanuelCharpentier]

Commit: c3bcef0

[EmmanuelCharpentier]

comment:4

Further verifications show that this does not work in all cases.

Back to the old drawing board...

[sagetrac-git]

Changed commit from c3bcef0 to 7f9666a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7f9666a

Fixed recursion when non-match at toplevel.

[EmmanuelCharpentier]

comment:6

Passes ptestlong with the same (unrelated) failures as before +one transient timeout :

sage -t --long src/sage/modular/modform/find_generators.py 

which passes when run standalone.

==>needs_review again.

[EmmanuelCharpentier]

Dependencies: 17505

[EmmanuelCharpentier]

comment:7

Planning to implement the multiplicative case allowed by #17505.

[tscrim]

comment:8

Minor comment: Instead of using map, you can do, e.g.,

map(lambda t:treat_term(op, t, la), aa)
treat_term(op, t, la) for t in aa

(with wrapping it as a list comprehension [treat_term(op, t, la) for t in aa] when you need a list).

Addendum - I feel this is cleaner and IIRC, it is faster.

[tscrim]

Changed dependencies from 17505 to #17505

[EmmanuelCharpentier]

comment:9

Replying to @tscrim:

Minor comment: Instead of using map, you can do, e.g.,

map(lambda t:treat_term(op, t, la), aa)
treat_term(op, t, la) for t in aa

(with wrapping it as a list comprehension [treat_term(op, t, la) for t in aa] when you need a list).

Indeed (my Lisp roots (and my age...) are showing).

Addendum - I feel this is cleaner and IIRC, it is faster.

I'll check that. But I'll submit first the "map" version (which works...), and re-submit the "comprehension" version afterwards if it makes a serious difference.

BTW : other enhancements are possible. For example create a local (static) dictionary of distributable operators, whose values are functions processing the corresponding case of distribution (with possible generalizations/factorizations). I didn't feel the four special cases we treat in SR so fare were worth it, but if you have other ideas, you're welcome...

Commit forthcoming. Review request after ptestlong (sually a couple of hours...).

[sagetrac-git]

Changed commit from 7f9666a to c67f957

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

647ff39	17505: unevaluated symbolic product
e4769b5	17505: symbolic product
58119b0	17505: fix doctests
7a56004	17505: address reviewer's suggestions
a018030	Merge branch 'u/rws/implement_symbolic_product' of trac.sagemath.org:sage into distribute
c67f957	Implement distribute() in the multiplicative case.

[tscrim]

comment:11

It's about 3x slower to use map:

sage: %timeit [i for i in range(10000)]
1000 loops, best of 3: 265 µs per loop
sage: %timeit map(lambda i: i, range(10000))
1000 loops, best of 3: 897 µs per loop

Also in Python2, map returns a list, which takes extra time and memory to create. Whereas for the sum, you only need a generator object.

I cannot comment so much about the operators as it is a little beyond my expertise.

[EmmanuelCharpentier]

comment:12

This version passes ptestlong with the same three failure (deemed unrelated).

I'll try Travis' version before marking the better version for review.

---

New commits:

647ff39	17505: unevaluated symbolic product
e4769b5	17505: symbolic product
58119b0	17505: fix doctests
7a56004	17505: address reviewer's suggestions
a018030	Merge branch 'u/rws/implement_symbolic_product' of trac.sagemath.org:sage into distribute
c67f957	Implement distribute() in the multiplicative case.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

687cc8e

Distribute : implement Travis Scrimshaw's suggestion for iterations.

[sagetrac-git]

Changed commit from c67f957 to 687cc8e

[sagetrac-git]

Changed commit from 4b6e71b to 2412f7a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2412f7a

Distribute : cosmetics on documentation.

[EmmanuelCharpentier]

comment:20

Cosmetic (but important) changes to the documentation. Thank you, Travis.

sage -t --long src/sage/symbolic/expression.pyx passes without failure. Would you mind reviewing it (I probably can't ptestlong right now...).

[EmmanuelCharpentier]

comment:21

Replying to @tscrim:

You are still listed as an author in the docstring (credit where credit is due...).

[tscrim]

comment:22

I shouldn't be because I just did some simple review changes (so please remove me). But thank you. :)

Everything else looks good.

[mforets]

comment:23

is the word "indiced" correct or it is "indexed"? (i'm not native english speaker though..)

[sagetrac-git]

Changed commit from 2412f7a to c28097a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c28097a

Distribute : at his request, Travis Crimshaw removed from Author's list.

[tscrim]

comment:25

indexed is correct adjective.

[sagetrac-git]

Changed commit from c28097a to 7aee739

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7aee739

Distribute : one last typo (I hope...).

[EmmanuelCharpentier]

comment:27

RReplying to @tscrim:

I shouldn't be because I just did some simple review changes

Your suggestion to do without map() was a good one (and teached me something I tend to oversee : Python is not Lisp...).

(so please remove me).

If you insist...

But thank you. :)

Everything else looks good.

So this last update (including indiced --> indexed) should be reviewed...

---

New commits:

7aee739

Distribute : one last typo (I hope...).

[tscrim]

comment:28

Replying to @EmmanuelCharpentier:

RReplying to @tscrim:

I shouldn't be because I just did some simple review changes

Your suggestion to do without map() was a good one (and teached me something I tend to oversee : Python is not Lisp...).

I am always learning things from my reviewers too.

(so please remove me).

If you insist...

Thank you. I didn't really author code other than give suggestions, so I don't think I should be listed as an author. :)

You will need to add a doctest in the dependency, but you don't have to merge it into this ticket explicitly (because it is a dependency and will be done by Volker in the develop branch).

[EmmanuelCharpentier]

comment:29

Replying to @tscrim:

[ Snip ... ]

You will need to add a doctest in the dependency, but you don't have to merge it into this ticket explicitly (because it is a dependency and will be done by Volker in the develop branch).

This should wait Ralf's implementation of the externally-visible product method and function (currently, we have to either import an internal function or cast to Sage a Maxima contraption...) : that will be cleaner an probably more useful to users.

[rwst]

comment:30

Interesting. Both branches apply but mine has a hunk that fuses two hunks into one; yours has the first of the two so my hunk cannot be applied. I'll upload a branch where the two are separated.

[rwst]

comment:31

Replying to @rwst:

Interesting. Both branches apply but mine has a hunk that fuses two hunks into one; yours has the first of the two so my hunk cannot be applied. I'll upload a branch where the two are separated.

Ah that should have gone to #22989.

[EmmanuelCharpentier]

comment:32

Replying to @rwst:

Replying to @rwst:

Interesting. Both branches apply but mine has a hunk that fuses two hunks into one; yours has the first of the two so my hunk cannot be applied. I'll upload a branch where the two are separated.

Ah that should have gone to #22989.

Go ahead. Do you need me to do anything ?

[vbraun]

Changed branch from u/charpent/distribute to 7aee739

[fchapoton]

Changed commit from 7aee739 to none

[fchapoton]

comment:34

WARNING

You have used here "apply()" which is not python3-compatible. Please correct this ASAP in another ticket.

Reference: www.diveintopython3.net/porting-code-to-python-3-with-2to3.html

The Python 2 builtin apply() has been removed in Python 3

[EmmanuelCharpentier]

comment:35

Replying to @fchapoton:

WARNING

You have used here "apply()" which is not python3-compatible. Please correct this ASAP in another ticket.

Will do that, maybe over the coming week-end, but have to think about it I'm not much of a Python coder...).

Reference: www.diveintopython3.net/porting-code-to-python-3-with-2to3.html

Thanks for the suggestion.

The Python 2 builtin apply() has been removed in Python 3

H... right.

[fchapoton]

comment:36

Do you want me to take care of that, and then be a reviewer ? Maybe this will be faster.

[fchapoton]

comment:37

I created #23030