Prolog

Prolog — логический язык программирования. Вы не пишете как вычислять, вы описываете факты и правила, а затем задаёте запросы. Интерпретатор сам ищет ответы через унификацию и поиск с возвратом. Весь язык — ниже, в комментариях к коду. Примеры для SWI-Prolog.

Концепция: декларативная парадигма

Программа на Prolog — это база знаний из фактов и правил. Вычисление — это доказательство цели.

% Это комментарий — от % до конца строки.
/* А это блочный комментарий
   на несколько строк. */

% Три кита Prolog:
%   1) ФАКТ    — утверждение, которое истинно:        кот(том).
%   2) ПРАВИЛО — вывод из других утверждений:          млекопитающее(X) :- кот(X).
%   3) ЗАПРОС  — вопрос к базе знаний (в консоли):      ?- кот(том).

% Императивный язык: "сделай шаг 1, потом шаг 2...".
% Prolog: "вот что истинно — найди решение сам".

Факты: предикаты, атомы, числа

Факт — это предикат с аргументами, оканчивающийся точкой.

% Атомы пишутся с МАЛЕНЬКОЙ буквы (или в 'одинарных кавычках').
кошка(мурка).            % предикат кошка/1, аргумент — атом мурка
собака(бобик).

% Предикат может иметь несколько аргументов (арность).
родитель(мария, анна).   % родитель/2: мария — родитель анны
родитель(мария, петр).
родитель(анна, олег).

% Аргументами бывают и числа.
возраст(анна, 30).       % 30 — целое число
цена(хлеб, 45.5).        % 45.5 — число с плавающей точкой

% Атом в кавычках — если нужны пробелы или большая буква.
город('Санкт-Петербург').
статус('OK').

% "Имя предиката + арность" задаёт уникальный предикат:
% кошка/1 и родитель/2 — разные предикаты.

Правила: «если», конъюнкция

Правило Голова :- Тело читается «Голова истинна, ЕСЛИ истинно Тело». Знак :- — это «если».

% X — бабушка Y, ЕСЛИ X родитель Z И Z родитель Y.
% Запятая в теле — это конъюнкция (логическое И).
бабушка(X, Y) :-
    родитель(X, Z),      % И ...
    родитель(Z, Y).      % И ...   (точка — конец правила)

% Несколько правил для одного предиката = логическое ИЛИ.
счастлив(X) :- богат(X).      % счастлив, если богат
счастлив(X) :- влюблен(X).    % ИЛИ если влюблён

% Точка с запятой ; — тоже ИЛИ, но внутри одного тела.
может_войти(X) :-
    взрослый(X) ; есть_пропуск(X).   % взрослый ИЛИ есть пропуск

% Факт — это правило с пустым (всегда истинным) телом:
% кошка(мурка).  эквивалентно  кошка(мурка) :- true.

Запросы: цель, унификация

?- — приглашение запроса. Prolog отвечает true/false или подставляет значения переменных.

% Закрытый вопрос (без переменных) — да/нет:
?- родитель(мария, анна).
% true.

?- родитель(анна, мария).
% false.   % такого факта в базе нет

% Вопрос с переменной — Prolog ищет подстановку:
?- родитель(мария, Кто).
% Кто = анна ;        % ; (точка с запятой) — "дай ещё решение"
% Кто = петр.

% Несколько переменных сразу:
?- родитель(Р, олег).
% Р = анна.

% Запрос к выведенному правилу:
?- бабушка(мария, олег).
% true.   % мария -> анна -> олег

Переменные и унификация

Переменные начинаются с Большой буквы или _. Унификация (=) пытается сделать два терма одинаковыми.

% = НЕ присваивание, а попытка сопоставить термы.
?- X = яблоко.
% X = яблоко.

?- точка(2, 3) = точка(A, B).
% A = 2, B = 3.    % структуры совпали по форме

?- точка(2, 3) = точка(2, 9).
% false.           % 3 и 9 не унифицируются

?- X = Y, Y = 5.
% X = 5, Y = 5.     % через Y переменная X тоже стала 5

% Переменные ИММУТАБЕЛЬНЫ: связанная один раз — не меняется
% в пределах решения (нет деструктивного присваивания).

% _ — анонимная переменная: "мне всё равно, что здесь".
?- родитель(мария, _).   % есть ли у марии хоть какой-то ребёнок?
% true.

Сопоставление и поиск с возвратом (backtracking)

Если выбор привёл в тупик, Prolog откатывается и пробует другую ветку. Это и есть backtracking.

любит(анна, чай).
любит(анна, кофе).
любит(олег, кофе).

% Найти всех, кто любит кофе:
?- любит(Кто, кофе).
% Кто = анна ;     % первое решение
% Кто = олег.      % после ; Prolog откатился и нашёл второе

% Поиск общего напитка для двоих:
общий_напиток(A, B, Напиток) :-
    любит(A, Напиток),     % перебирает напитки A ...
    любит(B, Напиток).     % ... и проверяет, любит ли их B

?- общий_напиток(анна, олег, Н).
% Н = кофе.
% (для чая B=олег не подошёл -> откат -> попробовал кофе -> успех)

% Backtracking автоматически перебирает ВСЕ комбинации,
% пока не найдёт удовлетворяющую все цели подстановку.

Списки: [H|T], member, append

Список — это [элементы]. Запись [H|T] делит его на голову H и хвост T.

% Литералы списков:
% []              — пустой список
% [1, 2, 3]       — три элемента
% [a, [b, c], d]  — вложенный список

% Голова и хвост через | :
?- [H | T] = [1, 2, 3].
% H = 1, T = [2, 3].

?- [A, B | T] = [10, 20, 30, 40].
% A = 10, B = 20, T = [30, 40].

