Did you know ... | Search Documentation: |
![]() | Blog: Using tabling to reason about a changing world |
Intelligent agents often have to reason about a changing world. Reasoning about a changing world is a form of stream reasoning. A classical Prolog system can do little better than implementing a loop that fetches updates from the outside world to update the world representation, typically represented as a set of dynamic predicates. Next, use backward reasoning rules (SLD resolution) can be used to make conclusions about the new state of the world. This approach has several disadvantages:
SWI-Prolog has a number of extensions that help dealing with reasoning over a changing blackboard. These extensions can be divided into several groups.
Tabling (SLG resolution) deals with non-termination, providing a super-set of the Datalog semantics. It also provides memoization avoiding re-computation. Tabling is provided by several Prolog implementations. SWI-Prolog provides several extensions to the original tabling implementations. We particularly thank Theresa Swift and David S. Warren for their help advancing SWI-Prolog's tabling.
Reactive intelligent agents have to deal with multiple streams providing new information about the world as well as multiple concurrent actions the agent may undertake. There are several ways in which SWI-Prolog can deal with this.
The most obvious solution is to use threads: fully concurrent Prolog engines that run on a same shared Prolog database. With low-cost IoT hardware such as the Raspberry-Pi having multiple cores, threads are attractive. Unfortunately, dealing with the dependencies is complicated and error-prone. For this reason, and notably when the threads are heavily mutually dependent and not particularly CPU intensive, threads may not always be the best solution. Note that popular languages such as JavaScript and Python are essentially single threaded, switching between tasks based on external events. SWI-Prolog has two mechanisms that provided similar single-threaded solutions to deal with multiple inputs and concurrent actions.
Prolog engines have been invented by Paul Tarau. An engine is almost the same as a thread, but it can be in two states: attached and detached. In the attached mode it is just a Prolog thread, while in the detached mode it represents the frozen state of the Prolog thread. Once attached (running), it can yield control to the thread that attached it either by producing an answer or by using engine_yield/1.
Engines allow a single OS thread to perform cooperative multitasking, similarly to what JavaScript and Python do. Cooperative multitasking does avoid many of the complications associated with multi threading. Unfortunately it breaks when tasks are not cooperative and hold the CPU for too long. Note that threads may be combined with engines.
Delimited continuations allows snapping _"the remainder of the current computation"_ as a Prolog term. This term can be restarted later, finishing the work. Delimited continuations can serve a goal similar to engines. Whenever a task needs to block for input or simply wants to give other tasks the opportunity to make progress, the task calls shift/1 indicating what it is waiting for. The toplevel control loop uses reset/3 to start tasks or resume continuations.
A simple skeleton for the overall control loop is below. The first clause checks for input and restarts a continuation (task) that was waiting for this input. The second clause checks for a clause willing to continue without waiting after it gave up the CPU to allow other tasks to make progress and the last waits for new input. Different scheduling policies may be realised using priority queues as provided by e.g., library(heaps).
loop(Pending) :- get_input_nonblocking(Message), !, find_continuation(Message, Pending, Continuation, Pending2), reset(Continuation, Ball, NewContinuation), ( NewContinuation == 0 -> loop(Pending2) % task completed ; append(Pending2, [Ball-NewContinuation], Pending3), loop(Pending3) ). loop(Pending) :- selectchk(yield-Continuation, Pending, Pending2), !, reset(Continuation, Ball, NewContinuation), ( NewContinuation == 0 -> loop(Pending2) % task completed ; append(Pending2, [Ball-NewContinuation], Pending3), loop(Pending3) ). loop(Pending) :- wait_for_input, loop(Pending).
Representing the world as a set of dynamic predicate poses problems. For example, a predicate temperature/1 representing the current ambient temperature must be updated using a retractall/1 to remove the current temperature followed by an asserta/1 to record the new temperature:
update_temp(Temp) :- retractall(temperature(_)), asserta(temperature(Temp)).
If we do the database update asynchronously with the reasoners, i.e., in a separate thread, the reasoner may find itself in a situation where no temperature is known. We can adjust the code to first add the new temperature and them remove the old. The presence of two temperature facts may upset the reasoner as well though.
What to do? If we use the cooperative multitasking approach based on engines or delimited continuations there is no problem as the main thread will read events from the input and handle them. As nothing runs concurrently, this works fine.
When using threads, one option is to use with_mutex/2 to make sure database updates and reasoning are fully synchronized. This makes threads far less useful as a slow reasoner may block updates and withhold urgent reasoners from notifying a change to the world. A second alternative is to use transaction/1. This allows a number of database changes to become available to the global Prolog database atomically. For example, wrapping update_temp/1 in transaction/1 ensures any thread will see exactly one temperature at any point in time.
A reasoner asking for the temperature multiple times during its reasoning process may, despite the use of transaction/1, get different values for the different requests. If this can pose problems, snapshot/1 comes into the picture. A goal called through snapshot/1 sees a frozen, isolated and consistent version of the dynamic database: changes made by other threads after the start of the snapshot are invisible and changes made inside the snapshot are invisible to other threads.
SWI-Prolog offers a large set of primitives to deal with a changing world. Tabling allows for truly declarative reasoning with minimal recomputation after updates to the world as well as sharing derivations between threads. Delimited continuations and engines allow for event driven reasoning over multiple concurrent tasks in a single thread based on cooperative multitasking. Transactions and snapshots allow for truly concurrent reasoning. Concurrent reasoning profits from multi-core hardware and is insensitive to tasks that hold the CPU, providing more reactive systems. SWI-Prolog allows combining the two approaches in one process.