1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: jan@swi-prolog.org 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2026, SWI-Prolog Solutions b.v. 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(random_terms, 36 [ random_term/2 % -Term, +Options 37 ]). 38:- use_module(library(random)). 39:- use_module(library(lists)). 40:- use_module(library(pairs)). 41:- use_module(library(debug)). 42 43/** <module> Random term generator 44 45This module generates random terms intented to test predicates that 46manage arbitrary terms. Think of variant detection (`=@=/2`), 47factorization, etc. The generated terms contain: 48 49 * Actually shared subterms (same cell reachable via multiple paths). 50 * Equivalent-but-not-shared subterms (fresh copies of earlier subterms). 51 * Cyclic subterms (back-references to an ancestor under construction). 52 * A sprinkling of fresh variables at the leaves. 53 54## Design 55 56During generation we thread two lists: 57 58 * `Done` — completed compound subterms. New subterms may either 59 _share_ these (unify with the same cell) or take a _copy_ 60 (`duplicate_term/2`, structurally equivalent but disjoint even 61 for ground subterms — `copy_term/2` would leak sharing here). 62 * `Anc` — currently under-construction ancestors. A _cycle_ 63 back-reference simply unifies the new subterm with one of these, 64 which produces a real cyclic term because the ancestor already 65 contains the argument slot being filled. 66 67At every non-leaf point a weighted choice is made among {leaf, share, 68copy, cycle, compound}. Options that are unavailable (empty pool / empty 69ancestor stack) are dropped from the choice rather than having their 70probability mass leak into the remaining options — otherwise early 71nodes, where the completed pool is still empty, would collapse into 72trivial self-cycles. 73 74The compound weight is scaled by `depth_decay^Level`, where `Level` is 75the distance from the root. This keeps the root strongly biased towards 76compounds (avoiding trivial one-leaf terms) while making the probability 77of descending further vanish geometrically with depth. 78*/ 79 80:- predicate_options(random_term/2, 2, 81 [ depth: nonneg, 82 depth_decay: between(0.0, 1.0), 83 max_arity: nonneg, 84 functors: list(atom), 85 atoms: list(atom), 86 max_int: nonneg, 87 p_zero_arity: between(0.0, 1.0), 88 w_leaf: between(0, 100), 89 w_share: between(0, 100), 90 w_copy: between(0, 100), 91 w_cycle: between(0, 100), 92 w_compound: between(0, 100), 93 w_var: between(0, 100), 94 w_atom: between(0, 100), 95 w_int: between(0, 100), 96 w_float: between(0, 100), 97 w_rational: between(0, 100), 98 w_string: between(0, 100) 99 ]). 100 101 102%! random_term(-Term, +Options) is det. 103% 104% Generate a random term. Options override the defaults below and may 105% be given either as an option list or as a dict. Weigths (w_*) are 106% handled as relative weights in two groups: 107% 108% - `w_leaf`, `w_share`, `w_copy`, `w_cycle` and `w_compound` 109% control the (compound) shape of the resulting term. 110% - `w_atom`, `w_int`, `w_float`, `w_rational` and `w_string` 111% control what _leaf_ node is generated after the group above 112% decided to create a _leaf_. 113% 114% Defaults: 115% 116% ``` 117% #{ 118% depth: 5, % maximum recursion depth 119% depth_decay: 0.5, % w_compound is scaled by this per level 120% max_arity: 3, % maximum compound arity 121% functors: [f,g,h,p,q], 122% atoms: [a,b,c], 123% max_int: 100, % random integer leaves in 0..max_int 124% p_zero_arity: 0.1, % fraction on zero-arity compounds. 125% w_leaf: 10, % choice weights 126% w_share: 30, 127% w_copy: 15, 128% w_cycle: 15, 129% w_compound: 50, 130% w_var: 10, % leaf-type weights 131% w_atom: 10, 132% w_int: 10, 133% w_float: 10, 134% w_rational: 10, 135% w_string: 10 136% } 137% ``` 138 139random_term(Term, Options) :- 140 params(Options, Params), 141 gen(0, Params, [], _Done, [], Term). 142 143default_params( 144 #{ depth: 5, 145 depth_decay: 0.5, 146 max_arity: 3, 147 functors: [f,g,h,p,q], 148 atoms: [a,b,c], 149 max_int: 100, 150 p_zero_arity: 0.10, 151 w_leaf: 10, 152 w_share: 30, 153 w_copy: 15, 154 w_cycle: 15, 155 w_compound: 50, 156 w_var: 10, 157 w_atom: 10, 158 w_int: 10, 159 w_float: 10, 160 w_rational: 10, 161 w_string: 10 162 }). 163 164params(Options, Params) :- 165 default_params(Def), 166 ( is_dict(Options) 167 -> User = Options 168 ; dict_create(User, #, Options) 169 ), 170 Params = Def.put(User). 171 172% gen(+Level, +Params, +Done0, -Done, +Anc, -Term) 173% 174% @arg Level is the distance from the root (0 at the top). 175 176gen(Level, Params, Done0, Done, Anc, Term) :- 177 ( Level >= Params.depth 178 -> gen_leaf(Params, Term), Done = Done0 179 ; choices(Level, Params, Done0, Anc, Cs), 180 weighted_pick(Cs, Action), 181 debug(random_term, 'Weigths: ~p --> ~p', [Cs, Action]), 182 do_action(Action, Level, Params, Done0, Done, Anc, Term) 183 ). 184 185%! choices(+Level, +Params, +Done, +Anc, -Cs) is det. 186% 187% Construct a list of choices Cs as `Weight-Action`, where `Action` is 188% one of `leaf`, `compound`, `share`, `copy`, `cycle`. 189 190choices(Level, Params, Done, Anc, Cs) :- 191 WCompound is Params.w_compound * Params.depth_decay ** Level, 192 Cs0 = [Params.w_leaf-leaf, WCompound-compound], 193 ( Done == [] 194 -> Cs1 = Cs0 195 ; Cs1 = [Params.w_share-share, Params.w_copy-copy | Cs0] 196 ), 197 ( Anc == [] 198 -> Cs = Cs1 199 ; Cs = [Params.w_cycle-cycle | Cs1] 200 ). 201 202weighted_pick(Pairs, Choice) :- 203 pairs_keys(Pairs, Ws), 204 sum_list(Ws, Sum), 205 R is random_float * Sum, 206 pick_(Pairs, R, Choice). 207 208pick_([_-C], _, C) :- !. 209pick_([W-C|_], R, C) :- R =< W, !. 210pick_([W-_|Rest], R, Choice) :- 211 R1 is R - W, 212 pick_(Rest, R1, Choice). 213 214do_action(leaf, _, Params, Done, Done, _, T) :- 215 gen_leaf(Params, T). 216do_action(share, _, _, Done, Done, _, T) :- 217 random_member(T, Done). 218do_action(copy, _, _, Done, Done, _, T) :- 219 random_member(T0, Done), 220 duplicate_term(T0, T). 221do_action(cycle, _, _, Done, Done, Anc, T) :- 222 random_member(T, Anc). 223do_action(compound, Level, Params, Done0, Done, Anc, T) :- 224 gen_compound(Level, Params, Done0, Done, Anc, T). 225 226gen_compound(Level, Params, Done0, Done, Anc, Term) :- 227 ( maybe(Params.p_zero_arity) 228 -> N = 0 229 ; random_between(1, Params.max_arity, N) 230 ), 231 random_member(F, Params.functors), 232 length(Args, N), 233 compound_name_arguments(Term, F, Args), 234 L1 is Level + 1, 235 gen_args(Args, L1, Params, Done0, Done1, [Term|Anc]), 236 Done = [Term|Done1]. 237 238gen_args([], _, _, Done, Done, _). 239gen_args([A|As], L, Params, Done0, Done, Anc) :- 240 gen(L, Params, Done0, Done1, Anc, A), 241 gen_args(As, L, Params, Done1, Done, Anc). 242 243gen_leaf(Params, Leaf) :- 244 pick_leaf_type(Params, Type), 245 gen_leaf_of(Type, Params, Leaf). 246 247pick_leaf_type(Params, Type) :- 248 Ts = [ Params.w_var-var, 249 Params.w_atom-atom, 250 Params.w_int-int, 251 Params.w_float-float, 252 Params.w_rational-rational, 253 Params.w_string-string 254 ], 255 weighted_pick(Ts, Type). 256 257gen_leaf_of(var, _, _). 258gen_leaf_of(atom, Params, Leaf) :- 259 random_member(Leaf, Params.atoms). 260gen_leaf_of(int, Params, Leaf) :- 261 Neg is -Params.max_int, 262 random_between(Neg, Params.max_int, Leaf). 263gen_leaf_of(float, Params, Leaf) :- 264 gen_leaf_of(int, Params, Int), 265 Leaf is (Int*100+random(100))/100.0. 266gen_leaf_of(rational, Params, Leaf) :- 267 Max = Params.max_int, 268 Min is -Max, 269 random_between(Min, Max, N), 270 random_between(1, Max, D), 271 Leaf is N rdiv D. 272gen_leaf_of(string, Params, Leaf) :- 273 random_member(A, Params.atoms), 274 atom_string(A, Leaf)