prolog - 某些特殊项的最坏情况指数运行时间

Question

本题基于a relatively recent issue on the Scryer Prolog GitHub page .

考虑以下谓词:

ptree(1).
ptree(X+X) :-
   ptree(X).

使用 ptree/1 我们可以很容易地得到可以在线性空间中表示的指数大小的树。

ground/1 和 (is)/2 可以按指数时间或线性时间运行——取决于 Prolog 系统的实现。

这是我的实际问题:

Which commonly used builtin and library predicates are (potentially) affected by this issue?

到目前为止我找到了term_variables/2和 library(terms) .

但是还有更多吗？

Answer 1

使用 blam 的其他示例:

在 GNU Prolog 和 Trealla Prolog 上，(=)/2 和 (==)/2 表现出与 bleq/1 相同的问题> 和 bleqeq/1 分别。

在 GNU Prolog、Trealla Prolog、Scryer Prolog 上，acyclic_term/1受到影响。

---

只要属性需要像 acyclic_term/1、(=)/2 那样递归保存，或者像 term_variables/2< 这样递归构建结果，这个问题可能会发生。

记忆化是解决这个问题的方法。查看 Scryer ($ git grep "let.*tabu")，它正在为 (=)/2 和 compare/3 使用内存。

但记忆化不适用于:

blem([]).
blem([L|R]) :-
    blem(R),
    same_length(R, L),
    blem(L).

Term sharing下一步是不要错过内存技术。