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?

You need a [base case](http://www.cse.unsw.edu.au/~billw/cs9414/notes/write-recursive-proc.html) — Guy Coder, Mar 27 '20 at 10:04
Prolog doesn't have statements so you can't "declare the exit statement". — Enigmativity, Mar 27 '20 at 10:33
Also Prolog doesn't "return" anything so you can't "return true". — Enigmativity, Mar 27 '20 at 10:33
One thing that many new programmers fail to do is to start by doing the problem with pen and paper to understand the problem. Once you understand the problem with pen and paper and can reproduce the results with different problems, then translate that to a program. Remember that a computer is a tool to help you accomplish a task like a screw driver will help you a use screw properly, so will a proper understanding of the problem. In other words you would not use a hammer to put in a screw. — Guy Coder, Mar 27 '20 at 10:39
`closure(directFlight, A, B)` using [`closure/3`](https://stackoverflow.com/q/26946133/772868). — false, Mar 27 '20 at 15:50
@false "I say we closure the whole site from orbit - it's the only way to be sure" — David Tonhofer, Mar 27 '20 at 16:23
@David: You meant quarantine, wait, I'll find something fit. — false, Mar 27 '20 at 19:05

David Tonhofer · Accepted Answer · 2020-03-27T13:14:10.083

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:

If there is a directFlight/2 between them (the base case)
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.
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.

@GuyCoder Not at all (or rather, I absolutely agress). Just encoding the transitive closure of `directFlight/2` as a two-clause predicate. — David Tonhofer, Mar 27 '20 at 10:51
Stackoverflow is now warning me that my latest edit can only be saved "if it is more thorough and the current edit". Did they sic a TensorFlow magic decision engine on edits? This place is going downstream. — David Tonhofer, Mar 27 '20 at 10:53
@GuyCoder I mean, the next question will be about building the routes. Thank you for the graphics appreciation. — David Tonhofer, Mar 27 '20 at 11:21

Recursive loop exit statement needed

1 Answers1

Addendum 1

Addendum 2

Linked