Recursive loop exit statement needed

Question

this is a simple prolog example of recursion. I cannot figure out where, and more or less how, to declare the exit statement. The test flight(sofia, dublin) should return true, but it keeps checking at the last steps if you can directFlight(dublin, dublin). Here is the code:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- 
   directFlight(City1, City3),      
   flight(City3, City2).

The output:

 [trace]  ?- flight(sofia, dublin).
   Call: (8) flight(sofia, dublin) ? creep
   Call: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, varna) ? creep
   Call: (9) flight(varna, dublin) ? creep
   Call: (10) directFlight(varna, _878) ? creep
   Fail: (10) directFlight(varna, _878) ? creep
   Fail: (9) flight(varna, dublin) ? creep
   Redo: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, paris) ? creep
   Call: (9) flight(paris, dublin) ? creep
   Call: (10) directFlight(paris, _878) ? creep
   Exit: (10) directFlight(paris, new_york) ? creep
   Call: (10) flight(new_york, dublin) ? creep
   Call: (11) directFlight(new_york, _878) ? creep
   Exit: (11) directFlight(new_york, seattle) ? creep
   Call: (11) flight(seattle, dublin) ? creep
   Call: (12) directFlight(seattle, _878) ? creep
   Fail: (12) directFlight(seattle, _878) ? creep
   Fail: (11) flight(seattle, dublin) ? creep
   Fail: (10) flight(new_york, dublin) ? creep
   Fail: (9) flight(paris, dublin) ? creep
   Redo: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, london) ? creep
   Call: (9) flight(london, dublin) ? creep
   Call: (10) directFlight(london, _878) ? creep
   Exit: (10) directFlight(london, edinburg) ? creep
   Call: (10) flight(edinburg, dublin) ? creep
   Call: (11) directFlight(edinburg, _878) ? creep
   Fail: (11) directFlight(edinburg, _878) ? creep
   Fail: (10) flight(edinburg, dublin) ? creep
   Redo: (10) directFlight(london, _878) ? creep
   Exit: (10) directFlight(london, dublin) ? creep
   Call: (10) flight(dublin, dublin) ? creep
   Call: (11) directFlight(dublin, _878) ? creep
   Fail: (11) directFlight(dublin, _878) ? creep
   Fail: (10) flight(dublin, dublin) ? creep
   Fail: (9) flight(london, dublin) ? creep
   Fail: (8) flight(sofia, dublin) ? creep
false.

The issue is here at: Fail: (10) flight(dublin, dublin) ? creep. Any ideas how to fix this?

Answer 1

Do not think in terms of loops needing exit statements. In fact, don't use the debugger at all, it's mightily confusing even if you DO know what is going on in the Prolog Processor.

You start off with a network of nodes connected by a set of edges (the relation).

In this case, the nodes are represented by atoms (denoting cities), the set of edges the relation called directFlight/2.

Now you want to overlay another set of edges, called flight/2.

So you have to ask yourself when do I have a flight/2 edge between two atoms A and B

There are two cases:

1. If there is a directFlight/2 between them (the base case)
2. If there is an intermediate node I such that there is a flight/2 from A to I and a directFlight/2 between I and B.
3. Alternatively, if there is an intermediate node I such that there is a directFlight/2 between A and I and a flight/2 from I to B.

Prolog will find the flight/2 edge by itself when asked for

flight(sofia, dublin).

(same as a relational database finds the result of an SQL query) but you have to pay some attention to termination. The alternative case (3) above will lead to a successful search or "false". The case (2) will lead to non-termination - entirely due to Prolog's search strategy (where decisions have to be taken on how a real-world machine searches through a network, in this case, depth-first, leftmost first).

Here is the base case for flight/2 (first image), all the flight/2 deduced by recursion of 1 call deep, and all the flight/2 deduced by recursion of 2 calls deep.

So:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, City3), flight(City3, City2).

And then:

?- flight(sofia,dublin).
true ;
false.

?- flight(sofia,X).
X = varna ;
X = paris ;
X = london ;
X = new_york ;
X = seattle ;
X = edinburg ;
X = dublin ;
false.

?- flight(X,sofia).
false.

Addendum 1

The above program can be read:

• "from LEFT :- to RIGHT" (as Prolog does). It is a search to ascertain whether a flight/2 fact holds or whether values can be found that make it true.
• "from RIGHT -: to LEFT". The mental image is of continually accumulating new facts about flight/2 until one has collected them all and nothing is added anymore: bottom-up search (this is somehow easier on the brain, at least for me). Safer than search as you don't risk hitting an infinite recursion sinkhole just because the clauses are arranged in an unfortunate way, and is what some Datalog implementations do.

The logical reading is of a (or two) statement ("the program") that gives constraints about how flight/2 is supposed to be structured:

∀(City1, City2) : 
  (flight(City1, City2) <= 
     directFlight(City1, City2))
∧

∀(City1, City2) :
  (flight(City1, City2) <= 
     (∃City3: directFlight(City1, City3) ∧ flight(City3, City2))

Note that there is nothing in the above that precludes that flight(X,Y) might hold for OTHER reasons than the one stated. We assume, however, that we know everything about when flight(X,Y) holds: Closed-World Assumption.

Addendum 2

Something one often forgets is that there need not be a recursive call at all. The recursion can be "unrolled" and the edge-to-edge linking made explicit:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, Ib), 
                        directFlight(Ib, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, Ib),
                        directFlight(Ib, Ic),
                        directFlight(Ic, City2).

None of the cities are more than 3 hops apart, so the above program will find all flight/2 connections.

In fact, another exercise would be to generate the above program, giving it as argument the "max depth" to consider.