matchpy.expressions.expressions module¶

This module contains the expression classes.

Expressions can be used to model any kind of tree-like data structure. They consist of operations and symbols. In addition, patterns can be constructed, which may additionally, contain wildcards and variables.

You can define your own symbols and operations like this:

>>> f = Operation.new('f', Arity.variadic)
>>> a = Symbol('a')
>>> b = Symbol('b')

Then you can compose expressions out of these:

>>> print(f(a, b))
f(a, b)

For more information on how to create you own operations and symbols you can look at their documentation.

Normal expressions are immutable and hence hashable:

>>> expr = f(b, x_)
>>> print(expr)
f(b, x_)
>>> hash(expr) == hash(expr)
True

Hence, some of the expression’s properties are cached and nor updated when you modify them:

>>> expr.is_constant
False
>>> expr.operands = [a]
>>> expr.is_constant
False
>>> print(expr)
f(a)
>>> f(a).is_constant
True

Therefore, you should modify an expression but rather create a new one:

>>> expr2 = type(expr)(*[a])
>>> expr2.is_constant
True
>>> print(expr2)
f(a)

class Expression(variable_name)¶

Bases: object

Base class for all expressions.

Do not subclass this class directly but rather Symbol or Operation. Creating a direct subclass of Expression might break several (matching) algorithms.

head¶

The head of the expression. For an operation, it is the type of the operation (i.e. a subclass of Operation). For wildcards, it is None. For symbols, it is the symbol itself.

Type:	Optional[Union[type, Atom]]

__getitem__(position: Union[Tuple[int, ...], slice]) → matchpy.expressions.expressions.Expression¶

Return the subexpression at the given position(s).

It is also possible to use a slice notation to extract a sequence of subexpressions:

>>> expr = f(a, b, a, c)
>>> expr[(1, ):(2, )]
[Symbol('b'), Symbol('a')]

Parameters:	position – The position as a tuple. See `preorder_iter()` for its format. Alternatively, a range of positions can be passed using the slice notation.
Returns:	The subexpression at the given position(s).
Raises:	`IndexError` – If the position is invalid, i.e. it refers to a non-existing subexpression.

__init__(variable_name)¶: Initialize self. See help(type(self)) for accurate signature.

collect_symbols(symbols: multiset.Multiset) → None¶

Recursively adds all symbols occuring in the expression to the given multiset.

This is used internally by symbols. Needs to be overwritten by inheriting expression classes that can contain symbols. This method can be used when gathering the symbols of multiple expressions, because only one multiset needs to be created and that is more efficient.

Parameters:	symbols – Multiset of symbols. All symbols contained in the expression are recursively added to this multiset.

collect_variables(variables: multiset.Multiset) → None¶

Recursively adds all variables occuring in the expression to the given multiset.

This is used internally by variables. Needs to be overwritten by inheriting container expression classes. This method can be used when gathering the variables of multiple expressions, because only one multiset needs to be created and that is more efficient.

Parameters:	variables – Multiset of variables. All variables contained in the expression are recursively added to this multiset.

is_constant¶: True, iff the expression does not contain any wildcards.

is_syntactic¶: True, iff the expression does not contain any associative or commutative operations or sequence wildcards.

preorder_iter(predicate: Optional[Callable[Expression, bool]] = None) → Iterator[Tuple[matchpy.expressions.expressions.Expression, Tuple[int, ...]]]¶

Iterates over all subexpressions that match the (optional) predicate.

Parameters:

predicate – A predicate to filter what expressions are yielded. It gets the expression and if it returns True, the expression is yielded.

Yields:

Every subexpression along with a position tuple. Each item in the tuple is the position of an operation operand:

() is the position of the root element

(0, ) that of its first operand

(0, 1) the position of the second operand of the root’s first operand.

etc.

A variable’s expression always has the position 0 relative to the variable, i.e. if the root is a variable, then its expression has the position (0, ).

