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)'
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.
Keyword Arguments:
 
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
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