sgt101

Prolog is deeply unsuited for work, use Clingo instead.

Try this on https://swish.swi-prolog.org/.

on(a,b). on(b,c). above(X,Y) :- on(X,Y). above(X,Y) :- on(X,Z), above(Z,Y).

Query above(a,c)

Ok, true - it works! no probs.

now try

on(a,b). on(b,c). above(X,Y) :- above(X,Z), on(Z,Y). above(X,Y) :- on(X,Y).

and query... and it explodes.

So - this kind of bug is very hard to find and extremely easy to introduce.

The good news is that answer set programming is not prone to it. So instead of prolog use Clingo !

https://potassco.org/clingo/

YeGoblynQueenne
As triska says, there are different execution strategies for Prolog and left-recursion is not a problem in practice. To plug my own work, the Inductive Logic Programming (ILP) system I developed during my PhD (https://github.com/stassa/louise) can learn left-recursive Prolog programs thanks to an inductive Prolog meta-interpreter executed with SLG-resolution (a.k.a. tabling). I mean to say that the inductive meta-interpreter itself is tabled, so it can prove left-recursive programs without entering an infinite recursion (it needs to do that because it learns a program by proving its generalisation). And so it can learn left-recursive programs without "going infinite". That used to be a big problem for ILP, but it's now well and truly solved, in theory as well as in practice. And I say "now" but SLG-resolution is old as a a very old thing; Tamaki and Sato described it in 1986, I believe:

https://link.springer.com/chapter/10.1007/3-540-16492-8_66

But then implementations took a bit to catch up.

>> Prolog is deeply unsuited for work, use Clingo instead.

Well, that doesn't make sense. ASP doesn't even allow lists, let alone side-effects (you know, like writing to a stream), so what "work" is it that it's better suited for, than Prolog?

Also, if I remember correctly, Clingo is not a language but a grounder? It takes a first-order program and grounds the entire Herbrand base into a set of propositions so that a SAT solver can then derive the stable models of the program? Do I have that wrong?

Let me say up front that I've never heard a worse idea in my life, and I've heard a few. First of all, that's why ASP can't use lists, or other functions, because then the Herbrand base goes infinite and good luck grounding it. Second, SAT-solving is NP-complete. As I realised recently (https://news.ycombinator.com/item?id=34072923) ASP is an elegant framework for dealing with uncertainty in a purely symbolic manner, with negation as failure and axiomatic, classical negation. But then, why go and mess this elegance up with a dumb propositionalisation approach that loses all the good stuff about first order logic, and that's terminally inefficient to boot? That, I still don't get.