SWI-Prolog Backtrace Infinite Loop

问题:

I have a toy module;

:- module(toys,toy/2).

%toy(TOY_NAME,PRICE).

and I have some toy elements,

toy(train,5).
toy(doll,6).
toy(car,3).
..ext.

I wrote a function that calculates the total price of given toy list such as

calculatePrice([],0).
calculatePrice([H|T],Result):- toy(H,P),calculatePrice(T,X), Result is X+P.

when I called calculatePrice([train,train,doll,train],X) it works fine and returns 21. But when I call calculatePrice(X,21) an infinite loop occurs.

I tried to user cut, but then i only got 1 answer, I want to get all possible answers like all combinations of toys that will be total price of 21.

回答1:

Prolog works depth first, so that means that it will keep looking to append the list further with toys into the list, and never looks whether the total price already is reached, and thus adding more elements makes no sense.

We can solve this by calculating the price in reverse: we can use the library(clpfd) and define the relation between the price of the list with the toy and the price without the toy, and add a constraint that the price we are looking for should always be larger than zero if we recurse, like:

:- use_module(library(clpfd)).

calculatePrice([], 0).
calculatePrice([H|T], PHT) :-
    PHT #> 0,
    toy(H, PH),
    PHT #= PT + PH,
    calculatePrice(T, PT).

We then obtain for example:

?- calculatePrice(L, 21).
L = [train, train, train, doll] ;
L = [train, train, train, car, car] ;
L = [train, train, doll, train] ;
L = [train, train, car, train, car] ;
L = [train, train, car, car, train] ;
L = [train, doll, train, train] ;
...

?- calculatePrice([train, train], P).
P = 10.

?- calculatePrice(L, P).
L = [],
P = 0 ;
L = [train],
P = 5 ;
L = [train, train],
P = 10 ;
L = [train, train, train],
P = 15 ;
L = [train, train, train, train],
P = 20 ;
L = [train, train, train, train, train],
P = 25 
...

The constraint PHT #> 0 is necessary here. You can see PHT when we query with for example calculatePrice(L, 21) as the "amount we have left to spend". In case that amount is less than or equal to zero, we can not spent any money anymore, and thus this constraint should fail.

回答2:

there is a method, iterative deepening, that is able to tackle your problem, has a basic implementation really easy in Prolog, and doesn't require any complex library:

:- module(calculatePrice,
          [calculatePrice/2
          ]).

toy(train,5).
toy(doll,6).
toy(car,3).

calculatePrice(L, P) :-
    length(L, _N),
    maplist(toy, L, Ps),
    sumlist(Ps, P).

yields

?- calculatePrice(Ts,21).
Ts = [train, train, train, doll] ;
Ts = [train, train, doll, train] ;
Ts = [train, doll, train, train] ;
...

Beware, it's not terminating. Can you spot why ? And correct it ? Otherwise, ask for help :)

If you want to know better about iterative deepening and Prolog, see this page, or this doc...