Tabling as a Library with Delimited Control

Abstract

The logic programming language Prolog uses a resource-efficient SLD resolution strategy for query answering. Yet, its propensity for nontermination seriously detracts from the language's declarative nature. This problem is remedied by tabling, a modified execution strategy that allows a larger class of programs to terminate. Unfortunately, few Prolog systems provide tabling, because the documented implementation techniques are complex, low-level and require a prohibitive engineering effort. To enable more widespread adoption, this paper presents a novel implementation of tabling for Prolog that is both high-level and compact. It comes in the form of a Prolog library that weighs in at under 600 lines of code, is based on delimited control and delivers reasonable performance. PDF