Help on Pattern Matching

246 views
Skip to first unread message

Matthew Rocklin

unread,
Oct 22, 2012, 11:52:45 AM10/22/12
to sy...@googlegroups.com
Hi Everyone, 

I'd like to know more about pattern matching within SymPy and how it can be applied beyond the Expr class. 

I see that Basic has a matches method that does exact matching (so for example requires the same number of args and same arg sequence between pattern and expression). I see that AssocOp(Expr) has a _matches_commutative method that (I assume) allows freer matching. 

Some questions:
How well does pattern matching work in SymPy on non-commutative symbols?
How well does pattern matching work in SymPy on non-Exprs. Could _matches_commutative be moved up out of Expr to work on Basics? This code appears pretty general. Union(Set) is commutative too.
The Wild class is a Symbol. How should we construct Wild objects for other non-expr types? How could we match sets for example?

The code in _matches_commutative and mul.matches are difficult for me to understand. Are these implementing a known algorithm that I can look up somewhere. Are there supplemental docs or references?

If anyone is knowledgeable or interested in extending pattern matching within SymPy I'd enjoy company on this project.

-Matt

Sergiu Ivanov

unread,
Oct 23, 2012, 2:07:04 AM10/23/12
to sy...@googlegroups.com
Hi Matthew,

On Mon, Oct 22, 2012 at 08:52:45AM -0700, Matthew Rocklin wrote:
>
> If anyone is knowledgeable or interested in extending pattern matching
> within SymPy I'd enjoy company on this project.

I would be interested in this (e.g., because it can eventually
contribute to the rules mechanism). However, I'm not knowledgeable
enough to answer your questions off-hand, while playing with SymPy is
not that accessible to me this week because of some seminars I'm
compelled to attempt.

Whenever you discover something new, please report this here, so that
I know where to start when I get freer in a couple days.

I'd be happy to know more about SymPy's pattern matching and extend
it.

Sergiu

Matthew Rocklin

unread,
Oct 23, 2012, 1:58:22 PM10/23/12
to sy...@googlegroups.com
Awesome. Despite it being a cool topic (I think so at least) I'd be very glad to not think about pattern matching. There are some other matrix related things I can work on in the meantime.

I recently asked a related question on stackoverflow


I'm not sure if SymPy can do this. If it can't I'd be happy to know of general algorithms. 


Sergiu

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.


Aaron Meurer

unread,
Oct 24, 2012, 2:27:53 AM10/24/12
to sy...@googlegroups.com
On Tue, Oct 23, 2012 at 11:58 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
> Awesome. Despite it being a cool topic (I think so at least) I'd be very
> glad to not think about pattern matching. There are some other matrix
> related things I can work on in the meantime.
>
> I recently asked a related question on stackoverflow
>
> http://stackoverflow.com/questions/13036336/set-of-all-possible-matches-in-sympy

I posted one possible answer there. Probably it would be nicer if
something like this were implemented directly.

Aaron Meurer

Aaron Meurer

unread,
Oct 24, 2012, 2:39:40 AM10/24/12
to sy...@googlegroups.com
On Mon, Oct 22, 2012 at 9:52 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
> Hi Everyone,
>
> I'd like to know more about pattern matching within SymPy and how it can be
> applied beyond the Expr class.
>
> I see that Basic has a matches method that does exact matching (so for
> example requires the same number of args and same arg sequence between
> pattern and expression). I see that AssocOp(Expr) has a _matches_commutative
> method that (I assume) allows freer matching.
>
> Some questions:
> How well does pattern matching work in SymPy on non-commutative symbols?
> How well does pattern matching work in SymPy on non-Exprs. Could
> _matches_commutative be moved up out of Expr to work on Basics? This code
> appears pretty general. Union(Set) is commutative too.
> The Wild class is a Symbol. How should we construct Wild objects for other
> non-expr types? How could we match sets for example?

