Opened 6 years ago

Closed 6 years ago

# Implement a "distribute" method

Reported by: Owned by: Emmanuel Charpentier major sage-8.0 symbolics Ralf Stephan, Travis Scrimshaw Emmanuel Charpentier, Ralf Stephan Travis Scrimshaw None of the above - read trac for reasoning. 7aee739 #17505

### Description

Motivation : some "obvious" transformations, sometimes helpful in routine calculations, cannot be obtained via the current methods. Some (elementary,

1. 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...

### comment:1 Changed 6 years ago by Emmanuel Charpentier

Discussion opened onsage-devel

### comment:2 Changed 6 years ago by Emmanuel Charpentier

Branch: → u/charpent/distribute

### comment:3 Changed 6 years ago by Emmanuel Charpentier

Commit: → c3bcef0564e154e930191471334b7c43e5637bea 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 Emmanuel Charpentier

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 git

Commit: c3bcef0564e154e930191471334b7c43e5637bea → 7f9666a22d0d290f4b3504bc1d4b61a4dcf7c455

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

 ​7f9666a `Fixed recursion when non-match at toplevel.`

### comment:6 Changed 6 years ago by Emmanuel Charpentier

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 Emmanuel Charpentier

Dependencies: → 17505 needs_review → needs_work

Planning to implement the multiplicative case allowed by #17505.

### comment:8 follow-up:  9 Changed 6 years ago by Travis Scrimshaw

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.

Last edited 6 years ago by Travis Scrimshaw (previous) (diff)

### comment:9 in reply to:  8 Changed 6 years ago by Emmanuel Charpentier

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...).

### comment:10 Changed 6 years ago by 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.`

### comment:11 Changed 6 years ago by Travis Scrimshaw

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.

Version 0, edited 6 years ago by Travis Scrimshaw (next)

### comment:12 Changed 6 years ago by Emmanuel Charpentier

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 git

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 Emmanuel Charpentier

Authors: → Emmanuel Charpentier, Ralf Stephan, Travis Scrimshaw Travis Scrimshaw added N/A → None of the above - read trac for reasoning. 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 git

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:16 Changed 6 years ago by Emmanuel Charpentier

Merged #17505 again. Should be reviewable.

### comment:17 Changed 6 years ago by Travis Scrimshaw

In general, it is always better to pass things to upstream. Although for now, we should do things on our side.

• 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 follow-up:  21 Changed 6 years ago by Travis Scrimshaw

Authors: Emmanuel Charpentier, Ralf Stephan, Travis Scrimshaw → Emmanuel Charpentier, Ralf Stephan → Travis Scrimshaw

### comment:19 Changed 6 years ago by git

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 Emmanuel Charpentier

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 in reply to:  18 Changed 6 years ago by Emmanuel Charpentier

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

### comment:22 follow-up:  27 Changed 6 years ago by Travis Scrimshaw

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 Marcelo Forets

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

### comment:24 Changed 6 years ago by git

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:25 Changed 6 years ago by Travis Scrimshaw

`indexed` is correct adjective.

### comment:26 Changed 6 years ago by git

Commit: c28097a513f90c7d4e738d6f97c1036d897b4d62 → 7aee739cceff13c596c12e93130250f1ea1fae3f

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

 ​7aee739 `Distribute : one last typo (I hope...).`

### comment:27 in reply to:  22 ; follow-up:  28 Changed 6 years ago by Emmanuel Charpentier

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...).

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 in reply to:  27 ; follow-up:  29 Changed 6 years ago by Travis Scrimshaw

Status: needs_review → positive_review

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.

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 in reply to:  28 Changed 6 years ago by Emmanuel Charpentier

[ 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.

### comment:30 follow-up:  31 Changed 6 years ago by Ralf Stephan

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 in reply to:  30 ; follow-up:  32 Changed 6 years ago by Ralf Stephan

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.

### comment:32 in reply to:  31 Changed 6 years ago by Emmanuel Charpentier

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 Volker Braun

Branch: u/charpent/distribute → 7aee739cceff13c596c12e93130250f1ea1fae3f → fixed positive_review → closed

### comment:34 follow-up:  35 Changed 6 years ago by Frédéric Chapoton

Commit: 7aee739cceff13c596c12e93130250f1ea1fae3f

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

### comment:35 in reply to:  34 Changed 6 years ago by Emmanuel Charpentier

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.

### comment:36 Changed 6 years ago by Frédéric Chapoton

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

### comment:37 Changed 6 years ago by Frédéric Chapoton

I created #23030

Note: See TracTickets for help on using tickets.