Efficient Evaluation of Deterministic Tabled Calls


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.


  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