symbols¶: A multiset of the symbol names occurring in the expression.

variables¶: A multiset of the variables occurring in the expression.

with_renamed_vars(renaming) → matchpy.expressions.expressions.Expression¶: Return a copy of the expression with renamed variables.

class Arity¶

Bases: matchpy.expressions.expressions._ArityBase

Arity of an operator as (int, bool) tuple.

The first component is the minimum number of operands. If the second component is True, the operator has fixed width arity. In that case, the first component describes the fixed number of operands required. If it is False, the operator has variable width arity.

binary = Arity(min_count=2, fixed_size=True)¶

nullary = Arity(min_count=0, fixed_size=True)¶

polyadic = Arity(min_count=2, fixed_size=False)¶

ternary = Arity(min_count=3, fixed_size=True)¶

unary = Arity(min_count=1, fixed_size=True)¶

variadic = Arity(min_count=0, fixed_size=False)¶

class Atom(variable_name)¶

Bases: matchpy.expressions.expressions.Expression

Base for all atomic expressions.

class Symbol(name: str, variable_name=None)¶

Bases: matchpy.expressions.expressions.Atom

An atomic constant expression term.

It is uniquely identified by its name.

name¶

The symbol’s name.

Type:	str

__init__(name: str, variable_name=None) → None¶

Parameters:	name – The name of the symbol that uniquely identifies it.

collect_symbols(symbols)¶

Recursively adds all symbols occuring in the expression to the given multiset.

This is used internally by symbols. Needs to be overwritten by inheriting expression classes that can contain symbols. This method can be used when gathering the symbols of multiple expressions, because only one multiset needs to be created and that is more efficient.

Parameters:	symbols – Multiset of symbols. All symbols contained in the expression are recursively added to this multiset.

with_renamed_vars(renaming) → matchpy.expressions.expressions.Symbol¶: Return a copy of the expression with renamed variables.

class Wildcard(min_count: int, fixed_size: bool, variable_name=None, optional=None)¶

Bases: matchpy.expressions.expressions.Atom

A wildcard that matches any expression.

The wildcard will match any number of expressions between min_count and fixed_size. Optionally, the wildcard can also be constrained to only match expressions satisfying a predicate.

min_count¶

The minimum number of expressions this wildcard will match.

Type:	int

fixed_size¶

If True, the wildcard matches exactly min_count expressions. If False, the wildcard is a sequence wildcard and can match min_count or more expressions.

Type:	bool

__init__(min_count: int, fixed_size: bool, variable_name=None, optional=None) → None¶

Parameters:	min_count – The minimum number of expressions this wildcard will match. Must be a non-negative number. fixed_size – If `True`, the wildcard matches exactly min_count expressions. If `False`, the wildcard is a sequence wildcard and can match min_count or more expressions.
Raises:	`ValueError` – if min_count is negative or when trying to create a fixed zero-length wildcard.

static dot(name=None) → matchpy.expressions.expressions.Wildcard¶

Create a Wildcard that matches a single argument.

Parameters:	name – An optional name for the wildcard.
Returns:	A dot wildcard.

head = None¶

static optional(name, default) → matchpy.expressions.expressions.Wildcard¶

Create a Wildcard that matches a single argument with a default value.

If the wildcard does not match, the substitution will contain the default value instead.

Parameters:	name – The name for the wildcard. default – The default value of the wildcard.
Returns:	A n optional wildcard.

static plus(name=None) → matchpy.expressions.expressions.Wildcard¶

Creates a Wildcard that matches at least one and up to any number of arguments

Parameters:	name – Optional variable name for the wildcard.
Returns:	A plus wildcard.

static star(name=None) → matchpy.expressions.expressions.Wildcard¶

Creates a Wildcard that matches any number of arguments.

Parameters:	name – Optional variable name for the wildcard.
Returns:	A star wildcard.

