Pattern Matching in Evaluation

Pattern matching is used in evaluation of Mathics Expression and therefore in Function resolution. Because this process is both time consuming and involved, it is important to understand how it works. We describe some of this process here.

Based on the Head of a Mathics Expression, the rules stored the Definitions object for Head are examined for matches. When a rule matches an expression, the rule specifies how sub-expressions get bound to names, and how the expression is transformed. After this happens, the evaluation process is repeated using the replaced expression.

The process repeats until the expression converges and there are no further changes.

The power of the WL then relies in the possibility of defining rules by patterns that can match with many different expressions, and building new expressions based on the variable part of the pattern.

Pattern Classes

We now describe the Class hierarchy for Pattern which is defined in mathics.core.pattern. This is the base class that represents the pattern for an expression.

Two of its subclasses are:

  • AtomPattern patterns that match with a given atomic expression, and

  • ExpressionPattern patterns matches with non-atomic expressions (i.e., expressions with a head and leaves).

There are also have several Builtin symbols (defined in mathics.builtin.patterns) that represent different pattern constructions like Pattern_, Blank, PatternTest or Alternatives. All of these Builtin classes are derived from the PatternObject class, which is derived from InstanceableBuiltin and Pattern.

Every Pattern object has three important methods: does_match(), get_match_candidates(), and match():

  • does_match() checks if certain expression matches the pattern

  • get_match_candidates() finds all the potential matches

  • match() performs what needs to be done when there is a match

The last method, match(), is the most involved. It has the following function signature:

match(yield_func, expression,
      vars,
      evaluation,
      head=None,
      leaf_index=None,
      leaf_count=None,
      fully=True,
      wrap_oneid=True
      )

When called, this method binds subexpressions of the expression to parts of the pattern. For each match, yield_func(vars, rest) is called with vars as a first parameter, and the second parameter depends on the specific context.