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

Урок объясняет, что такое логическое программирование и почему оно стоит в одном ряду с императивным и функциональным подходами.

Логическое программирование — парадигма, в которой программа описывает не последовательность шагов, а набор фактов и правил логики, а результат получается за счёт автоматического логического вывода.

Когда вы учились программировать, вы почти наверняка начинали с императивного стиля: переменная, цикл, присваивание, условие. Вы говорили компьютеру как именно получить ответ — шаг за шагом. Логическое программирование переворачивает эту картину. Здесь вы описываете что такое правильный ответ, а поиск самого ответа берёт на себя машина. Это звучит почти как магия, но за ней стоит строгая математика — логика предикатов первого порядка.

Зачем нужна ещё одна парадигма

Парадигма — это способ мышления о программе, набор базовых понятий, через которые вы описываете задачу. Императивная парадигма (C, Python, Java в привычном стиле) мыслит состоянием и его изменением. Функциональная (Haskell, частично Lisp) мыслит функциями и неизменяемыми значениями: программа — это композиция преобразований данных. Логическая парадигма мыслит отношениями и истинностью утверждений.

Зачем это нужно? Огромный класс задач формулируется естественно именно как «что должно быть истинно»: кто кому родственник, какие маршруты соединяют города, какой диагноз следует из симптомов, удовлетворяет ли расписание всем ограничениям. В императивном стиле вы вынуждены вручную писать перебор, рекурсию, обход графа. В логическом — достаточно записать сами отношения, а перебор за вас выполнит встроенный механизм вывода.

ЧТО истинно, а не КАК вычислять

Разберём на крошечном примере с родственными связями. Мы хотим выразить простую мысль: «дедушка — это родитель родителя». В логическом программировании это записывается почти дословно.

% Факты: кто чей родитель
roditel(ivan, petr).
roditel(petr, maria).
roditel(maria, anna).

% Правило: дедушка X для Z, если X родитель Y, а Y родитель Z
dedushka(X, Z) :- roditel(X, Y), roditel(Y, Z).

Строка с оператором :- читается как «если». То есть dedushka(X, Z) истинно, если найдётся такой Y, что roditel(X, Y) и одновременно roditel(Y, Z). Запятая здесь — логическое «И». Обратите внимание: мы нигде не написали цикл, не объявили переменную-счётчик, не сказали «сначала возьми Ивана, потом проверь». Мы лишь описали, при каких условиях двое связаны как дедушка и внук. Теперь можно задать вопрос:

?- dedushka(ivan, maria).

Вывод:

true

Машина сама подобрала Y = petr и проверила оба условия. Более того, можно спросить иначе — «кто внуки Ивана?» — оставив второй аргумент переменной:

?- dedushka(ivan, Kto).

Вывод:

Kto = maria.

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

Связь с логикой предикатов

Если вы проходили курс «Логика и булева алгебра» или «Дискретная математика», то многое покажется знакомым. Факт roditel(ivan, petr) — это атомарный предикат, утверждение, которое мы считаем истинным. Правило dedushka(X, Z) :- roditel(X, Y), roditel(Y, Z) — это импликация с квантором: «для всех X, Y, Z: если roditel(X,Y) и roditel(Y,Z), то dedushka(X,Z)». Запрос — это попытка доказать, что некоторое утверждение следует из базы знаний.

Формально программа на Prolog — это подмножество логики предикатов первого порядка, записанное в виде так называемых хорновских дизъюнктов. Это ограничение не случайно: именно для хорновских формул существует эффективная процедура автоматического вывода. Так теоретическая логика превращается в работающий язык.

Как работает под капотом

Когда вы задаёте запрос, интерпретатор не «вычисляет» его в обычном смысле. Он пытается доказать утверждение, перебирая факты и правила сверху вниз. Для запроса dedushka(ivan, maria) система берёт правило дедушки, сопоставляет X = ivan, Z = maria, и теперь ей нужно доказать подцели roditel(ivan, Y) и roditel(Y, maria). Она находит roditel(ivan, petr), фиксирует Y = petr и проверяет, есть ли roditel(petr, maria). Есть — значит, исходное утверждение доказано.

Этот процесс называется унификацией (подбором значений переменных так, чтобы термы совпали) и поиском с возвратами (backtracking): если очередная попытка завела в тупик, система откатывается и пробует другой факт. Детально мы разберём этот механизм в следующих разделах — пока важно уяснить, что движок вывода делает перебор за вас.

Частые ошибки

Путать порядок аргументов отношения. roditel(ivan, petr) и roditel(petr, ivan) — это разные утверждения. Вы сами назначаете смысл позициям, но дальше обязаны его придерживаться, иначе вывод даст бессмыслицу.

Думать, что программа «выполняется сверху вниз как скрипт». Порядок строк влияет на порядок перебора, но программа — это не последовательность команд, а описание отношений. Один и тот же набор правил отвечает на множество разных вопросов.

Ждать, что переменная — это ячейка памяти. В логическом программировании переменная (с заглавной буквы) — это «пока неизвестное значение», которое система сама подберёт. Ей нельзя присвоить новое значение в цикле, как в Python.

Итог

Логическое программирование — третья парадигма наряду с императивной и функциональной.
Вы описываете, что истинно (факты и правила), а поиск ответа выполняет встроенный механизм вывода.
Оператор :- читается «если», запятая — логическое «И».
Одно отношение отвечает на прямые и обратные вопросы — в этом суть декларативности.
Фундамент — логика предикатов первого порядка в форме хорновских дизъюнктов.