Tabling
Channel: Playing With Prolog
Date: 2019-09-02

Tabling

We cover the newly added Tabling for SWI-Prolog.
https://swish.swi-prolog.org/p/graph.swinb


Scenario: Annie wants to program a graph search that gives her the quickest route between two places.

Problem: The naive implementation requires at least three layers:

a predicate for the simple facts: which place is connected to what other place and how long does it take (e.g. distance(berlin, munich, 100).)
a predicate that provides the opposite direction also, i.e. a commutative version of distance
another predicate that transitively connects places

Solution: Tabling.

Tabling solves two problems:
Left recursion (a common problem in parsing, too)
Performance

Both problems are solved by the cache that is built by using tabling. At the same time it can also greatly simplify programs. We can merge all three of the above predicates into a single predicate.