10.25 Term Utilities—library(terms)

This library module provides miscellaneous operations on terms. Exported predicates:

subsumeschk(+General, +Specific)

is true when Specific is an instance of General. It does not bind any variables.

subsumes(+General, +Specific)

is true when 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)

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

term_subsumer(+Term1, +Term2, -Term)

binds Term to a most specific generalisation of Term1 and Term2. Using Plotkin's algorithm [Machine Intelligence 5, 1970], extended by Dan Sahlin to handle cyclic structures.

term_hash(+Term, -Hash)

Equivalent to term_hash(Term, [], Hash).

term_hash(+Term, +Options, -Hash)

Options is a list of options,

algorithm(Algorithm)

Algorithm specifies which hash function to use. An atom, one of,

default

This is currently the same as jenkins. This is the default. If we ever see a need to change the default hash algorithm again then the algorithm denoted by default may change but the algorithm denoted by the other names, like 'sicstus-4.0.5', will not change.

jenkins

Based on the algorithm “lookup3” by Bob Jenkins, see http://burtleburtle.net/bob/hash/doobs.html.

hsieh

Based on the algorithm “SuperFastHash” by Paul Hsieh, see http://www.azillionmonkeys.com/qed/hash.html. Despite the name neither this nor any other choice of algorithm significantly affects the speed of term_hash/3.

sdbm

Based on the well known algorithm “sdbm”.

'sicstus-4.0.4'

This is the algorithm used up to SICStus Prolog 4.0.4 (inclusive). It is only present to provide backwards compatibility. It is not as good as any of the above algorithms. Note that this atom needs to be quoted.

This algorithm produces hash values that may differ between platforms.

'sicstus-4.0.5'

This is the same as jenkins. I.e. the default since SICStus Prolog 4.0.5. Note that this atom needs to be quoted.

there are some other (not as good) algorithms available for the curious, see the source for detail.

Unless otherwise noted, the hash value will be identical across runs and platforms.

range(Range)

The resulting hash value will be non-negative and less than the upper bound specified by Range. Range should be either a positive integer, or an atom, one of,

infinite

Do not constrain the hash value. Currently all hash algorithms produce an unsigned 32-bit integer. Note that this may be too large to be used for first-argument indexing on 32-bit platforms.

smallint

Ensure the resulting hash value is a small integer, e.g. suitable for first argument indexing. This is the same as specifying a range of 2^28 on 32-bit platforms and 2^60 on 64-bit platforms.

smallint32

Ensure the resulting hash value is in the 32-bit platform range of small integers, i.e. the same as a range of 2^28.

default

The same as smallint32. This is the default. This ensures that, by default, the same hash value is computed for the same term on both 32-bit and 64-bit platforms.

depth(Depth)

Specifies how deep to descend into the term when calculating the hash value. If Depth is a non-negative integer the subterms up to depth Depth of Term are used in the computation. Alternatively, if Depth is the atom infinite, all subterms of Term are relevant in computing Hash. In the latter case Term must be acyclic. In this context 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. Note that this is similar to, but not the same as, the value computed by term_depth/2. For legacy reasons a Depth of -1 is treated the same a infinite.

if_var(IfVar)

Specifies what to do if a variable is encountered in the term (i.e. to the specified depth). IfVar should be an atom, one of,

error

An instantiation error is thrown.

ignore

The variable is ignored and the hash algorithm continues with the other parts of the term.

value(Value)

The hash algorithm stops, the intermediate hash result is discarded and Hash is bound to Value. There is no restrictions on Value, it need not be an integer or even be ground.

default

This is the same as value(_), i.e. term_hash/3 just succeeds without binding Hash. This is the default. This is useful when the hash value us used for first-argument indexing. This ensures that if the (possibly variable-valued) hash values for Term1 and Term2 are Hash1 and Hash2, respectively, then if Term1 and Term2 are unifiable (to the specified depth) then so are Hash1 and Hash2. For other use cases it is probably more appropriate to specify if_var(error).

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

