1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22 23:- comment(alias, "All Solutions"). 24:- comment(summary, "Built-ins to collect all solutions to nondeterministic goals"). 25:- comment(categories, ["Built-In Predicates"]). 26 27:- tool(bagof / 3). 28:- tool(coverof / 3). 29:- tool(findall / 3). 30:- tool(setof / 3). 31 32:- comment(bagof / 3, [ 33 summary:"Succeeds if List is the (non-empty) list of all instances of Term such that 34Goal is provable. 35 36", 37 amode:(bagof(?,+,-) is nondet), 38 desc:html(" Unifies List with the list (not ordered, duplicates retained) of all 39 instances of Term such that Goal is satisfied. The variables appearing 40 in Term should not appear anywhere else in the clause except within 41 Goal. 42 43<P> 44 The following table illustrates the difference between the all solutions 45 predicates: 46 47<P> 48<PRE> 49 built-in choice pts duplicates sorted pruned * 50 bagof/3 yes yes no no 51 coverof/3 yes no no yes 52 findall/3 no yes no no 53 setof/3 yes no yes no 54 * prune_instances/2 used on list of solutions. 55</PRE> 56 If Goal is not a callable term, exceptions are raised in call/2. 57 58<P> 59Note 60 If there are uninstantiated variables in Goal which do not appear in 61 Term, then bagof/3 can be resatisfied. It generates alternative values 62 for List corresponding to different instantiations of the free variables 63 of Goal not in Term. Such variables occurring in Goal will not be 64 treated as free if they are explicitly bound within Goal through an 65 existential quantification written as, for example, 66 67<P> 68<PRE> 69 bagof(X, Y^(X likes Y), S). 70</PRE> 71 Then bagof/3 will not backtrack over Y when getting a bag of solutions 72 of X. 73 74<P> 75"), 76 args:["Term" : "Prolog term, usually a variable, a compound term or list containing variables.", "Goal" : "Callable term.", "List" : "List or variable."], 77 fail_if:"Fails if Goal has no solution", 78 exceptions:[4 : "Goal is not instantiated.", 5 : "Goal is instantiated, but not to a compound term.", 68 : "Goal is an undefined procedure."], 79 eg:" 80Success: 81 82 83 % example using existential quantification: 84 [eclipse]: bagof(Name,Num^current_stream(Name,Mode,Num),L), 85 > writeq((Name,Mode,Num,L)), nl, fail. 86 _g72 , read , _g84 , [user, debug_input] % does not 87 _g72 , string , _g84 , [\"\"] % backtrack over 88 _g72 , update , _g84 , [null] % Num. 89 _g72 , write , _g84 , [user, error] 90 91 no (more) solution. 92 [eclipse]: bagof(Name,current_stream(Name,Mode,Num),L), 93 > writeq((Name,Mode,Num,L)), nl, fail. 94 _g72 , read , 0 , [user] % backtracks over Num. 95 _g72 , read , 3 , [debug_input] 96 _g72 , string , 5 , [\"\"] 97 _g72 , update , 4 , [null] 98 _g72 , write , 1 , [user] 99 _g72 , write , 2 , [error] 100 101 no (more) solution. 102 [eclipse]: bagof(Name,(Mode,Num)^current_stream(Name,Mode,Num),L), 103 > writeq((Name,Mode,Num,L)), nl, fail. 104 _g72 , _g78 , _g84 , [user, user, error, debug_input, null, \"\"] 105 106 no (more) solution. % retains duplicates; not sorted. 107 108 109 [eclipse]: [user]. 110 h(f(1,2)). 111 h(f(1,2)). 112 h(f(1,X)). 113 h(f(X,Y)). % instances of this element... 114 user compiled 476 bytes in 0.00 seconds 115 yes. 116 [eclipse]: bagof(X,h(X),L). 117 X = _g58 118 L = [f(1, 2), f(1,2), f(1, _g116), f(_g100, _g102)] 119 yes. % ...all bagged; includes duplicates. 120 121Fail: 122 bagof(Y,current_stream(X,Y,Z),[strin]). 123 124Error: 125 bagof(X,G,L). (Error 4). 126 bagof(X,\"G\",L). (Error 5). 127 bagof(X,a,L). (Error 68). 128 bagof(X,a(X),L). (Error 68). 129 130 131 132", 133 see_also:[coverof / 3, findall / 3, setof / 3]]). 134 135:- comment(coverof / 3, [ 136 summary:"Succeeds if List is the (non-empty) list of all the most general instances 137of Term such that Goal is provable. 138 139", 140 amode:(coverof(?,+,-) is nondet), 141 desc:html(" Unifies List with the list (not ordered, duplicates removed, pruned) of 142 all instances of Term such that Goal is satisfied. prune_instances/2 is 143 used on the list of solutions, with the result that no element of List 144 is an instance of any other element. 145 146<P> 147 The variables appearing in Term should not appear anywhere else in the 148 clause except within Goal. 149 150<P> 151 The following table illustrates the difference between the all solutions 152 predicates: 153 154<P> 155<PRE> 156 built-in choice pts duplicates sorted pruned * 157 bagof/3 yes yes no no 158 coverof/3 yes no no yes 159 findall/3 no yes no no 160 setof/3 yes no yes no 161 * prune_instances/2 used on list of solutions. 162</PRE> 163 If Goal is not a callable term, exceptions are raised in call/2. 164 165<P> 166 coverof/3 should not be used if Term is a variable. If the resulting 167 list List contains no compound terms or variables, it is usually more 168 efficient to use setof/3. 169 170<P> 171Note 172 If there are uninstantiated variables in Goal which do not appear in 173 Term, then coverof/3 can be resatisfied. It generates alternative 174 values for List corresponding to different instantiations of the free 175 variables of Goal not in Term. Such variables occurring in Goal will 176 not be treated as free if they are explicitly bound within Goal through 177 an existential quantification written as, for example, 178 179<P> 180<PRE> 181 coverof(X, Y^(X likes Y), S). 182</PRE> 183 Then coverof/3 will not backtrack over Y when getting a list of 184 solutions of X. 185 186<P> 187"), 188 args:["Term" : "Prolog term, usually a variable, a compound term or list containing variables.", "Goal" : "Callable term.", "List" : "List or variable."], 189 fail_if:"Fails if Goal has no solution", 190 exceptions:[4 : "Goal is not instantiated.", 5 : "Goal is instantiated, but not to a compound term.", 68 : "Goal is an undefined procedure."], 191 eg:" 192Success: 193 194 195 % example using existential quantification: 196 [eclipse]: [user]. 197 h(f(1,2),g(1,3)). 198 h(f(2,3),g(2,4)). 199 h(f(1,3),g(2,2)). 200 h(f(2,3),g(2,2)). 201 h(f(2,2),g(1,1)). 202 user compiled 900 bytes in 0.00 seconds 203 204 yes. 205 [eclipse]: coverof(f(X,Y),h(f(X,Y),g(W,Z)),L), 206 > writeln((X,Y,W,Z,L)), fail. 207 _g66 , _g72 , 1 , 1 , [f(2, 2)] 208 _g66 , _g72 , 1 , 3 , [f(1, 2)] 209 _g66 , _g72 , 2 , 2 , [f(1, 3), f(2, 3)] 210 _g66 , _g72 , 2 , 4 , [f(2, 3)] 211 212 no (more) solution. 213 [eclipse]: coverof(f(X,Y),g(W,Z)^h(f(X,Y),g(W,Z)),L). 214 X = _g76 215 Y = _g78 216 W = _g70 217 Z = _g72 218 L = [f(1, 2), f(2, 3), f(1, 3), f(2, 2)] 219 yes. 220Fail: 221 coverof(Y,current_stream(X,Y,Z),[strin]). 222Error: 223 coverof(X,G,L). (Error 4). 224 coverof(X,\"G\",L). (Error 5). 225 coverof(X,a,L). (Error 68). 226 227 228 229", 230 see_also:[bagof / 3, findall / 3, setof / 3]]). 231 232:- comment(findall / 3, [ 233 summary:"List is the (possibly empty) list of all instances of Term such that Goal 234is provable. 235 236", 237 amode:(findall(?,+,-) is det), 238 desc:html(" Unifies List with the list (not ordered, duplicates retained, no choice 239 point) of all instances of Term such that Goal is satisfied. The 240 variables appearing in Term should not appear anywhere else in the 241 clause except within Goal. 242 243<P> 244 The following table illustrates the difference between the all solutions 245 predicates: 246 247<P> 248<PRE> 249 built-in choice pts duplicates sorted pruned * 250 bagof/3 yes yes no no 251 coverof/3 yes no no yes 252 findall/3 no yes no no 253 setof/3 yes no yes no 254 * prune_instances/2 used on list of solutions. 255</PRE> 256 If Goal is not a callable term, exceptions are raised in call/2. 257 258<P> 259Note 260 261<P> 262 1. Even if there are uninstantiated variables in Goal which do not appear 263 in Term, then unlike bagof/3, findall/3 has no choice points i.e. 264 these variables are taken to be existentially quantified. 265 266<P> 267 2. findall/3 never fails; if no solution exists, the empty list is 268 returned. 269 270<P> 271"), 272 args:["Term" : "Prolog term, usually a variable, a compound term or list containing variables.", "Goal" : "Callable term.", "List" : "List or variable."], 273 exceptions:[4 : "Goal is not instantiated.", 5 : "Goal is instantiated, but not to a compound term.", 68 : "Goal is an undefined procedure."], 274 eg:" 275Success: 276 277 278 % all variables are taken to be existentially quantified: 279 [eclipse]: findall(Name,current_stream(Name,Mode,Num),L), 280 > writeq((Name,Mode,Num,L)), nl, fail. 281 _g72 , _g78 , _g84 , [user, user, error, debug_input, null, \"\"] 282 no (more) solution. 283 284 [eclipse]: [user]. 285 h(f(1,2)). 286 h(f(1,2)). 287 h(f(1,X)). 288 h(f(X,Y)). % instances of this element... 289 user compiled 476 bytes in 0.00 seconds 290 yes. 291 [eclipse]: findall(X,h(X),L). 292 X = _g58 293 L = [f(1, 2), f(1,2), f(1, _g116), f(_g100, _g102)] 294 yes. % ...all bagged; includes duplicates. 295 296 [eclipse]: findall(X,current_built_in(X),L). 297 X = _g58 298 L = [findall/3, !/0, delayed_goals/1, delayed_goals/2, 299 '.'/2, (;)/2, (<)/2, (;)/4, (;)/5, error/2, error/3, 300 (',')/2, (',')/4, close_window/0, (=)/2, op/3, (>)/2, 301 array/3, (spied)/1, ... / ..., ...] 302 yes. 303 304 [eclipse]: findall(X,append_strings(X,Y,\"abc\"),L). 305 X = _g58 306 Y = _g66 307 L = [\"\", \"a\", \"ab\", \"abc\"] 308 309Fail: 310 findall(Y,current_stream(X,Y,Z),[strin]). 311 312Error: 313 findall(X,G,L). (Error 4). 314 findall(X,\"G\",L). (Error 5). 315 findall(X,a,L). (Error 68). 316 findall(X,a(X),L). (Error 68). 317 318 319 320", 321 see_also:[bagof / 3, coverof / 3, setof / 3]]). 322 323:- comment(setof / 3, [ 324 summary:"Succeeds if List is the (non-empty) ordered list of all instances of Term 325such that Goal is provable. 326 327", 328 amode:(setof(?,+,-) is nondet), 329 desc:html(" Unifies List with the ordered list (no duplicates) of all instances of 330 Term such that Goal is satisfied. The variables appearing in Term 331 should not appear anywhere else in the clause except within Goal. 332 333<P> 334 The following table illustrates the difference between the all solutions 335 predicates: 336 337<P> 338<PRE> 339 built-in choice pts duplicates sorted pruned * 340 bagof/3 yes yes no no 341 coverof/3 yes no no yes 342 findall/3 no yes no no 343 setof/3 yes no yes no 344 * prune_instances/2 used on list of solutions. 345</PRE> 346 If Goal is not a callable term, exceptions are raised in call/2. 347 348<P> 349Note 350 If there are uninstantiated variables in Goal which do not appear in 351 Term, then setof/3 can be resatisfied. It generates alternative values 352 for List corresponding to different instantiations of the free variables 353 of Goal not in Term. Such variables occurring in Goal will not be 354 treated as free if they are explicitly bound within Goal through an 355 existential quantification written as, for example, 356 357<P> 358<PRE> 359 setof(X, Y^(X likes Y), S). 360</PRE> 361 Then setof/3 will not backtrack over Y when getting a set of solutions 362 of X. 363 364<P> 365"), 366 args:["Term" : "Prolog term, usually a variable, a compound term or list containing variables.", "Goal" : "Callable term.", "List" : "List or variable."], 367 fail_if:"Fails if Goal has no solution", 368 exceptions:[4 : "Goal is not instantiated.", 5 : "Goal is instantiated, but not to a compound term.", 68 : "Goal is an undefined procedure."], 369 eg:" 370Success: 371 372 373 % example using existential quantification: 374 [eclipse]: setof(Name,Num^current_stream(Name,Mode,Num),L), 375 > writeq((Name,Mode,Num,L)), nl, fail. 376 _g72 , read , _g84 , [debug_input, user] % does not 377 _g72 , string , _g84 , [\"\"] % backtrack over 378 _g72 , update , _g84 , [null] & Num. 379 _g72 , write , _g84 , [error, user] 380 381 no (more) solution. 382 [eclipse]: setof(Name,current_stream(Name,Mode,Num),L), 383 > writeq((Name,Mode,Num,L)), nl, fail. 384 _g72 , read , 0 , [user] % backtracks over Num. 385 _g72 , read , 3 , [debug_input] 386 _g72 , string , 5 , [\"\"] 387 _g72 , update , 4 , [null] 388 _g72 , write , 1 , [user] 389 _g72 , write , 2 , [error] 390 391 no (more) solution. 392 [eclipse]: setof(N,(Mode,Num)^current_stream(N,Mode,Num),L), 393 > writeq((Name,Mode,Num,L)), nl, fail. 394 _g72 , _g78 , _g84 , [\"\", debug_input, error, null, user] 395 396 no (more) solution. % removes duplicates; sorted. 397 398 399 [eclipse]: [user]. 400 h(f(1,2)). 401 h(f(1,2)). 402 h(f(1,X)). 403 h(f(X,Y)). % instances of this element... 404 user compiled 476 bytes in 0.00 seconds 405 yes. 406 [eclipse]: setof(X,h(X),L). 407 X = _g58 408 L = [f(_g86, _g88), f(1, _g102), f(1, 2)] 409 yes. % ...all bagged; removes duplicates; sorted. 410 411Fail: 412 setof(Y,current_stream(X,Y,Z),[strin]). 413 414Error: 415 setof(X,G,L). (Error 4). 416 setof(X,\"G\",L). (Error 5). 417 setof(X,a,L). (Error 68). 418 setof(X,a(X),L). (Error 68). 419 420 421 422", 423 see_also:[bagof / 3, coverof / 3, findall / 3]]). 424