Monotonic tabling without actual dynamic predicate asserts?

Help!
1

Let’s say I have an external system that provides information to my Prolog program. I can both query that system by making a request to it via dedicated predicate, or that system can push a message when new information is available and I can register a corresponding hook.

get_info(P1, P2, P3)      % query info from external system

hook_added(add_hook)      % add_hook(P1,P2,P3) when new info comes

hook_deleted(delete_hook) % delete_hook(P1,P2,P3) when info is removed

Now, I want to do some reasoning with monotonic tabling based on this info, but I don’t want to copy the info itself into Prolog dynamic predicate (assume querying is cheap and info is huge).

:- table reason/1 as monotonic.
:- dynamic get_info/3 as monotonic.

reason(Result) :-
   ...
   get_info(X, Y, Z),
   ...

add_hook(P1, P2, P3) :-
  ? % need something here to update IDG without asserta(get_info...)

delete_hook(P1, P2, P3) :-
  incr_invalidate_calls(get_info(P1, P2, P3)).

Question: does it make sense to introduce a documented method of updating dependency on dynamic predicate without updating the Prolog database?

I mean, something like '$tabling':mon_propagate(asserta, get_info(P1,P2,P3), Ref) triggered not by prolog event, but by add_hook and, of course, there is no Ref.

XSB seems to have incr_trie_intern/2 for similar purpose.

1 Like
2

Good question! The delete_hook/3 probably works fine. The add_hook/3 should indeed call mon_propagate/3. This should work as is for the (default) eagerly monotonic tables. The lazy version is harder as we need a clause reference to store in the monotonic dependency queue. Well, maybe we can simply use the eager propagation for a lazy table in the case.

Did you give it a try to call the internal mon_propagate/3?

This is not the same as incr_trie_intern/2 as that points at a trie (tabled predicate) while this deals with a dynamic predicate. It could be an interesting option to avoid duplicating data that is already externally available.

I propose to move the increeval.pl library to the core library and add two new predicates to deal with the add and delete hook. What would be good names? incr_new_fact/1 and incr_delete_fact/1?

2 Likes
3

Yes, I tried with mon_propagate/3 and fake Ref and it seems to work, but I’m doubtful about correctness in all cases as Ref is actually used by '$mono_idg_changed' and I’m not on top of the implementation just yet. What is this Ref used for later? And you’re right, it segfaults with fake Ref and lazy tabling.

I fully support moving increeval.pl to the core! The proposed names also work, we may vote here :slight_smile: Alternatively, incr_propagate_call/1, and leave incr_invalidate_call/1.

4

Found unrelated issue with monotonic tabling (reproducible with and without my hack). Probably a symptom of a bug.

There is an extra choice point left in reason/1 after a pair of add/delete calls that wasn’t there before. It is left when delete invalidates the last call, i.e. add(1),add(2),delete(1) doesn’t leave it, but add(1),add(2),delete(2) does (given the order is not changed by tabling). It also segfaults if I start graphical tracing of that choice point.

Code 
:- module(monotonic, []).

:- use_module(library(dialect/xsb/increval)).

:- table reason/1 as monotonic.
:- dynamic get_info/1 as monotonic.

reason(bb) :-
    get_info(b),
    get_info(1).
reason(aa) :-
    get_info(a),
    get_info(1).
reason(cc) :-
    get_info(c),
    get_info(1).

:- dynamic source/1.

get_info(X) :-
  format('checking get_info(~w)~n', [X]),
  source(X).

source(a).
source(1).

addf(X) :-
  assertz(source(X)),
  '$tabling':mon_propagate(asserta, monotonic:get_info(X), '').

delf(X) :-
  retract(source(X)),
  incr_invalidate_calls(monotonic:get_info(X)).

:- prolog_listen(reason/1, reason_change).

reason_change(new_answer, _:reason(X)) :-
  format('Inferred (~w) ~n', [X]).
Issue 
% The graphical front-end will be used for subsequent tracing
Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.23)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- reason(X).
checking get_info(b)
checking get_info(a)
checking get_info(1)
checking get_info(c)
X = aa.

?- addf(c).
checking get_info(c)
checking get_info(1)
Inferred (cc)
true.

?- reason(X).
X = cc ;
X = aa.

?- addf(b).
checking get_info(b)
checking get_info(1)
Inferred (bb)
true.

?- reason(X).
X = cc ;
X = aa ;
X = bb.

?- delf(b).
true.

?- reason(X).
checking get_info(b)
checking get_info(a)
checking get_info(1)
checking get_info(c)
checking get_info(1)
X = cc ;
X = aa ;
false.          %  <========= EXTRA CHOICE POINT

?- trace.
true.

[trace]  ?- reason(X).
X = cc ;
X = aa ;

