Pattern-Matching Algorithm Description

The pattern matching algorithm can be roughly recursively defined as follows:¹¹

    // match (pattern, expression) -> bool
    match (v , E) = true    a pattern-matching-variable matches any expression
    match (E , E) = true    two identical expressions match
    match ((op P1, P2), (op E1 E2)) = true 
          if match(P1, E1) and match(P2, E2), false otherwise
    match (P, E) = false

In other words, a pattern P matches an expression E if we can replace the free variables v1, v2, ... in P with subexpressions E1, E2, ... from E to make it identical to E. That is, P matches E if there exist E1, E2, ... such that P[v1=E1, v2=E2, ...] == E.