qnet.algebra.pattern_matching module

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

Classes:

MatchDict Dictionary of wildcard names to expressions.
Pattern Pattern for matching an expression
ProtoExpr Object representing an un-instantiated Expression that may matched by a

Functions:

match_pattern Recursively match expr with the given expr_or_pattern, which is either a direct expression (equal to expr for a successful match), or an instance of Pattern.
pattern ‘Flat’ constructor for the Pattern class, where positional and keyword
pattern_head Helper function to create a Pattern object specfically matching a ProtoExpr.
wc Helper function to create a Pattern object with an emphasis on wildcard

__all__: MatchDict, Pattern, match_pattern, pattern, pattern_head, wc

Reference

class qnet.algebra.pattern_matching.MatchDict(*args)[source]

Bases: collections.OrderedDict

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 do 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 matching 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)[source]

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)[source]

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 os 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:

>>> from qnet.algebra.circuit_algebra import *
>>> C1 = CircuitSymbol('C1', 3)
>>> C2 = CircuitSymbol('C2', 3)
>>> C3 = CircuitSymbol('C3', 3)
>>> C4 = CircuitSymbol('C4', 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.name[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()[source]

Return an iterator over patterns for positional arguments to be matched. This yields the elements of args, extended by their mode value

match(expr) → qnet.algebra.pattern_matching.MatchDict[source]

Match the given expression (recursively) and return 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 evalute to True in a boolean context. If the match is not successful, it will evaluate as False, and the reason for failure is stored in the reason attribute of the MatchDict object.

findall(expr)[source]

Return a list of all matching (sub-)expressions in expr

qnet.algebra.pattern_matching.pattern(head, *args, mode=1, wc_name=None, conditions=None, **kwargs) → qnet.algebra.pattern_matching.Pattern[source]

‘Flat’ constructor for the Pattern class, where positional and keyword arguments are mapped into args and kwargs, respectively. Useful for defining rules that match an instantiated Expression with specific arguments

qnet.algebra.pattern_matching.pattern_head(*args, conditions=None, wc_name=None, **kwargs) → qnet.algebra.pattern_matching.Pattern[source]

Helper function to create a Pattern object specfically matching a ProtoExpr. The patterns used associated with _rules and _binary_rules of an Expression subclass must be instantiated through this routine. The function does not allow to set a wildcard name (wc_name must not be given / be None)

qnet.algebra.pattern_matching.wc(name_mode='_', head=None, args=None, kwargs=None, *, conditions=None) → qnet.algebra.pattern_matching.Pattern[source]

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, ...)
class qnet.algebra.pattern_matching.ProtoExpr(args, kwargs, cls=None)[source]

Bases: collections.abc.Sequence

Object representing an un-instantiated Expression that may matched by a Pattern created via pattern_head()

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

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.
instantiate(cls=None)[source]

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

Parameters:
  • cls (class) – The class of the instatiated expression. If not given,
  • will be used. (self.cls) –
classmethod from_expr(expr)[source]

Instantiate proto-expression from the given Expression

qnet.algebra.pattern_matching.match_pattern(expr_or_pattern: object, expr: object) → qnet.algebra.pattern_matching.MatchDict[source]

Recursively match expr with the given expr_or_pattern, which is either a direct expression (equal to expr for a successful match), or an instance of Pattern.