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)