10.1 Rules of matching

The rules of matching are actually quite simple, though it takes some work to get used to understanding how matching works. On this page, we will list the rules, and on three subsequent pages, we will give three examples of how the rules are used in practice.

The rules of matching are as follows:

Rule 1: Constants

Two constants (string constants, numeric constants, and atomic constants) match if they are the same.

For example, "abc" matches "abc", 12 matches 12, and Lisa matches Lisa.

However, "12" does not match 12, since they are two different kinds of constants (a string constant and a numeric constant). Likewise, "Lisa" does not match with Lisa (a string constant and an atomic constant).

Rule 2: Structures

Two structures match if:

  1. The two functors are the same, and
  2. Their arities are the same, and
  3. All of the arguments match, from left to right.

    It is important that the matching occurs left to right because variables can occur more than once in a structure. If a variable binding occurs at an occurrence to the left in the structure, then the same binding will be used later in the structure.

Rule 3: Variables

Variable binding

When a variable is matched, a variable binding occurs. Thus there is a side-effect to the matching: Not only does the matching occur, but the variable in question is bound to a value (or another variable).

Free variables

A free variable A matches:

  1. Any structure or constant. A is bound to the value of the structure or constant.

    However, A only matches a structure B if A is not also a part of B. For example, X does not match foo(X).

  2. Another variable B. The two variables are bound to each other (this is called "sharing").

    If B is already bound, A is bound to the same value as B.

    If B is a free variable, then A also remains free. However, if either A or B is later bound to a value, then both are bound to the same value, since they are bound to each other.

Bound variables

A bound variable A matches another term B if the term that A is bound to matches the term B. For example, if A has the following variable binding:

{A = name(Nick)}

then A matches the structure


A also matches the following structure:


provided B is a free variable (see above). In this case, B is bound to Nick.


That was a lot of detail in a very short stretch of space. On the following three pages, we will look at three examples explaining the three rules. However, we will not do this so that the first example explains the first rule, the second example explains the second rule, etc. We will not do this. Instead, we will give three examples that will hopefully enable you to understand all of the three rules of matching.

PrevLite: 10 Matching
NextLite: 10.2 Example I

Prev: 10 Matching
Up: 10 Matching
Next: 10.2 Example I