Modify subs so that it can accept multiple equations just like subs_expr

[JoalHeagney]

In this ticket:

• we make expr.substitute(in_dict, **kwds) as expr.substitute(*args, **kwds) and make it accepts any kind of arguments (symbolic equalities, dictionnaries or lists of them)
• we deprecate subs_expr as a duplicate of subs

This came up as a method of passing solutions from solve back into symbolic equations:

    f(x,y) = (1-x)^2 + 100*(y - x^2)^2
    solution = solve([f.diff(ar) for ar in f.args()],f.args())[0]

Gives me a list of solutions as:

    [x=1;y=1]

Is there any way to programatically substitute this list of equalities back into f?

The solution provided by Michael Orlitzky was

f(x,y).subs_expr(*solution)

Anycase, as noted by Michael, it would be nice if subs had the same behaviour:

Passing it one equation does work,

  sage: f.subs(x == 1)
  y + z + 1

But more than one doesn't,

  sage: f.subs(x == 1, y == 2)
  ...
  TypeError: substitute() takes at most 1 positional argument (2 given)

I guess all that's missing is the ability to pass it multiple equations,
like `subs_expr`. It would probably be easy to add that ability to
`subs` if you want to create a ticket for something.

With the branch applied we have:

sage: f(x,y) = (1-x)^2 + 100*(y - x^2)^2
sage: solution = solve([f.diff(ar) for ar in f.args()],f.args())
sage: solution
[[x == 1, y == 1]]
sage: f.subs(solution[0])
(x, y) |--> 0

[nbruin]

subs_expr is already just doing a bit of preprocessing and then calling subs, so if the interface of subs is changed to accept a wider variety of input then subs_expr can simply be done away with. I'd say

subs(self,*args,**kwargs):
   for k in args:
       if is_symbolic_equation(k):
            kwargs[k.lhs()]=k.rhs() # but signal an error if key k is already present
       elif is_dict(k):
            add entries of k to kwargs # but signal error any key in k is already in kwargs.
       elif is_iterable(k):
            for e in k:
                if is_symbolic_equation(e):
                    same as before
                else:
                    error
       else:
            error
   ...

Note that behaviour at the moment is a bit random:

sage: x.subs({x:1})
1
sage: x.subs({x:1},x=2)
2
sage: x.subs(x==1,x=2)
1
sage: x.subs(x=1,x=2)
SyntaxError: keyword argument repeated

[JoalHeagney]

I would argue that we accept the weird behaviour in the cases above, but document it.

Most users are (hopefully) unlikely to use such mixed arguments, and trying to predict the desired behaviour of those that do will probably result in the wrong answer.

[mjo]

Make Expression.subs() accept lists, throw errors on subs conflicts, and doc cleanup.

[mjo]

Some Cython limitations made this more of an event than it had to be, but the patch implements the requested feature and Nils' suggestions from comment 1.

When you pass subs() a list, it's processed recursively, which has the nice side effect of allowing you to call solve() and pass the result to subs() without caring about the form of the return value.

The new subs() throws an error on conflicting substitutions... nobody reads the documentation unless they have to so I think it's better to alert the user that he's likely making a mistake.

[JoalHeagney]

Well I tried the patch out on my example and it seems to work well.

[vbraun]

Patch needs to be rediffed for current Sage...

[mjo]

Updated!

[vdelecroix]

Hello,

I updated the patch as a git branch (trivial conflict) and I propose some cleanup in a second commit. Tell me what you think.

Vincent

---

New commits:

​447b35d	Trac #12834: Allow Expression.subs() to take a list similarly to Expression.subs_expr().
​045eebf	Trac #12384: simplification and cleanup

[mmezzarobba]

As it happens, I had started doing my own version of something similar a while ago at a time where I had no internet access and hence without seeing this ticket. The implementation here is probably better, but I pushed mine to u/mmezzarobba/subs in case somebody wants to see if there is anything to be salvaged. (I may doit myself in a few days/weeks, but I have no time right now.)

[vdelecroix]

Hi Marc,

There is some difference of designs.

• in your version, the rightmost occurrence of a substitution takes precedence, while in Michael's one an error is raised
• you deprecate subs_expr and substitute_expression (I think this is good)
• is this a bug or a feature?

  sage: var('x,y,t')
  sage: A = cos(x) + sin(y) + x^2 + y^2 + t
  sage: A.subs({x^2 + y^2: t})
  x^2 + y^2 + t + cos(x) + sin(y)
  sage: A.subs({cos(x) + x^2 + sin(y) + t + + y^2: 1})
  1
  

