qnet.algebra.pattern_matching package

QNET’s pattern matching engine.

Patterns may be constructed by either instantiating a Pattern instance directly, or (preferred) by calling the pattern(), pattern_head(), or wc() helper routines.

The pattern may then be matched against an expression using match_pattern(). The result of a match is a MatchDict object, which evaluates to True or False in a boolean context to indicate the success or failure of the match (or alternatively, through the success attribute). The MatchDict object also maps any wildcard names to the expression that the corresponding wildcard Pattern matches.

Summary

__all__ Classes:

MatchDict	Result of a Pattern.match()
Pattern	Pattern for matching an expression

Private Classes:

ProtoExpr

Object representing an un-instantiated Expression

__all__ Functions:

match_pattern	Recursively match expr with the given expr_or_pattern
pattern	‘Flat’ constructor for the Pattern class
pattern_head	Constructor for a Pattern matching a ProtoExpr
wc	Constructor for a wildcard-Pattern

Reference

class qnet.algebra.pattern_matching.MatchDict(*args)

Bases: collections.OrderedDict

Result of a Pattern.match()

Dictionary of wildcard names to expressions. Once the value for a key is set, attempting to set it again with a different value raises a KeyError. The attribute merge_lists may be set to modify this behavior for values that are lists: If it is set to a value different from zero, two lists that are set via the same key are merged. If merge_lists is negative, the new values are appended to the existing values; if it is positive, the new values are prepended.

In a boolean context, a MatchDict always evaluates as True (even if empty, unlike a normal dictionary), unless the success attribute is explicitly set to False (which a failed Pattern.match() should do)

Attributes:

• success (bool) – Value of the MatchDict object in a boolean context: bool(match) == match.success
• reason (str) – If success is False, string explaining why the match failed
• merge_lists (int) – Code that indicates how to combine multiple values that are lists

update(*others)

Update dict with entries from other

If other has an attribute success=False and reason, those attributes are copied as well

class qnet.algebra.pattern_matching.Pattern(head=None, args=None, kwargs=None, *, mode=1, wc_name=None, conditions=None)

Bases: object

Pattern for matching an expression

Parameters:

• head (type or None) – The type (or tuple of types) of the expression that can be matched. If None, any type of Expression matches
• args (list or None) – List or tuple of positional arguments of the matched Expression (cf. Expression.args). Each element is an expression (to be matched exactly) or another Pattern instance (matched recursively). If None, no arguments are checked
• kwargs (dict or None) – Dictionary of keyword arguments of the expression (cf. Expression.kwargs). As for args, each value is an expression or Pattern instance.
• mode (int) – If the pattern is used to match the arguments of an expression, code to indicate how many arguments the Pattern can consume: Pattern.single, Pattern.one_or_more, Pattern.zero_or_more
• wc_name (str or None) – If pattern matches an expression, key in the resulting MatchDict for the expression. If None, the match will not be recorded in the result
• conditions (list of callables, or None) – If not None, a list of callables that take expr and return a boolean value. If the return value is False, the pattern is determined not to match expr.

Note

For (sub-)patterns that occur nested in the args attribute of another pattern, only the first or last sub-pattern may have a mode other than Pattern.single. This also implies that only one of the args may have a mode other than Pattern.single. This restrictions ensures that patterns can be matched without backtracking, thus guaranteeing numerical efficiency.

Example

Consider the following nested circuit expression:

>>> C1 = CircuitSymbol('C1', cdim=3)
>>> C2 = CircuitSymbol('C2', cdim=3)
>>> C3 = CircuitSymbol('C3', cdim=3)
>>> C4 = CircuitSymbol('C4', cdim=3)
>>> perm1 = CPermutation((2, 1, 0))
>>> perm2 = CPermutation((0, 2, 1))
>>> concat_expr = Concatenation(
...                   (C1 << C2 << perm1),
...                   (C3 << C4 << perm2))

We may match this with the following pattern:

>>> conditions = [lambda c: c.cdim == 3,
...               lambda c: c.label[0] == 'C']
>>> A__Circuit = wc("A__", head=CircuitSymbol,
...                 conditions=conditions)
>>> C__Circuit = wc("C__", head=CircuitSymbol,
...                 conditions=conditions)
>>> B_CPermutation = wc("B", head=CPermutation)
>>> D_CPermutation = wc("D", head=CPermutation)
>>> pattern_concat = pattern(
...         Concatenation,
...         pattern(SeriesProduct, A__Circuit, B_CPermutation),
...         pattern(SeriesProduct, C__Circuit, D_CPermutation))
>>> m = pattern_concat.match(concat_expr)

