Title: More declarative tabling in Prolog using multi-prompt delimited control,
Abstract: Several Prolog implementations include a facility for tabling, an alternative
resolution strategy which uses memoisation to avoid redundant duplication of
computations. Until relatively recently, tabling has required either low-level
support in the underlying Prolog engine, or extensive program transormation (de
Guzman et al., 2008). An alternative approach is to augment Prolog with low
level support for continuation capturing control operators, particularly
delimited continuations, which have been investigated in the field of
functional programming and found to be capable of supporting a wide variety of
computational effects within an otherwise declarative language.
This technical report describes an implementation of tabling in SWI Prolog
based on delimited control operators for Prolog recently introduced by
Schrijvers et al. (2013). In comparison with a previous implementation of
tabling for SWI Prolog using delimited control (Desouter et al., 2015), this
approach, based on the functional memoising parser combinators of Johnson
(1995), stays closer to the declarative core of Prolog, requires less code, and
is able to deliver solutions from systems of tabled predicates incrementally
(as opposed to finding all solutions before delivering any to the rest of the
program).
A collection of benchmarks shows that a small number of carefully targeted
optimisations yields performance within a factor of about 2 of the optimised
version of Desouter et al.'s system currently included in SWI Prolog.