% member/2 — проверка/перебор принадлежности:
?- member(2, [1, 2, 3]).
% true.
?- member(X, [a, b]).
% X = a ; X = b.

% append/3 — конкатенация (или разбиение!) списков:
?- append([1, 2], [3, 4], R).
% R = [1, 2, 3, 4].
?- append(X, [3, 4], [1, 2, 3, 4]).   % работает "в обе стороны"
% X = [1, 2].

% length/2 — длина:
?- length([a, b, c], N).
% N = 3.

Рекурсия

Рекурсия в Prolog — норма: базовый случай (факт) плюс рекурсивное правило.

% Своя реализация member/2:
мой_member(X, [X | _]).              % база: X — голова списка
мой_member(X, [_ | T]) :-            % шаг: ищем X в хвосте
    мой_member(X, T).

% Длина списка через рекурсию:
длина([], 0).                        % база: пустой -> 0
длина([_ | T], N) :-                 % шаг: 1 + длина хвоста
    длина(T, N1),
    N is N1 + 1.

?- длина([a, b, c, d], N).
% N = 4.

% Предок через рекурсию (родитель, или родитель родителя, ...):
предок(X, Y) :- родитель(X, Y).               % база
предок(X, Y) :- родитель(X, Z), предок(Z, Y).  % шаг

?- предок(мария, олег).
% true.   % мария -> анна -> олег

Арифметика: is и сравнения

Для вычислений нужен is. Обычное = НЕ считает, а лишь унифицирует.

% is вычисляет правую часть и связывает с левой:
?- X is 2 + 3 * 4.
% X = 14.

% ВАЖНО: = не вычисляет!
?- X = 2 + 3.
% X = 2+3.      % это терм +(2,3), а не 5
?- X is 2 + 3.
% X = 5.

% Операции: + - * / (деление), // (целое), mod, abs, max, min, sqrt.
?- X is 17 mod 5.
% X = 2.
?- X is 17 // 5.
% X = 3.

% Сравнения чисел (вычисляют обе стороны):
?- 5 > 3.         % больше
% true.
?- 4 =< 4.        % меньше или равно (пишется именно =<, не <=)
% true.
?- 2 + 2 =:= 4.   % арифметическое равенство
% true.
?- 2 + 2 =\= 5.   % арифметическое неравенство
% true.

% Операторы сравнения: >  <  >=  =<  =:=  =\=

Отсечение (cut !) и отрицание

! (cut) отбрасывает альтернативы и фиксирует уже сделанный выбор. \+ — отрицание как недоказуемость.

% Без cut max даст лишнее решение при backtracking.
% С cut фиксируем первый подошедший случай:
макс(X, Y, X) :- X >= Y, !.   % если X>=Y — берём X и НЕ ищем дальше
макс(_, Y, Y).               % иначе — Y

?- макс(7, 3, M).
% M = 7.    % cut отсёк второе правило

% \+ Цель — истинно, если Цель НЕ доказывается ("отрицание"):
?- \+ член(5, [1, 2, 3]).
% true.    % 5 в списке нет -> отрицание истинно

вегетарианец(анна).
не_вегетарианец(X) :- \+ вегетарианец(X).   % кто не вегетарианец

?- не_вегетарианец(олег).
% true.    % факта вегетарианец(олег) нет

% Осторожно: \+ — это "замкнутый мир": чего нет в базе — ложно.

Встроенные предикаты: findall, between, sort

Полезный инструментарий для сбора и обработки решений.

% findall(Шаблон, Цель, Список) — собрать ВСЕ решения в список:
?- findall(Реб, родитель(мария, Реб), Дети).
% Дети = [анна, петр].

% between(Low, High, X) — перебор целых из диапазона:
?- between(1, 5, X).
% X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5.

% Собрать диапазон в список через findall + between:
?- findall(X, between(1, 5, X), L).
% L = [1, 2, 3, 4, 5].

% sort/2 — сортировка с удалением дубликатов:
?- sort([3, 1, 2, 1, 3], S).
% S = [1, 2, 3].

% msort/2 — сортировка БЕЗ удаления дубликатов:
?- msort([3, 1, 2, 1], S).
% S = [1, 1, 2, 3].

% Другие полезные: nth0/nth1 (доступ по индексу),
% sum_list/2, max_list/2, reverse/2, atom_string/2.

Практический пример: родственные связи

Соберём мини-базу знаний о семье и выведем отношения через правила.

% --- ФАКТЫ ---
мужчина(иван).
мужчина(петр).
мужчина(олег).
женщина(мария).
женщина(анна).
женщина(ольга).

родитель(иван, петр).      % иван — родитель петра
родитель(мария, петр).
родитель(иван, анна).
родитель(петр, олег).
родитель(петр, ольга).

% --- ПРАВИЛА ---
отец(X, Y)  :- родитель(X, Y), мужчина(X).
мать(X, Y)  :- родитель(X, Y), женщина(X).

% Брат/сестра: общий родитель, но это не один и тот же человек.
сиблинг(X, Y) :-
    родитель(P, X),
    родитель(P, Y),
    X \== Y.               % \== — "не идентичны" (термы разные)

брат(X, Y) :- сиблинг(X, Y), мужчина(X).

дед(X, Y) :- родитель(X, Z), родитель(Z, Y).

% --- ЗАПРОСЫ ---
?- отец(иван, анна).
% true.

?- дед(иван, олег).
% true.    % иван -> петр -> олег

?- findall(B, брат(B, ольга), Братья).
% Братья = [олег].

?- findall(Реб, отец(иван, Реб), Дети).
% Дети = [петр, анна].

% Вся мощь Prolog: мы описали ЧТО значит "дед" и "брат",
% а поиск конкретных людей сделал интерпретатор сам.