Equivalent to term_hash(Term, [depth(Depth), range(Range)], Hash). term_hash/[2,3,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. Note that, for this usage, it is very important that the hash value is a small integer, as it will be by default.

term_variables(+Term, -Variables)

True if Variables is the set of variables occurring in Term.

term_variables_bag(+Term, -Variables)

True if Variables is the list of variables occurring in Term, in first occurrence order.

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.

term_order(+X, +Y, -R)

is true when X and Y are arbitrary terms, and R is <, =, or > according as X @< Y, X == Y, or X @> Y. This is the same as compare/3, except for the argument order.

contains_term(+Kernel, +Expression)

is true when the given Kernel occurs somewhere in the Expression. It can only be used as a test; to generate sub-terms use sub_term/2.

free_of_term(+Kernel, +Expression)

is true when the given Kernel does not occur anywhere in the Expression. NB: if the Expression contains an unbound variable, this must fail, as the Kernel might occur there. Since there are infinitely many Kernels not contained in any Expression, and also infinitely many Expressions not containing any Kernel, it doesn't make sense to use this except as a test.

occurrences_of_term(+Kernel, +Expression, -Tally)

is true when the given Kernel occurs exactly Tally times in Expression. It can only be used to calculate or test Tally; to enumerate Kernels you'll have to use sub_term/2 and then test them with this routine. If you just want to find out whether Kernel occurs in Expression or not, use contains_term/2 or free_of_term/2.

contains_var(+Variable, +Term)

is true when the given Term contains at least one sub-term which is identical to the given Variable. We use == to check for the variable (contains_term/2 uses =) so it can be used to check for arbitrary terms, not just variables.

free_of_var(+Variable, +Term)

is true when the given Term contains no sub-term identical to the given Variable (which may actually be any term, not just a var). For variables, this is precisely the "occurs check" which is needed for sound unification.

occurrences_of_var(+Term, +Variable, -Tally)

is true when the given Variable occurs exactly Tally times in Term. It can only be used to calculate or test Tally; to enumerate Variables you'll have to use sub_term/2 and then test them with this routine. If you just want to find out whether Variable occurs in Term or not, use contains_var/2 or free_of_var/2.

sub_term(?Kernel, +Term)

is true when Kernel is a sub-term of Term. It enumerates the sub-terms of Term in an arbitrary order. Well, it is defined that a sub-term of Term will be enumerated before its own sub-terms are (but of course some of those sub-terms might be elsewhere in Term as well).

depth_bound(+Term, +Bound)

is true when the term depth of Term is no greater than Bound, that is, when constructor functions are nested no more than Bound deep. Later variable bindings may invalidate this bound. To find the (current) depth, use term_depth/2.

length_bound(?List, +Bound)

is true when the length of List is no greater than Bound. It can be used to enumerate Lists up to the bound.

size_bound(+Term, +Bound)

is true when the number of constant and function symbols in Term is (currently) at most Bound. If Term is non-ground, later variable bindings may invalidate this bound. To find the (current) size, use term_size/2.

term_depth(+Term, -Depth)

calculates the Depth of a Term, using the definition

              term_depth(Var) = 0
              term_depth(Const) = 0
              term_depth(F(T1,...,Tn)) = 1+max(term_depth(T1),...,term_depth(Tn))

Could be defined as:

          term_depth(X, Depth) :-
          	simple(X), !, Depth = 0.
          term_depth(X, Depth) :-
          	(   foreacharg(A,X),
          	    fromto(0,D0,D,Depth0)
          	do  term_depth(A, D1),
          	    D is max(D0,D1)
          	),
          	Depth is Depth0+1.

term_size(+Term, -Size)

calculates the Size of a Term, defined to be the number of constant and function symbol occurrences in it. Could be defined as:

          term_size(X, Size) :-
          	var(X), !, Size = 0.
          term_size(X, Size) :-
          	simple(X), !, Size = 1.
          term_size(X, Size) :-
          	(   foreacharg(A,X),
          	    fromto(1,S0,S,Size)
          	do  term_size(A, S1),
          	    S is S0+S1
          	).

same_functor(?T1, ?T2)

is true when T1 and T2 have the same principal functor. If one of the terms is a variable, it will be instantiated to a new term with the same principal functor as the other term (which should be instantiated) and with arguments being new distinct variables. If both terms are variables, an error is reported.

same_functor(?T1, ?T2, ?N)

is true when T1 and T2 have the same principal functor, and their common arity is N. Like same_functor/3, at least one of T1 and T2 must be bound, or an error will be reported.

same_functor(?T1, ?T2, ?F, ?N)

is true when T1 and T2 have the same principal functor, and their common functor is F/N. Given T1 (or T2) the remaining arguments can be computed. Given F and N, the remaining arguments can be computed. If too many arguments are unbound, an error is reported.