static symbol(name: str = None, symbol_type: Type[matchpy.expressions.expressions.Symbol] = <class 'matchpy.expressions.expressions.Symbol'>) → matchpy.expressions.expressions.SymbolWildcard¶

Create a SymbolWildcard that matches a single Symbol argument.

Parameters:	name – Optional variable name for the wildcard. symbol_type – An optional subclass of `Symbol` to further limit which kind of symbols are matched by the wildcard.
Returns:	A `SymbolWildcard` that matches the symbol_type.

with_renamed_vars(renaming) → matchpy.expressions.expressions.Wildcard¶: Return a copy of the expression with renamed variables.

class Operation(operands: List[matchpy.expressions.expressions.Expression], variable_name=None)¶

Bases: matchpy.expressions.expressions.Expression

Base class for all operations.

Do not instantiate this class directly, but create a subclass for every operation in your domain. You can use new() as a shortcut for doing so.

__getitem__(key: Union[Tuple[int, ...], slice]) → matchpy.expressions.expressions.Expression¶

Return the subexpression at the given position(s).

It is also possible to use a slice notation to extract a sequence of subexpressions:

>>> expr = f(a, b, a, c)
>>> expr[(1, ):(2, )]
[Symbol('b'), Symbol('a')]

Parameters:	position – The position as a tuple. See `preorder_iter()` for its format. Alternatively, a range of positions can be passed using the slice notation.
Returns:	The subexpression at the given position(s).
Raises:	`IndexError` – If the position is invalid, i.e. it refers to a non-existing subexpression.

__init__(operands: List[matchpy.expressions.expressions.Expression], variable_name=None) → None¶

Create an operation expression.

Parameters:	*operands – The operands for the operation expression.
Raises:	`ValueError` – if the operand count does not match the operation’s arity. `ValueError` – if the operation contains conflicting variables, i.e. variables with the same name that match different things. A common example would be mixing sequence and fixed variables with the same name in one expression.

arity = Arity(min_count=0, fixed_size=False)¶

The arity of the operator.

Trying to construct an operation expression with a number of operands that does not fit its operation’s arity will result in an error.

Type:	Arity

associative = False¶

True if the operation is associative, i.e. f(a, f(b, c)) = f(f(a, b), c).

This attribute is used to flatten nested associative operations of the same type. Therefore, the arity of an associative operation has to have an unconstrained maximum number of operand.

Type:	bool

collect_symbols(symbols) → None¶

Recursively adds all symbols occuring in the expression to the given multiset.

This is used internally by symbols. Needs to be overwritten by inheriting expression classes that can contain symbols. This method can be used when gathering the symbols of multiple expressions, because only one multiset needs to be created and that is more efficient.

Parameters:	symbols – Multiset of symbols. All symbols contained in the expression are recursively added to this multiset.

collect_variables(variables) → None¶

Recursively adds all variables occuring in the expression to the given multiset.

This is used internally by variables. Needs to be overwritten by inheriting container expression classes. This method can be used when gathering the variables of multiple expressions, because only one multiset needs to be created and that is more efficient.

Parameters:	variables – Multiset of variables. All variables contained in the expression are recursively added to this multiset.

commutative = False¶

True if the operation is commutative, i.e. f(a, b) = f(b, a).

Note that commutative operations will always be converted into canonical form with sorted operands.

Type:	bool

head¶: alias of Operation

infix = False¶

True if the name of the operation should be used as an infix operator by str().

Type:	bool

name = None¶

Name or symbol for the operator.

This needs to be overridden in the subclass.

Type:	str

static new(name: str, arity: matchpy.expressions.expressions.Arity, class_name: str = None, *, associative: bool = False, commutative: bool = False, one_identity: bool = False, infix: bool = False) → Type[matchpy.expressions.expressions.Operation]¶

Utility method to create a new operation type.

Example:

