View source with raw comments or as raw
    1/*  Part of SWI-Prolog
    2
    3    Author:        Jan Wielemaker
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2008-2016, University of Amsterdam, VU University Amsterdam
    7    All rights reserved.
    8
    9    Redistribution and use in source and binary forms, with or without
   10    modification, are permitted provided that the following conditions
   11    are met:
   12
   13    1. Redistributions of source code must retain the above copyright
   14       notice, this list of conditions and the following disclaimer.
   15
   16    2. Redistributions in binary form must reproduce the above copyright
   17       notice, this list of conditions and the following disclaimer in
   18       the documentation and/or other materials provided with the
   19       distribution.
   20
   21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   25    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   29    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   31    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   32    POSSIBILITY OF SUCH DAMAGE.
   33*/
   34
   35:- module(terms,
   36          [ term_hash/2,                % @Term, -HashKey
   37            term_hash/4,                % @Term, +Depth, +Range, -HashKey
   38            term_size/2,                % @Term, -Size
   39            term_variables/2,           % @Term, -Variables
   40            term_variables/3,           % @Term, -Variables, +Tail
   41            variant/2,                  % @Term1, @Term2
   42            subsumes/2,                 % +Generic, @Specific
   43            subsumes_chk/2,             % +Generic, @Specific
   44            cyclic_term/1,              % @Term
   45            acyclic_term/1,             % @Term
   46            term_subsumer/3,            % +Special1, +Special2, -General
   47            term_factorized/3           % +Term, -Skeleton, -Subsitution
   48          ]).   49:- autoload(library(rbtrees),
   50	    [ rb_empty/1,
   51	      rb_lookup/3,
   52	      rb_insert/4,
   53	      rb_new/1,
   54	      rb_visit/2,
   55	      ord_list_to_rbtree/2,
   56	      rb_update/5
   57	    ]).

Term manipulation

Compatibility library for term manipulation predicates. Most predicates in this library are provided as SWI-Prolog built-ins.

Compatibility
-
YAP, SICStus, Quintus. Not all versions of this library define exactly the same set of predicates, but defined predicates are compatible. */
 term_size(@Term, -Size) is det
True if Size is the size in cells occupied by Term on the global (term) stack. A cell is 4 bytes on 32-bit machines and 8 bytes on 64-bit machines. The calculation does take sharing into account. For example:
?- A = a(1,2,3), term_size(A,S).
S = 4.
?- A = a(1,2,3), term_size(a(A,A),S).
S = 7.
?- term_size(a(a(1,2,3), a(1,2,3)), S).
S = 11.

Note that small objects such as atoms and small integers have a size 0. Space is allocated for floats, large integers, strings and compound terms.

   90term_size(Term, Size) :-
   91    '$term_size'(Term, _, Size).
 variant(@Term1, @Term2) is semidet
Same as SWI-Prolog Term1 =@= Term2.
   97variant(X, Y) :-
   98    X =@= Y.
 subsumes_chk(@Generic, @Specific)
True if Generic can be made equivalent to Specific without changing Specific.
deprecated
- Replace by subsumes_term/2.
  107subsumes_chk(Generic, Specific) :-
  108    subsumes_term(Generic, Specific).
 subsumes(+Generic, @Specific)
True if Generic is unified to Specific without changing Specific.
deprecated
- It turns out that calls to this predicate almost always should have used subsumes_term/2. Also the name is misleading. In case this is really needed, one is adviced to follow subsumes_term/2 with an explicit unification.
  120subsumes(Generic, Specific) :-
  121    subsumes_term(Generic, Specific),
  122    Generic = Specific.
 term_subsumer(+Special1, +Special2, -General) is det
General is the most specific term that is a generalisation of Special1 and Special2. The implementation can handle cyclic terms.
author
- Inspired by LOGIC.PRO by Stephen Muggleton
Compatibility
- SICStus
  133%       It has been rewritten by  Jan   Wielemaker  to use the YAP-based
  134%       red-black-trees as mapping rather than flat  lists and use arg/3
  135%       to map compound terms rather than univ and lists.
  136
  137term_subsumer(S1, S2, G) :-
  138    cyclic_term(S1),
  139    cyclic_term(S2),
  140    !,
  141    rb_empty(Map),
  142    lgg_safe(S1, S2, G, Map, _).
  143term_subsumer(S1, S2, G) :-
  144    rb_empty(Map),
  145    lgg(S1, S2, G, Map, _).
  146
  147lgg(S1, S2, G, Map0, Map) :-
  148    (   S1 == S2
  149    ->  G = S1,
  150        Map = Map0
  151    ;   compound(S1),
  152        compound(S2),
  153        functor(S1, Name, Arity),
  154        functor(S2, Name, Arity)
  155    ->  functor(G, Name, Arity),
  156        lgg(0, Arity, S1, S2, G, Map0, Map)
  157    ;   rb_lookup(S1+S2, G0, Map0)
  158    ->  G = G0,
  159        Map = Map0
  160    ;   rb_insert(Map0, S1+S2, G, Map)
  161    ).
  162
  163lgg(Arity, Arity, _, _, _, Map, Map) :- !.
  164lgg(I0, Arity, S1, S2, G, Map0, Map) :-
  165    I is I0 + 1,
  166    arg(I, S1, Sa1),
  167    arg(I, S2, Sa2),
  168    arg(I, G, Ga),
  169    lgg(Sa1, Sa2, Ga, Map0, Map1),
  170    lgg(I, Arity, S1, S2, G, Map1, Map).
 lgg_safe(+S1, +S2, -G, +Map0, -Map) is det