I only have experience with matching expressions, particularly in the
ode module with classify_ode. If you want to match some complicated
expressions, you will run into some limitations soon. One issue is
that you can't match "n" terms, so for example, I had to write a
custom matcher for a linear ODE with constant coefficients (an*y^(n) +
... + a1*y' + a0*y = g).

Another issue is that the pattern matcher will give non-deterministic
results unless you specify the exclude keyword on the Wild objects
very carefully.

A third issue is that automatic simplification (and in many cases,
even non-automatic simplification, i.e., expressions being written in
different equivalent forms) can move an expression into a form that
the pattern matcher won't recognize. For example:

In [20]: p = Wild('p', exclude=[x])

In [21]: q = Wild('q')

In [24]: (pi*(x + 1)).match(p*q)
Out[24]: {p: π, q: x + 1}

In [26]: (2*(x + 1)).match(p*q)
Out[26]: {p: 1, q: 2⋅x + 2}

Note that 2*(x + 1) is automatically converted to 2*x + 2.

Another good example is at http://code.google.com/p/sympy/issues/detail?id=1784.

The good news is that there are a lot of good algorithms that you can
use to write custom targeted matching solutions. For example, with
the above, you could use some of the gcd algorithms (I'm not sure
which exactly; terms_gcd I think) to pull out the coefficient, if
that's what you want.

The bad news is that it isn't automated in the pattern matcher.
Matching pure ast trees is easy enough, but you'll find that you
really want to match things on a mathematical basis to some level, and
for this, the power is there, but it's not automated.

>
> The code in _matches_commutative and mul.matches are difficult for me to
> understand. Are these implementing a known algorithm that I can look up
> somewhere. Are there supplemental docs or references?

I thought we tried to document this a while back when we were fixing
some bugs. Are the inline comments and docstrings not enough?

Aaron Meurer

>
> If anyone is knowledgeable or interested in extending pattern matching
> within SymPy I'd enjoy company on this project.
>
> -Matt
>

Chris Smith

unread,
Oct 24, 2012, 3:03:05 AM10/24/12
to sy...@googlegroups.com
You might also search the issues for label:Matching and see my old
notes at http://code.google.com/p/sympy/issues/detail?id=1601, FWIW.

/c

Matthew Rocklin

unread,
Oct 24, 2012, 10:22:35 AM10/24/12
to sy...@googlegroups.com
I only have experience with matching expressions, particularly in the
ode module with classify_ode.  If you want to match some complicated
expressions, you will run into some limitations soon.  One issue is
that you can't match "n" terms, so for example, I had to write a
custom matcher for a linear ODE with constant coefficients (an*y^(n) +
... + a1*y' + a0*y = g).

I'm just trying to do fairly simple non-expr expressions. Here is an example.

In [1]: p = Wild('p')
In [2]: s = Union(FiniteSet(1,2,3), Interval(5, 7))
In [3]: s.match(Union(p, Interval(5, 7)))
TypeError: Input must be Sets or iterables of Sets

Do we have a non-Expr wild?

Another issue is that the pattern matcher will give non-deterministic
results unless you specify the exclude keyword on the Wild objects
very carefully.

Right, I'd actually like to explore this. I want all of the possible matches. This is one trivial way to defeat non-determinism :) Is there a way to explore the non-determinism here?
 
A third issue is that automatic simplification (and in many cases,
even non-automatic simplification, i.e., expressions being written in
different equivalent forms) can move an expression into a form that
the pattern matcher won't recognize. For example:

In my particular case automatic simplification shouldn't be an issue but yes, I can see how this could be annoying. Presumably this would work if you built the expr and pattern with evaluate=False?

The good news is that there are a lot of good algorithms that you can
use to write custom targeted matching solutions.  For example, with
the above, you could use some of the gcd algorithms (I'm not sure
which exactly; terms_gcd I think) to pull out the coefficient, if
that's what you want.

Are there good general pattern matching/unification algorihtms? Something like risch or meijerint but for this domain?
 
I thought we tried to document this a while back when we were fixing
some bugs.  Are the inline comments and docstrings not enough?

I was not sufficiently clever for this.

Aaron Meurer

unread,
Oct 24, 2012, 11:14:54 AM10/24/12
to sy...@googlegroups.com
On Wed, Oct 24, 2012 at 8:22 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
>
>> I only have experience with matching expressions, particularly in the
>> ode module with classify_ode. If you want to match some complicated
>> expressions, you will run into some limitations soon. One issue is
>> that you can't match "n" terms, so for example, I had to write a
>> custom matcher for a linear ODE with constant coefficients (an*y^(n) +
>> ... + a1*y' + a0*y = g).
>
>
> I'm just trying to do fairly simple non-expr expressions. Here is an
> example.
>
> In [1]: p = Wild('p')
> In [2]: s = Union(FiniteSet(1,2,3), Interval(5, 7))
> In [3]: s.match(Union(p, Interval(5, 7)))
> TypeError: Input must be Sets or iterables of Sets
>
> Do we have a non-Expr wild?

I don't think we do, but I could be missing it.

I don't imagine it would be too hard to just create BasicWild, had
Wild subclass from it (and Symbol), and then move _matches_commutative
to Basic as you said, and change other commutative classes like Union
to call it.

>
>> Another issue is that the pattern matcher will give non-deterministic
>> results unless you specify the exclude keyword on the Wild objects
>> very carefully.
>
>
> Right, I'd actually like to explore this. I want all of the possible
> matches. This is one trivial way to defeat non-determinism :) Is there a way
> to explore the non-determinism here?

I see some potential issues with this. First is that depending on how
you define a match, you might have infinitely many possible results.
For examples, (x**n).match(p*q) might give x**n*1 or x**(n - 1)*x or
(x**n*a)*(1/a) or x**(n - a)*x**a (for arbitrary a). The third one in
particular sounds a little contrived, but consider if we had a*x**2 +
x, and we wanted to match against p*q, where q excludes x. We might
want that to give a*(x**2 + x/a). So it's not too far off to consider
"adding a new term" to a multiplication.

So it's clear that to do this, you need to make sure that the matching
is very precisely defined. Probably in an AST way more than a
mathematical way (but not necessarily). Another issue might be that
all possible matches might be large, possibly even combinatorially
large, depending on what your expression is.

With that being said, I think this is a good idea, and that you should
explore it.

>
>>
>> A third issue is that automatic simplification (and in many cases,
>> even non-automatic simplification, i.e., expressions being written in
>> different equivalent forms) can move an expression into a form that
>> the pattern matcher won't recognize. For example:
>
>
> In my particular case automatic simplification shouldn't be an issue but
> yes, I can see how this could be annoying. Presumably this would work if you
> built the expr and pattern with evaluate=False?

But even as I said, you run into issues with simplification that is
not automatic, i.e., the expression not being in exactly the form you
expect.

>
>> The good news is that there are a lot of good algorithms that you can
>> use to write custom targeted matching solutions. For example, with
>> the above, you could use some of the gcd algorithms (I'm not sure
>> which exactly; terms_gcd I think) to pull out the coefficient, if
>> that's what you want.
>
>
> Are there good general pattern matching/unification algorihtms? Something
> like risch or meijerint but for this domain?

Probably, but I don't know them. See what Mathematica does, as I've
heard it has good pattern matching.

>
>>
>> I thought we tried to document this a while back when we were fixing
>> some bugs. Are the inline comments and docstrings not enough?
>
>
> I was not sufficiently clever for this.

Well, the code is complicated, which is why we tried to document it.
If you can figure it out, perhaps you should document it some more.

Aaron Meurer

Matthew Rocklin

unread,
Oct 25, 2012, 10:02:29 PM10/25/12
to sy...@googlegroups.com
I see some potential issues with this.  First is that depending on how
you define a match, you might have infinitely many possible results.
For examples, (x**n).match(p*q) might give x**n*1 or x**(n - 1)*x or
(x**n*a)*(1/a) or x**(n - a)*x**a (for arbitrary a). The third one in
particular sounds a little contrived, but consider if we had a*x**2 +
x, and we wanted to match against p*q, where q excludes x. We might
want that to give a*(x**2 + x/a). So it's not too far off to consider
"adding a new term" to a multiplication.

So it's clear that to do this, you need to make sure that the matching
is very precisely defined. Probably in an AST way more than a
mathematical way (but not necessarily). Another issue might be that
all possible matches might be large, possibly even combinatorially
large, depending on what your expression is.

With that being said, I think this is a good idea, and that you should
explore it.

Yes, I'm more interested in structural matching. After reading more about this I think I'm actually interested in Unification. I'm not interested right now in mixing matching with mathematical transformations. I think that's likely to be a harder problem. 

Regarding combinatorial explosion yes, that's an issue. There are a few ways to get past this, the first is to do this whole experiment with lazy generators. Get one match quickly, ask for another if you don't like it, if you want all of them you have that option. I believe that Prolog works this way. You might also be able to do some sort of guided search. Ideally we find a way to separate the search mechanism from the matching.

Sergiu Ivanov

unread,
Oct 26, 2012, 7:13:44 AM10/26/12
to sy...@googlegroups.com
On Thu, Oct 25, 2012 at 07:02:29PM -0700, Matthew Rocklin wrote:
>
> Regarding combinatorial explosion yes, that's an issue. There are a few
> ways to get past this, the first is to do this whole experiment with lazy
> generators. Get one match quickly, ask for another if you don't like it, if
> you want all of them you have that option. I believe that Prolog works this
> way. You might also be able to do some sort of guided search. Ideally we
> find a way to separate the search mechanism from the matching.

I'm fully supportive of applying the lazy approach by means of
generators. In my GSoC-2012 work I relied on generators a great deal
and I haven't yet had an occasion to regret this.

Sergiu

Matthew Rocklin

unread,
Oct 26, 2012, 2:49:32 PM10/26/12
to sy...@googlegroups.com
I've asked this question on StackOverflow. It has a clear example of what I want.

http://stackoverflow.com/questions/13092092/algorithms-for-unification-of-list-based-trees

Can anyone here point us to standard solutions to this problem?

Matthew Rocklin

unread,
Oct 30, 2012, 2:20:18 PM10/30/12
to sy...@googlegroups.com
I adapted a general algorithm to perform structural matching on list-based trees (like our trees). My code is here

It works on any trees where each node can be described as a type (like our Add, Mul) and a list of children (like our args). It also handles associative operations well. For example if you want to match

Add(a, b, c) 
Add(x, y)

It will rearrange the first expression so that the number of args match. In this case it will test each of the two options.

Add(a, Add(b, c))
Add(Add(a, b), c)

As a result this code returns many possible matches. It does this lazily using generators. 

Standard SymPy method
In [1]: p, q = map(Wild, 'pq')
In [2]: (x+y+z).match(p+q)
Out[2]: {p: y + z, q: x}

Structural Unification
In [5]: from unify_sympy import unify
In [6]: unify(x+y+z, p+q, {})
Out[6]: <generator object unify at 0x54b8640>

In [7]: list(_)
Out[7]: [{p: y, q: x + z}, {p: y + z, q: x}]

Note that this doesn't yet handle commutativity. For example the case {p: x+y, q: z} is not represented. The ordering in this example is made slightly more confusing because Add is rearranging the args (x, y, z).

The commutativity problem can be solved if this stackoverflow problem can be solved

Aaron Meurer

unread,
Oct 30, 2012, 2:28:50 PM10/30/12
to sy...@googlegroups.com
Will you be able to extend this to match Mul(2, x) against Add(a, b) (where a = b = x)?

Aaron Meurer 

Matthew Rocklin

unread,
Oct 30, 2012, 3:14:31 PM10/30/12
to sy...@googlegroups.com
Short answer is "No". This version of pattern matching knows nothing about mathematics. It only knows about matching trees. This does not replace SymPy pattern matching. 

Long answer is that you might be able to obtain this by composing unification (pattern matching) with rewrite rules. 

Chris Smith

unread,
Oct 30, 2012, 3:19:15 PM10/30/12
to sy...@googlegroups.com
> The commutativity problem can be solved if this stackoverflow problem can be
> solved
> http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily

I think you've got all you need in the treasure trove that is
iterables. Tim Peter's routine for partitions is very fast. You just
harness that to your sequence (commutative or non-commutative) that
you want to partition, something like:


def kbin(l, k, ordered=True):
"""
Return sequence ``l`` partitioned into ``k`` bins.
If ordered is True then the order of the items in the
flattened partition will be the same as the order of the
items in ``l``; if False, all permutations of the items will
be given.

Examples
========

>>> for p in kbin(range(3), 2):
... print p
...
[[0], [1, 2]]
[[0, 1], [2]]
>>> for p in kbin(range(3), 2, ordered=False):
... print p
...
[(0,), (1, 2)]
[(0,), (2, 1)]
[(1,), (0, 2)]
[(1,), (2, 0)]
[(2,), (0, 1)]
[(2,), (1, 0)]
[(0, 1), (2,)]
[(0, 2), (1,)]
[(1, 0), (2,)]
[(1, 2), (0,)]
[(2, 0), (1,)]
[(2, 1), (0,)]

"""
from sympy.utilities.iterables import partitions
from sympy.core.compatibility import permutations

for p in partitions(len(l), k):
if sum(p.values()) != k:
continue
for pe in permutations(p.keys()):
rv = []
i = 0
for part in pe:
for do in range(p[part]):
j = i + part
rv.append(l[i: j])
i = j
if ordered:
yield rv
else:
take = [len(i) for i in rv]
for pp in permutations(l):
rvp = []
ii = 0
for t in take:
jj = ii + t
rvp.append(pp[ii: jj])
ii = jj
yield rvp

Matthew Rocklin

unread,
Oct 30, 2012, 4:42:52 PM10/30/12
to sy...@googlegroups.com
Awesome. Following the "if you give a bear a cookie he'll ask for a glass of milk principle" can we use these algorithms to efficiently only produce unique sets in the commutative case? 

E.g. can we turn 

    >>> for p in kbin(range(3), 2, ordered=False):
    ...     print p
    ...
    [(0,), (1, 2)]
    [(0,), (2, 1)]
    [(1,), (0, 2)]
    [(1,), (2, 0)]
    [(2,), (0, 1)]
    [(2,), (1, 0)]
    [(0, 1), (2,)]
    [(0, 2), (1,)]
    [(1, 0), (2,)]
    [(1, 2), (0,)]
    [(2, 0), (1,)]
    [(2, 1), (0,)]
 
into

    >>> for p in kbin(range(3), 2, ordered=False):
    ...     print p
    ...
    [(0,), (1, 2)]
    [(1,), (0, 2)]
    [(2,), (0, 1)]

This could be done with an ifilter but as n and k become moderately sized this might become quite large. 

Matthew Rocklin

unread,
Oct 30, 2012, 4:46:57 PM10/30/12
to sy...@googlegroups.com
Ideally I would also like to have the core of the unify algorithm be sympy independent. The Theano project might also be able to use it. 

Chris Smith

unread,
Oct 30, 2012, 5:14:50 PM10/30/12
to sy...@googlegroups.com
I think if you use rotations instead of permutations it will give you
what you want:

```

def rotations(seq):
for i in range(len(seq)):
yield seq
seq.append(seq.pop(0))

def kbins:
if unordered:
if unique:
func = rotations
else:
func = permutations
...
if ordered:
yield
else:
...
for p in func(...) <-- instead of permutations(...)
...
```

Chris

Chris Smith

unread,
Oct 30, 2012, 5:16:00 PM10/30/12
to sy...@googlegroups.com
The things that are in iterables are generally sympy-independent. i.e.
there is no sympification going on.

Chris Smith

unread,
Oct 30, 2012, 5:27:23 PM10/30/12
to sy...@googlegroups.com
What is said works, I believe...see the docstring

def kbin(l, k, ordered=True):
"""
Return sequence ``l`` partitioned into ``k`` bins.
If ordered is True then the order of the items in the
flattened partition will be the same as the order of the
items in ``l``; if False, all permutations of the items will
be given; if None, only unique permutations for a given
partition will be given.

Examples
========

>>> from sympy.utilities.iterables import kbin
>>> for p in kbin(range(3), 2):
... print p
...
[[0], [1, 2]]
[[0, 1], [2]]
>>> for p in kbin(range(3), 2, ordered=False):
... print p
...
[(0,), (1, 2)]
[(0,), (2, 1)]
[(1,), (0, 2)]
[(1,), (2, 0)]
[(2,), (0, 1)]
[(2,), (1, 0)]
[(0, 1), (2,)]
[(0, 2), (1,)]
[(1, 0), (2,)]
[(1, 2), (0,)]
[(2, 0), (1,)]
[(2, 1), (0,)]
>>> for p in kbin(range(3), 2, ordered=None):
... print p
...
[[0], [1, 2]]
[[1], [2, 0]]
[[2], [0, 1]]
[[0, 1], [2]]
[[1, 2], [0]]
[[2, 0], [1]]

"""
from sympy.utilities.iterables import partitions, permutations
def rotations(seq):
for i in range(len(seq)):
yield seq
seq.append(seq.pop(0))
if ordered is None:
func = rotations
else:
func = permutations
for p in partitions(len(l), k):
if sum(p.values()) != k:
continue
for pe in permutations(p.keys()):
rv = []
i = 0
for part in pe:
for do in range(p[part]):
j = i + part
rv.append(l[i: j])
i = j
if ordered:
yield rv
else:
template = [len(i) for i in rv]
for pp in func(l):
rvp = []
ii = 0
for t in template:

Matthew Rocklin

unread,
Oct 30, 2012, 6:13:31 PM10/30/12
to sy...@googlegroups.com
Yes, that works quite well. Thanks Chris!


Matthew Rocklin

unread,
Oct 30, 2012, 6:25:18 PM10/30/12
to sy...@googlegroups.com
Chris' code now enables unification to produce all possible matches

In [1]: run ../unify/unify_sympy.py
In [2]: expr = Add(1, 2, 3, evaluate=False)
In [3]: a, b = map(Wild, 'ab')
In [4]: pattern = Add(a, b, evaluate=False)

In [5]: for x in unify(expr, pattern, {}): print x
{a_: 1, b_: 2 + 3}
{a_: 2, b_: 1 + 3}
{a_: 3, b_: 1 + 2}
{a_: 1 + 2, b_: 3}
{a_: 2 + 3, b_: 1}
{a_: 1 + 3, b_: 2}

Of course, this quickly leads to computational blowup. Fortunately you can ask very efficiently for just the first, second, etc...

Note that, as Aaron pointed out, this doesn't handle mathematical matching. Here is an example which matches a very particular structure.

In [8]: from sympy.abc import x
In [9]: expr = Add(1, 2*x, 3, evaluate=False)
In [10]: pattern = Add(a, 2*b, evaluate=False)
In [11]: for x in unify(expr, pattern, {}): print x
{a_: 1 + 3, b_: x}

Of course, we don't need to match exact structure. Wilds can currently match any node.

In [6]: pattern = Add(a, b, evaluate=False)

In [7]: for x in unify(expr, pattern, {}): print x
{a_: 1, b_: 2*x + 3}
{a_: 2*x, b_: 1 + 3}
{a_: 3, b_: 2*x + 1}
{a_: 2*x + 1, b_: 3}
{a_: 2*x + 3, b_: 1}
{a_: 1 + 3, b_: 2*x}

Chris Smith

unread,
Oct 30, 2012, 6:46:09 PM10/30/12
to sy...@googlegroups.com
If you want to match a + b to 2*x you just have to partition the 2. If
objects had an _eval_partition they could give you back their
partitions...just a thought. May be totally unworkable in practice.
Alternatively, you could gradually, for a failing pattern, allow
symbol degeneracy...so a + b would become a + a = 2*a if the a + b
didn't match or a + b*c would become a + a*c or a + b*b, etc...

Matthew Rocklin

unread,
Oct 30, 2012, 7:02:02 PM10/30/12
to sy...@googlegroups.com
I think that going down this route leads us to SymPy's current (and quite capable) pattern matcher. 

This unification system is completely independent from mathematical logic. I've intentionally used namedtuples to try to enforce this separation. 

Of course, one could build something on top of the unification system. For example we could try to unify, if we fail then try each of our simplification or expansion routines in some order hoping to come across a match. There are lots of more sophisticated options. I think that unification should remain an atomic building block though.

Aaron Meurer

unread,
Oct 30, 2012, 8:25:40 PM10/30/12
to sy...@googlegroups.com
As I noted on StackOverflow, if you allow the kbin to return empty
sets, those could represent identities (assuming your operation has
one). Then you would get the matches {a:0, b: 1 + 2 + 3} and {a: 1 +
2 + 3, b: 0}. Depending on what you use this for, it may be desirable
to include those.

Aaron Meurer

Matthew Rocklin

unread,
Oct 30, 2012, 8:31:34 PM10/30/12
to sy...@googlegroups.com
You're right. This might be useful. I'll keep it in mind as I continue to experiment with this. 

I hope to issue a PR with this in the next couple days. People can also play with and improve it after then. While I like the separation of this code I think each of the pieces could be improved by someone with more time and attention to devote to it.

Matthew Rocklin

unread,
Oct 31, 2012, 10:34:22 AM10/31/12
to sy...@googlegroups.com
Just to keep everyone up to date we now have basic rewrite rules via pattern matching

In [1]: run ../unify/unify_sympy.py
In [2]: p, q = map(Wild, 'pq')
In [3]: pattern1 = p + q
In [4]: pattern2 = p * q
In [5]: add_to_mul = rewriterule(pattern1, pattern2)
In [6]: for x in add_to_mul(x*y + z):
    print x
   ...:     
x*y*z

rewriterule is written as follows. It uses an exact subs currently in my blas branch.

def rewriterule(p1, p2):
    from sympy.rules.tools import subs
    from sympy import Expr
    def rewrite_rl(expr):
        matches = unify(p1, expr, {})
        for match in matches:
            expr2 = subs(match)(p2)
            if isinstance(expr2, Expr):
                expr2 = rebuild(expr2) # Exprs need to be rebuilt without Basic.__new__
            yield expr2
    return rewrite_rl

It still has issues that need to be worked out. I'm not matching things that I think I should. I'll write up a blogpost and a PR when its' better. 

Matthew Rocklin

unread,
Nov 1, 2012, 1:10:33 PM11/1/12
to sy...@googlegroups.com

Chris Smith

unread,
Nov 2, 2012, 5:20:42 PM11/2/12
to sy...@googlegroups.com
On Wed, Oct 31, 2012 at 2:27 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
> Awesome. Following the "if you give a bear a cookie he'll ask for a glass of
> milk principle" can we use these algorithms to efficiently only produce
> unique sets in the commutative case?
>

Do you only need the two types of partitions: lists of lists and sets
of sets as you said at
http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily/13184004#13184004
?

Matthew Rocklin

unread,
Nov 2, 2012, 5:24:36 PM11/2/12
to sy...@googlegroups.com
Yes. I'm turning things like Add(a,b,c,d,e) into things like Add(a, Add(b, c, d), e). Either both Adds are commutative (using sets) or neither are. 


?

Chris Smith

unread,
Nov 2, 2012, 5:48:08 PM11/2/12
to sy...@googlegroups.com
OK. Then see http://tinyurl.com/bgklazd again for the updated
algorithm. Note that the ordered=None case is reported as lists of
lists but they should be thought of as sets of sets.
Message has been deleted

Matthew Rocklin

unread,
Nov 9, 2012, 8:59:32 AM11/9/12
to sy...@googlegroups.com
No, that's a very reasonable idea. I believe that this is how Maude does it.

I haven't thought much about this problem. It's large and I don't have much experience with it. Suggestions like this are helpful.

Thanks
-Matt


On Wed, Nov 7, 2012 at 5:29 PM, Mark <mfe...@gmail.com> wrote:
I only skimmed into this thread from a discussion on theano-dev (which I was, in turn, only casually following).  So, my comment may be meaningless.  

But one thought I had was can you prevent some of the combinatorial blowup by asserting (or converting) to canonical form before applying rewrite rules?  [Perhaps you have cases where you specifically want arbitrarily ordered expressions written to other (arbitrarily ordered) expressions.]

Again, possibly just a stray thread.

Best,
Mark

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To view this discussion on the web visit https://groups.google.com/d/msg/sympy/-/WaYFHoReKnIJ.
Reply all
Reply to author
Forward
0 new messages