sympy/sympy — pull request #8055 by Upabjojr (2014-09-17 17:00:14+00:00)
Title: Sort key for rule pattern dispatch

The set of all possible matching patterns is a partially ordered set when one considers the _specificity_ of the patterns. A pattern is more _specific_ if it matches a proper subset of the expressions that another pattern matches.

The goal of this PR is to create a key that promotes this partial order to a total order.

Clearly, `f(sin(x_))` is more specific than `f(x_)`, while there may be cases in which this kind of order is not defined, e.g. `f(cos(x_))` vs `f(sin(x_))`. In this last case, the sets of matching expressions are disjoint, but that's not a serious problem, as one could add an additional factor (say, lexicographic order) to determine which of `f(cos(x_))` and `f(sin(x_))` comes first.

Unfortunately, there is an even worse case, in which the sets of matching expressions for two patterns partly overlap, which creates ambiguities. This problem may be solved by considering the argument order in the expression tree.

If assumptions on wildcards were included, it would get even worse. This case is currently ignored, as SymPy Wilds still ignore assumptions.

Node dispatching priority (order given by the list below):
* non-atoms
* numbers
* symbols
* wildcards

`x_` in Mathematica is short for `Pattern[x, Blank[]]`, because `_` is an operator.

* [ ] which order for `f(sin(w_))` and `f(x)`. Mathematica has `f(x) > f(sin(w_))`
* [ ] how to treat non-sympified objects? Should they be treated as atoms?
* [ ] add parser for non-sympified objects. Maybe sympify them?
* [ ] add tests for non-sympified objects.
* [ ] what to do with uninstanciated classes? `Add` vs `Add(x, y)`. If `Add` is in the expression without being called?
* [ ] what to do with dummies?
* [ ] add tests for dummies.
* [ ] test expressions that are one-parameter-identities.