That was just to test this somewhat baffling line:
I don't know in what system this paragraph is true, but it's manifestly false of SWI Prolog. Negation by failure works fine; the line that's supposed to have no definition, returns results.
This bizarreness is just the sort of thing you find when you read 1980s or early-90s logic programming papers.
@natecull This example does not show it well, but negation as failure has two main problems: first, it’s not constructive so it can’t bind any values (you can’t say “give me a value for which P is false” without enumerating all possible values of P, which may not be feasible/possible).
Second (and much worse), each \+ goal is logically independent of the others, so you could have two \+ goals succeed but in different “worlds”, yet combine that into a joint inconsistent world interpretation.
@natecull I was a prolog hacker for several years in my PhD, so I’ve followed your threads lately with interest!
Nowadays I feel that A.) there are benefits to separating spec and implementation; largely the redundancy is actually helpful to debug specification bugs (so you don’t just get “no.” If things aren’t working); and B.) logic programs are still great, if the semantics are good. Answer set programming is a real good semantics with a fast solver (clingo), CLP(X) is okay too.
@natecull On the other hand there are few PL tricks as cool as Tom Schrijver’s “tor” pluggable disjunction for Prolog, I really recommend finding that paper. It’s the lispiest prolog paper around. XSB prolog’s tabling engine by the other David Warren is also interesting and patches some holes in Prolog.
@JoeOsborn Thanks for these comments! These all sound fascinating.
I guess what confuses/annoys me about the sort of general collapse of interest in logic programming circa mid-1990s, is that although there are now all these separate systems from, I guess, Mercury to XSB which each, individually, claim to be 'the next Prolog'.. they all seem very small, and very separated, and none of them has actually become 'the next Prolog'.
I suppose it's a bit like the Lisp scene.
@JoeOsborn I woke up dreaming about my pointfree Prolog idea again, which may or may not be a sign that I need more sleep.
On the surface it seems simple enough, though I can't quite find a logic it relates to. Quine's Predicate Functor Logic, I think, is perhaps the closest.
@natecull I think the central question for logic programs is whether commitments made on one branch of a proof persist in the other branches, versus whether we can target queries. IOW, given that we want nonmonotonic logics, do we accept unsoundness or do we accept computing complete (thus finite) models and never partial ones? Tabling is a reaction that keeps SLD, minikanren swaps out resolution to dodge some uses of nonmonotonicity, ASP avoids it by grounding and stable model semantics.
@JoeOsborn I wish I knew enough to parse out what all those terms mean.
*Do* we in fact want nonmonotonic logics? Is this a decision that we've come to? My impression was that there are a lot of nonmonotonic logics and they're all different and this suggests to me that they're all... maybe not right?
Rather than trying to make the *logic* nonmonotonic, couldn't we perhaps keep the logic simple and instead just be thinking about there being multiple *databases*?
@natecull If you want negation as failure, argumentation, defeasibility, defaults, certain uses of disjunction, or change over time, you most likely want nonmonotonicity. The latter can be obtained without it if you accept the constraint of modular logic programs at each discrete timestep.
Multiple models/interpretations/databases is fine, but orthogonal to monotonicity (new facts/rules only add inferences and never remove or invalidate any).
@natecull I should also say that pure (assert-less, cut-less) Prolog implicitly has the multiple database view you mention but the scope is on individual queries or goals modulo shared variable bindings; this means you need to meta-interpret and/or reify models into argument positions if you want to reason explicitly about multiple databases. It’s also still separate from monotonicity.
@JoeOsborn Is there a single accepted nonmonotonic logic, yet? Did one of the competing 1980s-90s theories win? Or is nonmonotonicity still a thing that we want but don't know how to get?
@JoeOsborn I guess 'reifying models as arguments' is exactly what I'm trying to do and what I find Prolog fights me about... I don't like that the Prolog database is this sort of invisible thing that's not actually a logical statement itself. I want everything in the program to be one kind of thing, like everything is an 'expression' in Lisp. I want to pass around sets of statements (where even a 'set' is a statement).
This might be an unhelpful thing to want, but it seems intuitive to me.
@natecull I had a similar experience. Prolog written like Haskell is powerful but awkward and slow. Splitting procedures from relations can help some IF you have a principled way of choosing between interpretations at each timestep and/or can reason about multiple timelines. But, computers, so everything is bad in some way. It depends on what you really need.
@natecull I think answer set semantics are the best behaved. AFAIK they won the “semantics wars” and you can model e.g. argumentation and other syntax with them. Of course nothing is ever one size fits all.
@JoeOsborn One of my other Mastodon friends talked a lot about answer set programming (well-founded semantics I think?) so it sounds cool!
But I could find hardly any information online about it. It still seems very niche.
Is ASP something one can just implement over top of Prolog or Kanren as a library, or does it need a ground-up algorithm rewrite?
@natecull It is implementable only in the boring sense that Prolog is Turing-equivalent. Separate algorithms are used; the most mature system is clingo (potassco tools). Adam Smith has some good papers on videogame design support applications of ASP, I also worked on a project called “Gemini” focused on generating and reasoning about game dynamics. Smith’s phrasing is that ASP is a very convenient formalism for specifying SAT and optimization problems compared to something like, say, SMTLIB.
@natecull There are lots of good papers linked from the Potassco site; my memory is shaky but I think Gelfond and Lifschitz are two of the theorists iirc, some papers out of UT Austin, but now the activity is at Potsdam on the engineering side.
dlvHEX is another interesting asp system, now built on top of asp. You may like it? Stock clingo also has very good support for constraint satisfaction/propagation now.
@JoeOsborn I guess what I'm really looking for is a suitably well-worn language kernel which is small enough for me to fit in my head and reimplement and understand (ie: to use as a game-design-oriented domain-specific language), rather than a full-fledged general logic prover.
Classical Prolog is almost small enough to fit in my head (once I figure out how to represent unknowns... I guess integers is fine, it's nasty and I don't like it, but sigh, it'll have to do) but ASP...
@JoeOsborn Glancing at some of these papers, it seems like most of the ASP work revolves around a Prolog variant called AnsProlog, which is more the sort of thing I'm looking for rather than a piece of software.
Is there a good standard reference for the AnsProlog language?
@natecull There is an AnsProlog reference but it’s mostly about syntax. Potassco site links to it I believe, it is a recent standard. Naive implementations are not complex but efficient ones probably have to be. Minikanren is much more implementable if it will work for you.
I do believe it’s easier to embed/control clingo from code rather than reimplement it, and its runtime supports that.
You may also be interested in Ian Horswill’s CatSAT project.
@natecull ASP as a game design formalism has been tried a few times and seems ok (ludocore, Gemini). It really is meant for combinatorial optimization, but it works well for modeling design spaces. With tricks around projecting answer sets onto subsets of the predicates you can also obtain “interestingly different” answer sets.
I think for Prolog, pointers and union-find data structures can suffice for logic vars; might need more than that to implement freeze/2 though.
@JoeOsborn omg, thanks for the Adam Smith mention!
<< Answer Set Programming for Procedural Content
Generation: A Design Space Approach >>
That sounds fun!
Server run by the main developers of the project It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!