How to stop infinite recursion in PROLOG

user_14741508 0
Viewed 151

I have a knowledge base of people and how much they trust in each other based on a number, if A trusts B then B trusts A the same amount.

  trusts(josemari,lucia,4.0).
  trusts(raul,josemari,3.0).
  trusts(luis,felipe,2.0).
  trusts(manolo,felipe,2.5).
  trusts(pepe,vidal,1.0).
  trusts(pepe,luis,0.5).

  trusts(A,B,K):-
         trusts(B,A,K).

That gets me in an infinite recursion, so, how could I break the recursion? chaning the trusts predicate is not an option and rewriting the Knowledge base adding the opposits is not an option either.

prolog recursion
2 Answers

If you are using SWI-Prolog, you can table the predicate. Just add a table directive:

:- table trusts/3.

trusts(josemari,lucia,4.0).
trusts(raul,josemari,3.0).
trusts(luis,felipe,2.0).
trusts(manolo,felipe,2.5).
trusts(pepe,vidal,1.0).
trusts(pepe,luis,0.5).

trusts(A,B,K):-
     trusts(B,A,K).

Now it works as intended:

?- trusts(josemari, X, Y).
X = lucia,
Y = 4.0 ;
X = raul,
Y = 3.0.

?- trusts(luis, X, Y).
X = pepe,
Y = 0.5 ;
X = felipe,
Y = 2.0.

?- trusts(X, luis, Y).
X = pepe,
Y = 0.5 ;
X = felipe,
Y = 2.0.

?- trusts(A, B, K), K >= 3.0.
A = josemari,
B = lucia,
K = 4.0 ;
A = josemari,
B = raul,
K = 3.0 ;
A = lucia,
B = josemari,
K = 4.0 ;
A = raul,
B = josemari,
K = 3.0 ;
false.

If you don't have SWI-Prolog or another implementation with tabling, you need to define another rule, with a different name:

trusts(josemari,lucia,4.0).
trusts(raul,josemari,3.0).
trusts(luis,felipe,2.0).
trusts(manolo,felipe,2.5).
trusts(pepe,vidal,1.0).
trusts(pepe,luis,0.5).

trusts_commutative(A, B, K):-
    trusts(A, B, K).
trusts_commutative(A, B, K):-
    trusts(B, A, K).

The result is the same.

?- trusts_commutative(X, luis, Y).
X = pepe,
Y = 0.5 ;
X = felipe,
Y = 2.0.

?- trusts_commutative(A, B, K), K >= 3.0.
A = josemari,
B = lucia,
K = 4.0 ;
A = raul,
B = josemari,
K = 3.0 ;
A = lucia,
B = josemari,
K = 4.0 ;
A = josemari,
B = raul,
K = 3.0 ;
false.
user_144119970

You can require that A and B are bound:

trusts(A,B,K) :- nonvar(A), nonvar(B), trusts(B,A,K)

But it will work only in some cases. That is it will never get stuck but you won't be able to use it to find all the trusts relations.

I think better solution is to separate the basic trust levels from the advanced trust relations. Like

advanced_trust(A,B,K) :- trusts(A,B,K) ; trusts(B,A,K).
user_31986380
Related