• I like very much the presence of examples involving maple and mathematica

Vincent

[mjo]

@Vincent: Most of your changes look fine to me, thanks for picking this up again. I have a few comments:

1. When making multiple duplicate substitutions, all of the errors are no longer reported. This used to work like,

sage: d1 = {'a': 1, 'b': 2}
sage: d2 = {'b': 1, 'a': 2}
sage: _subs_safe_merge(d1, d2)
ValueError: Duplicate substitutions given: a, b

showing that both a and b had duplicate substitituons. Now it only shows the error for a:

ValueError: duplicate substitutions a->1 and a->2

The test "We should report all such conflicts..." was intended to show that =)

2. I like the fact that you show the whole substitution in the error, e.g. ValueError: duplicate substitutions a->b and a->c, but I think the arrow notation is confusing. I can't tell at a glance whether a or b is the variable. In some programming languages, the arrow is used to mean "take the value of a and put that into b." In other contexts, you could think of it as "take a and make it become b", which is actually the reverse substitution.
   
   Above, you can deduce which is which (if you think for a minute), but you can also wind up with ValueError: duplicate substitutions x->y and x->y where it's totally ambiguous.
   
   Is there some other notation that people generally agree on? Maybe the colon-equals, which defines the thing on the left to be equal to the thing on the right? For example, x := 3 would mean that x is being defined to be 3; i.e. 3 is substituted for x. It's a slight abuse of notation, but we can think of := as "make the thing on the left equal the thing on the right from now on." That's basically what a substitution is.

3. My "And finally, a list containing one of everything" test was meant to show that we can handle all three types (symbolic equality, a dict, and another list) at the same time. You noticed that I forgot tuples (thanks!), but can we do them all at the same time? For example,
   

   sage: w, x, y, z = SR.var('w, x, y, z')
   sage: _subs_make_dict([w == 1, {x: 1}, [y == 1], (z == 1,)])
   {w: 1, y: 1, x: 1, z: 1}
   

4. I agree that we can deprecate the other substitution methods subs_expr and substitute_expression.

That's it, thanks again for taking the time to work on this.

[vdelecroix]

Replying to mjo:

@Vincent: Most of your changes look fine to me, thanks for picking this up again. I have a few comments:

1. When making multiple duplicate substitutions, all of the errors are no longer reported. This used to work like,

This is not really doable and makes no sense if there are a lot of arguments like

sage: expr.subs((a == b), [a == c, x == 3], {a: 4})

The dictionary of substitutions is constructed sequentially.

I just removed the problematic doctest. If you prefer to report all collisions, please tell me why...

2. I like the fact that you show the whole substitution in the error, e.g. ValueError: duplicate substitutions a->b and a->c, but I think the arrow notation is confusing.

You are perfectly right. This is now a whole sentence

duplicate substitution for a, got values 1 and 2

3. My "And finally, a list containing one of everything" test was meant to show that we can handle all three types (symbolic equality, a dict, and another list) at the same time. You noticed that I forgot tuples (thanks!), but can we do them all at the same time? For example,
   

There is a now a doctest for that.

4. I agree that we can deprecate the other substitution methods subs_expr and substitute_expression.

Done.

Vincent

---

New commits:

​0272d29	Trac 12834: merge sage-6.7.beta4
​b6e196d	Trac 12834: remove trailing whitespaces
​a09094a	Trac 12834: review
​02ca484	Trac 12834: fix the french book that is using subs_expr

[vdelecroix]

Replying to vdelecroix:

• is this a bug or a feature?

  sage: var('x,y,t')
  sage: A = cos(x) + sin(y) + x^2 + y^2 + t
  sage: A.subs({x^2 + y^2: t})
  x^2 + y^2 + t + cos(x) + sin(y)
  sage: A.subs({cos(x) + x^2 + sin(y) + t + + y^2: 1})
  1
  

I opened #18396 for that purpose.

[mjo]

Replying to vdelecroix:

I just removed the problematic doctest. If you prefer to report all collisions, please tell me why...

It can be annoying to have to retry the call to subs() over and over again getting a different error every time. But it's not a big deal to me.

I made a few more changes noted in the commit messages.. everything seems OK otherwise, pending a ptestlong. I also rebased on top of the develop branch to get a clean commit history.

[mjo]

New commits:

