7.9 Shared tabling

Tables can both be private to a thread or shared between all threads. Private tables are used only by the calling threads and are discarded as the thread terminates. Shared tables are used by all threads and can only be discarded explicitly. Tables are declared as shared using, e.g.,

:- table (p/1, q/2) as shared.

A thread may find a table for a particular variant of a shared tabled predicate in any of the following states:

Complete

If the table is complete we can simply use its answers.

Fresh/non-existent

If the table is still fresh, claim ownership for it and start filling the table. When completed, the ownership relation is terminated.

Incomplete

If the table is incomplete and owned by the calling thread, simply continue. If it is owned by another thread we wait for the table unless there is a cycle of threads waiting for each others table. The latter situation would cause a deadlock and therefore we raise a deadlock exception. This exception causes the current SCC to be abandoned and gives other threads the opportunity to claim ownership of the tables that were owned by this thread. The thread that raised the exception and abandoned the SCC simply restarts the leader goal of the SCC. As other threads now have claimed more variants of the SCC it will, in most cases, wait for these threads instead of creating a new deadlock.

A thread that waits for a table may be faced with three results. If the table is complete it can use the answers. It is also possible that the thread that was filling the table raised an exception (either a deadlock or any other exception), in which case we find a fresh table for which we will try to claim ownership. Finally, some thread may have abolished the table. This situation is the same as when the owning thread raised an exception.

7.9.1 Abolishing shared tables

This section briefly explains the interaction between deleting shared tables and running threads. The core rule is that abolishing a shared table has no effect on the semantics of the tabled predicates. An attempt to abolish an incomplete table results in the table to be marked for destruction on completion. The thread that is completing the table continues to do so and continues execution with the computed table answers. Any other thread blocks, waiting for the table to complete. Once completed, the table is destroyed and the waiting threads see a fresh table^{192Future versions may avoid waiting by converting the abolished shared table to a private table.}.

The current implementation never reclaims shared tables. Instead, they remain part of the global variant table and only the answers of the shared table are reclaimed. Future versions may garbage collect such tables. See also abolish_shared_tables/0.

7.9.2 Status and future of shared tabling

Currently, shared tabling has many restrictions. The implementation does not verify that the limitations are met and violating these restrictions may cause incorrect results or crashes. Future versions are expected to resolve these issues.

• Shared tabling currently only handles the basic scenario and cannot yet deal with well formed semantics or incremental tabling.
• As described in section 7.9.1, abolishing shared tables may cause unnecessary waiting for threads to complete the table.
• Only the answers of shared tables can be reclaimed, not the answer table itself.

SWI-Prolog's continuation based tabling offers the opportunity to perform completion using multiple threads.