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) 2019-2021, VU University Amsterdam 7 SWI-Prolog Solutions b.v. 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(increval, 37 [ incr_assert/1, % :Clause 38 incr_asserta/1, % :Clause 39 incr_assertz/1, % :Clause 40 incr_retractall/1, % :Head 41 incr_retract/1, % :Clause 42 43 is_incremental_subgoal/1, % :Goal 44 incr_directly_depends/2, % :Goal1, :Goal2 45 incr_trans_depends/2, % :Goal1, :Goal2 46 incr_invalid_subgoals/1, % -List 47 incr_is_invalid/1, % :Goal 48 49 incr_invalidate_call/1, % :Goal 50 incr_invalidate_calls/1, % :Goal 51 incr_table_update/0, 52 53 incr_propagate_calls/1 % :Answer 54 ]). 55:- use_module(library(tables)). 56 57/** <module> Incremental dynamic predicate modification 58 59This module emulates the XSB module `increval`. This module serves two 60goals: (1) provide alternatives for the dynamic clause manipulation 61predicates that propagate into the incremental tables and (2) query the 62dynamically maintained _Incremental Depency Graph_ (IDG). 63 64The change propagation for incremental dynamic predicates. SWI-Prolog 65relies in prolog_listen/2 to forward any change to dynamic predicates to 66the table IDG and incr_assert/1 and friends thus simply call the 67corresponding database update. 68 69@compat XSB 70*/ 71 72:- meta_predicate 73 incr_assert(), 74 incr_asserta(), 75 incr_assertz(), 76 incr_retractall(), 77 incr_retract(), 78 is_incremental_subgoal(), 79 incr_directly_depends(,), 80 incr_trans_depends(, ), 81 incr_is_invalid(), 82 incr_invalidate_call(), 83 incr_invalidate_calls(), 84 incr_propagate_calls(). 85 86incr_assert(T) :- assertz(T). 87incr_asserta(T) :- asserta(T). 88incr_assertz(T) :- assertz(T). 89incr_retractall(T) :- retractall(T). 90incr_retract(T) :- retract(T). 91 92%! is_incremental_subgoal(?SubGoal) is nondet. 93% 94% This predicate non-deterministically unifies Subgoal with 95% incrementally tabled subgoals that are currently table entries. 96 97is_incremental_subgoal(SubGoal) :- 98 '$tbl_variant_table'(VTrie), 99 trie_gen(VTrie, SubGoal, ATrie), 100 ( '$idg_edge'(ATrie, _Dir, _Value) 101 -> true 102 ). 103 104%! incr_directly_depends(:Goal1, :Goal2) is nondet. 105% 106% True if Goal1 depends on Goal2 in the IDG. 107% 108% @compat: In XSB, at least one of Goal 1 or Goal 2 must be bound. 109% This implementation may be used with both arguments unbound. 110 111incr_directly_depends(Goal1, Goal2) :- 112 '$tbl_variant_table'(VTrie), 113 ( nonvar(Goal2) 114 -> trie_gen(VTrie, Goal2, ATrie2), 115 '$idg_edge'(ATrie2, affected, ATrie1), 116 '$tbl_table_status'(ATrie1, _Status, Goal1, _Return) 117 ; trie_gen(VTrie, Goal1, ATrie1), 118 '$idg_edge'(ATrie1, dependent, ATrie2), 119 '$tbl_table_status'(ATrie2, _Status, Goal2, _Return) 120 ). 121 122%! incr_trans_depends(:Goal1, Goal2) is nondet. 123% 124% True for each pair in the transitive closure of 125% incr_directly_depends(G1, G2). 126 127incr_trans_depends(Goal1, Goal2) :- 128 '$tbl_variant_table'(VTrie), 129 ( nonvar(Goal1) 130 -> trie_gen(VTrie, Goal1, ATrie1), 131 incr_trans_depends(ATrie1, dependent, ATrie2, []), 132 '$tbl_table_status'(ATrie2, _Status, Goal2, _Return) 133 ; trie_gen(VTrie, Goal2, ATrie2), 134 incr_trans_depends(ATrie2, affected, ATrie1, []), 135 '$tbl_table_status'(ATrie1, _Status, Goal1, _Return) 136 ). 137 138incr_trans_depends(ATrie1, Dir, ATrie, Done) :- 139 '$idg_edge'(ATrie1, Dir, ATrie2), 140 \+ memberchk(ATrie2, Done), 141 ( ATrie = ATrie2 142 ; incr_trans_depends(ATrie2, Dir, ATrie, [ATrie2|Done]) 143 ). 144 145%! incr_invalid_subgoals(-List) is det. 146% 147% List is a sorted list (set) of the incremental subgoals that are 148% currently invalid. 149 150incr_invalid_subgoals(List) :- 151 findall(Invalid, invalid_subgoal(Invalid, _), List0), 152 sort(List0, List). 153 154invalid_subgoal(Goal, ATrie) :- 155 '$tbl_variant_table'(VTrie), 156 trie_gen(VTrie, Goal, ATrie), 157 ( '$idg_edge'(ATrie, _Dir, _Value) 158 -> true 159 ), 160 '$idg_falsecount'(ATrie, Count), 161 Count > 0, 162 \+ '$tbl_table_status'(ATrie, dynamic, _Goal, _Return). 163 164%! incr_is_invalid(:Subgoal) is semidet. 165% 166% True when Subgoal's table is marked as invalid. 167 168incr_is_invalid(Subgoal) :- 169 get_calls(Subgoal, Table, _Return), 170 '$idg_falsecount'(Table, Count), 171 Count > 0. 172 173%! incr_invalidate_calls(:Goal) is det. 174% 175% Invalidate all tables for subgoals of Goal as well as tables that 176% are affected by these. 177 178incr_invalidate_calls(Goal) :- 179 '$tbl_variant_table'(VTable), 180 !, 181 forall(trie_gen(VTable, Goal, ATrie), 182 '$idg_changed'(ATrie)). 183incr_invalidate_calls(_). 184 185%! incr_invalidate_call(:Goal) is det. 186% 187% This is the XSB name, but the manual says incr_invalidate_calls/1 188% and the comment with the code suggests this is misnamed. 189% 190% @deprecated Use incr_invalidate_calls/1. 191 192incr_invalidate_call(Goal) :- 193 incr_invalidate_calls(Goal). 194 195%! incr_table_update 196% 197% Updated all invalid tables 198 199incr_table_update :- 200 repeat, 201 ( invalid_subgoal(Goal, ATrie) 202 -> '$tabling':reeval(ATrie, Goal, _Return), 203 fail 204 ; ! 205 ). 206 207%! incr_propagate_calls(:Answer) is det. 208% 209% Activate the monotonic answer propagation similarly to when a new 210% fact is asserted for a monotonic dynamic predicate. The Answer term 211% must match a monotonic dynamic predicate. 212 213incr_propagate_calls(Answer) :- 214 setup_call_cleanup( 215 '$tbl_propagate_start'(Old), 216 '$tabling':incr_propagate_assert(Answer), 217 '$tbl_propagate_end'(Old))