Почему это вызывает бесконечную рекурсию?

Question

У меня есть эта программа в прологе, где я в основном определяю график людей, и мне нужно сделать некоторые предикаты, которые покажут мне, какие люди связаны, а какие - клики. Вот факты:

graph([person(susan, [reed, jen, andrzej, jessica]),
   person(reed, [tony, jessica]),
   person(jessica, [jen,susan]),
   person(tony, []),
   person(ken, [andrzej]),
   person(jen, [tony, susan, jessica]),
   person(andrzej, [susan, ken])]).

И вот определение моего предиката по имени клика. Он принимает в качестве параметров граф G и список людей и пытается проверить, действительно ли человек в списке является кликой друзей (это означает, что предикат хороших друзей верен для каждой пары людей в списке)

clique(G, [FriendOne, FriendTwo]):-
  goodfriends(G, FriendOne, FriendTwo).
clique(G, [FriendOne | FriendList]):-
  atLeastTwoElements(FriendList),
  clique(G, FriendList),
  goodFriendWith(G, FriendOne, FriendList).

Что делает клика: если список состоит только из двух человек, просто проверьте этих двух людей, если они хорошие друзья. Если это правда, то между ними есть клика. Если в списке людей более двух человек, то для каждого главы списка, т.е. человека, проверьте, является ли он хорошим другом с остальными людьми в конце списка, и сделайте это рекурсивно для всего списка. человек. Ниже определены остальные предикаты помощника для клики для работы.

goodfriends(G, FriendOne, FriendTwo):-
  getPerson(G, FriendOne, PersonOne),
  getPerson(G, FriendTwo, PersonTwo),
  hasFriend(PersonOne, FriendTwo),
  hasFriend(PersonTwo, FriendOne).

%% checks if this friend is goodfriend with all these friends
goodFriendWith(_, _, []).
goodFriendWith(G, FriendOne, [FriendTwo | FriendList]):-
  goodFriendWith(G, FriendOne, FriendList),
  goodfriends(G, FriendOne, FriendTwo).

%% gets specific person by a name from the graph
getPerson([person(Name, Friends)|_], Name, person(Name, Friends)).
getPerson([_|T], Name, Result):-
  getPerson(T, Name, Result).

%% checks if a person has a certain friend
hasFriend(person(_, Friends), Friend):-
  member_(Friend, Friends).

member_(X, [X|_]).
member_(X, [_|Tail]) :- member_(X, Tail).
atLeastOneElement([_|_]).
atLeastTwoElements([_,_|_]).

Вопрос

Когда я создаю предикат с именем runner, чтобы проверить предикат "клика":

runner(R):-
  graph(G),  
  clique(G, R).

Я хочу, чтобы он возвращал все клики внутри графика, но мой результат:

?- runner(R).
R = [susan, jessica] ;
R = [susan, jen] ;
R = [susan, andrzej] ;
R = [jessica, susan] ;
R = [jessica, jen] ;
R = [ken, andrzej] ;
R = [jen, susan] ;
R = [jen, jessica] ;
R = [andrzej, susan] ;
R = [andrzej, ken] ;
R = [jen, susan, jessica] ;
R = [jessica, susan, jen] ;
R = [jen, jessica, susan] ;
R = [susan, jessica, jen] ;
R = [jessica, jen, susan] ;
R = [susan, jen, jessica] ;
ERROR: Out of local stack

Что не так в рекурсии? Я знаю, что получаю правильные результаты, но по какой-то причине после того, как все результаты показаны, он продолжает повторяться.

Заранее спасибо.

Answer 1

В чистой монотонной программе, подобной вашей, есть простая техника отладки. Просто добавь false цели в вашу программу. Если результирующая программа все еще зацикливается, оставшаяся видимая часть должна быть исправлена. (Может быть больше ошибок, но пока эта часть не исправлена, вы не исправите проблему)

Вот что я получил так далеко:

второе место (R) -
  граф (G)
  клика (G, R), ложь.

клика (G, [FriendOne, FriendTwo]):- ложь,
  хорошие друзья (G, FriendOne, FriendTwo).
клика (G, [FriendOne | FriendList]):-
  atLeastTwoElements(список друзей),
  goodFriendWith (G, FriendOne, FriendList), false,
  клика (G, FriendList).

Поэтому одна или одна проблема заключается в goodFriendWith, Я нашел несколько раздражающим, что ваше определение успешно для бесконечного числа списков, например, так:

?- length(L,N),
   maplist(=(jessica),L),
   goodFriendWith(
      [  person(susan,[reed,jen,andrzej,jessica]),
         person(reed,[tony,jessica]),
         person(jessica,[jen,susan]),
         person(tony,[]),
         person(ken,[andrzej]),
         person(jen,[tony,susan,jessica]),
         person(andrzej,[susan,ken])],
      susan,
      L).
L = [],
N = 0 ;
L = [jessica],
N = 1 ;
L = [jessica, jessica],
N = 2 ;
L = [jessica, jessica, jessica],
N = 3 ;
L = [jessica, jessica, jessica, jessica],
N = 4 ;
L = [jessica, jessica, jessica, jessica, jessica],
N = 5 ...

Так что для двух человек уже существует бесконечное множество разных решений. Это не может прекратить! Вы должны это исправить.

Или, если выразиться еще точнее:

?- goodFriendWith([person(susan,[jessica]),person(jessica,[susan])],susan,L).
L = [] ;
L = [jessica] ;
L = [jessica, jessica] ;
L = [jessica, jessica, jessica] ;
L = [jessica, jessica, jessica, jessica] ;
L = [jessica, jessica, jessica, jessica, jessica] 

Эта цель должна привести к конечному числу решений. Однако их бесконечно много.

Поскольку вы удивлены результатом, давайте продолжим отладку. Чтобы сделать это еще более очевидным, я сейчас добавлю дополнительные цели (=)/2, Эти цели будут также специализироваться на программе:

goodFriendWith (_, _, []):- неверно.
goodFriendWith (G, FriendOne, [FriendTwo | FriendList]):-
  FriendOne = Сьюзен,
  FriendTwo = Джессика,
  хорошие друзья (G, FriendOne, FriendTwo),
  goodFriendWith (G, FriendOne, FriendList), false.? - goodFriendWith ([человек (Сьюзен, [Джессика]), человек (Джессика, [Сьюзан])], Сьюзен,L).

Опять же, запрос зацикливается! Вы действительно должны увидеть проблему сейчас.