Title: Table Space Designs For Implicit and Explicit Concurrent Tabled Evaluation,
Abstract: One of the main advantages of Prolog is its potential for the implicit
exploitation of parallelism and, as a high-level language, Prolog is also often
used as a means to explicitly control concurrent tasks. Tabling is a powerful
implementation technique that overcomes some limitations of traditional Prolog
systems in dealing with recursion and redundant sub-computations. Given these
advantages, the question that arises is if tabling has also the potential for
the exploitation of concurrency/parallelism. On one hand, tabling still
exploits a search space as traditional Prolog but, on the other hand, the
concurrent model of tabling is necessarily far more complex since it also
introduces concurrency on the access to the tables. In this paper, we summarize
Yap's main contributions to concurrent tabled evaluation and we describe the
design and implementation challenges of several alternative table space designs
for implicit and explicit concurrent tabled evaluation which represent
different trade-offs between concurrency and memory usage. We also motivate for
the advantages of using fixed-size and lock-free data structures, elaborate on
the key role that the engine's memory allocator plays on such environments, and
discuss how Yap's mode-directed tabling support can be extended to concurrent
evaluation. Finally, we present our future perspectives towards an efficient
and novel concurrent framework which integrates both implicit and explicit
concurrent tabled evaluation in a single Prolog engine. Under consideration in
Theory and Practice of Logic Programming (TPLP).