How to get Prolog to explain your result beyond the true statement

Question

I have the following facts and rules:

  flight(sea,msp).
  flight(msp,jfk).

 route(A,B) :- flight(A,B). 
 route(B,A) :- flight(A,B). 
 route(A,C) :- flight(A,B) , flight(B,C). 

when query for route(sea,jfk) I get a result true but what I wish to get is the explination:

sea-->msp-->jfk this way I can tell not only that it's true but also how it's true.

Answer 1

So you want to get from A to B, but not only that, you also want to know the list of stations of your itinerary.

Be sure to carefully look at the following two related questions and the answers proposed to the question:

• Definition of path/trail/walk
• Definition of Reflexive Transitive Closure

The meta-predicates presented in above links allow you to delegate the handling of recursion to a solid, tested, reusable component. More time to focus on other parts of the problem solving!

Answer 2

You keep track of what nodes in your graph that you've already visited. You need to do this anyway, as you need to detect cycles in your graph lest you fall into the rabbit hole of infinite recursion.

And in Prolog, we use helper methods that carry state around as 1 or more extra arguments. A frequently used convention is to have a "public" predicate — say route/3 that invokes a "private" worker predicate having the same name with a higher arity, say route/4. Something like this ought to do you:

route( A , B , R  ) :- % find a route R from A to B
  route(A,B,[],R)      % - by invoking a worker, seeding its list of visited nodes with the empty list
  .                    % Easy!

route(B,B,V,R) :-    % we've arrived at the destination (B) when the origination node is the same as the destination node.
  reverse([B|V],R)   % - just reverse the list of visited nodes to get the routing.
  .                  %
route(A,B,V,R) :-    % otherwise...
  flight(A,T) ,      % - if there's an edge out of the current node (A) ,
  \+ member(T,V) ,   % - to an as-yet unvisited node...
  route(T,B,[A|V],R) % - go visit that node, marking the current node as visited.
  .                  % Easy!

Answer 3

If you neither want to use debugging, nor write additional methods using helper predicates, a third option is to make use of the many built-in capabilities of SWI-Prolog for meta-programming. In this case, the clause/2 predicate might be helpful (it is part of the ISO standard, so other Prolog dialects might have it too, but I haven't checked):

clause(:Head, ?Body)

True if Head can be unified with a clause head and Body with the corresponding clause body. Gives alternative clauses on backtracking. For facts, Body is unified with the atom true.

So we could write a generic predicate expl(+Goal,-Expl) that constructs an "explanation" for a Goal, in case the Goal succeeds:

flight(sea,msp).
flight(msp,jfk).

route(A,B) :- flight(A,B). 
route(B,A) :- flight(A,B). 
route(A,C) :- flight(A,B) , flight(B,C). 

% construct an explanation for a solution
expl([],[]).
expl([Goal|Goals],[(Goal,BodyExpl)|Expl]) :-
        clause(Goal,Body),
        clause_body_list(Body,BodyL),
        expl(BodyL,BodyExpl),
        expl(Goals,Expl).

% turn output of clause/2 into a list
clause_body_list(true,[]) :- !.
clause_body_list((A,B),[A|BL]) :- !,
        clause_body_list(B,BL).
clause_body_list(A,[A]) :- !.

This yields:

?- expl([route(sea,jfk)],X).
X = [(route(sea, jfk), [(flight(sea, msp), []),  (flight(msp, jfk), [])])].

It also supports backtracking and queries with variables:

?- expl([route(A,B)],X).
A = sea,
B = msp,
X = [(route(sea, msp), [(flight(sea, msp), [])])] ;
A = msp,
B = jfk,
X = [(route(msp, jfk), [(flight(msp, jfk), [])])] ;
A = msp,
B = sea,
X = [(route(msp, sea), [(flight(sea, msp), [])])] ;
A = jfk,
B = msp,
X = [(route(jfk, msp), [(flight(msp, jfk), [])])] ;
A = sea,
B = jfk,
X = [(route(sea, jfk), [(flight(sea, msp), []),  (flight(msp, jfk), [])])] ;
false.

Note that such an explanation is not necessarily a list, but generally takes the form of a (SLD) tree, hence the nested structure of the output.

Edit: To explain the above a bit further: The output is a list of "explanations" of the form (Goal, BodyExpl), where each Goal is a (sub)goal that was proved, and BodyExpl is again a list of such explanations for all the recursive subgoals that were used for proving Goal. For facts, the BodyExpl part is simply empty. In general, this structure can be nested arbitrarily deep (depending on your input program).

If you find this hard to read, are not interested in processing the output any further, and only want a human-readable explanation, you could do the following:

flight(sea,msp).
flight(msp,jfk).

route(A,B) :- flight(A,B). 
route(B,A) :- flight(A,B). 
route(A,C) :- flight(A,B) , flight(B,C). 

% construct an explanation for a solution
expl([]).
expl([Goal|Goals]) :-
        clause(Goal,Body),
        clause_body_list(Body,BodyL),
        expl(BodyL),
        expl(Goals),
        write_expl(Goal,Body).

% turn output of clause/2 into a list
clause_body_list(true,[]) :- !.
clause_body_list((A,B),[A|BL]) :- !,
        clause_body_list(B,BL).
clause_body_list(A,[A]) :- !.

% write explanation
write_expl(Goal, true) :- !,
        writef('%w is a fact.\n',[Goal]).
write_expl(Goal, Body) :- !,
        writef('%w because of %w.\n', [Goal,Body]).

This yields for example:

?- expl([route(sea,jfk)]).
flight(msp,jfk) is a fact.
flight(sea,msp) is a fact.
route(sea,jfk) because of flight(sea,msp),flight(msp,jfk).

Note that you want to call write_expl only after making the recursive calls to expl, since some of the variables may only get instantiated during the recursive calls.

Answer 4

This is something that heavily depends on your prolog-system. As you have tagged it as swi, I'll give you a SWI-specific answer.

You can start the tracer. With trace/0:

?: trace.
true

[trace]?:

When you now enter a query, you can see all the call, exits, fails and redos of a predicate. You can't see the variable names in the command line tracer, though. To see what actions you can take, you can type h. The most interesting are probably n for next step and f to finish the current goal.

Or also can make use of trace/1 and trace/2 to output parts of the call stack:

?: trace(flight/2). % calls, exits, fails and redos are output for flight/2

?: trace(route/2, +exit).  % only exits are output for route/2.

If you also have xpce installed, you can use gtrace/0 for a graphical interface.

If you want to access your route from within prolog, you also could write a new route/3 that also outputs a list of the way.

So for your case, you could do the following query:

?- trace(flight/2,+exit).
%         flight/2: [exit]
true.

[debug]  ?- route(sea,jfk).
 T Exit: (7) flight(sea, msp)
 T Exit: (7) flight(msp, jfk)
true.