1/*  Part of SWI-Prolog
   2
   3    Author:        Jan Wielemaker
   4    E-mail:        J.Wielemaker@vu.nl
   5    WWW:           http://www.swi-prolog.org
   6    Copyright (c)  2008-2016, University of Amsterdam
   7                              VU University Amsterdam
   8    All rights reserved.
   9
  10    Redistribution and use in source and binary forms, with or without
  11    modification, are permitted provided that the following conditions
  12    are met:
  13
  14    1. Redistributions of source code must retain the above copyright
  15       notice, this list of conditions and the following disclaimer.
  16
  17    2. Redistributions in binary form must reproduce the above copyright
  18       notice, this list of conditions and the following disclaimer in
  19       the documentation and/or other materials provided with the
  20       distribution.
  21
  22    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33    POSSIBILITY OF SUCH DAMAGE.
  34*/
  35
  36:- module(aggregate,
  37          [ foreach/2,                  % :Generator, :Goal
  38            aggregate/3,                % +Templ, :Goal, -Result
  39            aggregate/4,                % +Templ, +Discrim, :Goal, -Result
  40            aggregate_all/3,            % +Templ, :Goal, -Result
  41            aggregate_all/4,            % +Templ, +Discrim, :Goal, -Result
  42            free_variables/4            % :Generator, :Template, +Vars0, -Vars
  43          ]).
  44:- use_module(library(ordsets)).
  45:- use_module(library(pairs)).
  46:- use_module(library(error)).
  47:- use_module(library(lists)).
  48:- use_module(library(apply)).
  49
  50:- meta_predicate
  51    foreach(0,0),
  52    aggregate(?,^,-),
  53    aggregate(?,?,^,-),
  54    aggregate_all(?,0,-),
  55    aggregate_all(?,?,0,-).
  56
  57/** <module> Aggregation operators on backtrackable predicates
  58
  59This library provides aggregating operators  over   the  solutions  of a
  60predicate. The operations are a generalisation   of the bagof/3, setof/3
  61and findall/3 built-in predicates. The   defined  aggregation operations
  62are counting, computing the sum, minimum,   maximum,  a bag of solutions
  63and a set of solutions. We first   give  a simple example, computing the
  64country with the smallest area:
  65
  66==
  67smallest_country(Name, Area) :-
  68        aggregate(min(A, N), country(N, A), min(Area, Name)).
  69==
  70
  71There are four aggregation predicates (aggregate/3, aggregate/4, aggregate_all/3 and aggregate/4), distinguished on two properties.
  72
  73    $ aggregate vs. aggregate_all :
  74    The aggregate predicates use setof/3 (aggregate/4) or bagof/3
  75    (aggregate/3), dealing with existential qualified variables
  76    (Var^Goal) and providing multiple solutions for the remaining free
  77    variables in Goal. The aggregate_all/3 predicate uses findall/3,
  78    implicitly qualifying all free variables and providing exactly one
  79    solution, while aggregate_all/4 uses sort/2 over solutions that
  80    Discriminator (see below) generated using findall/3.
  81
  82    $ The Discriminator argument :
  83    The versions with 4 arguments deduplicate redundant solutions of
  84    Goal. Solutions for which both the template variables and
  85    Discriminator are identical will be treated as one solution. For
  86    example, if we wish to compute the total population of all
  87    countries, and for some reason =|country(belgium, 11000000)|= may
  88    succeed twice, we can use the following to avoid counting the
  89    population of Belgium twice:
  90
  91    ==
  92        aggregate(sum(P), Name, country(Name, P), Total)
  93    ==
  94
  95All aggregation predicates support  the   following  operators  below in
  96Template. In addition, they allow for  an arbitrary named compound term,
  97where each of the arguments is a term  from the list below. For example,
  98the term r(min(X), max(X)) computes both the minimum and maximum binding
  99for X.
 100
 101        * count
 102        Count number of solutions.  Same as sum(1).
 103        * sum(Expr)
 104        Sum of Expr for all solutions.
 105        * min(Expr)
 106        Minimum of Expr for all solutions.
 107        * min(Expr, Witness)
 108        A term min(Min, Witness), where Min is the minimal version
 109        of Expr over all solutions, and Witness is any other template
 110        applied to solutions that produced Min.  If multiple
 111        solutions provide the same minimum, Witness corresponds to
 112        the first solution.
 113        * max(Expr)
 114        Maximum of Expr for all solutions.
 115        * max(Expr, Witness)
 116        As min(Expr, Witness), but producing the maximum result.
 117        * set(X)
 118        An ordered set with all solutions for X.
 119        * bag(X)
 120        A list of all solutions for X.
 121
 122*Acknowledgements*
 123
 124_|The development of this library was sponsored by SecuritEase,
 125  http://www.securitease.com
 126|_
 127
 128@compat Quintus, SICStus 4. The forall/2 is a SWI-Prolog built-in and
 129        term_variables/3 is a SWI-Prolog built-in with
 130        *|different semantics|*.
 131@tbd    Analysing the aggregation template and compiling a predicate
 132        for the list aggregation can be done at compile time.
 133@tbd    aggregate_all/3 can be rewritten to run in constant space using
 134        non-backtrackable assignment on a term.
 135*/
 136
 137                 /*******************************
 138                 *           AGGREGATE          *
 139                 *******************************/
 140
 141%!  aggregate(+Template, :Goal, -Result) is nondet.
 142%
 143%   Aggregate bindings in Goal according to Template.  The aggregate/3
 144%   version performs bagof/3 on Goal.
 145
 146aggregate(Template, Goal0, Result) :-
 147    template_to_pattern(bag, Template, Pattern, Goal0, Goal, Aggregate),
 148    bagof(Pattern, Goal, List),
 149    aggregate_list(Aggregate, List, Result).
 150
 151%!  aggregate(+Template, +Discriminator, :Goal, -Result) is nondet.
 152%
 153%   Aggregate bindings in Goal according to Template.  The aggregate/4
 154%   version performs setof/3 on Goal.
 155
 156aggregate(Template, Discriminator, Goal0, Result) :-
 157    template_to_pattern(bag, Template, Pattern, Goal0, Goal, Aggregate),
 158    setof(Discriminator-Pattern, Goal, Pairs),
 159    pairs_values(Pairs, List),
 160    aggregate_list(Aggregate, List, Result).
 161
 162%!  aggregate_all(+Template, :Goal, -Result) is semidet.
 163%
 164%   Aggregate  bindings  in  Goal   according    to   Template.  The
 165%   aggregate_all/3 version performs findall/3 on   Goal.  Note that
 166%   this predicate fails if Template contains one or more of min(X),
 167%   max(X),  min(X,Witness)  or  max(X,Witness)  and   Goal  has  no
 168%   solutions, i.e., the minumum and  maximum   of  an  empty set is
 169%   undefined.
 170
 171aggregate_all(Var, _, _) :-
 172    var(Var),
 173    !,
 174    instantiation_error(Var).
 175aggregate_all(count, Goal, Count) :-
 176    !,
 177    aggregate_all(sum(1), Goal, Count).
 178aggregate_all(sum(X), Goal, Sum) :-
 179    !,
 180    State = state(0),
 181    (  call(Goal),
 182           arg(1, State, S0),
 183           S is S0 + X,
 184           nb_setarg(1, State, S),
 185           fail
 186    ;  arg(1, State, Sum)
 187    ).
 188aggregate_all(max(X), Goal, Max) :-
 189    !,
 190    State = state(X),
 191    (  call(Goal),
 192           arg(1, State, M0),
 193           M is max(M0,X),
 194           nb_setarg(1, State, M),
 195           fail
 196    ;  arg(1, State, Max),
 197           nonvar(Max)
 198    ).
 199aggregate_all(min(X), Goal, Min) :-
 200    !,
 201    State = state(X),
 202    (  call(Goal),
 203           arg(1, State, M0),
 204           M is min(M0,X),
 205           nb_setarg(1, State, M),
 206           fail
 207    ;  arg(1, State, Min),
 208           nonvar(Min)
 209    ).
 210aggregate_all(max(X,W), Goal, max(Max,Witness)) :-
 211    !,
 212    State = state(false, _Max, _Witness),
 213    (  call(Goal),
 214           (   State = state(true, Max0, _)
 215           ->  X > Max0,
 216               nb_setarg(2, State, X),
 217               nb_setarg(3, State, W)
 218           ;   number(X)
 219           ->  nb_setarg(1, State, true),
 220               nb_setarg(2, State, X),
 221               nb_setarg(3, State, W)
 222           ;   type_error(number, X)
 223           ),
 224           fail
 225    ;  State = state(true, Max, Witness)
 226    ).
 227aggregate_all(min(X,W), Goal, min(Min,Witness)) :-
 228    !,
 229    State = state(false, _Min, _Witness),
 230    (  call(Goal),
 231           (   State = state(true, Min0, _)
 232           ->  X < Min0,
 233               nb_setarg(2, State, X),
 234               nb_setarg(3, State, W)
 235           ;   number(X)
 236           ->  nb_setarg(1, State, true),
 237               nb_setarg(2, State, X),
 238               nb_setarg(3, State, W)
 239           ;   type_error(number, X)
 240           ),
 241           fail
 242    ;  State = state(true, Min, Witness)
 243    ).
 244aggregate_all(Template, Goal0, Result) :-
 245    template_to_pattern(all, Template, Pattern, Goal0, Goal, Aggregate),
 246    findall(Pattern, Goal, List),
 247    aggregate_list(Aggregate, List, Result).
 248
 249%!  aggregate_all(+Template, +Discriminator, :Goal, -Result) is semidet.
 250%
 251%   Aggregate  bindings  in  Goal   according    to   Template.  The
 252%   aggregate_all/4 version performs findall/3 followed by sort/2 on
 253%   Goal. See aggregate_all/3 to understand   why this predicate can
 254%   fail.
 255
 256aggregate_all(Template, Discriminator, Goal0, Result) :-
 257    template_to_pattern(all, Template, Pattern, Goal0, Goal, Aggregate),
 258    findall(Discriminator-Pattern, Goal, Pairs0),
 259    sort(Pairs0, Pairs),
 260    pairs_values(Pairs, List),
 261    aggregate_list(Aggregate, List, Result).
 262
 263template_to_pattern(All, Template, Pattern, Goal0, Goal, Aggregate) :-
 264    template_to_pattern(Template, Pattern, Post, Vars, Aggregate),
 265    existential_vars(Goal0, Goal1, AllVars, Vars),
 266    clean_body((Goal1, Post), Goal2),
 267    (   All == bag
 268    ->  add_existential_vars(AllVars, Goal2, Goal)
 269    ;   Goal = Goal2
 270    ).
 271
 272existential_vars(Var, Var) -->
 273    { var(Var) },
 274    !.
 275existential_vars(Var^G0, G) -->
 276    !,
 277    [Var],
 278    existential_vars(G0, G).
 279existential_vars(M:G0, M:G) -->
 280    !,
 281    existential_vars(G0, G).
 282existential_vars(G, G) -->
 283    [].
 284
 285add_existential_vars([], G, G).
 286add_existential_vars([H|T], G0, H^G1) :-
 287    add_existential_vars(T, G0, G1).
 288
 289
 290%!  clean_body(+Goal0, -Goal) is det.
 291%
 292%   Remove redundant =true= from Goal0.
 293
 294clean_body((Goal0,Goal1), Goal) :-
 295    !,
 296    clean_body(Goal0, GoalA),
 297    clean_body(Goal1, GoalB),
 298    (   GoalA == true
 299    ->  Goal = GoalB
 300    ;   GoalB == true
 301    ->  Goal = GoalA
 302    ;   Goal = (GoalA,GoalB)
 303    ).
 304clean_body(Goal, Goal).
 305
 306
 307%!  template_to_pattern(+Template, -Pattern, -Post, -Vars, -Aggregate)
 308%
 309%   Determine which parts of the goal we must remember in the
 310%   findall/3 pattern.
 311%
 312%   @param Post is a body-term that evaluates expressions to reduce
 313%               storage requirements.
 314%   @param Vars is a list of intermediate variables that must be
 315%               added to the existential variables for bagof/3.
 316%   @param Aggregate defines the aggregation operation to execute.
 317
 318template_to_pattern(Term, Pattern, Goal, Vars, Aggregate) :-
 319    templ_to_pattern(Term, Pattern, Goal, Vars, Aggregate),
 320    !.
 321template_to_pattern(Term, Pattern, Goal, Vars, term(MinNeeded, Functor, AggregateArgs)) :-
 322    compound(Term),
 323    !,
 324    Term =.. [Functor|Args0],
 325    templates_to_patterns(Args0, Args, Goal, Vars, AggregateArgs),
 326    needs_one(AggregateArgs, MinNeeded),
 327    Pattern =.. [Functor|Args].
 328template_to_pattern(Term, _, _, _, _) :-
 329    invalid_template(Term).
 330
 331templ_to_pattern(sum(X),           X,         true,    [],   sum) :- var(X), !.
 332templ_to_pattern(sum(X0),          X,         X is X0, [X0], sum) :- !.
 333templ_to_pattern(count,            1,         true,    [],   count) :- !.
 334templ_to_pattern(min(X),           X,         true,    [],   min) :- var(X), !.
 335templ_to_pattern(min(X0),          X,         X is X0, [X0], min) :- !.
 336templ_to_pattern(min(X0, Witness), X-Witness, X is X0, [X0], min_witness) :- !.
 337templ_to_pattern(max(X0),          X,         X is X0, [X0], max) :- !.
 338templ_to_pattern(max(X0, Witness), X-Witness, X is X0, [X0], max_witness) :- !.
 339templ_to_pattern(set(X),           X,         true,    [],   set) :- !.
 340templ_to_pattern(bag(X),           X,         true,    [],   bag) :- !.
 341
 342templates_to_patterns([], [], true, [], []).
 343templates_to_patterns([H0], [H], G, Vars, [A]) :-
 344    !,
 345    sub_template_to_pattern(H0, H, G, Vars, A).
 346templates_to_patterns([H0|T0], [H|T], (G0,G), Vars, [A0|A]) :-
 347    sub_template_to_pattern(H0, H, G0, V0, A0),
 348    append(V0, RV, Vars),
 349    templates_to_patterns(T0, T, G, RV, A).
 350
 351sub_template_to_pattern(Term, Pattern, Goal, Vars, Aggregate) :-
 352    templ_to_pattern(Term, Pattern, Goal, Vars, Aggregate),
 353    !.
 354sub_template_to_pattern(Term, _, _, _, _) :-
 355    invalid_template(Term).
 356
 357invalid_template(Term) :-
 358    callable(Term),
 359    !,
 360    domain_error(aggregate_template, Term).
 361invalid_template(Term) :-
 362    type_error(aggregate_template, Term).
 363
 364%!  needs_one(+Ops, -OneOrZero)
 365%
 366%   If one of the operations in Ops needs at least one answer,
 367%   unify OneOrZero to 1.  Else 0.
 368
 369needs_one(Ops, 1) :-
 370    member(Op, Ops),
 371    needs_one(Op),
 372    !.
 373needs_one(_, 0).
 374
 375needs_one(min).
 376needs_one(min_witness).
 377needs_one(max).
 378needs_one(max_witness).
 379
 380%!  aggregate_list(+Op, +List, -Answer) is semidet.
 381%
 382%   Aggregate the answer  from  the   list  produced  by  findall/3,
 383%   bagof/3 or setof/3. The latter  two   cases  deal  with compound
 384%   answers.
 385%
 386%   @tbd    Compile code for incremental state update, which we will use
 387%           for aggregate_all/3 as well.  We should be using goal_expansion
 388%           to generate these clauses.
 389
 390aggregate_list(bag, List0, List) :-
 391    !,
 392    List = List0.
 393aggregate_list(set, List, Set) :-
 394    !,
 395    sort(List, Set).
 396aggregate_list(sum, List, Sum) :-
 397    sum_list(List, Sum).
 398aggregate_list(count, List, Count) :-
 399    length(List, Count).
 400aggregate_list(max, List, Sum) :-
 401    max_list(List, Sum).
 402aggregate_list(max_witness, List, max(Max, Witness)) :-
 403    max_pair(List, Max, Witness).
 404aggregate_list(min, List, Sum) :-
 405    min_list(List, Sum).
 406aggregate_list(min_witness, List, min(Min, Witness)) :-
 407    min_pair(List, Min, Witness).
 408aggregate_list(term(0, Functor, Ops), List, Result) :-
 409    !,
 410    maplist(state0, Ops, StateArgs, FinishArgs),
 411    State0 =.. [Functor|StateArgs],
 412    aggregate_term_list(List, Ops, State0, Result0),
 413    finish_result(Ops, FinishArgs, Result0, Result).
 414aggregate_list(term(1, Functor, Ops), [H|List], Result) :-
 415    H =.. [Functor|Args],
 416    maplist(state1, Ops, Args, StateArgs, FinishArgs),
 417    State0 =.. [Functor|StateArgs],
 418    aggregate_term_list(List, Ops, State0, Result0),
 419    finish_result(Ops, FinishArgs, Result0, Result).
 420
 421aggregate_term_list([], _, State, State).
 422aggregate_term_list([H|T], Ops, State0, State) :-
 423    step_term(Ops, H, State0, State1),
 424    aggregate_term_list(T, Ops, State1, State).
 425
 426
 427%!  min_pair(+Pairs, -Key, -Value) is det.
 428%!  max_pair(+Pairs, -Key, -Value) is det.
 429%
 430%   True if Key-Value has the  smallest/largest   key  in  Pairs. If
 431%   multiple pairs share the smallest/largest key, the first pair is
 432%   returned.
 433
 434min_pair([M0-W0|T], M, W) :-
 435    min_pair(T, M0, W0, M, W).
 436
 437min_pair([], M, W, M, W).
 438min_pair([M0-W0|T], M1, W1, M, W) :-
 439    (   M0 < M1
 440    ->  min_pair(T, M0, W0, M, W)
 441    ;   min_pair(T, M1, W1, M, W)
 442    ).
 443
 444max_pair([M0-W0|T], M, W) :-
 445    max_pair(T, M0, W0, M, W).
 446
 447max_pair([], M, W, M, W).
 448max_pair([M0-W0|T], M1, W1, M, W) :-
 449    (   M0 > M1
 450    ->  max_pair(T, M0, W0, M, W)
 451    ;   max_pair(T, M1, W1, M, W)
 452    ).
 453
 454%!  step(+AggregateAction, +New, +State0, -State1).
 455
 456step(bag,   X, [X|L], L).
 457step(set,   X, [X|L], L).
 458step(count, _, X0, X1) :-
 459    succ(X0, X1).
 460step(sum,   X, X0, X1) :-
 461    X1 is X0+X.
 462step(max,   X, X0, X1) :-
 463    X1 is max(X0, X).
 464step(min,   X, X0, X1) :-
 465    X1 is min(X0, X).
 466step(max_witness, X-W, X0-W0, X1-W1) :-
 467    (   X > X0
 468    ->  X1 = X, W1 = W
 469    ;   X1 = X0, W1 = W0
 470    ).
 471step(min_witness, X-W, X0-W0, X1-W1) :-
 472    (   X < X0
 473    ->  X1 = X, W1 = W
 474    ;   X1 = X0, W1 = W0
 475    ).
 476step(term(Ops), Row, Row0, Row1) :-
 477    step_term(Ops, Row, Row0, Row1).
 478
 479step_term(Ops, Row, Row0, Row1) :-
 480    functor(Row, Name, Arity),
 481    functor(Row1, Name, Arity),
 482    step_list(Ops, 1, Row, Row0, Row1).
 483
 484step_list([], _, _, _, _).
 485step_list([Op|OpT], Arg, Row, Row0, Row1) :-
 486    arg(Arg, Row, X),
 487    arg(Arg, Row0, X0),
 488    arg(Arg, Row1, X1),
 489    step(Op, X, X0, X1),
 490    succ(Arg, Arg1),
 491    step_list(OpT, Arg1, Row, Row0, Row1).
 492
 493finish_result(Ops, Finish, R0, R) :-
 494    functor(R0, Functor, Arity),
 495    functor(R, Functor, Arity),
 496    finish_result(Ops, Finish, 1, R0, R).
 497
 498finish_result([], _, _, _, _).
 499finish_result([Op|OpT], [F|FT], I, R0, R) :-
 500    arg(I, R0, A0),
 501    arg(I, R, A),
 502    finish_result1(Op, F, A0, A),
 503    succ(I, I2),
 504    finish_result(OpT, FT, I2, R0, R).
 505
 506finish_result1(bag, Bag0, [], Bag) :-
 507    !,
 508    Bag = Bag0.
 509finish_result1(set, Bag,  [], Set) :-
 510    !,
 511    sort(Bag, Set).
 512finish_result1(max_witness, _, M-W, R) :-
 513    !,
 514    R = max(M,W).
 515finish_result1(min_witness, _, M-W, R) :-
 516    !,
 517    R = min(M,W).
 518finish_result1(_, _, A, A).
 519
 520%!  state0(+Op, -State, -Finish)
 521
 522state0(bag,   L, L).
 523state0(set,   L, L).
 524state0(count, 0, _).
 525state0(sum,   0, _).
 526
 527%!  state1(+Op, +First, -State, -Finish)
 528
 529state1(bag, X, L, [X|L]) :- !.
 530state1(set, X, L, [X|L]) :- !.
 531state1(_,   X, X, _).
 532
 533
 534                 /*******************************
 535                 *             FOREACH          *
 536                 *******************************/
 537
 538%!  foreach(:Generator, :Goal)
 539%
 540%   True if conjunction of results is   true. Unlike forall/2, which
 541%   runs a failure-driven loop that proves Goal for each solution of
 542%   Generator, foreach/2 creates a conjunction.   Each member of the
 543%   conjunction is a copy of  Goal,   where  the variables it shares
 544%   with Generator are filled with the values from the corresponding
 545%   solution.
 546%
 547%   The implementation executes forall/2 if   Goal  does not contain
 548%   any variables that are not shared with Generator.
 549%
 550%   Here is an example:
 551%
 552%   ==
 553%   ?- foreach(between(1,4,X), dif(X,Y)), Y = 5.
 554%   Y = 5.
 555%   ?- foreach(between(1,4,X), dif(X,Y)), Y = 3.
 556%   false.
 557%   ==
 558%
 559%   @bug    Goal is copied repeatedly, which may cause problems if
 560%           attributed variables are involved.
 561
 562foreach(Generator, Goal) :-
 563    term_variables(Generator, GenVars0), sort(GenVars0, GenVars),
 564    term_variables(Goal, GoalVars0), sort(GoalVars0, GoalVars),
 565    ord_subtract(GoalVars, GenVars, SharedGoalVars),
 566    (   SharedGoalVars == []
 567    ->  \+ (Generator, \+Goal)      % = forall(Generator, Goal)
 568    ;   ord_intersection(GenVars, GoalVars, SharedVars),
 569        Templ =.. [v|SharedVars],
 570        SharedTempl =.. [v|SharedGoalVars],
 571        findall(Templ, Generator, List),
 572        prove_list(List, Templ, SharedTempl, Goal)
 573    ).
 574
 575prove_list([], _, _, _).
 576prove_list([H|T], Templ, SharedTempl, Goal) :-
 577    copy_term(Templ+SharedTempl+Goal,
 578              H+SharedTempl+Copy),
 579    Copy,
 580    prove_list(T, Templ, SharedTempl, Goal).
 581
 582
 583%!  free_variables(:Generator, +Template, +VarList0, -VarList) is det.
 584%
 585%   Find free variables in bagof/setof template.  In order to handle
 586%   variables  properly,  we  have  to   find  all  the  universally
 587%   quantified variables in the  Generator.   All  variables  as yet
 588%   unbound are universally quantified, unless
 589%
 590%       1. they occur in the template
 591%       2. they are bound by X^P, setof/3, or bagof/3
 592%
 593%   free_variables(Generator, Template, OldList, NewList) finds this
 594%   set using OldList as an accumulator.
 595%
 596%   @author Richard O'Keefe
 597%   @author Jan Wielemaker (made some SWI-Prolog enhancements)
 598%   @license Public domain (from DEC10 library).
 599%   @tbd Distinguish between control-structures and data terms.
 600%   @tbd Exploit our built-in term_variables/2 at some places?
 601
 602free_variables(Term, Bound, VarList, [Term|VarList]) :-
 603    var(Term),
 604    term_is_free_of(Bound, Term),
 605    list_is_free_of(VarList, Term),
 606    !.
 607free_variables(Term, _Bound, VarList, VarList) :-
 608    var(Term),
 609    !.
 610free_variables(Term, Bound, OldList, NewList) :-
 611    explicit_binding(Term, Bound, NewTerm, NewBound),
 612    !,
 613    free_variables(NewTerm, NewBound, OldList, NewList).
 614free_variables(Term, Bound, OldList, NewList) :-
 615    functor(Term, _, N),
 616    free_variables(N, Term, Bound, OldList, NewList).
 617
 618free_variables(0, _, _, VarList, VarList) :- !.
 619free_variables(N, Term, Bound, OldList, NewList) :-
 620    arg(N, Term, Argument),
 621    free_variables(Argument, Bound, OldList, MidList),
 622    M is N-1,
 623    !,
 624    free_variables(M, Term, Bound, MidList, NewList).
 625
 626%   explicit_binding checks for goals known to existentially quantify
 627%   one or more variables.  In particular \+ is quite common.
 628
 629explicit_binding(\+ _Goal,             Bound, fail,     Bound      ) :- !.
 630explicit_binding(not(_Goal),           Bound, fail,     Bound      ) :- !.
 631explicit_binding(Var^Goal,             Bound, Goal,     Bound+Var) :- !.
 632explicit_binding(setof(Var,Goal,Set),  Bound, Goal-Set, Bound+Var) :- !.
 633explicit_binding(bagof(Var,Goal,Bag),  Bound, Goal-Bag, Bound+Var) :- !.
 634
 635%!  term_is_free_of(+Term, +Var) is semidet.
 636%
 637%   True if Var does not appear  in   Term.  This has been rewritten
 638%   from the DEC10 library source   to exploit our non-deterministic
 639%   arg/3.
 640
 641term_is_free_of(Term, Var) :-
 642    \+ var_in_term(Term, Var).
 643
 644var_in_term(Term, Var) :-
 645    Var == Term,
 646    !.
 647var_in_term(Term, Var) :-
 648    compound(Term),
 649    arg(_, Term, Arg),
 650    var_in_term(Arg, Var),
 651    !.
 652
 653
 654%!  list_is_free_of(+List, +Var) is semidet.
 655%
 656%   True if Var is not in List.
 657
 658list_is_free_of([Head|Tail], Var) :-
 659    Head \== Var,
 660    !,
 661    list_is_free_of(Tail, Var).
 662list_is_free_of([], _).
 663
 664
 665%       term_variables(+Term, +Vars0, -Vars) is det.
 666%
 667%       True if Vars is the union of variables in Term and Vars0.
 668%       We cannot have this as term_variables/3 is already defined
 669%       as a difference-list version of term_variables/2.
 670
 671%term_variables(Term, Vars0, Vars) :-
 672%       term_variables(Term+Vars0, Vars).
 673
 674
 675%!  sandbox:safe_meta(+Goal, -Called) is semidet.
 676%
 677%   Declare the aggregate meta-calls safe. This cannot be proven due
 678%   to the manipulations of the argument Goal.
 679
 680:- multifile sandbox:safe_meta_predicate/1.
 681
 682sandbox:safe_meta_predicate(aggregate:foreach/2).
 683sandbox:safe_meta_predicate(aggregate:aggregate/3).
 684sandbox:safe_meta_predicate(aggregate:aggregate/4).
 685sandbox:safe_meta_predicate(aggregate:aggregate_all/3).
 686sandbox:safe_meta_predicate(aggregate:aggregate_all/4).