occurscheck

OccursCheck is a guard used in unification algorithms, primarily in logic programming and type inference. It ensures that a logic variable does not become bound to a term that already contains that variable, preventing the creation of cyclic or infinite structures. In practice, during unification, when a variable X is to be bound to a term T, the algorithm may check whether X occurs inside T. If it does, the unification fails.

In logic programming languages such as Prolog, the occurs check helps preserve well-founded terms. If the check is performed and X occurs in T, the binding is rejected, avoiding the construction of self-referential terms. If the check is omitted, unification can produce cyclic or infinite structures, such as a binding X = f(X). Such cyclic terms may lead to non-terminating computations or unusual representations.

In type inference and type checking, the occurs check prevents recursive or infinite types, for example attempting to unify a type variable a with List a. With the occurs check, such unifications fail, preserving soundness. Some language implementations omit the check to improve performance, which can lead to the possibility of infinite or otherwise problematic types in edge cases. The trade-off is between faster unification and guaranteed safety against cyclicities.

Overall, the occurs check is a classic component of unification theory. Its use and omission vary by language and implementation, reflecting different priorities between efficiency and guarantees of terminating, well-defined terms.