​d7eb66e	Trac #12834: Allow Expression.subs() to take a list similarly to Expression.subs_expr().
​3cf4498	Trac #12384: simplification and cleanup
​27bbade	Trac 12834: remove trailing whitespaces
​9721512	Trac 12834: review
​bb5de82	Trac 12834: fix the french book that is using subs_expr
​05492f4	Trac #12834: Avoid iterating over the substitution dict twice.
​0d34382	Trac #12834: Ensure consistent failures by sorting duplicate substitutions.
​9030aba	Trac #12834: Test equality of dictionaries to avoid sorting bugs.
​6b0676c	Trac #12834: Mention the tuple representation in _subs_make_dict's docstring.
​24b98a0	Trac #12834: Manually word-wrap some lines.

[vdelecroix]

Hello,

I do not agree with your 05492f4 and 0d34382. First of all, if something is wrong, then it is not a big deal to go through the dictionaries again. Your version is way much too complicated. Please do something along

dup = [k for k in d2 if k in d1]
if dup:
    k = min(dup)   
    msg = "duplicate substitution for {}, got values {} and {}"
    raise ValueError(msg.format(k, d1[k], d2[k]))

And you can remark that I iterated over d2 and this was intentional. The dictionary d1 is intended to be large compared to d2 (think about expr.subs(u == 18, v == 15, w == 19, x == 1, y == 2, z == 3)). In your commit you reversed that. And you should know that to get the minimum of a list you do not need to sort it ;-) Was the call to sorted intentional compared to min?

If you have access to Maple/Mathematica I would be curious to know what they do for

sage: (x + x^2 + x^4).subs(x + x^2 == 2)

The other changes are fine to me.

Vincent

[vdelecroix]

I just asked some collegues and maple does

>> subs(x = t, x + x^2 + x^3)
                           3    2
                          t  + t  + t
>> subs(x^2 = t, x + x^2 + x^3) 
                            3
                           x  + t + x
>> subs(x + x^3 = t, x + x^2 + x^3) 
                           3    2
                          x  + x  + x
>> subs(x + x^2 = t, x + x^2 + x^3) 
                           3    2
                          x  + x  + x
>> subs(x + x^2 + x^3 = t, x + x^2 + x^3) 
                               t

It would be cool to have these doctests. I found these examples simpler than what we currently have.

[mjo]

Replying to vdelecroix:

Hello,

I do not agree with your 05492f4 and 0d34382. First of all, if something is wrong, then it is not a big deal to go through the dictionaries again. Your version is way much too complicated. Please do something along

dup = [k for k in d2 if k in d1]
if dup:
    k = min(dup)   
    msg = "duplicate substitution for {}, got values {} and {}"
    raise ValueError(msg.format(k, d1[k], d2[k]))

And you can remark that I iterated over d2 and this was intentional. The dictionary d1 is intended to be large compared to d2 (think about expr.subs(u == 18, v == 15, w == 19, x == 1, y == 2, z == 3)). In your commit you reversed that. And you should know that to get the minimum of a list you do not need to sort it ;-) Was the call to sorted intentional compared to min?

I guess I wasn't very clear in my commit message =)

The original code was,

if any(k in d1 for k in d2):
    k = (k for k in d1 if k in d2).next()
    raise ValueError...

The first any(k in d1 for k in d2) is probably O(m*n), since it (potentially) has to look through all of both dictionaries to see if there are any duplicates. Then,

    k = (k for k in d1 if k in d2).next()

also looks through both dictionaries, essentially to do the same thing: to see if there are any duplicates, but this time we write down the first duplicate key.

Since we're going to find the first duplicate key anyway, we don't need to do the first any check. If the dupe is toward the end of the list, the anyless version could be a lot faster. Once the any check is gone, my version isn't much different than yours. But since I've removed the any check, I no longer know that next() is safe in

k = (k for k in d1 if k in d2).next()

because it could throw a StopIteration exception. Instead of catching the exception, I chose to use a "for ... in" loop iteration:

for k in (k for k in d1 if k in d2)

That achieves the same thing without having to check whether or not there were any dupes. I tested it with some big dictionaries and it is a little faster. But since I can't force a dupe to be "at the end" of a dictionary, I can't check the worst-case.

In any case, I'm going to push another version that should be faster and simpler than both =)

[git]

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

​e195b36

Trac #12834: Simplify duplicate detection in _dict_update_check_duplicate.

[vdelecroix]

Replying to mjo:

Replying to vdelecroix:

Hello,

I do not agree with your 05492f4 and 0d34382. First of all, if something is wrong, then it is not a big deal to go through the dictionaries again. Your version is way much too complicated. Please do something along

