This paper presents a systematic approach to the compilation of logic programs for efficient clause indexing. As the kernel of the approach, we propose the indexing tree, which provides a simple, but precise representation of the average parallelism per node (i.e., choice point) as well as the number of clause trials. It also provides a way to evaluate the number of cases in which the control is passed to the failure code by means of an indexing instruction, such as switch_on_term, switch_on_constant, or switch_on_structure. By analyzing the indexing tree created when the indexing scheme is implemented in the WAM, we show the drawback of the WAM indexing scheme in terms of parallelism exposition and scheduling. Subsequently, we propose a new indexing scheme, which we call the the Flat indexing. The experimental results show that over one half of our benchmarks benefit from Flat indexing such that, compared with the WAM indexing scheme, the number of choice points is reduced by 15%. Moreover, the amount of failures which occur during the execution of indexing instructions is reduced by 35%.

Keywords: logic programming, clause indexing, OR-parallelism, WAM, Prolog

Retrieve PDF document (200003_04.pdf : 3,563,874 bytes)

Received March 28, 1999; revised July 16, 1999; accepted November 26, 1999.
Communicated by Shang-Rong Tsai.