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

Question

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

Answer 1

您的直觉是正确的，但 Prolog 设计使用深度优先搜索（请参阅此处的 SLDNF 分辨率），并且有充分的理由，那么这种限制不容易避免。

OTOH，Ciao Prolog 提供了适当的扩展。

您可以使用元解释器模拟广度优先递归，例如这里为左递归 DCG 所做的（左递归语法是一种常见情况），但这通常不是一种容易遵循的方法。

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