>>> Times = Operation.new('*', Arity.polyadic, 'Times', associative=True, commutative=True, one_identity=True)
>>> Times
Times['*', Arity(min_count=2, fixed_size=False), associative, commutative, one_identity]
>>> str(Times(Symbol('a'), Symbol('b')))
'*(a, b)'

Keyword Arguments:
Parameters:	name – Name or symbol for the operator. Will be used as name for the new class if `class_name` is not specified. arity – The arity of the operator as explained in the documentation of `Operation`. class_name – Name for the new operation class to be used instead of name. This argument is required if `name` is not a valid python identifier.
	associative – See `associative`. commutative – See `commutative`. one_identity – See `one_identity`. infix – See `infix`.
Raises:	`ValueError` – if the class name of the operation is not a valid class identifier.

one_identity = False¶

True if the operation with a single argument is equivalent to the identity function.

This property is used to simplify expressions, e.g. for f with f.one_identity = True the expression f(a) if simplified to a.

Type:	bool

unpacked_args_to_init = False¶

True if the class must be instantiated with *operands instead of operands.

Type:	bool

with_renamed_vars(renaming) → matchpy.expressions.expressions.Operation¶: Return a copy of the expression with renamed variables.

class SymbolWildcard(symbol_type: Type[matchpy.expressions.expressions.Symbol] = <class 'matchpy.expressions.expressions.Symbol'>, variable_name=None)¶

Bases: matchpy.expressions.expressions.Wildcard

A special Wildcard that matches a Symbol.

symbol_type¶: A subclass of Symbol to constrain what the wildcard matches. If not specified, the wildcard will match any Symbol.

__init__(symbol_type: Type[matchpy.expressions.expressions.Symbol] = <class 'matchpy.expressions.expressions.Symbol'>, variable_name=None) → None¶

Parameters:	symbol_type – A subclass of `Symbol` to constrain what the wildcard matches. If not specified, the wildcard will match any `Symbol`.
Raises:	`TypeError` – if symbol_type is not a subclass of `Symbol`.

with_renamed_vars(renaming) → matchpy.expressions.expressions.SymbolWildcard¶: Return a copy of the expression with renamed variables.

class Pattern(expression, *constraints)¶

Bases: object

A pattern is a term that can be matched against another subject term.

A pattern can contain variables and can optionally have constraints attached to it. Those constraints a predicates which limit what the pattern can match.

__init__(expression, *constraints) → None¶

Parameters:	expression – The term that forms the pattern. *constraints – Optional constraints for the pattern.

global_constraints¶

The subset of the pattern constraints which are global.

A global constraint does not define dependency variables and can only be evaluated, once the match has been completed.

is_syntactic¶: True, iff the pattern is syntactic.

local_constraints¶

The subset of the pattern constraints which are local.

A local constraint has a defined non-empty set of dependency variables. These constraints can be evaluated once their dependency variables have a substitution.

make_dot_variable(name)¶

Create a new variable with the given name that matches a single term.

Parameters:	name – The name of the variable
Returns:	The new dot variable.

make_plus_variable(name)¶

Create a new variable with the given name that matches any number of terms.

Only matches sequences with at least one argument.

Parameters:	name – The name of the variable
Returns:	The new plus variable.

make_star_variable(name)¶

Create a new variable with the given name that matches any number of terms.

Can also match an empty argument sequence.

Parameters:	name – The name of the variable
Returns:	The new star variable.

make_symbol_variable(name, symbol_type=<class 'matchpy.expressions.expressions.Symbol'>)¶

Create a new variable with the given name that matches a single symbol.

Optionally, a symbol type can be specified to further limit what the variable can match.

Parameters:	name – The name of the variable symbol_type – The symbol type must be a subclass of `Symbol`. Defaults to `Symbol` itself.
Returns:	The new symbol variable.

class AssociativeOperation¶: Bases: object

class CommutativeOperation¶: Bases: object

class OneIdentityOperation¶: Bases: object