Pattern matching and evaluation.

This module implements the matcher used by rewrite rules together with the main expression evaluator.

Pattern Matching

The pattern matching algorithm implemented here is described in:

• https://www.sciencedirect.com/science/article/pii/S0747717121000079
• PDF: https://www3.risc.jku.at/publications/download/risc_6260/variadic-equational-matching-jsc-final-with-mma-versions.pdf

Specifically, Howl implements algorithm M_{Mma}, which is an incomplete, strict variant of the algorithm described in that paper.

Evaluation

The Wolfram Language evaluation sequence is described here: https://reference.wolfram.com/language/tutorial/Evaluation.html

The list below summarizes the intended evaluation order together with the current Howl status.

• If the expression is a raw object such as Integer or String, leave it unchanged. Howl: done.
• Evaluate the head h of the expression. Howl: done.
• Evaluate each element e_i of the expression in turn. If h is a symbol with attributes HoldFirst, HoldRest, HoldAll, or HoldAllComplete, then skip evaluation of certain elements. Howl: HoldAllComplete not implemented.
• Unless h has attributes SequenceHold or HoldAllComplete, flatten out all Sequence objects that appear among the e_i. Howl: SequenceHold and HoldAllComplete not implemented.
• Unless h has attribute HoldAllComplete, strip the outermost Unevaluated wrappers that appear among the e_i. Howl: not implemented.
• If h has attribute Flat, flatten out all nested expressions with head h. Howl: done.
• If h has attribute Listable, thread through any e_i that are lists. Howl: Listable not implemented.
• If h has attribute Orderless, sort the e_i. Howl: done.
• Unless h has attribute HoldAllComplete, use any user-defined upvalues of symbols f appearing in expressions of the form h[f[e1,...], ...]. Howl does not look for upvalues inside the head. For example, the following is not supported:

g /: f[g[x_]][1] := foo;

because g appears inside the head of the expression rather than in the top-level argument sequence.

• Use any builtin upvalues. Howl lets the user choose the ordering and gives no special privilege to builtin versus user-defined upvalues.
• Use any user-defined downvalues associated to h in expressions of the form h[...] or h[...][...], including repeated curried application such as h[...][...][...]. Wolfram Language distinguishes between downvalues and subvalues; Howl currently does not and instead associates downvalues to the root symbol.
• Use any builtin transformation rules for h[...] or h[...][...]. Howl again does not distinguish between builtin and user-defined downvalues.

Conceptually, we would like to try every rule in the Context when evaluating expressions. In practice this would perform poorly for large contexts, so the upvalue/downvalue machinery serves as a set of heuristics for pre-selecting rules that may have a chance of matching.