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.

or with iterative deepening. well, you said you don't care about efficiency... :) — Will Ness
Thanks for the suggestion, Will. Iterative deepening actually works better. I tried the BF extension of Ciao with a small example, got stackoverflow (no pun ;). — day

CapelliC CapelliC · Accepted Answer · 2013-06-03T10:14:52

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.

Any Prolog implementation that allows left recursion?

1 Answers