Reporting *why* a query failed in Prolog in a systematic way

Question

I'm looking for an approach, pattern, or built-in feature in Prolog that I can use to return why a set of predicates failed, at least as far as the predicates in the database are concerned. I'm trying to be able to say more than "That is false" when a user poses a query in a system.

For example, let's say I have two predicates. blue/1 is true if something is blue, and dog/1 is true if something is a dog:

blue(X) :- ...
dog(X) :- ...

If I pose the following query to Prolog and foo is a dog, but not blue, Prolog would normally just return "false":

? blue(foo), dog(foo)
false.

What I want is to find out why the conjunction of predicates was not true, even if it is an out of band call such as:

? getReasonForFailure(X)
X = not(blue(foo))

I'm OK if the predicates have to be written in a certain way, I'm just looking for any approaches people have used.

The way I've done this to date, with some success, is by writing the predicates in a stylized way and using some helper predicates to find out the reason after the fact. For example:

blue(X) :-
    recordFailureReason(not(blue(X))),
    isBlue(X).

And then implementing recordFailureReason/1 such that it always remembers the "reason" that happened deepest in the stack. If a query fails, whatever failure happened the deepest is recorded as the "best" reason for failure. That heuristic works surprisingly well for many cases, but does require careful building of the predicates to work well.

Any ideas? I'm willing to look outside of Prolog if there are predicate logic systems designed for this kind of analysis.

Leatriceleave

This sound rather like en.wikipedia.org/wiki/Halting_problem. – Centurial

Just add default clauses for all predicates, the default predicates should be reached when a predicate fails and just report the predicate failed. Once you do this your next question will be, How do I get the path Prolog took to get to the failed predicate?. If you continue down this slippery slope you will find yourself creating a debugger, then you will want it to be nice and graphical. So with SWI-Prolog save yourself the trouble and use gtrace. – Unctuous

Answer 1

Some thoughts:

Why did the logic program fail: The answer to "why" is of course "because there is no variable assignment that fulfills the constraints given by the Prolog program".

This is evidently rather unhelpful, but it is exactly the case of the "blue dog": there are no such thing (at least in the problem you model).

In fact the only acceptable answer to the blue dog problem is obtained when the system goes into full theorem-proving mode and outputs:

blue(X) <=> ~dog(X)

or maybe just

dog(X) => ~blue(X)

or maybe just

blue(X) => ~dog(X)

depending on assumptions. "There is no evidence of blue dogs". Which is true, as that's what the program states. So a "why" in this question is a demand to rewrite the program...

There may not be a good answer: "Why is there no x such that x² < 0" is ill-posed and may have as answer "just because" or "because you are restricting yourself to the reals" or "because that 0 in the equation is just wrong" ... so it depends very much.

To make a "why" more helpful, you will have to qualify this "why" somehow. which may be done by structuring the program and extending the query so that additional information collecting during proof tree construction is bubbling up, but you will have to decide beforehand what information that is:

query(Sought, [Info1, Info2, Info3])

And this query will always succeed (for query/2, "success" no longer means "success in finding a solution to the modeled problem" but "success in finishing the computation"),

Variable Sought will be the reified answer of the actual query you want answered, i.e. one of the atoms true or false (and maybe unknown if you have had enough with two-valued logic) and Info1, Info2, Info3 will be additional details to help you answer a why something something in case Sought is false.

Note that much of the time, the desire to ask "why" is down to the mix-up between the two distinct failures: "failure in finding a solution to the modeled problem" and "failure in finishing the computation". For example, you want to apply maplist/3 to two lists and expect this to work but erroneously the two lists are of different length: You will get false - but it will be a false from computation (in this case, due to a bug), not a false from modeling. Being heavy-handed with assertion/1 may help here, but this is ugly in its own way.

In fact, compare with imperative or functional languages w/o logic programming parts: In the event of failure (maybe an exception?), what would be a corresponding "why"? It is unclear.

Addendum

This is a great question but the more I reflect on it, the more I think it can only be answer in a task-specific way: You must structure your logic program to be why-able, and you must decide what kind of information why should actually return. It will be something task-specific: something about missing information, "if only this or that were true" indications, where "this or that" are chosen from a dedicates set of predicates. This is of course expected, as there is no general way to make imperative or functional programs explain their results (or lack thereof) either.

I have looked a bit for papers on this (including IEEE Xplore and ACM Library), and have just found:

• Reasoning about Explanations for Negative Query Answers in DL-Lite which is actually for Description Logics and uses abductive reasoning.
• WhyNot: Debugging Failed Queries in Large Knowledge Bases which discusses a tool for Cyc.
• I also took a random look at the documentation for Flora-2 but they basically seem to say "use the debugger". But debugging is just debugging, not explaining.

There must be more.

Cropeared

Obviously a hard question to “answer”. Thanks for the pointers to some of the great research you found and thoughts on approach. That at least gave me some good avenues to keep following. – Leatriceleave

Answer 2

As long as you remain within the pure monotonic subset of Prolog, you may consider generalizations as explanations. To take your example, the following generalizations might be thinkable depending on your precise definition of blue/1 and dog/1.

?- blue(foo), * dog(foo).
   false.

In this generalization, the entire goal dog(foo) was removed. The prefix * is actually a predicate defined like :- op(950, fy, *). *(_). Informally, above can be read as: Not only this query fails, but even this generalized query fails. There is no blue foo at all (provided there is none). But maybe there is a blue foo, but no blue dog at all...

?- blue(_X/*foo*/), dog(_X/*foo*/).
   false.

Now we have generalized the program by replacing foo with the new variable _X. In this manner the sharing between the two goals is retained.

There are more such generalizations possible like introducing dif/2.

This technique can be both manually and automatically applied. For more, there is a collection of example sessions. Also see Declarative program development in Prolog with GUPU

Edington

After reading through your example sessions and (some of the) GUPU doc, these seem like great debugging best practices! Thanks for sharing that on its own. I get the idea of slicing and how you could apply it to a specific predicate to determine what "should have been true" to make it true and report that. It looks like, if applied automatically, reported errors could be about parts of a predicate's conjunction that don't have much meaning to the (non-programmer) human running the program. Perhaps adding some additional labeling on the predicates could solve that. I'll take a look thanks! – Leatriceleave

@EricZinda: How would "additional labeling" improve the explanation in your example? – Edington

I don't think it would in my example above, but in the real code there are more complicated predicates where just reporting the failure of a single term in a conjunction won't give the human enough information to really understand what happened. In those cases, I could add some extra metadata that says: "if any of these X terms in the conjunction fail, it means Y to a human". That is basically what I'm doing in my current solution. Does that help? – Leatriceleave

You gave an incomplete example. You need to give a complete example. – Edington