dup = [k for k in d2 if k in d1]
if dup:
    k = min(dup)   
    msg = "duplicate substitution for {}, got values {} and {}"
    raise ValueError(msg.format(k, d1[k], d2[k]))

And you can remark that I iterated over d2 and this was intentional. The dictionary d1 is intended to be large compared to d2 (think about expr.subs(u == 18, v == 15, w == 19, x == 1, y == 2, z == 3)). In your commit you reversed that. And you should know that to get the minimum of a list you do not need to sort it ;-) Was the call to sorted intentional compared to min?

I guess I wasn't very clear in my commit message =)

The original code was,

if any(k in d1 for k in d2):
    k = (k for k in d1 if k in d2).next()
    raise ValueError...

The first any(k in d1 for k in d2) is probably O(m*n), since it (potentially) has to look through all of both dictionaries to see if there are any duplicates. Then,

You are wrong. A dictionary is a hash table not a list. Assuming that there is no collision this is a O(m) where m=size(d2).

[vdelecroix]

And looking at your last commit k2 in d1.keys() is O(n) in any case whereas k2 in d1 is a lookup in a hash table.

[vdelecroix]

And if you want to be convinced

sage: l = range(1000)
sage: timeit("-1 in l", number=2000)
2000 loops, best of 3: 26.1 µs per loop
sage: d = dict.fromkeys(range(1000))
sage: timeit("-1 in d", number=2000)
2000 loops, best of 3: 460 ns per loop

[vdelecroix]

In other words, just do

for k in sorted(d2, key=str):
    if k in d1:
        ...

[mjo]

Replying to vdelecroix:

And looking at your last commit k2 in d1.keys() is O(n) in any case whereas k2 in d1 is a lookup in a hash table.

You are definitely right about this, I'll fix it.

[mjo]

Replying to vdelecroix:

The first any(k in d1 for k in d2) is probably O(m*n), since it (potentially) has to look through all of both dictionaries to see if there are any duplicates. Then,

You are wrong. A dictionary is a hash table not a list. Assuming that there is no collision this is a O(m) where m=size(d2).

Right, but doesn't this

k in d1 for k in d2

do the d1[k] lookup (which is O(n)) m times, once for each key in d2?

[git]

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

​33fd449

Trac #12834: Fix hash lookup in _dict_update_check_duplicate.

[vdelecroix]

Replying to mjo:

Replying to vdelecroix:

The first any(k in d1 for k in d2) is probably O(m*n), since it (potentially) has to look through all of both dictionaries to see if there are any duplicates. Then,

You are wrong. A dictionary is a hash table not a list. Assuming that there is no collision this is a O(m) where m=size(d2).

Right, but doesn't this

k in d1 for k in d2

do the d1[k] lookup (which is O(n)) m times, once for each key in d2?

The lookup is O(1). And once for each key in d2 gives O(m). There is no for loop on d1, isn't it?

[vdelecroix]

Looks good to me. Can I add a commit to show a more relevant example about comparisons of maple/mathematica with respect to substitution?

[mjo]

Replying to vdelecroix:

The lookup is O(1). And once for each key in d2 gives O(m). There is no for loop on d1, isn't it?

Ah, I was using the worst-case O(n) instead of the average O(1).

Looks good to me. Can I add a commit to show a more relevant example about comparisons of maple/mathematica with respect to substitution?

Sure.

[vdelecroix]

Sorry for the delay!

I added a more complete example comparing maxima/maple/mathematica. Tested with the last version of maple but I do not have access to Mathematica. So it lacks some test.

I think I am done. So I let you review my last commit.

note: it is based on 6.7.rc0

Vincent

---

Last 10 new commits:

​e8b9c05	Trac 12834: review
​81ebcdc	Trac 12834: fix the french book that is using subs_expr
​f7a233b	Trac #12834: Avoid iterating over the substitution dict twice.
​322981e	Trac #12834: Ensure consistent failures by sorting duplicate substitutions.
​003fa00	Trac #12834: Test equality of dictionaries to avoid sorting bugs.
​5460cfc	Trac #12834: Mention the tuple representation in _subs_make_dict's docstring.
​e617094	Trac #12834: Manually word-wrap some lines.
​37aa1f8	Trac #12834: Simplify duplicate detection in _dict_update_check_duplicate.
​d2d58a3	Trac #12834: Fix hash lookup in _dict_update_check_duplicate.
​a56c969	Trac 12834: more details substitution examples

[mjo]