SWI-Prolog [thread 1 (main) at Wed May  5 18:34:57 2021]: received fatal signal 11 (segv)
C-stack trace labeled "crash":
  [0] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(save_backtrace+0x62) [0x1064c0a42]
  [1] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(print_c_backtrace+0x15) [0x1064c1345]
  [2] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(sigCrashHandler+0x146) [0x1064c1236]
  [3] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(dispatch_signal+0x3fe) [0x106407fbe]
  [4] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(pl_signal_handler+0x15) [0x10640aa55]
  [5] /usr/lib/system/libsystem_platform.dylib(_sigtramp+0x1d) [0x7fff701fc5fd]
  [7] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(replacedBreakUnlocked+0x53) [0x1063990e3]
  [8] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(replacedBreak+0x3e) [0x106395a6e]
  [9] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(fetchop+0x3b) [0x1063b408b]
  [10] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(clearUninitialisedVarsFrame+0x29) [0x1063b3bf9]
  [11] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(clear_frame_vars+0x8d) [0x1064133ad]
  [12] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(prolog_frame_attribute+0x547) [0x1064128c7]
  [13] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(pl_prolog_frame_attribute3_va+0x37) [0x106411017]
  [14] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(PL_next_solution+0xfcef) [0x10635412f]
  [15] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(callProlog+0x289) [0x1063df9f9]
  [16] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(pl_notrace1_va+0x54) [0x1063e0cc4]
  [17] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(PL_next_solution+0xfcef) [0x10635412f]
  [18] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(traceInterception+0x620) [0x10640cd90]
  [19] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(tracePort+0x9be) [0x10640bcbe]
  [20] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(PL_next_solution+0x804b) [0x10634c48b]
  [21] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(query_loop+0xf0) [0x1063df160]
  [22] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(prologToplevel+0x7a) [0x1063dfd0a]
  [23] /usr/local/Cellar/swipl/8.3.23/libexec/lib/swipl/lib/x86_64-darwin/libswipl.8.3.23.dylib(PL_toplevel+0x21) [0x10636e301]
  [24] /usr/local/Cellar/swipl/8.3.23/libexec/bin/swipl(main+0x44) [0x106324f14]
  [25] /usr/lib/system/libdyld.dylib(start+0x1) [0x7fff70003cc9]
Prolog stack:
  [36] prolog_frame_attribute/3 [PC=1 in supervisor]
  [35] pce_prolog_tracer:find_frame/5 [PC=34 in clause 1]
  [34] pce_prolog_tracer:show/5 [PC=11 in clause 1]
  [33] pce_prolog_tracer:show/4 [PC=10 in clause 2]
  [32] pce_prolog_tracer:do_intercept_/4 [PC=109 in clause 1]
  [31] system:setup_call_catcher_cleanup/4 [PC=5 in clause 1]
  [27] pce_prolog_tracer:intercept_/4 [PC=48 in clause 1]
  [26] system:setup_call_catcher_cleanup/4 [PC=5 in clause 1]
  [22] system:$c_call_prolog/0 [PC=0 in top query clause]
  [21] notrace/1 <foreign>
  [20] pce_prolog_tracer:prolog_trace_interception_gui/4 [PC=23 in clause 1]
  [19] system:setup_call_catcher_cleanup/4 [PC=5 in clause 1]
  [15] system:$c_call_prolog/0 [PC=0 in top query clause]
  [14] system:fail/0 <foreign>
  [13] system:trie_gen_compiled/2 [PC=-1 in clause 1]
  [12] $tabling:start_tabling_2/6 [PC=25 in clause 1]
  [11] start_tabling/3 [PC=75 in clause 1]
  [10] monotonic:$wrap$reason/1 [PC=21 in clause 1]
  [9] $toplevel:toplevel_call/1 [PC=3 in clause 1]
  [8] $toplevel:stop_backtrace/1 [PC=4 in clause 1]
  [7] $tabling:$wfs_call/2 [PC=17 in clause 1]
  [6] $toplevel:residue_vars/3 [PC=11 in clause 2]
  [5] $toplevel:$execute_goal2/3 [PC=29 in clause 1]
  [3] $toplevel:$query_loop/0 [PC=39 in clause 2]
  [2] $toplevel:$runtoplevel/0 [PC=19 in clause 1]
Running on_halt hooks with status 139
Killing 46507 with default signal handlers
Segmentation fault: 11
1 Like
5

Ok. Moved library(increval) to core library. If you use use_module(library(dialect/xsb/increval)) you must adjust the code to simply use_module(library(increval)). Trying to maintain compatibility by providing both seems a bit over the top for a library of which few people are aware of its existence.

Added incr_propagate_answer/1 and incr_invalidate_answer/1. to the above library I think answer is a better name than call, but while I’m writing this I start to doubt. What was your reason for call?

This can be the result of compiling tries that hold deleted nodes. Ideally we should probably optimize that. I’m a bit reluctant as this is far from trivial and probably requires a two pass compilation procedure while compiling tries can be a significant part of the cost. Of course this should not crash. Fixed that.

1 Like
6

Works like a charm! One day request-to-implementation is unprecedented level of support, thanks, Jan!

Mostly, to follow XSB’s naming, and somehow it made sense to me, because nobody is actually asking for an answer, but rather notifying that a call will be answered if made. No strong preferences on naming as long as the meaning is clear.