The match returns the following dictionary:

>>> result = {'A': [C1, C2], 'B': perm1, 'C': [C3, C4], 'D': perm2}
>>> assert m == result

single = 1

one_or_more = 2

zero_or_more = 3

extended_arg_patterns()

Iterator over patterns for positional arguments to be matched

This yields the elements of args, extended by their mode value

match(expr)

Match the given expression (recursively)

Returns a MatchDict instance that maps any wildcard names to the expressions that the corresponding wildcard pattern matches. For (sub-)pattern that have a mode attribute other than Pattern.single, the wildcard name is mapped to a list of all matched expression.

If the match is successful, the resulting MatchDict instance will evaluate to True in a boolean context. If the match is not successful, it will evaluate as False, and the reason for failure is available in the reason attribute of the MatchDict object.

Return type:MatchDict

findall(expr)

list of all matching (sub-)expressions in expr

See also

finditer() yields the matches (MatchDict instances) for the matched expressions.

finditer(expr)

Return an iterator over all matches in expr

Iterate over all MatchDict results of matches for any matching (sub-)expressions in expr. The order of the matches conforms to the equivalent matched expressions returned by findall().

wc_names

Set of all wildcard names occurring in the pattern

qnet.algebra.pattern_matching.pattern(head, *args, mode=1, wc_name=None, conditions=None, **kwargs)

‘Flat’ constructor for the Pattern class

Positional and keyword arguments are mapped into args and kwargs, respectively. Useful for defining rules that match an instantiated Expression with specific arguments

Return type:Pattern

qnet.algebra.pattern_matching.pattern_head(*args, conditions=None, wc_name=None, **kwargs)

Constructor for a Pattern matching a ProtoExpr

The patterns associated with _rules and _binary_rules of an Expression subclass, or those passed to Expression.add_rule(), must be instantiated through this routine. The function does not allow to set a wildcard name (wc_name must not be given / be None)

Return type:Pattern

qnet.algebra.pattern_matching.wc(name_mode='_', head=None, args=None, kwargs=None, *, conditions=None)

Constructor for a wildcard-Pattern

Helper function to create a Pattern object with an emphasis on wildcard patterns, if we don’t care about the arguments of the matched expressions (otherwise, use pattern())

Parameters:

• name_mode (str) – Combined wc_name and mode for Pattern constructor argument. See below for syntax
• head (type, or None) – See Pattern
• args (list or None) – See Pattern
• kwargs (dict or None) – See Pattern
• conditions (list or None) – See Pattern

The name_mode argument uses trailing underscored to indicate the mode:

• A -> Pattern(wc_name="A", mode=Pattern.single, ...)
• A_ -> Pattern(wc_name="A", mode=Pattern.single, ...)
• B__ -> Pattern(wc_name="B", mode=Pattern.one_or_more, ...)
• B___ -> Pattern(wc_name="C", mode=Pattern.zero_or_more, ...)

Return type:Pattern

class qnet.algebra.pattern_matching.ProtoExpr(args, kwargs, cls=None)

Bases: collections.abc.Sequence

Object representing an un-instantiated Expression

A ProtoExpr may be matched by a Pattern created via pattern_head(). This is used in Expression.create(): before an expression is instantiated, a ProtoExpr is constructed with the positional and keyword arguments passed to create(). Then, this ProtoExpr is matched against all the automatic rules create() knows about.

Parameters:

• args (list) – positional arguments that would be used in the instantiation of the Expression
• kwargs (dict) – keyword arguments. Will we converted to an OrderedDict
• cls (class or None) – The class of the Expression that will ultimately be instantiated.

The combined values of args and kwargs are accessible as a (mutable) sequence.

instantiate(cls=None)

Return an instantiated Expression as cls.create(*self.args, **self.kwargs)

Parameters:

• cls (class) – The class of the instantiated expression. If not
• self.cls will be used. (given,) –

classmethod from_expr(expr)

Instantiate proto-expression from the given Expression

qnet.algebra.pattern_matching.match_pattern(expr_or_pattern, expr)

Recursively match expr with the given expr_or_pattern

Parameters:

• expr_or_pattern (object) – either a direct expression (equal to expr for a successful match), or an instance of Pattern.
• expr (object) – the expression to be matched

Return type:

MatchDict