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(,,), 63 mapsubterms(,,), 64 mapsubterms_var(,,), 65 foldsubterms(,,,), 66 foldsubterms(,,,,). 67 68:- autoload(library(rbtrees), 69 [ rb_empty/1, 70 rb_lookup/3, 71 rb_insert/4 72 ]). 73 74 75/** <module> Term manipulation 76 77Compatibility library for term manipulation predicates. Most predicates 78in this library are provided as SWI-Prolog built-ins. 79 80@compat YAP, SICStus, Quintus. Not all versions of this library define 81 exactly the same set of predicates, but defined predicates are 82 compatible. 83*/ 84 85%! term_size(@Term, -Size) is det. 86% 87% True if Size is the size in _cells_ occupied by Term on the global 88% (term) stack. A _cell_ is 8 bytes. The calculation does take 89% _sharing_ into account and handles _cycles_ correctly. For example: 90% 91% ``` 92% ?- A = a(1,2,3), term_size(A,S). 93% S = 4. 94% ?- A = a(1,2,3), term_size(a(A,A),S). 95% S = 7. 96% ?- term_size(a(a(1,2,3), a(1,2,3)), S). 97% S = 11. 98% ``` 99% 100% Note that small objects such as atoms and small integers have a 101% size 0. Space is allocated for floats, large integers, strings 102% and compound terms. 103 104term_size(Term, Size) :- 105 '$term_size'(Term, _, Size). 106 107%! variant(@Term1, @Term2) is semidet. 108% 109% Same as SWI-Prolog =|Term1 =@= Term2|=. 110 111variant(X, Y) :- 112 X =@= Y. 113 114%! subsumes_chk(@Generic, @Specific) 115% 116% True if Generic can be made equivalent to Specific without 117% changing Specific. 118% 119% @deprecated Replace by subsumes_term/2. 120 121subsumes_chk(Generic, Specific) :- 122 subsumes_term(Generic, Specific). 123 124%! subsumes(+Generic, @Specific) 125% 126% True if Generic is unified to Specific without changing 127% Specific. 128% 129% @deprecated It turns out that calls to this predicate almost 130% always should have used subsumes_term/2. Also the name is 131% misleading. In case this is really needed, one is adviced to 132% follow subsumes_term/2 with an explicit unification. 133 134subsumes(Generic, Specific) :- 135 subsumes_term(Generic, Specific), 136 Generic = Specific. 137 138%! term_subsumer(+Special1, +Special2, -General) is det. 139% 140% General is the most specific term that is a generalisation of 141% Special1 and Special2. The implementation can handle cyclic 142% terms. 143% 144% @compat SICStus 145% @author Inspired by LOGIC.PRO by Stephen Muggleton 146 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). 185 186 187%! lgg_safe(+S1, +S2, -G, +Map0, -Map) is det. 188% 189% Cycle-safe version of the above. The difference is that we 190% insert compounds into the mapping table and check the mapping 191% table before going into a compound. 192 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. 223 224 225%! mapargs(:Goal, ?Term1, ?Term2) 226% 227% Term1 and Term2 have the same functor (name/arity) and for each 228% matching pair of arguments call(Goal, A1, A2) is true. 229 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_(_, _, _, _, _). 243 244 245%! mapsubterms(:Goal, +Term1, -Term2) is det. 246%! mapsubterms_var(:Goal, +Term1, -Term2) is det. 247% 248% Recursively map sub terms of Term1 into subterms of Term2 for every 249% pair for which call(Goal, ST1, ST2) succeeds. Procedurably, the 250% mapping for each (sub) term pair `T1/T2` is defined as: 251% 252% - If `T1` is a variable 253% - mapsubterms/3 unifies `T2` with `T1`. 254% - mapsubterms_var/3 treats variables as other terms. 255% - If call(Goal, T1, T2) succeeds we are done. Note that the 256% mapping does not continue in `T2`. If this is desired, `Goal` 257% must call mapsubterms/3 explicitly as part of its conversion. 258% - If `T1` is a dict, map all values, i.e., the _tag_ and _keys_ 259% are left untouched. 260% - If `T1` is a list, map all elements, i.e., the list structure 261% is left untouched. 262% - If `T1` is a compound, use same_functor/3 to instantiate `T2` 263% and recurse over the term arguments left to right. 264% - Otherwise `T2` is unified with `T1`. 265% 266% Both predicates are implemented using foldsubterms/5. 267 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). 279 280%! foldsubterms(:Goal3, +Term1, +State0, -State) is semidet. 281%! foldsubterms(:Goal4, +Term1, ?Term2, +State0, -State) is semidet. 282% 283% The predicate foldsubterms/5 calls call(Goal4, SubTerm1, SubTerm2, 284% StateIn, StateOut) for each subterm, including variables, in Term1. 285% If this call fails, `StateIn` and `StateOut` are the same. This 286% predicate may be used to map subterms in a term while collecting 287% state about the mapped subterms. The foldsubterms/4 variant does not 288% map the term. 289 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). 335 336 337%! same_functor(?Term1, ?Term2) is semidet. 338%! same_functor(?Term1, ?Term2, -Arity) is semidet. 339%! same_functor(?Term1, ?Term2, ?Name, ?Arity) is semidet. 340% 341% True when Term1 and Term2 are terms that have the same functor 342% (Name/Arity). The arguments must be sufficiently instantiated, which 343% means either Term1 or Term2 must be bound or both Name and Arity 344% must be bound. 345% 346% If Arity is 0, Term1 and Term2 are unified with Name for 347% compatibility. 348% 349% @compat SICStus 350 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 )