Search code examples
prologfirst-order-logic

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

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.

Solution

  • 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:

    There must be more.