Efficient Evaluation of Deterministic Tabled Calls

Miguel Areias and Ricardo Rocha

December 2008

---

Abstract

The execution model in which most tabling engines are based allocates a choice point whenever a new tabled subgoal is called. This happens even when the call is deterministic. However, some of the information from the choice point is never used when evaluating deterministic tabled calls with batched scheduling. Thus, if tabling is applied to a long deterministic computation, the system may end up consuming a huge amount of memory inadvertently. In this paper, we propose a solution that reduces this memory overhead to a minimum. Our results show that, for deterministic tabled calls with batched scheduling, it is possible not only to reduce the memory usage overhead, but also the running time of the evaluation.

Bibtex

@InProceedings{areias-ciclops08,
  author =    {M. Areias and R. Rocha},
  title =     {{Efficient Evaluation of Deterministic Tabled Calls}},
  booktitle = {Proceedings of the 8th Colloquium on Implementation of Constraint and LOgic Programming 
               Systems (CICLOPS 2008)},
  pages =     {60--74},
  editor =    {M. Carro and B. Demoen},
  month =     {December},
  year =      {2008},
  address =   {Udine, Italy},
}

Download Paper

PDF file

Download Slides

PDF file