modelparameters.sympy.unify package

Submodules

modelparameters.sympy.unify.core module

Generic Unification algorithm for expression trees with lists of children

This implementation is a direct translation of

Artificial Intelligence: A Modern Approach by Stuart Russel and Peter Norvig Second edition, section 9.2, page 276

It is modified in the following ways:

1. We allow associative and commutative Compound expressions. This results in combinatorial blowup.

2. We explore the tree lazily.

3. We provide generic interfaces to symbolic algebra libraries in Python.

A more traditional version can be found here http://aima.cs.berkeley.edu/python/logic.html

class modelparameters.sympy.unify.core.Compound(op, args)

Bases: object

A little class to represent an interior node in the tree

This is analagous to SymPy.Basic for non-Atoms

class modelparameters.sympy.unify.core.CondVariable(arg, valid)

Bases: object

A wild token that matches conditionally

arg - a wild token valid - an additional constraining function on a match

class modelparameters.sympy.unify.core.Variable(arg)

Bases: object

A Wild token

modelparameters.sympy.unify.core.allcombinations(A, B, ordered)

Restructure A and B to have the same number of elements

ordered must be either ‘commutative’ or ‘associative’

A and B can be rearranged so that the larger of the two lists is reorganized into smaller sublists.

>>> from .core import allcombinations
>>> for x in allcombinations((1, 2, 3), (5, 6), 'associative'): print(x)
(((1,), (2, 3)), ((5,), (6,)))
(((1, 2), (3,)), ((5,), (6,)))

>>> for x in allcombinations((1, 2, 3), (5, 6), 'commutative'): print(x)
    (((1,), (2, 3)), ((5,), (6,)))
    (((1, 2), (3,)), ((5,), (6,)))
    (((1,), (3, 2)), ((5,), (6,)))
    (((1, 3), (2,)), ((5,), (6,)))
    (((2,), (1, 3)), ((5,), (6,)))
    (((2, 1), (3,)), ((5,), (6,)))
    (((2,), (3, 1)), ((5,), (6,)))
    (((2, 3), (1,)), ((5,), (6,)))
    (((3,), (1, 2)), ((5,), (6,)))
    (((3, 1), (2,)), ((5,), (6,)))
    (((3,), (2, 1)), ((5,), (6,)))
    (((3, 2), (1,)), ((5,), (6,)))

modelparameters.sympy.unify.core.assoc(d, key, val)

Return copy of d with key associated to val

modelparameters.sympy.unify.core.index(it, ind)

Fancy indexing into an indexable iterable (tuple, list)

>>> from .core import index
>>> index([10, 20, 30], (1, 2, 0))
[20, 30, 10]

modelparameters.sympy.unify.core.is_args(x)

Is x a traditional iterable?

modelparameters.sympy.unify.core.occur_check(var, x)

var occurs in subtree owned by x?

modelparameters.sympy.unify.core.partition(it, part)

Partition a tuple/list into pieces defined by indices

>>> from .core import partition
>>> partition((10, 20, 30, 40), [[0, 1, 2], [3]])
((10, 20, 30), (40,))

modelparameters.sympy.unify.core.unify(x, y, s=None, **fns)

Unify two expressions

inputs:

x, y - expression trees containing leaves, Compounds and Variables s - a mapping of variables to subtrees

outputs:

lazy sequence of mappings {Variable: subtree}

Examples

>>> from .core import unify, Compound, Variable
>>> expr    = Compound("Add", ("x", "y"))
>>> pattern = Compound("Add", ("x", Variable("a")))
>>> next(unify(expr, pattern, {}))
{Variable(a): 'y'}

modelparameters.sympy.unify.core.unify_var(var, x, s, **fns)

modelparameters.sympy.unify.core.unpack(x)

modelparameters.sympy.unify.rewrite module

Functions to support rewriting of SymPy expressions

modelparameters.sympy.unify.rewrite.rewriterule(source, target, variables=(), condition=None, assume=None)

Rewrite rule

Transform expressions that match source into expressions that match target treating all variables as wilds.

>>> from ..abc import w, x, y, z
>>> from .rewrite import rewriterule
>>> from ..utilities import default_sort_key
>>> rl = rewriterule(x + y, x**y, [x, y])
>>> sorted(rl(z + 3), key=default_sort_key)
[3**z, z**3]

Use condition to specify additional requirements. Inputs are taken in the same order as is found in variables.

>>> rl = rewriterule(x + y, x**y, [x, y], lambda x, y: x.is_integer)
>>> list(rl(z + 3))
[3**z]

Use assume to specify additional requirements using new assumptions.

>>> from ..assumptions import Q
>>> rl = rewriterule(x + y, x**y, [x, y], assume=Q.integer(x))
>>> list(rl(z + 3))
[3**z]

Assumptions for the local context are provided at rule runtime

>>> list(rl(w + z, Q.integer(z)))
[z**w]

modelparameters.sympy.unify.usympy module

SymPy interface to Unification engine

See sympy.unify for module level docstring See sympy.unify.core for algorithmic docstring

modelparameters.sympy.unify.usympy.construct(t)

Turn a Compound into a SymPy object

modelparameters.sympy.unify.usympy.deconstruct(s, variables=())

Turn a SymPy object into a Compound

modelparameters.sympy.unify.usympy.is_associative(x)

modelparameters.sympy.unify.usympy.is_commutative(x)

modelparameters.sympy.unify.usympy.mk_matchtype(typ)

modelparameters.sympy.unify.usympy.rebuild(s)

Rebuild a SymPy expression

This removes harm caused by Expr-Rules interactions

modelparameters.sympy.unify.usympy.sympy_associative(op)

modelparameters.sympy.unify.usympy.sympy_commutative(op)

modelparameters.sympy.unify.usympy.unify(x, y, s=None, variables=(), **kwargs)

Structural unification of two expressions/patterns

Examples

>>> from .usympy import unify
>>> from .. import Basic, cos
>>> from ..abc import x, y, z, p, q

>>> next(unify(Basic(1, 2), Basic(1, x), variables=[x]))
{x: 2}

>>> expr = 2*x + y + z
>>> pattern = 2*p + q
>>> next(unify(expr, pattern, {}, variables=(p, q)))
{p: x, q: y + z}

Unification supports commutative and associative matching

>>> expr = x + y + z
>>> pattern = p + q
>>> len(list(unify(expr, pattern, {}, variables=(p, q))))
12

Symbols not indicated to be variables are treated as literal, else they are wild-like and match anything in a sub-expression.

>>> expr = x*y*z + 3
>>> pattern = x*y + 3
>>> next(unify(expr, pattern, {}, variables=[x, y]))
{x: y, y: x*z}

The x and y of the pattern above were in a Mul and matched factors in the Mul of expr. Here, a single symbol matches an entire term:

>>> expr = x*y + 3
>>> pattern = p + 3
>>> next(unify(expr, pattern, {}, variables=[p]))
{p: x*y}

Module contents

Unification in SymPy

See sympy.unify.core docstring for algorithmic details

See http://matthewrocklin.com/blog/work/2012/11/01/Unification/ for discussion