AI Glossary / Graphs and symbolic AI / Intermediate

Occur check

Definition

An occur check, more commonly called an occurs check, tests whether a variable appears inside a term before binding that variable to the term during unification. In finite first-order term unification, it prevents a binding that would make a term contain itself. It is a structural check, not a search for repeated words in ordinary text.

What it means

Unification tries to make symbolic expressions identical by finding compatible substitutions for their variables. For example, shipment(X) and shipment(box7) can match by assigning box7 to X. The expressions have the same outer structure and can share the same argument.

Trouble arises if matching would require X to equal container(X). Any finite substitution for X would have to equal a version of itself with another surrounding container. The occurs check identifies this self-containment problem. It does not reject ordinary identity: matching X with the very same X requires no new binding and is valid.

How it works

A unification procedure compares the structures of the terms, decomposes matching compound terms into argument pairs, and maintains variable bindings. Before connecting an unbound variable to a compound term, it checks the term for that variable, taking existing bindings into account.

Checking only the original spelling is insufficient. If X already shares a value with Y, binding Y to wrapper(X) would also create a cycle. The check must follow the relevant variable relationships rather than treating X and Y as unrelated labels.

Some logic-programming implementations support cyclic structures, often represented as rational trees, and do not use finite-term unification by default. That is a different choice of term semantics. SWI-Prolog provides explicit checked unification, but its documented check prevents newly created cycles rather than guaranteeing that input structures were already acyclic. Programs requiring acyclic inputs need to validate that property separately.

Three practical examples

• Symbolic rule matching: reject an attempted substitution that makes a finite rule argument contain itself.
• Expression processing: distinguish a valid repeated variable from an impossible finite recursive binding when matching expression trees.
• Logic-system integration: check whether a component expecting ordinary finite terms can accept structures returned by a component supporting cycles.

Think of it this way

Think of defining a box's contents using a packing list. A finite nested-box description cannot require the same box to contain itself through another layer of packaging.

The analogy is limited because computer systems can represent a reference pointing back to an earlier object. Such a cyclic graph is perfectly representable; the question is whether that structure belongs to the term language the reasoning procedure is supposed to use.

Worked example

Try unifying pair(X,X) with pair(Y,wrap(Y)), assuming finite first-order terms. The outer pair symbols and their two-argument structures agree, so compare their corresponding arguments.

The first comparison requires X=Y. The second requires X=wrap(Y). Applying the first relationship to the second gives Y=wrap(Y). The variable Y occurs within wrap(Y), so the occurs check rejects the proposed binding. There is no finite-term unifier.

Now compare pair(X,Z) with pair(wrap(a),a), where a is a constant. Assigning X=wrap(a) and Z=a makes both expressions pair(wrap(a),a). Neither assignment creates self-containment, so this pair has a valid unifier.

Finally, pair(X,X) and pair(a,a) also unify, using X=a. Repetition of X is not itself an error. It imposes a consistency requirement on both positions. These are symbolic hand derivations, not reported results from running a Prolog interpreter. The examples separate three issues: matching structure, consistent substitution, and avoiding cyclic bindings.

Illustrative case study

Fictional case: a team connects a symbolic configuration assistant to a service that stores ordinary nested expressions. An unusual rule match produces a self-referential structure that the receiving service cannot serialize in its expected tree format.

The team documents that its interface accepts finite acyclic terms, validates incoming structures, and uses an appropriate unification operation when creating new bindings. It adds tests for indirect cycles and harmless repeated variables. This fictional case illustrates agreement about representation semantics; it does not imply that cyclic terms are universally defective or that one check solves every integration problem.

Common misconceptions and mistakes

The occurs check is not a general proof that a program terminates. A rule system can loop for many other reasons even when every individual term is finite.

Nor does it prohibit recursion in rules. A recursive procedure can process finite structures without ever binding a variable to a term containing itself. Recursive control flow and cyclic data are separate concerns.

Do not assume that every language or every unification operator makes the same choice. Also distinguish preventing a new cycle from detecting cycles already present in an argument. Interface requirements should specify which property is needed.

Business use

For businesses using logic-based configuration, rule engines, or symbolic assistants, the practical value is avoiding mismatches between the mathematical assumptions of reasoning and the structures software actually accepts.

Engineering reviews can ask whether the application expects finite terms, whether external data may contain cycles, and whether printing, copying, storage, and downstream processing support those cycles. Performance decisions about checks should follow the chosen semantics and measured workload. Omitting a check is not evidence that the application can never encounter a problematic binding.

People also ask

Does X=X fail an occurs check?

No. Identity does not require constructing a self-containing replacement term.

Does a repeated variable always cause failure?

No. pair(X,X) matches pair(a,a), but cannot match pair(a,b) when a and b are distinct constants.

Can a computer store a cyclic term?

Yes. Some systems support finite graph representations of cyclic terms; that differs from requiring finite tree-shaped terms.

Check your understanding

After X=Y, why is Y=wrap(X) problematic for finite terms?

Answer: Substituting the existing relationship gives Y=wrap(Y), which requires the same term to contain itself.

Related terms

• Unification
• First-order logic
• Term
• substitution
• variable binding
• rational tree
• cyclic structure
• logic programming

Learn next

Draw the two pair expressions in the worked example as trees and track each substitution. Then study how your chosen logic system handles existing cyclic inputs, rather than inferring that behavior from the name of its unification operation.

• Unification

More in Graphs and symbolic AI

• Null-move heuristic - The null-move heuristic is a selective game-search technique that tests a position by hypothetically passing the current player's turn and searching the...
• Occupancy grid - An occupancy grid is a spatial map divided into cells, with each cell storing an estimate of whether that part of the environment is occupied.
• Occupied space - Occupied space is the region physically taken up by a robot, obstacle, or other object.
• Ockham's razor - Ockham's razor, also spelled Occam's razor, is a preference for avoiding unnecessary complexity when choosing among explanations or models.
• Offline inference - Offline inference is the use of a trained machine-learning model to generate predictions in advance, usually for a collection of known inputs, and store...
• Offline search - Offline search is a problem-solving approach in which an agent computes a solution using a model before executing the corresponding actions in the environment.

Sources

SWI-Prolog reference, unify_with_occurs_check/2: https://www.swi-prolog.org/pldoc/man?predicate=unify_with_occurs_check/2 — checked unification and the important existing-cycle qualification.

Blackburn, Bos, and Striegnitz, Learn Prolog Now!, Unification: https://lpn.swi-prolog.org/lpnpage.php?pageid=lpn-htmlse5&pagetype=html — introductory unification and occurs-check discussion. The supplied heading is retained; examples are original.

Previous: Occupied space Next: Ockham's razor