Prolog: логическое программирование на практике

Prolog появился в 1972 году как язык для работы с логикой, но до сих пор остаётся сильным инструментом в узкой нише: там, где задачу проще описать правилами и ограничениями, чем пошаговым алгоритмом. Проверка конфигураций, планирование смен, разбор формальных грамматик, подбор комплектации — во всех этих случаях перебор с возвратом и унификация экономят сотни строк кода. Разберём практику на SWI-Prolog: от фактов до CLP(FD), отсечения и сборки исполняемого файла.

Где Prolog действительно уместен

Prolog — декларативный язык: вы описываете, что истинно, а не как это вычислить. Механизм вывода сам перебирает варианты и возвращается назад при неудаче. Это даёт короткие решения для задач с комбинаторной структурой.

• Экспертные системы и правила диагностики.
• Планирование и распределение ресурсов с ограничениями.
• Разбор языков, протоколов и конфигурационных форматов.
• Прототипирование запросов к графам и базам знаний.

Для веб-бэкенда, потоковой обработки и численных расчётов Prolog брать не стоит: идиоматический код там будет медленнее и менее понятным, чем на Python или Go. Лучший сценарий — небольшая подсистема, вызываемая из основного приложения.

Установка и первая программа

В большинстве дистрибутивов пакет называется swi-prolog. После установки доступна интерактивная среда swipl, где запросы вводятся с вопросительным знаком.

sudo apt install swi-prolog
swipl --version
swipl -q
?- write('hello'), nl.

Файл с программой принято называть с расширением .pl. Загружается он предикатом consult/1 или ключом командной строки.

swipl family.pl
?- [family].
?- listing(parent/2).

Факты, правила и унификация

База знаний состоит из фактов и правил. Факт утверждает истину, правило выводит её из других условий. Переменные начинаются с заглавной буквы, атомы — со строчной.

parent(tom, bob).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Запрос ?- ancestor(tom, jim). вернёт true, а ?- ancestor(tom, Who). последовательно выдаст всех потомков. Ключевой механизм — унификация, то есть сопоставление термов с подстановкой переменных. Именно она позволяет одному правилу работать и в прямом, и в обратном направлении.

Порядок правил влияет на порядок ответов и на завершаемость. Левое рекурсивное правило ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y). уйдёт в бесконечный поиск на циклическом графе, поэтому сначала ставят шаг к базе.

Списки и рекурсия

Список — это либо пустой список [], либо пара [Голова|Хвост]. Почти все операции над списками выражаются рекурсией из двух предложений: база и шаг.

my_sum([], 0).
my_sum([H|T], S) :-
    my_sum(T, S0),
    S is H + S0.

last_item([X], X).
last_item([_|T], X) :- last_item(T, X).

В стандартной библиотеке уже есть member/2, append/3, nth1/3, length/2 и msort/2. append/3 примечателен тем, что работает в обе стороны: по результату он перечислит все варианты разбиения списка. Это удобно для генерации, но опасно в горячем коде, потому что перебор ничем не ограничен.

Отсечение и детерминизм

Отсечение ! запрещает возврат к альтернативам, принятым до него. Оно делает предикат детерминированным и часто ускоряет код, но применять его нужно осознанно: вместе с побочными эффектами оно легко превращает программу в неверную.

max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).

sign(X, negative) :- X < 0, !.
sign(0, zero) :- !.
sign(_, positive).

Без отсечения max(3, 3, X) вернул бы два решения. Для локального выбора удобнее конструкция if-then-else: (Условие -> Тогда ; Иначе). Предикат once/1 берёт только первое доказательство, не меняя логику правил.

Ограничения: CLP(FD)

Библиотека library(clpfd) превращает Prolog в решатель задач на конечных доменах. Вы задаёте диапазоны и уравнения, а label/1 находит конкретные значения. Это самый практичный способ использовать язык сегодня.

:- use_module(library(clpfd)).

plan(Cpu, Ram) :-
    Cpu = [Web, Db, Cache],
    Ram = [WebRam, DbRam, CacheRam],
    append(Cpu, Ram, All),
    All ins 1..64,
    Web #>= 2, Db #>= 4, Cache #>= 2,
    sum(Cpu, #=<, 16),
    sum(Ram, #=<, 64),
    WebRam #= 4 * Web,
    DbRam #= 8 * Db,
    CacheRam #= 2 * Cache,
    labeling([max(Web)], Cpu),
    labeling([], Ram).

Классический пример SEND + MORE = MONEY занимает десяток строк и решается за миллисекунды: восемь переменных, all_distinct/1, одно уравнение и label/1. Для расписаний добавляют serialized/2 и cumulative/2, для маршрутов — element/3 и матрицы переходов.

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

Файлы, динамические предикаты, ввод-вывод

Для чтения построчно удобно использовать setup_call_cleanup/3: он гарантирует закрытие потока даже при исключении.

load_lines(File, Lines) :-
    setup_call_cleanup(
        open(File, read, In),
        read_lines(In, Lines),
        close(In)).

read_lines(In, []) :-
    at_end_of_stream(In), !.
read_lines(In, [Line|Rest]) :-
    read_line_to_string(In, Line),
    Line \== end_of_file,
    read_lines(In, Rest).

Изменяемое состояние моделируют динамическими предикатами. Их объявляют директивой :- dynamic task/3., добавляют через assertz/1 и удаляют через retract/1. Такой подход подходит для небольших рабочих очередей, но не для конкурентного доступа: база знаний Prolog не является транзакционной.

Отладка

Главный инструмент — трассировка. trace/0 включает пошаговый вывод, spy/1 следит за конкретным предикатом, gtrace/0 открывает графический отладчик, если установлен GUI-пакет.

?- trace.
?- spy(ancestor/2).
?- gtrace, ancestor(tom, X).
?- nodebug.

Если запрос не завершается, проверьте порядок рекурсивных правил и наличие базового случая. Если выдаётся false там, где ожидался ответ, включите listing/1 и убедитесь, что арность и имена совпадают.

Сборка и вызов из другого кода

SWI-Prolog умеет собирать исполняемый файл с сохранённым состоянием. Точка входа задаётся директивой initialization/1 или ключом --goal.

swipl -O --goal=main -o planner -c planner.pl
./planner
swipl -O -o planner.sav -c planner.pl
swipl -x planner.sav -- --input tasks.csv

Есть HTTP-клиент и встраивание через C. На практике проще держать Prolog отдельным процессом с обменом JSON по stdin и stdout: так язык не диктует архитектуру остального приложения, а падение решателя не роняет веб-сервис.

Итог

Prolog стоит изучать не как замену универсальным языкам, а как инструмент для задач с правилами, ограничениями и перебором. Начните с фактов и рекурсии, затем освойте отсечение и CLP(FD): этого достаточно для большинства практических сценариев. Держите логику в отдельном модуле, собирайте исполняемый файл и вызывайте его из основного сервиса, и язык окупится там, где императивный код утонул бы в переборе вариантов.