Cycle-safe version of the above. The difference is that we insert compounds into the mapping table and check the mapping table before going into a compound.
  179lgg_safe(S1, S2, G, Map0, Map) :-
  180    (   S1 == S2
  181    ->  G = S1,
  182        Map = Map0
  183    ;   rb_lookup(S1+S2, G0, Map0)
  184    ->  G = G0,
  185        Map = Map0
  186    ;   compound(S1),
  187        compound(S2),
  188        functor(S1, Name, Arity),
  189        functor(S2, Name, Arity)
  190    ->  functor(G, Name, Arity),
  191        rb_insert(Map0, S1+S2, G, Map1),
  192        lgg_safe(0, Arity, S1, S2, G, Map1, Map)
  193    ;   rb_insert(Map0, S1+S2, G, Map)
  194    ).
  195
  196lgg_safe(Arity, Arity, _, _, _, Map, Map) :- !.
  197lgg_safe(I0, Arity, S1, S2, G, Map0, Map) :-
  198    I is I0 + 1,
  199    arg(I, S1, Sa1),
  200    arg(I, S2, Sa2),
  201    arg(I, G, Ga),
  202    lgg_safe(Sa1, Sa2, Ga, Map0, Map1),
  203    lgg_safe(I, Arity, S1, S2, G, Map1, Map).
 term_factorized(+Term, -Skeleton, -Substiution)
Is true when Skeleton is Term where all subterms that appear multiple times are replaced by a variable and Substitution is a list of Var=Value that provides the subterm at the location Var. I.e., After unifying all substitutions in Substiutions, Term == Skeleton. Term may be cyclic. For example:
?- X = a(X), term_factorized(b(X,X), Y, S).
Y = b(_G255, _G255),
S = [_G255=a(_G255)].
  220term_factorized(Term, Skeleton, Substitutions) :-
  221    rb_new(Map0),
  222    add_map(Term, Map0, Map),
  223    rb_visit(Map, Counts),
  224    common_terms(Counts, Common),
  225    (   Common == []
  226    ->  Skeleton = Term,
  227        Substitutions = []
  228    ;   ord_list_to_rbtree(Common, SubstAssoc),
  229        insert_vars(Term, Skeleton, SubstAssoc),
  230        mk_subst(Common, Substitutions, SubstAssoc)
  231    ).
  232
  233add_map(Term, Map0, Map) :-
  234    (   primitive(Term)
  235    ->  Map = Map0
  236    ;   rb_update(Map0, Term, Old, New, Map)
  237    ->  New is Old+1
  238    ;   rb_insert(Map0, Term, 1, Map1),
  239        assoc_arg_map(1, Term, Map1, Map)
  240    ).
  241
  242assoc_arg_map(I, Term, Map0, Map) :-
  243    arg(I, Term, Arg),
  244    !,
  245    add_map(Arg, Map0, Map1),
  246    I2 is I + 1,
  247    assoc_arg_map(I2, Term, Map1, Map).
  248assoc_arg_map(_, _, Map, Map).
  249
  250primitive(Term) :-
  251    var(Term),
  252    !.
  253primitive(Term) :-
  254    atomic(Term),
  255    !.
  256primitive('$VAR'(_)).
  257
  258common_terms([], []).
  259common_terms([H-Count|T], List) :-
  260    !,
  261    (   Count == 1
  262    ->  common_terms(T, List)
  263    ;   List = [H-_NewVar|Tail],
  264        common_terms(T, Tail)
  265    ).
  266
  267insert_vars(T0, T, _) :-
  268    primitive(T0),
  269    !,
  270    T = T0.
  271insert_vars(T0, T, Subst) :-
  272    rb_lookup(T0, S, Subst),
  273    !,
  274    T = S.
  275insert_vars(T0, T, Subst) :-
  276    functor(T0, Name, Arity),
  277    functor(T,  Name, Arity),
  278    insert_arg_vars(1, T0, T, Subst).
  279
  280insert_arg_vars(I, T0, T, Subst) :-
  281    arg(I, T0, A0),
  282    !,
  283    arg(I, T,  A),
  284    insert_vars(A0, A, Subst),
  285    I2 is I + 1,
  286    insert_arg_vars(I2, T0, T, Subst).
  287insert_arg_vars(_, _, _, _).
  288
  289mk_subst([], [], _).
  290mk_subst([Val0-Var|T0], [Var=Val|T], Subst) :-
  291    functor(Val0, Name, Arity),
  292    functor(Val,  Name, Arity),
  293    insert_arg_vars(1, Val0, Val, Subst),
  294    mk_subst(T0, T, Subst)