Re:Turning the IDE Inside Out with Datalog
by YeGoblynQueenne on Monday July 20, 2020 @06:45PM
(#23902677)
Ah, phew, OK. I was really confused by that. No worries, I'm still grateful for your comments :)
Yes, ASP is not Horn so it has rules with multiple literals in the head. "Choice rules", writen as {s,t}:- p. Also, like you say, I believe it doesn't suffer from Prolog's non-termination, again because unlike Prolog it's not Turing-complete. But in any case ASP is based on stable model semantics, not fixpoint semantics.
However I'm really very far from being anything like an expert in ASP! I really should learn a bit of it because it's actually necessary in my research.
Half-remembered university courses from >= 10 years ago, I'm afraid. I now think I was probably thinking of ASP, not Datalog. See for example the "Disjunctive logic programs" section of https://www.cs.uni-potsdam.de/~torsten/Lehre/ASP/Folien/asp-.... Since the syntax is very Prolog/Datalog-like, I probably got mixed up. My bad, sorry. The first few sources on Datalog I looked at only talked about Horn clauses, not ones with more heads.
> My understanding is that without definite clauses (and "p,q:-r" is not definite) there are no fixpoint semantics and without fixpoint semantics there is no guarantee of program termination.
Skimming https://en.wikipedia.org/wiki/Answer_set_programming and https://en.wikipedia.org/wiki/Stable_model_semantics I get the impression that even disjunctive logic programs appear to always terminate, though the complexity might be daunting.