#22937 closed enhancement (fixed)
Implement a "distribute" method
Reported by:  Emmanuel Charpentier  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  symbolics  Keywords:  
Cc:  Ralf Stephan, Travis Scrimshaw  Merged in:  
Authors:  Emmanuel Charpentier, Ralf Stephan  Reviewers:  Travis Scrimshaw 
Report Upstream:  None of the above  read trac for reasoning.  Work issues:  
Branch:  7aee739 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #17505  Stopgaps: 
Description
Motivation : some "obvious" transformations, sometimes helpful in routine calculations, cannot be obtained via the current methods. Some (elementary,
 e. highschool or undergradlevel) 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 righthand form from the lefthand form of these various examples is sometimes useful in (lowlevel) examples. The examples (1) and/or (2) arise naturally when deriving the maximumlikelihood 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...
Change History (37)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
Branch:  → u/charpent/distribute 

comment:3 Changed 6 years ago by
Commit:  → c3bcef0564e154e930191471334b7c43e5637bea 

Status:  new → needs_review 
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.

comment:4 Changed 6 years ago by
Status:  needs_review → needs_work 

Further verifications show that this does not work in all cases.
Back to the old drawing board...
comment:5 Changed 6 years ago by
Commit:  c3bcef0564e154e930191471334b7c43e5637bea → 7f9666a22d0d290f4b3504bc1d4b61a4dcf7c455 

Branch pushed to git repo; I updated commit sha1. New commits:
7f9666a  Fixed recursion when nonmatch at toplevel.

comment:6 Changed 6 years ago by
Status:  needs_work → needs_review 

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.
comment:7 Changed 6 years ago by
Dependencies:  → 17505 

Status:  needs_review → needs_work 
Planning to implement the multiplicative case allowed by #17505.
comment:8 followup: 9 Changed 6 years ago by
Dependencies:  17505 → #17505 

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.
comment:9 Changed 6 years ago by
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 resubmit 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...).
comment:10 Changed 6 years ago by
Commit:  7f9666a22d0d290f4b3504bc1d4b61a4dcf7c455 → c67f95735d1f816c0255dad81985a8c98aa49757 

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.

comment:11 Changed 6 years ago by
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.
comment:12 Changed 6 years ago by
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.

comment:13 Changed 6 years ago by
Commit:  c67f95735d1f816c0255dad81985a8c98aa49757 → 687cc8ea8b0a225d81309bcfffcb3aa948afd31b 

Branch pushed to git repo; I updated commit sha1. New commits:
687cc8e  Distribute : implement Travis Scrimshaw's suggestion for iterations.

comment:14 Changed 6 years ago by
Authors:  → Emmanuel Charpentier, Ralf Stephan, Travis Scrimshaw 

Cc:  Travis Scrimshaw added 
Report Upstream:  N/A → None of the above  read trac for reasoning. 
Status:  needs_work → needs_review 
With Travis' suggestion, passes ptestlong
with the same result as before ==> needs_review
Do you think that this enhancement should be passed to Maxima ? The algorithm seems simple to port in Maxima or Lisp.
comment:15 Changed 6 years ago by
Commit:  687cc8ea8b0a225d81309bcfffcb3aa948afd31b → 4b6e71b471ac6747defcc0784208baea42f1da20 

Branch pushed to git repo; I updated commit sha1. New commits:
d420ec4  17505: fix latex, cosmetics

b784a2c  Merge branch 'u/rws/implement_symbolic_product' of trac.sagemath.org:sage into distribute

5779423  17505: fix doctests

4b6e71b  Merge branch 'u/rws/implement_symbolic_product' of trac.sagemath.org:sage into distribute

comment:17 Changed 6 years ago by
In general, it is always better to pass things to upstream. Although for now, we should do things on our side.
Some other small comments:
 There is a typo:
_ Symbolic product of a product ==> product of symbolic products.
self
is not considered as an input. Small change to your
INPUT:
: ``recursive``  (default: ``True``) the distribution proceeds along the subtrees of the expression
comment:18 followup: 21 Changed 6 years ago by
Authors:  Emmanuel Charpentier, Ralf Stephan, Travis Scrimshaw → Emmanuel Charpentier, Ralf Stephan 

Reviewers:  → Travis Scrimshaw 
comment:19 Changed 6 years ago by
Commit:  4b6e71b471ac6747defcc0784208baea42f1da20 → 2412f7a387cf0dec3a764a52a8e644d545cef5f8 

Branch pushed to git repo; I updated commit sha1. New commits:
2412f7a  Distribute : cosmetics on documentation.

comment:20 Changed 6 years ago by
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...).
comment:21 Changed 6 years ago by
Replying to tscrim:
You are still listed as an author in the docstring (credit where credit is due...).
comment:22 followup: 27 Changed 6 years ago by
I shouldn't be because I just did some simple review changes (so please remove me). But thank you. :)
Everything else looks good.
comment:23 Changed 6 years ago by
is the word "indiced" correct or it is "indexed"? (i'm not native english speaker though..)
comment:24 Changed 6 years ago by
Commit:  2412f7a387cf0dec3a764a52a8e644d545cef5f8 → c28097a513f90c7d4e738d6f97c1036d897b4d62 

Branch pushed to git repo; I updated commit sha1. New commits:
c28097a  Distribute : at his request, Travis Crimshaw removed from Author's list.

comment:26 Changed 6 years ago by
Commit:  c28097a513f90c7d4e738d6f97c1036d897b4d62 → 7aee739cceff13c596c12e93130250f1ea1fae3f 

Branch pushed to git repo; I updated commit sha1. New commits:
7aee739  Distribute : one last typo (I hope...).

comment:27 followup: 28 Changed 6 years ago by
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...).

comment:28 followup: 29 Changed 6 years ago by
Status:  needs_review → positive_review 

Replying to charpent:
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).
comment:29 Changed 6 years ago by
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 externallyvisible 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.
comment:30 followup: 31 Changed 6 years ago by
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.
comment:31 followup: 32 Changed 6 years ago by
comment:32 Changed 6 years ago by
Replying to rws:
Replying to rws:
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 ?
comment:33 Changed 6 years ago by
Branch:  u/charpent/distribute → 7aee739cceff13c596c12e93130250f1ea1fae3f 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:34 followup: 35 Changed 6 years ago by
Commit:  7aee739cceff13c596c12e93130250f1ea1fae3f 

WARNING
You have used here "apply()" which is not python3compatible. Please correct this ASAP in another ticket.
Reference: www.diveintopython3.net/portingcodetopython3with2to3.html
The Python 2 builtin apply() has been removed in Python 3
comment:35 Changed 6 years ago by
Replying to chapoton:
WARNING
You have used here "apply()" which is not python3compatible. Please correct this ASAP in another ticket.
Will do that, maybe over the coming weekend, but have to think about it I'm not much of a Python coder...).
Reference: www.diveintopython3.net/portingcodetopython3with2to3.html
Thanks for the suggestion.
The Python 2 builtin apply() has been removed in Python 3
H... right.
comment:36 Changed 6 years ago by
Do you want me to take care of that, and then be a reviewer ? Maybe this will be faster.
Discussion opened onsagedevel