Логическое программирование

Логическое программирование — это парадигма программирования, основанная на представлении знаний в виде фактов и правил логического вывода. В отличие от императивного программирования, где программа описывает последовательность шагов для достижения результата, логическое программирование формулирует, что должно быть истинным, а интерпретатор (система логического вывода) сам ищет способ доказать или опровергнуть утверждение. Основу парадигмы составляет математическая логика, в частности — исчисление предикатов первого порядка.

История

Истоки логического программирования восходят к работам по автоматическому доказательству теорем в 1950–1960-х годах. Ключевой вклад внёс британский логик и программист Алан Робинсон, который в 1965 году разработал принцип резолюции — метод доказательства теорем в логике предикатов, ставший основой для выполнения логических программ.

В 1972 году группа исследователей во главе с Аленом Колмероэ и Филиппом Русселем в Марсельском университете (Франция) создала язык программирования Prolog (от фр. programmation en logique — программирование в логике). Именно Prolog стал первым и наиболее распространённым практическим воплощением логического программирования. В 1980-х годах в Японии была предпринята попытка создать «компьютеры пятого поколения», ориентированные на логическое программирование, в частности на Prolog, однако проект не достиг коммерческого успеха.

В последующие десятилетия логическое программирование развивалось в нескольких направлениях: появились расширения для работы с ограничениями (Constraint Logic Programming), базами данных (Datalog), а также методы распределённого вывода.

Основные принципы

Факты, правила и запросы

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

• Фактов — безусловных утверждений (например: родитель(иван, мария). — «Иван является родителем Марии»).
• Правил — условных утверждений, определяющих отношения через другие отношения (например: предок(X, Y) :- родитель(X, Y). — «X является предком Y, если X — родитель Y»).
• Запросов — целей, которые необходимо доказать: система пытается найти такие значения переменных, при которых запрос становится истинным на основе имеющихся фактов и правил.

Логический вывод

Выполнение программы состоит в автоматическом доказательстве или опровержении запроса с помощью механизма резолюции и унификации. Унификация — это процесс сопоставления термов (объектов логического языка) для нахождения наиболее общего подстановки, при которой они становятся идентичными. Резолюция, как правило, применяется в виде SLD-резолюции (Selective Linear Definite clause resolution) — стратегии, используемой в Prolog.

Декларативность

Программист описывает логику задачи, а не алгоритм её решения. Интерпретатор или компилятор самостоятельно выбирает порядок и способ перебора вариантов. Это делает логическое программирование особенно удобным для задач, где естественно формулируются отношения, классификация, вывод на основе правил.

Языки логического программирования

Prolog

Prolog — стандартный и наиболее известный язык, реализующий логическое программирование. Существует несколько стандартов (Edinburgh Prolog, ISO Prolog). Основные диалекты: SWI-Prolog (распространённый с открытым кодом), GNU Prolog, Ciao Prolog, SICStus Prolog, Visual Prolog.

Datalog

Datalog — декларативный язык запросов к реляционным базам данных, основанный на принципах логического программирования. Отличается от Prolog тем, что не допускает рекурсии, требующей управления порядком вывода, и гарантирует конечность вычислений. Применяется в анализе данных, защите информации (например, анализ графа зависимостей), синтаксическом анализе программ.

Mercury

Mercury — функционально-логический язык программирования, наследующий идеи Prolog, но с более строгой типизацией, модульной системой и эффективной компиляцией. Разработан в Мельбурнском университете (Австралия) в 1990-х годах. Используется для разработки аналитических систем и компиляторов.

Отдельные системы

• ASP (Answer Set Programming) — парадигма, основанная на семантике устойчивых моделей ответов. Системы-решатели (clasp, dlv, potassco) применяются для задач планирования, конфигурации, биоинформатики.
• CLP (Constraint Logic Programming) — расширение логического программирования для работы с ограничениями на числовые и символьные области. Применяется в задачах оптимизации, построения расписаний.

Применение

Искусственный интеллект и экспертные системы

Логическое программирование традиционно связано с разработкой экспертных систем — программ, моделирующих знания экспертов в узкой предметной области. В 1980–1990-х годах были созданы системы на Prolog для медицинской диагностики (MYCIN — одна из ранних, хотя она использовала другие подходы; более поздние: CADUCEUS, INTERNIST), геологоразведки, проектирования.

Обработка естественного языка

Prolog и языки на его основе применяются для синтаксического и семантического анализа предложений. На основе логического программирования реализованы грамматики, способные строить синтаксические деревья и интерпретировать смысл запросов на естественном языке.

Базы данных и дедуктивные системы

Datalog и родственные системы используются для извлечения знаний из реляционных баз данных. Дедуктивные базы данных могут выводить неявно заданные факты на основе правил — например, для контроля целостности, автоматической классификации клиентов, выявления аномалий.

Компьютерная алгебра и символьные вычисления

Логическое программирование применяется в системах символьной алгебры (например, Simplify), а также при автоматизированном доказательстве теорем (система Otter, реализованная на основе резолюции).

Планирование и робототехника

ASP и CLP используются для построения планов действий в условиях неопределённости. В робототехнике логическое программирование позволяет формализовать знания об окружающей среде и генерировать последовательности действий, необходимые для достижения целей.

Преимущества и недостатки

Преимущества

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

Недостатки

• Производительность: интерпретация логических правил, особенно с рекурсией и большими базами данных, часто медленнее императивных алгоритмов.
• Сложность контроля побочных эффектов: логическое программирование плохо приспособлено для управления внешними устройствами, вводом-выводом, изменением состояния — для этого приходится вводить специальные механизмы (например, предикаты I/O в Prolog с побочными эффектами).
• Проблема полноты и сложности: при определённых типах правил (с отрицанием через неудачу, рекурсией) вывод может не завершиться или породить бесконечное количество решений.

Сравнение с другими парадигмами

Логическое программирование ближе всего к формальной спецификации: программа может рассматриваться как формула, на основе которой строится доказательство заданного запроса.

Современное состояние

После всплеска интереса в 1980-х годах логическое программирование уступило позиции другим парадигмам в коммерческой разработке, однако продолжает активно развиваться в академических и прикладных областях: компьютерная лингвистика, анализ знаний, биоинформатика, верификация программ, анализ защищённости (Datalog для анализа потоков данных графа) и системы рекомендаций. С открытием принципов работы больших языковых моделей (трансформеров) интерес к гибридным системам, сочетающим нейросетевые представления и символьные логические выводы, возрождается: создаются модели, интегрирующие нейросети и логическое программирование (Neural-Symbolic AI). В России логическое программирование входит в учебные программы ряда вузов по направлениям «Прикладная математика» и «Информатика».

Источники

• Kowalski R. «Logic for Problem Solving». North-Holland, 1979.
• Lloyd J. W. «Foundations of Logic Programming». Springer, 1987.
• Стерлинг Л., Шапиро Э. «Искусство программирования на Прологе». Мир, 1990.
• Clocksin W. F., Mellish C. S. «Programming in Prolog». Springer, 2003.
• Lifschitz V. «What Is Answer Set Programming?» Proceedings of the AAAI Conference, 2008.