246 views

Skip to first unread message

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

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

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.

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

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.

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

something like this were implemented directly.

Aaron Meurer

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
> 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?

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?

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

>

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

notes at http://code.google.com/p/sympy/issues/detail?id=1601, FWIW.

/c

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.

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 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 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?

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?

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?

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.

If you can figure it out, perhaps you should document it some more.

Aaron Meurer

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.

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
>

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

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

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?

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

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

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

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.

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
> solved

> http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily

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

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.

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.

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

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

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.

there is no sympification going on.

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

[[2], [0, 1]]

[[0, 1], [2]]

[[1, 2], [0]]

[[2, 0], [1]]

"""

from sympy.utilities.iterables import partitions, permutations

func = rotations

else:

func = permutations

for pp in func(l):

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

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]]

[[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,)]

... print p

...

[[0], [1, 2]]

[[1], [2, 0]]
...

[[0], [1, 2]]

[[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:
for i in range(len(seq)):

yield seq

seq.append(seq.pop(0))

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]
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:

for pp in func(l):

rvp = []

ii = 0

for t in template:
ii = 0

Oct 30, 2012, 6:13:31 PM10/30/12

to sy...@googlegroups.com

Yes, that works quite well. Thanks Chris!

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}

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

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

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.

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

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

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.

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.

Nov 1, 2012, 1:10:33 PM11/1/12

to sy...@googlegroups.com

Blogpost on this topic

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
> 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?

>

of sets as you said at

http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily/13184004#13184004

?

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.

?

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.

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

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

Search

Clear search

Close search

Google apps

Main menu