The pattern matching algorithm can be roughly recursively defined as follows:11
// 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) = falseIn 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.