21 Term Utilities

This package defines operations on terms for subsumption checking, “anti-unification”, testing acyclicity, and getting the variables.

Please note: anti-unification is a purely syntactic operation; any attributes attached to the variables are ignored.

To load the package, enter the query

     | ?- use_module(library(terms)).

subsumes_chk(?General, ?Specific)

Provided General and Specific have no variables in common, Specific is an instance of General, i.e. if there is a substitution that leaves Specific unchanged and makes General identical to Specific. It doesn't bind any variables.

          | ?- subsumes_chk(f(X), f(a)).
          
          true
          
          | ?- subsumes_chk(f(a), f(X)).
          
          no
          
          | ?- subsumes_chk(A-A, B-C).
          
          no
          
          | ?- subsumes_chk(A-B, C-C).
          
          true
     

subsumes(?General, ?Specific)

Provided General and Specific have no variables in common, Specific is an instance of General. It will bind variables in General (but not those in Specific) so that General becomes identical to Specific.

variant(?Term, ?Variant)

Term and Variant are identical modulo renaming of variables, provided Term and Variant have no variables in common.

term_subsumer(?Term1, ?Term2, ?General)

General is the most specific term that generalizes Term1 and Term2. This process is sometimes called anti-unification, as it is the dual of unification.

          | ?- term_subsumer(f(g(1,h(_))), f(g(_,h(1))), T).
          
          T = f(g(_B,h(_A)))
          
          | ?- term_subsumer(f(1+2,2+1), f(3+4,4+3), T).
          
          T = f(_A+_B,_B+_A)
     

term_hash(?Term, ?Hash)

term_hash(?Term, +Depth, +Range, ?Hash)

If Term is instantiated up to the given Depth, an integer hash value in the range [0,Range) as a function of Term is unified with Hash. Otherwise, the goal just succeeds, leaving Hash uninstantiated.

If Term contains floats or integers outside the small integer range, the hash value will be platform dependent. Otherwise, the hash value will be identical across runs and platforms.

The depth of a term is defined as follows: the (principal functor of) the term itself has depth 1, and an argument of a term with depth i has depth i+1.

Depth should be an integer >= -1. If Depth = -1 (the default), Term must be ground, and all subterms of Term are relevant in computing Hash. Otherwise, only the subterms up to depth Depth of Term are used in the computation.

Range should be an integer >= 1. The default will give hash values in a range appropriate for all platforms.

          | ?- term_hash([a,b,_], 3, 4, H).
          
          H = 2
          
          | ?- term_hash([a,b,_], 4, 4, H).
          
          true
          
          | ?- term_hash(f(a,f(b,f(_,[]))), 2, 4, H).
          
          H = 2
     

term_hash/[2,4] is provided primarily as a tool for the construction of sophisticated Prolog clause access schemes. Its intended use is to generate hash values for terms that will be used with first argument clause indexing, yielding compact and efficient multi-argument or deep argument indexing.

term_variables(?Term, ?Variables)

Variables is the set of variables occurring in Term.

term_variables_bag(?Term, ?Variables)

Variables is the list of variables occurring in Term, in first occurrence order. Each variable occurs once only in the list.

acyclic_term(?X)

True if X is finite (acyclic). Runs in linear time.

cyclic_term(?X)

True if X is infinite (cyclic). Runs in linear time.