Wolfram Research, Inc.
A.9.3 Basic System Features
Mathematica is fundamentally an interpreter which scans through expressions calling internal code pointed to by the symbol table entries of heads that it encounters.
Any transformation rule—whether given as x -> y or in a definition—is automatically compiled into a form which allows for rapid pattern matching. Many different types of patterns are distinguished and are handled by special code.
A form of hashing that takes account of blanks and other features of patterns is used in pattern matching.
The internal code associated with pattern matching is approximately 250 pages long.
When a large number of definitions are given for a particular symbol, a hash table is automatically built using a version of Dispatch so that appropriate rules can quickly be found.