Prolog backtracks and loses all values

Question

I have a few prolog predicates which calculate the cost of given cities. The process begins with a command like: best_route([std, lhr, bud, dse], 2013-5-5, X).

best_route(Cities, StartDate, Cost):-
    begin_routing(Cities, StartDate, Cost, []).

begin_routing(Cities, StartDate, Cost, CostList):-
    route(Cities, StartDate, CostList),
    min_list(CostList, Cost).

route(Cities, StartDate, Costing):-
    % stop if all cities have been covered once.
    length(Cities, Stop),
    length(Costing, Stop);

    [Origin, Dest|_] = Cities,
    flights(Origin, Dest, StartDate, Costing, Cities, [Cities, Origin, StartDate]).

Using the trace function in SWI-Prolog, I found that once the route predicate - length(Costing, Stop) is satisfied i.e., length of Costing List is equal to Stop. Prolog instead of stopping there, and proceeding with min_list(CostList, Cost), instead backtracks until CostLost loses all its values again. Once it finishes that, it goes to min_list when the list is [].

I am not sure why this might be happening. Any help is appreciated.

EDIT:

flights(..):-
    % Code omitted.
    get_next_date(OriginalDate, NextDate),
    route(Cities, NextDate, [DayCost|Costing]).
    % where DayCost is a simple integer calculated before this is added to the current Costing list

Towards the end, the last correct call is route([std, lhr, bud, dse], 2013-5-6, [329, 499, 323, 311]).

Reading through best_route and begin_routing, it appears that when route is first called, Cities is instantiated to [std, lhr, bud, dse] and Costing is instantiated to []. The call to length(Costing, Stop) becomes length([], 4) and fails. It is terminated in a disjunction (;) and, therefore route doesn't fail at that point but continues with [Origin, Dest|_] = Cities instantiating Origin and Dest and then calling flights. Since you don't show what flights does, it's unclear what it does from there. — lurker
@mbratch: Please have a look at the edited question, I am omitting parts of code as they are fairly unnecessary and lengthy. Hope this makes it clearer. — Namit
@Namit: min_list(CostList, Cost) fails or requires more evaluation ? to force termination, add a dumb alternative: ( min_list(CostList, Cost) ; true ) — CapelliC
@mbratch: It fails because the CostList is not being carried over the recursion period. Adding true does not make much difference either. — Namit
@Namit, I was indicating why it didn't immediately go back to the min_list — lurker

Alexander Serebrenik Alexander Serebrenik · Accepted Answer · 2013-07-08T19:19:38

It seems that the intention of CostList is to record the costs of different routes and then to select the one with the smallest cost. However, you initialize CostList as [], and while the recursion is building CostList you do not provide means of communicating it back when the recursion returns. A possible solution would be to add a new argument FinalCostList that is being simply passed through the recursion until the termination clause. Alternatively, you can use difference lists.

To illustrate this point, consider the following example:

p :- q([]).
q(X) :- go(X), !, q([a|X]).
q(X) :- stop(X).

with some mutually exclusive go and stop. The desired outcome (q with all as as long as go) is computed but not returned. A better solution would be

p(Y) :- q([],Y).
q(X,Y) :- go(X), !, q([a|X],Y).
q(X,X) :- stop(X).

As said above difference lists can also be used.

Prolog backtracks and loses all values

1 Answers