1 Like
7

That was my misconception. My initial thought (and misconception) is that you are feeding in an answer, but in fact you are indeed feeding in a possible goal/call that may result in answers. In the normal case you feed in the head of a new clause and thus any goal that unifies with this head may yield new answers. I’ll rename this while it is still possible.

2 Likes
8

Ok. Renamed to incr_propagate_calls/1 (note the s) with the already present incr_invalidate_calls/1 as its companion. Regarding the s: all similar XSB predicates use the plural form if all unifying terms are implied and the singular form if a specific variant is addressed. There is incr_invalidate_call/1 with this comment:

This is the XSB name, but the manual says incr_invalidate_calls/1 and the comment with the code suggests this is misnamed.

I deprecated incr_invalidate_call/1.

This should be it (possibly with some bugs I leave as an exercise for you to find :slight_smile: )

9

The API is getting cleaner and cleaner, I like it.

In the meanwhile, I found another issue. The following code works fine for monotonic tabling, but doesn’t work, if I add “shared” option:

:- table a/2 as (monotonic,shared).

a(X, b) :-
  a(c, X).
a(X, a) :-
  a(X, b).

Instead I get an exception:

?- a(a, _).
ERROR: Unhandled exception: Type error: `trie' expected, found `fail' (an atom)
ERROR: In:
ERROR:   [31] '$idg_add_monotonic_dep'(fail,dependency(ret,_418,call_continuation(...),ret),<trie>(0x7ff48dc1bf20))
ERROR:   [29] delim(ret,'<garbage_collected>',140688327032784,[]) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:606
ERROR:   [28] activate(ret,'<garbage_collected>',140688327032784) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:584
ERROR:   [27] run_leader(ret,'<garbage_collected>','<garbage_collected>',_514,_516) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:570
ERROR:   [26] setup_call_catcher_cleanup('$tabling':'$idg_set_current'(<trie>(0x7ff48fb50380),<trie>(0x7ff48dc1bf20)),'$tabling':run_leader(ret,...,...,_574,_576),_544,'$tabling':finished_leader(<trie>(0x7ff48fb50380),_588,...,...)) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:646
ERROR:   [25] create_table(<trie>(0x7ff48dc1bf20),fresh(140688327435904,140688327032784),ret,'<garbage_collected>','<garbage_collected>') at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:384
ERROR:   [24] catch('$tabling':create_table(<trie>(0x7ff48dc1bf20),...,ret,...,...),deadlock,'$tabling':restart_tabling(<closure>(a/2),...,...)) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:546
ERROR:   [21] call_continuation('<garbage_collected>') at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:601
ERROR:   [20] reset('<garbage_collected>',_740,_742) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:572
ERROR:   [19] delim(ret(a),'<garbage_collected>',140688359752944,[]) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:606
ERROR:   [17] activate('<garbage_collected>','<garbage_collected>',140688359752944) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:584
ERROR:   [16] run_leader(ret(a),'<garbage_collected>','<garbage_collected>',_834,_836) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:570
ERROR:   [15] setup_call_catcher_cleanup('$tabling':'$idg_set_current'(_880,<trie>(0x7ff48fb50380)),'$tabling':run_leader(...,...,...,_898,_900),_868,'$tabling':finished_leader(_910,_912,...,...)) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:646
ERROR:   [14] create_table(<trie>(0x7ff48fb50380),fresh(140688359752864,140688359752944),ret(a),'<garbage_collected>','<garbage_collected>') at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:384
ERROR:   [13] catch('$tabling':create_table(<trie>(0x7ff48fb50380),...,...,...,...),deadlock,'$tabling':restart_tabling(<closure>(a/2),...,...)) at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/init.pl:546
ERROR:   [12] start_tabling_2(<closure>(a/2),'<garbage_collected>','<garbage_collected>','<garbage_collected>','<garbage_collected>','<garbage_collected>') at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/tabling.pl:370
ERROR:   [10] '$wrap$a'(a,'<garbage_collected>')1-st clause of '$wrap$a'/2 <no source>
ERROR:    [9] toplevel_call('<garbage_collected>') at /usr/local/Cellar/swipl/HEAD-2589a45/libexec/lib/swipl/boot/toplevel.pl:1113
10

Now it is getting more serious. Fixing this is probably not too hard. There are some more issues regarding shared monotonic tabling though. Where for normal shared tabling we have synchronization for a thread grabbing an invalid table (first does the evaluation, others wait while we watch out for deadlocks of multiple threads waiting for each other), shared monotonic evaluation is a different beast that requires more thought on how to deal with concurrency.

If you are serious about this stuff, please contact me offline so we can see what we can do in what time frame.

11

I see, no, nothing serious depends on it, I’m just experimenting with monotonic tabling feature to see what’s possible, and trying to come up with various design patterns that may be useful in my daily work. I thought you might be interested in simple test cases like this, when stabilising the code.

1 Like
12

Would you post these patterns? I think it would be useful for all of us. Thanks!