I made some minor cosmetic fixes (typo fix and word-wrap). Other than that it looks good to me. As long as those optional tests work (I don't have maple/mathematica), you can mark it positive review.

---

Last 10 new commits:

​81ebcdc	Trac 12834: fix the french book that is using subs_expr
​f7a233b	Trac #12834: Avoid iterating over the substitution dict twice.
​322981e	Trac #12834: Ensure consistent failures by sorting duplicate substitutions.
​003fa00	Trac #12834: Test equality of dictionaries to avoid sorting bugs.
​5460cfc	Trac #12834: Mention the tuple representation in _subs_make_dict's docstring.
​e617094	Trac #12834: Manually word-wrap some lines.
​37aa1f8	Trac #12834: Simplify duplicate detection in _dict_update_check_duplicate.
​d2d58a3	Trac #12834: Fix hash lookup in _dict_update_check_duplicate.
​a56c969	Trac 12834: more details substitution examples
​66b961c	Trac #12834: Typo fix and manually word-wrap a few doctests.

[vdelecroix]

Thanks for the last fixes!

[vbraun]

sage -t --long --warn-long 26.6 src/sage/doctest/sources.py
**********************************************************************
File "src/sage/doctest/sources.py", line 694, in sage.doctest.sources.FileDocTestSource._test_enough_doctests
Failed example:
    for path, dirs, files in itertools.chain(os.walk('sage'), os.walk('doc')): # long time
        path = os.path.relpath(path)
        dirs.sort(); files.sort()
        for F in files:
            _, ext = os.path.splitext(F)
            if ext in ('.py', '.pyx', '.pxd', '.pxi', '.sage', '.spyx', '.rst'):
                filename = os.path.join(path, F)
                FDS = FileDocTestSource(filename, DocTestDefaults(long=True,optional=True))
                FDS._test_enough_doctests(verbose=False)
Expected:
    There are 7 tests in sage/combinat/dyck_word.py that are not being run
    There are 4 tests in sage/combinat/finite_state_machine.py that are not being run
    There are 6 tests in sage/combinat/interval_posets.py that are not being run
    There are 18 tests in sage/combinat/partition.py that are not being run
    There are 15 tests in sage/combinat/permutation.py that are not being run
    There are 14 tests in sage/combinat/skew_partition.py that are not being run
    There are 18 tests in sage/combinat/tableau.py that are not being run
    There are 8 tests in sage/combinat/crystals/tensor_product.py that are not being run
    There are 11 tests in sage/combinat/rigged_configurations/rigged_configurations.py that are not being run
    There are 15 tests in sage/combinat/root_system/cartan_type.py that are not being run
    There are 8 tests in sage/combinat/root_system/type_A.py that are not being run
    There are 8 tests in sage/combinat/root_system/type_G.py that are not being run
    There are 3 unexpected tests being run in sage/doctest/parsing.py
    There are 1 unexpected tests being run in sage/doctest/reporting.py
    There are 9 tests in sage/graphs/graph_plot.py that are not being run
    There are 3 tests in sage/rings/invariant_theory.py that are not being run
Got:
    There are 7 tests in sage/combinat/dyck_word.py that are not being run
    There are 4 tests in sage/combinat/finite_state_machine.py that are not being run
    There are 6 tests in sage/combinat/interval_posets.py that are not being run
    There are 18 tests in sage/combinat/partition.py that are not being run
    There are 15 tests in sage/combinat/permutation.py that are not being run
    There are 14 tests in sage/combinat/skew_partition.py that are not being run
    There are 18 tests in sage/combinat/tableau.py that are not being run
    There are 8 tests in sage/combinat/crystals/tensor_product.py that are not being run
    There are 11 tests in sage/combinat/rigged_configurations/rigged_configurations.py that are not being run
    There are 15 tests in sage/combinat/root_system/cartan_type.py that are not being run
    There are 8 tests in sage/combinat/root_system/type_A.py that are not being run
    There are 8 tests in sage/combinat/root_system/type_G.py that are not being run
    There are 3 unexpected tests being run in sage/doctest/parsing.py
    There are 1 unexpected tests being run in sage/doctest/reporting.py
    There are 9 tests in sage/graphs/graph_plot.py that are not being run
    There are 3 tests in sage/rings/invariant_theory.py that are not being run
    There are 10 tests in sage/symbolic/expression.pyx that are not being run

[vdelecroix]

My mistake. Sorry.

---

New commits:

​cb5347e

Trac 12834: move doctests related to the deprecated subs_expr

[vdelecroix]

This time all tests pass.