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)).

Random term generator

This module generates random terms intented to test predicates that manage arbitrary terms. Think of variant detection (=@=/2), factorization, etc. The generated terms contain:

Actually shared subterms (same cell reachable via multiple paths).
Equivalent-but-not-shared subterms (fresh copies of earlier subterms).
Cyclic subterms (back-references to an ancestor under construction).
A sprinkling of fresh variables at the leaves.

Design

During generation we thread two lists:

Done — completed compound subterms. New subterms may either share these (unify with the same cell) or take a copy (duplicate_term/2, structurally equivalent but disjoint even for ground subterms — copy_term/2 would leak sharing here).
Anc — currently under-construction ancestors. A cycle back-reference simply unifies the new subterm with one of these, which produces a real cyclic term because the ancestor already contains the argument slot being filled.

At every non-leaf point a weighted choice is made among {leaf, share, copy, cycle, compound}. Options that are unavailable (empty pool / empty ancestor stack) are dropped from the choice rather than having their probability mass leak into the remaining options — otherwise early nodes, where the completed pool is still empty, would collapse into trivial self-cycles.

The compound weight is scaled by depth_decay^Level, where Level is the distance from the root. This keeps the root strongly biased towards compounds (avoiding trivial one-leaf terms) while making the probability of descending further vanish geometrically with depth.

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 ]).

#{ depth: 5, % maximum recursion depth depth_decay: 0.5, % w_compound is scaled by this per level max_arity: 3, % maximum compound arity functors: [f,g,h,p,q], atoms: [a,b,c], max_int: 100, % random integer leaves in 0..max_int p_zero_arity: 0.1, % fraction on zero-arity compounds. w_leaf: 10, % choice weights w_share: 30, w_copy: 15, w_cycle: 15, w_compound: 50, w_var: 10, % leaf-type weights w_atom: 10, w_int: 10, w_float: 10, w_rational: 10, w_string: 10 }

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 ).

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)