prolog - 左再帰を許可する Prolog 実装はありますか?

Question

句で左再帰を許可する Prolog 実装があるかどうか疑問に思います。私の直感では、実装で幅優先のゴール検索を使用する場合、左再帰がサポートされる可能性があります。しかし、よくわかりません。効率についてはあまり気にしないことに注意してください。

Answer 1

あなたの直感は正しいですが、Prolog は設計により深さ優先検索を使用し (ここでSLDNF 解決を参照)、正当な理由があるため、その制限を簡単に回避することはできません。

OTOH, Ciao Prolog は適切な拡張子を提供しています。

たとえばここで左再帰 DCG (左再帰文法は一般的なケースです) に対して行われたように、メタ インタープリターを使用して幅優先再帰をシミュレートできますが、一般的に従うのは簡単な方法ではありません。

IMO は、あなたの要求を近似/満足できる最も一般的な拡張機能であり、 tableling です。YAP Prolog、XSB、B-Prolog で見つけることができます。