Magic Sets vs. SLD-Resolution
Magic Sets vs. SLD-Resolution
复制标题
Magic Sets 与 SLD 分辨率
DOI：
10.1007/978-1-4471-1486-4_13
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Stefan Brass
中科院分区：
文献类型：
--
作者：
Stefan Brass
时至今日，对一档节目进行自下而上的评价，经过《法套》改造后，其效率与自上而下的评价一样，也就是民间传说了。在文献中有许多对此的形式化描述。然而，这种天真的形式化是错误的：正如Ross所展示的，SLD-解析可能比在尾递归程序上使用魔术集进行自底向上求值要高效得多。
It is by now folklore that the bottom-up evaluation of a program after the “magic set” transformation is “as efficient as” top-down evaluation. There are a number of formalizations of this in the literature. However, the naive formalization is false: As shown by Ross, SLD-resolution can be much more efficient than bottom-up evaluation with magic sets on tail-recursive programs.