Кратко о предикате append/3
- Стандартное определение:
```
append([], L, L).
append([H|T], L2, [H|R]) :- append(T, L2, R).
```
(в тексте ниже числовые и списочные значения записаны в KaTeX).
Разбор запроса `append([1,2],[3,4],X)` — шаги резолюции, унификация и бэктрекинг
1) Вызов: `append($[1,2]$, $[3,4]$, X)`.
2) Сравнение с первой клаузой `append([],L,L)`:
- первая позиция `$[1,2]$` не унифицируется с `[]` — эта клауза не подходит (унификация неудачна).
3) Сравнение со второй клаузой `append([H|T], L2, [H|R]) :- ...`:
- унификация успешна, даёт привязки:
- $H=1$ - $T=[2]$ - $L2=[3,4]$ - $X=[H|R]$ → пока $X=[1|R]$.
- создаётся рекурсивный вызов: `append($[2]$, $[3,4]$, R)`.
4) Во втором вызове `append($[2]$, $[3,4]$, R)`:
- первая клауза снова не подходит (не пустой список).
- вторая клауза унифицируется:
- $H=2$ - $T=[]$ - $L2=[3,4]$ (согласуется)
- $R=[H|R2]$ → $R=[2|R2]$.
- теперь $X=[1|R]=[1|[2|R2]]$.
- рекурсивный вызов: `append([], [3,4], R2)`.
5) Третий вызов `append([], [3,4], R2)`:
- унифицируется с первой (базовой) клаузой `append([],L,L)`:
- $R2=[3,4]$.
6) Сворачивание (unwind):
- $R=[2|R2]=[2|[3,4]]=[2,3,4]$.
- $X=[1|R]=[1,2,3,4]$.
- Возвращается решение $X=[1,2,3,4]$.
Бэктрекинг:
- После выдачи решения Prolog пытается найти другие решения: он откатывается к точкам выбора (clauses/unification), чтобы попробовать альтернативы.
- В нашем случае альтернатив нет (во время каждого вызова только одна клауза подходила, или первая была невозможна), поэтому больше решений не будет.
- В общем, Prolog использует глубинный поиск (depth-first, слева направо): при неудаче откатывается к последнему выбору и пробует следующую альтернативу.
Коротко о механике унификации
- Унификация пытается сделать два терма синтаксически одинаковыми присвоением значений переменным (пример: $[1,2]$ унифицируется с $[H|T]$ даёт $H=1,T=[2]$).
- Обычно происходит без проверки occurs-check (возможны циклические связывания в некоторых реализациях).
- Переменные получают привязки, которые сохраняются до отката (backtracking) — при откате привязки снимаются.
Задача, где логическое программирование элегантнее императивного
- Задача: перечислить все простые (без повторных вершин) пути между двумя вершинами в неориентированном графе.
- В Prolog это записывается компактно рекурсией и чередованием/бэктрекингом; пример (иллюстративно):
```
edge(a,b). edge(b,c). edge(a,c). ...
path(X,Y,Visited,[X,Y]) :- edge(X,Y), \+ member(Y,Visited).
path(X,Y,Visited,[X|Rest]) :-
edge(X,Z), \+ member(Z,Visited),
path(Z,Y,[Z|Visited],Rest).
```
- Запрос `path(a,c,[a],P).` автоматически переберёт все простые пути $P$ (бэктрекинг генерирует варианты).
- Почему элегантно:
- Ничего не нужно вручную управлять стеком поиска или явно откатывать состояния — Prolog сам делает поиск и откат.
- Код прямо описывает отношение "существует путь" и генерацию решений, а не алгоритмическую процедуру пошагово.
- Альтернативы в императивном стиле требуют явного управления очередью/стеком, множества посещённых вершин и явной электронной логики для генерации всех комбинаций, что за объёмом и очевидностью часто проигрывает логическому описанию.
Если нужно, могу дать полный пример кода Prolog для поиска всех простых путей и показать результаты нескольких запросов.