is/2谓词本可线性执行却呈指数级运行时长的技术问询

在Prolog中，很容易构建出看似庞大实则是小型图结构的树，比如这段代码：

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

许多Prolog系统针对这类术语的ground/1内置谓词提供了优化实现，但并未对is/2做类似优化。针对相关疑问，解答如下：

问题1：是否存在Prolog系统，其is/2实现对这类术语可实现线性运行？ #

确实存在。比如SWI-Prolog在处理带有共享子结构的算术表达式时，通过结构共享检测机制避免重复计算，能实现近似线性的运行效率；还有部分专注于逻辑编程性能优化的小众Prolog系统，也针对这类场景做了专门的优化处理。

问题2：诸多Prolog系统选择不提供此类优化实现是否存在特定原因？ #

主要有几方面原因：

• 通用场景优先级更高：大多数Prolog用户的常规算术计算场景中，这类带共享子结构的表达式并不常见。为这类小众场景优化is/2，会增加实现复杂度，反而可能拖慢普通算术运算的执行速度，得不偿失。
• 实现成本与资源限制：要检测并利用结构共享优化is/2，需要额外的遍历、标记逻辑，对解释器或编译器的底层设计要求较高。很多系统开发者会优先把资源投入到更常用的功能优化上。
• 语义兼容性顾虑：这类优化可能引入潜在的语义歧义，比如在特殊绑定场景下，共享结构的计算结果是否符合用户预期，需要大量兼容性测试，这也让很多系统不愿贸然添加此类优化。

内容的提问来源于stack exchange，提问作者repeat