I’m considering adding some events to a Prolog API pertaining to change detection and propagation. I’m thinking about change detection and propagation where, upon assertions or retractions, all direct and indirect changes could be detected.
There could be some new API to subscribe to such direct and indirect changes to a Prolog knowledgebase. There could also be a new type of Prolog query which, after completion of a traditional query, could present an event with which to notify a caller in the event of updates. The result of a query could interface as an observable collection (see also: ObservableCollection, INotifyCollectionChanged, Bindable LINQ, Continuous LINQ, Reactive LINQ).
Does anyone know of any research into change detection and propagation with Prolog knowledgebases?
Related, Logtalk supports event-driven programming. The API allows you to define the events that you want to observe and to define monitors for those events that are automatically called by the runtime. For details, see:
The main difference with what you describe is that in this case you monitor the calls (or exits) to the predicates that make the changes, not the “raw” asserts and retracts.
The related work I know is from XSB, which uses this to implement incremental tabling. That feature will most likely be added to SWI-Prolog’s tabling as well.
Note that an event API is already present as user:prolog_even_hook/1. This doesn’t trap assert. It does trap retract (or actually erased clause references). It is used for the debugger. This needs to be generalized. As is, the hook has significant impact on performance. This is fine for debugging, but I think the new one should be able to register a hook using an event mask, such that we can trap only the stuff we are interested in and have multiple hooks.
Go ahead with proposing a generalization of the current API. Be aware it is used in several highly time critical places.
Thank you. I, for one, might need some time before offering a fuller proposal here.
Some preliminary topics to consider include: encapsulating the making of an incremental table for a query, mapping a query to a rule with a new, dynamic, incrementally-tabled predicate as its head. We could consider extending the SWI-Prolog foreign language interface to include some exported functions with which to implement higher-level API in .NET for tables, e.g. PrologTable which could implement functionality including: IEnumerable and INotifyCollectionChanged. Topics to consider, in that regard, include subscribing to incremental tabling events, for specific tables, using function pointer callbacks, as well as unsubscribing from such events.
There are, then, higher-level API topics to consider and SWI-Prolog foreign language interface API topics to consider and all while mindful of time-critical performance.
We could also, perhaps, consider new builtin predicates like: assert_list/1, retract_list/1 and retract_assert_lists/2 which could atomically assert a list of terms, retract a list of terms, and retract one list of terms while asserting another. These could be designed to assert, retract and simultaneously retract and assert collections of terms atomically instead of via iteration of other atomic builtin predicates. Interestingly, retract_assert_lists/2 resembles the processing of a knowledgebase delta, diff or update and also resembles processing the effects of actions (see also: PDDL) which can modeled as retracting some terms while asserting others.
Interesting points. What I have in mind right now is something like prolog_register_event_hook(+Events, :Predicate), where Events is a list of event-type identifiers, mapped to a C bitmap. Then there is a C linked list mapping masks to a predicate pointer. I think that both provides the performance and flexibility. What is added on top of that is something to worry about later.
I once wrote a ciclops workshop paper proposing database transactions. A lot of the work for that has been done as reloading a source file is currently implemented as an atomic transaction. For dynamic databases there are a few more interesting opportunities. One is XSB’s trie store. An other is (I think Ciao) option to have a thread waiting on asserted clauses (as a choice point). I’m still considering something really simple to deal with the common case of a dynamic predicate that has only one clause that needs to be replaced. For this case an atomic operation would be really helpful and is simple. But possibly a generic solution is better. Plenty of things to think about
Instead of adding predicates like assert_list/1 and so on, maybe instead adding algebraic data types to Prolog. Hopefully by doing this it would then pass the complications of the user having to track the necessary data structures as groups of separate data structures but as just one onto the compiler. Granted a user could have many different types built on ADTs but for the ADT of interest it would be simpler. Mercury has ADTs (Discriminated unions), and in ML based langues I find them invaluable.
More views are always welcome! This topic is about the dynamic database though, which has only rather indirect links to Prolog terms. Seems @AdamSobieski wants to solve two also a little indirectly connected topics: be notified about changes to the dynamic database and atomic modification.
Abstract data types sort of exist in Prolog through objects such as AVL trees (library(assoc)). Mercury mostly adds typing to that picture. Despite many attempts, typing in Prolog is in many people’s mind, but nothing generally accepted ever emerged
(Ground) Prolog terms as such as immutable, so we do not need notification. If they are not ground we can use coroutining to follow their bindings. Atomicy is not relevant as Prolog terms are (in SWI-Prolog) only accessible from a single thread.
That discriminated union idea definitely seems doable in raw SWI-Prolog. One part is freezing aspects of a term so it can only be instantiated in certain ways.
term(_, _, left(_)) or term(_,_, right(_)) for example.
The thing that Prolog lacks is static checking. A useful aspect of typed discriminated unions in Haskell is that tagcasing forces you to address all cases. It’d be weird but you could use term_expansion and cause it to error if your tagcase expression didn’t include all the cases in the declaration.
The functionality of ObservableCollection and INotifyCollectionChanged have roots in dependents (from Smalltalk) and publish/subscribe mechanisms. These mechanisms can be implemented system-wide, with the functionality supported at the runtime level, or as a library, where the functionality is only used where needed (but note that one solution doesn’t preclude the other; in fact, I provide both in Logtalk). There are pros and cons in both approaches, as expected E.g. performance and coupling. Regarding an API, it must clearly define:
event semantics
monitor semantics
how to register/de-register events
how to register/de-register monitors
When an event is considered atomic, then the API semantics must specify if the monitors should be activated before, after, or before and after an event (if these reminds you of attributed variables, that’s not a coincidence ). The Logtalk events mechanism I mentioned earlier discusses in detail the implicit design choices if you’re looking for an example on how these mechanism can be implemented in a logic programming context.
An interesting use case scenario to consider with respect to the new high-level APIs is that of an artificial intelligence topic: knowledge-based computer simulation. The high-level APIs for event-driven Prolog and knowledgebases can also be of use for advanced interfaces to interactive computer simulations.
We can envision an interactive computer simulation with four balls: one red, one green, one blue and one yellow. We can also envision four boxes, colored identically. Each box can be envisioned as having one empty or hollow side and the interior of each box can be envisioned as such that at least one ball can fit inside of it. Then, a user or player could move the balls and boxes around, including to place the balls into the boxes or to move the boxes, hollow-side down, atop the balls, and so forth. As the user or player moves the balls and boxes around, one or more knowledgebase tables could update on the screen.
Artificial intelligence topics include interfacing with interactive 3D computer simulations and, interestingly, the use case scenario pertains to the high-level APIs that we are discussing. Incremental tables and queries can be of use for providing instantaneous views of the unfolding situations and events occurring in computer simulations. Interactive computer simulations can interface as knowledgebases.
). The Logtalk events mechanism I mentioned earlier discusses in detail the implicit design choices if you’re looking for an example on how these mechanism can be implemented in a logic programming context.