Worst-case exponential runtime for some special terms

Question

This question is based on a relatively recent issue on the Scryer Prolog GitHub page.

Consider the following predicate:

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

Using ptree/1 we can easily get exponentially-sized trees which can be represented in linear space.

ground/1 and (is)/2 can run in exponential time or in linear time—depending on the implementation of the Prolog system.

Here's my actual question:

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

So far I found term_variables/2 and library(terms).

But are there more?

Answer 1

Other examples using blam:

On GNU Prolog and Trealla Prolog, (=)/2 and (==)/2 exhibit the same issue with bleq/1 and bleqeq/1 respectively.

On GNU Prolog, Trealla Prolog, Scryer Prolog, acyclic_term/1 is affected.

---

As long as a property needs to hold recursively like acyclic_term/1, (=)/2 or a result is built recursively like term_variables/2, this issue can happen.

Memoization is the way to solve this. Looking at Scryer ($ git grep "let.*tabu"), it's using memoization for (=)/2 and compare/3.

But memoization wouldn't work on:

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

Term sharing is the next step to not miss the memoization technique.