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?
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.