Кратко о самом коде
member(X,[X|_]).
member(X,[_|T]) :- member(X,T).
1) Как идёт поиск (backtracking)
- При вызове запроса Prolog пробует первую подходящую по унификации клаузу, затем при успехе возвращает ответ; при последующем backtracking идёт к следующей клаузе и т. д.
- Пример: запрос `member(a,[b,a,c])`. Шаги:
1. Пробует первую клаузу: унификация $X=a$ с головой \([X|_]=[b|_']\) неудачна ( $a\ne b$ ).
2. Переходит ко второй: $[b,a,c]={[}_{|}T]$ даёт $T=[a,c]$, рекурсивно вызывает `member(a,[a,c])`.
3. Внутри рекурсии первая клаузa теперь удачна: $[a,c]=[X{|}_{]}$ даёт $X=a$ — успех, возвращается ответ.
4. При backtracking Prolog попытается найти другие варианты: внутри рекурсии других вариантов в первой клаузе уже нет, возвращается наверх и пробует, есть ли ещё варианты при предыдущих унификациях (например другие места в списке) — он продолжит искать дальше по второй клаузе, пока список не исчерпается.
2) Когда возникает бесконечный поиск
a) Порядок правил
- Если поставить рекурсивную клаузу раньше базовой:
member(X,[_|T]) :- member(X,T).
member(X,[X|_]).
- Запрос `member(X,L)` (с $L$ неинициализированным) будет приводить к бесконечной рекурсии: Prolog сначала всегда выбирает рекурсивную клаузу, унифицирует $L={[}_{G}1|T]$ и вызывает `member(X,T)` с $T$ всё ещё неинициализированным, затем снова и снова — цепочка $T={[}_{G}2|T2]$, $T2={[}_{G}3|T3]$ … никогда не достигается базовый случай, потому что он стоит после рекурсии. Пример унификаций: $L={[}_{G}1|T],T={[}_{G}2|T2],T2={[}_{G}3|T3],\dots$ — бесконечный спуск.
b) Порядок аргументов (ошибка в рекурсивном вызове)
- Если по опечатке поменять аргументы в рекурсивном вызове, например:
member(X,[X|_]).
member(X,[_|T]) :- member(T,X).
то предикат начинает вызывать себя с несовместными позициями аргументов, что может привести к бесконечной рекурсии или к бессмысленному разрастанию термов в зависимости от запроса. Например запрос с незаполненными переменными легко породит нескончаемую генерацию некорректных унификаций.
Вывод/рекомендация: базовый (не рекурсивный) случай нужно ставить раньше рекурсивного; в рекурсивных вызовах следить за тем, чтобы аргументы передавались в той же роли, в которой они ожидались, иначе возможно зацикливание.