occurs check

O o

Transcription

- US Pronunciation
- US IPA

- US Pronunciation
- US IPA

Definition of occurs check words

noun Technical meaning of occurs check (programming) A feature of some implementations of unification which causes unification of a logic variable V and a structure S to fail if S contains V. Binding a variable to a structure containing that variable results in a cyclic structure which may subsequently cause unification to loop forever. Some implementations use extra pointer comparisons to avoid this. Most implementations of Prolog do not perform the occurs check for reasons of efficiency. Without occurs check the complexity of unification is O(min(size(term1), size(term2))) with occurs check it's O(max(size(term1), size(term2))) In theorem proving unification without the occurs check can lead to unsound inference. For example, in Prolog it is quite valid to write X = f(X). which will succeed, binding X to a cyclic structure. Clearly however, if f is taken to stand for a function rather than a constructor, then the above equality is only valid if f is the identity function. Weijland calls unification without occur check, "complete unification". The reference below describes a complete unification algorithm in terms of Colmerauer's consistency algorithm. 1

Just one definition for occurs check

Information block about the term

Parts of speech for Occurs check

noun

adjective

verb

adverb

pronoun

preposition

conjunction

determiner

exclamation

Full grammatical hierarchy of Occurs check

See also

All definitions of occurs check

Was this page helpful?

Yes No

Thank you for your feedback! Tell your friends about this page

Tell us why?