Occurs check

The Occurs check referred to in the computer science part of the unification algorithm. It prevents that a variable is replaced with a term which includes the variable. He finds application, for example, in the type test in functional programming languages ​​in order to prevent the construction of infinite data types, as well as in logic programming languages.

Example

In the following example were, and variables, and a 2- ary function symbol. The variable and the term should be unified. Due to the Occurs checks the unification fails because occurs in a variable. The unification of with would, however successful.

Prologue

In the language of the prologue of an occur check in the verification of rule definitions for performance reasons is normally turned off, which poses the risk of an endless loop in the evaluation in itself. In some implementations of Prolog, but it can be activated as required.

The complexity of unification without the occurs check is in:

And with the occurs check in: