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

 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 8 bytes. The calculation does take sharing into account and handles cycles correctly. 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.

  104term_size(Term, Size) :-
  105    '$term_size'(Term, _, Size).

 variant(@Term1, @Term2) is semidet

Same as SWI-Prolog Term1 =@= Term2.

  111variant(X, Y) :-
  112    X =@= Y.

 subsumes_chk(@Generic, @Specific)

True if Generic can be made equivalent to Specific without changing Specific.

deprecated

- Replace by subsumes_term/2.

  121subsumes_chk(Generic, Specific) :-
  122    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.

  134subsumes(Generic, Specific) :-
  135    subsumes_term(Generic, Specific),
  136    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

  147%       It has been rewritten by  Jan   Wielemaker  to use the YAP-based
  148%       red-black-trees as mapping rather than flat  lists and use arg/3
  149%       to map compound terms rather than univ and lists.
  150
  151term_subsumer(S1, S2, G) :-
  152    cyclic_term(S1),
  153    cyclic_term(S2),
  154    !,
  155    rb_empty(Map),
  156    lgg_safe(S1, S2, G, Map, _).
  157term_subsumer(S1, S2, G) :-
  158    rb_empty(Map),
  159    lgg(S1, S2, G, Map, _).
  160
  161lgg(S1, S2, G, Map0, Map) :-
  162    (   S1 == S2
  163    ->  G = S1,
  164        Map = Map0
  165    ;   compound(S1),
  166        compound(S2),
  167        compound_name_arity(S1, Name, Arity),
  168        compound_name_arity(S2, Name, Arity)
  169    ->  compound_name_arity(G, Name, Arity),
  170        lgg(0, Arity, S1, S2, G, Map0, Map)
  171    ;   rb_lookup(S1+S2, G0, Map0)
  172    ->  G = G0,
  173        Map = Map0
  174    ;   rb_insert(Map0, S1+S2, G, Map)
  175    ).
  176
  177lgg(Arity, Arity, _, _, _, Map, Map) :- !.
  178lgg(I0, Arity, S1, S2, G, Map0, Map) :-
  179    I is I0 + 1,
  180    arg(I, S1, Sa1),
  181    arg(I, S2, Sa2),
  182    arg(I, G, Ga),
  183    lgg(Sa1, Sa2, Ga, Map0, Map1),
  184    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.

  193lgg_safe(S1, S2, G, Map0, Map) :-
  194    (   S1 == S2
  195    ->  G = S1,
  196        Map = Map0
  197    ;   rb_lookup(S1+S2, G0, Map0)
  198    ->  G = G0,
  199        Map = Map0
  200    ;   compound(S1),
  201        compound(S2),
  202        compound_name_arity(S1, Name, Arity),
  203        compound_name_arity(S2, Name, Arity)
  204    ->  compound_name_arity(G, Name, Arity),
  205        rb_insert(Map0, S1+S2, G, Map1),
  206        lgg_safe(0, Arity, S1, S2, G, Map1, Map)
  207    ;   rb_insert(Map0, S1+S2, G, Map)
  208    ).
  209
  210lgg_safe(Arity, Arity, _, _, _, Map, Map) :- !.
  211lgg_safe(I0, Arity, S1, S2, G, Map0, Map) :-
  212    I is I0 + 1,
  213    arg(I, S1, Sa1),
  214    arg(I, S2, Sa2),
  215    arg(I, G, Ga),
  216    lgg_safe(Sa1, Sa2, Ga, Map0, Map1),
  217    lgg_safe(I, Arity, S1, S2, G, Map1, Map).
  218
  219
  220%       term_factorized/3 and term_factorized/4 are built in.  They are
  221%       named in the export list above because that is where they used to
  222%       live and where they are imported from.

 mapargs(:Goal, ?Term1, ?Term2)

Term1 and Term2 have the same functor (name/arity) and for each matching pair of arguments call(Goal, A1, A2) is true.

  230mapargs(Goal, Term1, Term2) :-
  231    same_functor(Term1, Term2, Arity),
  232    mapargs_(1, Arity, Goal, Term1, Term2).
  233
  234mapargs_(I, Arity, Goal, Term1, Term2) :-
  235    I =< Arity,
  236    !,
  237    arg(I, Term1, A1),
  238    arg(I, Term2, A2),
  239    call(Goal, A1, A2),
  240    I2 is I+1,
  241    mapargs_(I2, Arity, Goal, Term1, Term2).
  242mapargs_(_, _, _, _, _).

 mapsubterms(:Goal, +Term1, -Term2) is det

 mapsubterms_var(:Goal, +Term1, -Term2) is det

Recursively map sub terms of Term1 into subterms of Term2 for every pair for which call(Goal, ST1, ST2) succeeds. Procedurably, the mapping for each (sub) term pair T1/T2 is defined as:

• If T1 is a variable
  • mapsubterms/3 unifies T2 with T1.
  • mapsubterms_var/3 treats variables as other terms.
• If call(Goal, T1, T2) succeeds we are done. Note that the mapping does not continue in T2. If this is desired, Goal must call mapsubterms/3 explicitly as part of its conversion.
• If T1 is a dict, map all values, i.e., the tag and keys are left untouched.
• If T1 is a list, map all elements, i.e., the list structure is left untouched.
• If T1 is a compound, use same_functor/3 to instantiate T2 and recurse over the term arguments left to right.
• Otherwise T2 is unified with T1.

Both predicates are implemented using foldsubterms/5.

  268mapsubterms(Goal, Term1, Term2) :-
  269    foldsubterms(map2(Goal), Term1, Term2, _, _).
  270mapsubterms_var(Goal, Term1, Term2) :-
  271    foldsubterms(map2_var(Goal), Term1, Term2, _, _).
  272
  273map2(Goal, Term1, Term2, _, _) :-
  274    nonvar(Term1),
  275    call(Goal, Term1, Term2).
  276
  277map2_var(Goal, Term1, Term2, _, _) :-
  278    call(Goal, Term1, Term2).

 foldsubterms(:Goal3, +Term1, +State0, -State) is semidet

 foldsubterms(:Goal4, +Term1, ?Term2, +State0, -State) is semidet

The predicate foldsubterms/5 calls call(Goal4, SubTerm1, SubTerm2, StateIn, StateOut) for each subterm, including variables, in Term1. If this call fails, StateIn and StateOut are the same. This predicate may be used to map subterms in a term while collecting state about the mapped subterms. The foldsubterms/4 variant does not map the term.

  290foldsubterms(Goal, Term1, State0, State) :-
  291    foldsubterms(fold1(Goal), Term1, _, State0, State).
  292
  293fold1(Goal, Term1, _Term2, State0, State) :-
  294    call(Goal, Term1, State0, State).
  295
  296foldsubterms(Goal, Term1, Term2, State0, State) :-
  297    call(Goal, Term1, Term2, State0, State),
  298    !.
  299foldsubterms(Goal, Term1, Term2, State0, State) :-
  300    is_dict(Term1),
  301    !,
  302    dict_pairs(Term1, Tag, Pairs1),
  303    fold_dict_pairs(Pairs1, Pairs2, Goal, State0, State),
  304    dict_pairs(Term2, Tag, Pairs2).
  305foldsubterms(Goal, Term1, Term2, State0, State) :-
  306    is_list(Term1),
  307    !,
  308    fold_some(Term1, Term2, Goal, State0, State).
  309foldsubterms(Goal, Term1, Term2, State0, State) :-
  310    compound(Term1),
  311    !,
  312    same_functor(Term1, Term2, Arity),
  313    foldsubterms_(1, Arity, Goal, Term1, Term2, State0, State).
  314foldsubterms(_, Term, Term, State, State).
  315
  316fold_dict_pairs([], [], _, State, State).
  317fold_dict_pairs([K-V0|T0], [K-V|T], Goal, State0, State) :-
  318    foldsubterms(Goal, V0, V, State0, State1),
  319    fold_dict_pairs(T0, T, Goal, State1, State).
  320
  321fold_some([], [], _, State, State).
  322fold_some([H0|T0], [H|T], Goal, State0, State) :-
  323    foldsubterms(Goal, H0, H, State0, State1),
  324    fold_some(T0, T, Goal, State1, State).
  325
  326foldsubterms_(I, Arity, Goal, Term1, Term2, State0, State) :-
  327    I =< Arity,
  328    !,
  329    arg(I, Term1, A1),
  330    arg(I, Term2, A2),
  331    foldsubterms(Goal, A1, A2, State0, State1),
  332    I2 is I+1,
  333    foldsubterms_(I2, Arity, Goal, Term1, Term2, State1, State).
  334foldsubterms_(_, _, _, _, _, State, State).

 same_functor(?Term1, ?Term2) is semidet

 same_functor(?Term1, ?Term2, -Arity) is semidet

 same_functor(?Term1, ?Term2, ?Name, ?Arity) is semidet

True when Term1 and Term2 are terms that have the same functor (Name/Arity). The arguments must be sufficiently instantiated, which means either Term1 or Term2 must be bound or both Name and Arity must be bound.

If Arity is 0, Term1 and Term2 are unified with Name for compatibility.

Compatibility

- SICStus

  351same_functor(Term1, Term2) :-
  352    same_functor(Term1, Term2, _Name, _Arity).
  353
  354same_functor(Term1, Term2, Arity) :-
  355    same_functor(Term1, Term2, _Name, Arity).
  356
  357same_functor(Term1, Term2, Name, Arity) :-
  358    (   nonvar(Term1)
  359    ->  functor(Term1, Name, Arity, Type),
  360        functor(Term2, Name, Arity, Type)
  361    ;   nonvar(Term2)
  362    ->  functor(Term2, Name, Arity, Type),
  363        functor(Term1, Name, Arity, Type)
  364    ;   functor(Term2, Name, Arity),
  365        functor(Term1, Name, Arity)
  366    )