prolog - 任何允许左递归的 Prolog 实现？

Question

我想知道是否有任何 Prolog 实现允许子句中的左递归。我的直觉是，如果实现使用广度优先目标搜索，它可能支持左递归。但我不太确定。请注意，我不太关心效率。

Answer 1

您的直觉是正确的，但 Prolog 按设计使用深度优先搜索(请参阅 SLDNF 分辨率 here )并且有充分的理由，那么该限制不容易避免。

OTOH，Ciao Prolog 提供了一个合适的 extension .

您可以使用元解释器模拟广度优先递归，例如 here对于左递归 DCG(左递归文法是一种常见情况)，但这通常不是一种容易遵循的方法。

IMO 可以近似/满足您的要求的最常见扩展是制表，您可以在 YAP Prolog、XSB、B-Prolog 中找到它。