Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs
Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs
复制标题
表式 Prolog 的增量评估：超越纯逻辑程序
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
C. Ramakrishnan
中科院分区：
文献类型：
--
作者：
Diptikalyan Saha;C. Ramakrishnan
表处理（tabling），或称记忆化（memoization），能够对逻辑程序进行增量式求值。当一个程序的规则或事实发生变化时，我们只需重新计算那些受变化影响的结果。当前用于增量式维护记忆表的算法对事实/规则的插入和删除区别对待。因此，这些技术不能直接应用于对任意表处理程序的增量式求值，特别是那些涉及Prolog内置函数（如findall）、其他聚合操作或非分层否定的程序。在本文中，我们探索一种更简单的增量式求值算法，该算法基于动态调用图，使整个调用失效并重新求值。该算法与依赖关系是向表中添加还是删除答案无关，因此可以统一应用于具有否定的程序，即使否定是隐含的（某些聚合操作就是这种情况）。我们发现，在调用依赖关系大部分为无环的示例中（例如动态规划示例），基于调用的算法非常有效，而在依赖关系包含独立循环组件时（例如数据流分析问题），该算法具有一定的有效性。这是第一个能够处理所有合法的、增量式求值有意义的表处理逻辑程序的实用算法。
Tabling, or memoization, enables incremental evaluation of logic programs. When the rules or facts of a program change, we need to recompute only those results that are affected by the changes. The current algorithms for incrementally maintaining memo tables treat insertion of facts/rules differently from their deletion. Hence these techniques cannot be directly applied for incremental evaluation of arbitrary tabled programs, especially those involving Prolog builtins such as findall, other aggregation operations, or non-stratified negation. In this paper, we explore a simpler incremental evaluation algorithm that, based on the dynamic call graph, invalidates and re-evaluates entire calls. The algorithm is agnostic to whether a dependency adds or removes answers from tables, and hence can be applied uniformly to programs with negation, even when the negation is implicit (as is the case with certain aggregation operations). We find that the call-based algorithm is very effective in examples where the call dependencies are largely acyclic (e.g. dynamic programming examples) and is moderately effective when the dependencies contain independent cyclic components (e.g. data flow analysis problems). This is the first practical algorithm to handle all legal tabled logic programs for which incremental evaluation is meaningful.