Blogpost on this topic http://matthewrocklin.com/blog/work/2012/11/01/Unification/
On Wed, Oct 31, 2012 at 9:34 AM, Matthew Rocklin <[email protected]> wrote: > 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. > > > > On Tue, Oct 30, 2012 at 7:31 PM, Matthew Rocklin <[email protected]>wrote: > >> 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. >> >> On Tue, Oct 30, 2012 at 7:25 PM, Aaron Meurer <[email protected]> wrote: >> >>> 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 >>> >>> On Tue, Oct 30, 2012 at 4:25 PM, Matthew Rocklin <[email protected]> >>> wrote: >>> > 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} >>> > >>> > On Tue, Oct 30, 2012 at 5:13 PM, Matthew Rocklin <[email protected]> >>> wrote: >>> >> >>> >> Yes, that works quite well. Thanks Chris! >>> >> >>> >> >>> >> On Tue, Oct 30, 2012 at 4:27 PM, Chris Smith <[email protected]> >>> wrote: >>> >>> >>> >>> 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: >>> >>> jj = ii + t >>> >>> rvp.append(pp[ii: jj]) >>> >>> ii = jj >>> >>> yield rvp >>> >>> >>> >>> -- >>> >>> You received this message because you are subscribed to the Google >>> Groups >>> >>> "sympy" group. >>> >>> To post to this group, send email to [email protected]. >>> >>> To unsubscribe from this group, send email to >>> >>> [email protected]. >>> >>> For more options, visit this group at >>> >>> http://groups.google.com/group/sympy?hl=en. >>> >>> >>> >> >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "sympy" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > For more options, visit this group at >>> > http://groups.google.com/group/sympy?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/sympy?hl=en. >>> >>> >> > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
