Any Prolog implementation that allows left recursion?

Question

I wonder if there is any Prolog implementation that allows left recursion in clauses. My intuition is that if the implementation uses a breadth-first goal search, it may support left recursion. But I am not quite sure. Note that I do not care much about efficiency.

Answer 1

Your intuition is correct, but Prolog uses depth first search by design (see SLDNF resolution here) and with good reasons, then that limitation is not easily avoided.

OTOH, Ciao Prolog offers an appropriate extension.

You can simulate breadth first recursion, using a meta interpreter, as done for instance here for a left recursive DCG (left recursive grammars are a common case), but it's not generally an easy way to follow.

IMO the most common extension that could approximate/satisfy your request, is tabling, you can find it in YAP Prolog, XSB, B-Prolog.