Введение в логическое программирование (Prolog)

На блоге я публиковал ряд статей по логическому программированию, а также разбирал решения задач на языке Prolog. Недавно я заметил, что из всего этого могла бы получиться полноценная методичка если добавить введение. Введение написано так, чтобы после его прочтения Вы смогли начать программировать на Prolog, более строгой с математической точки зрения материал стоит искать в книгах по ФЛП [2].

Первые языки логической парадигмы программирования были разработаны в середине 20 века как инструменты для автоматического доказательства теорем, при этом в их основе лежал математический аппарат исчисления предикатов [1]. Позже их стали применять в качестве языков программирования общего назначения, при этом языки были дополнены рядом синтаксических конструкций.

Языки логического программирования имеют небольшое распространение, тем не менее их применяют при разработке трансляторов и искусственного интеллекта [2], они могут использоваться для разработки любых десктопных и мобильных  приложений [3, 4], а также сайтов [5]. Компания PDC, разрабатывающая Visual Prolog, применяет его при программировании авиационных и медицинских систем (конкретные проекты можно посмотреть на официальном сайте) [6]. Сам я разрабатываю на Prolog инструменты оптимизации программ — это оказалось гораздо удобнее чем на С++, при этом пользуюсь SWI Prolog (поэтому именно на нем написаны все примеры этой статьи).

Если вы когда-либо программировали на императивных языках, таких как Java — то Prolog покажется вам необоснованно запутанным. Императивные языки создавались для вычислительных машин архитектуры фон Неймана, в которой команды для выполнения выбираются последовательно, а циклы и ветвление реализуются посредством специальных команд перехода. В языках логической парадигмы это работает совсем иначе.

Логическая программа состоит из предикатов, представляющими собой функции, вырабатывающие логические значения — любой предикат содержит вычисления, которые могут быть либо истинными, либо ложными. При этом результаты вычисления предикат возвращает только если вычисления истинны. Предикаты состоят из правил (предложений), описывающих вычисления и соединенных между собой логическими операторами И/ИЛИ, при этом логическому И соответствует оператор запятая, а ИЛИоператор точка. Программы на языке Prolog могут содержать также переменные (их имена обязательно должны начинаться с большой буквы — этим они отличаются от других объектов), однако одним из базовых в логическом и функциональном программировании является принцип однократного присваивания, в соответствии с которым переменная может получить значение лишь один раз, все остальные попытки присваивания будут работать как проверка на равенство. Следствием принципа однократного присваивания является отсутствия циклических конструкций в Prolog — вместо них везде применяется рекурсия, что не снижает скорость работы программы, т.к. хвостовая рекурсия также  эффективна, как и цикл [9].

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

digit_sum(Number, Sum):-
  Number < 10, !, Sum is Number.
digit_sum(Number, Sum):-
  Digit is Number mod 10,
  NumberPart is Number div 10,
  digit_sum(NumberPart, SumPart),
  Sum is SumPart + Digit.

prolog_computation_flow.png

дерево вычислений prolog (вычисление суммы цифр числа)

Подобное дерево строится во многих интерпретаторах языка Prolog, т.к. выбор операторов для выполнения в программе должен выполняться в порядке обхода дерева слева направо. Розовым цветом я обозначил предикат, состоящий из двух правил, выделенных зеленым цветом. Листья дерева соответствуют операциям, вычисление которых может завершится либо истиной, либо ложью. В операциях, соединенных логическим И все операции должны вернуть истинное значение чтобы результатом стала истина, поэтому если любая из таких операций завершилась ложью — результат может быть получен сразу (без вычисления остальных). Так например, если Number >= 10, то первое правило сразу завершится ложью и управление будет передано второму правилу, т.к. они соединены с помощью логического ИЛИ.

Чуть позже мы еще раз вернемся к примеру с суммой цифр числа, но сначала рассмотрим механизмы поиска с возвратами (backtracking) и сопоставления с образцом (pattern matching), которые также лежат в основе логического программирования. Рассмотрим их на примере программы вычисления стоимости покраски плоской поверхности.

colour_cost(red, 1000).
colour_cost(white, 1030).
colour_cost(blue, 1070).

colouring_cost(Height, Width, Colour, Cost):-
  colour_cost(Colour, ColourCost),
  Square is Height * Width,
  Cost is Square * ColourCost.

prolog backtracking example

Поиск с возвратами в prolog

В данном случае программа состоит из двух предикатов:

  • colour_cost позволяет получить информацию о цене покраски одного метра квадратного заданным цветом, например красная краска стоит 1000 рублей, а белая — 1030. Мы можем спросить у интерпретатора:
    • сколько стоит покраска белой краской?;
    • у какой краски цена метра равна 1070 рублям?;
    • какие есть варианты покраски? (вывести все цены);
    • у каких красок цена метра квадратного ниже 1050 рублей.
colour_prolog_example

Примеры запросов о покраске на Prolog

  • colouring_cost возвращает стоимость покраски для заданных площади и цвета, при этом для получения стоимости покраски одного метра обращается к предикату colour_cost. Мы можем написать запросы для получения всех возможных вариантов покраски заданной площади или узнать сколько будет стоить покраска определенным цветом:

    colouring_prolog_example

    Примеры запросов о покраске поверхности на Prolog

В приведенном фрагменте исходного кода предикат colour_cost состоит из трех правил, в качестве аргументов правила используются константы (например red и 1000), значения которых интерпретатор пытается присвоить передаваемым переменным или выполнить сравнение. Так, например, при обработке colour_cost(Color, 1070) выбирается сначала самый левый узел дерева, поэтому переменной Color присваивается значение red, а 1070 сравнивается с 1000 — сравнение возвращает false поэтому результат работы не возвращается и интерпретатор пытается подставить следующий узел дерева (colour_cost(white, 1030)). Такой механизм называется сопоставлением с образцом.

Кроме того видно, что при интерпретации предиката пролог может возвращать несколько вариантов решений — это является следствием работы механизма поиска с возвратами, заключающегося в полном переборе вариантов решений. При поиске интерпретатор обходит узлы дерева слева направо, если какая либо ветвь завершилась успешно (вернула истину) — результат возвращается, после чего поиск по дереву может быть продолжен для получения других вариантов решения. Так например, при интерпретации цели всех вариантов покраски прямоугольника 10 на 5 метров с ценой менее 52000 вызывается colour_cost, который в свою очередь вызывает colour_cost(Colour, ColourCost), а значит инициирует полный перебор вариантов покраски. Для каждого варианта будет рассчитана цена, которая после выхода из функции colour_cost сравнивается с константной 52000. Если сравнение проваливается (оператор возвращает false), интерпретатор пытается найти другое решение путем возврата внутрь colouring_cost, а затем подставит следующий необработанный цвет и его стоимость. Если решение для цели найдено — результат возвращается, однако поиск все равно может быть продолжен.

На механизм поиска с возвратам, а следовательно и на управление вычислениями (порядок выполнения операторов) может влиять оператор отсечения, обозначаемое в языке Prolog восклицательным знаком (вы могли видеть его использование в примере функции вычисления суммы цифр числа). При выполнении оператора отсечения перебор решений ограничивается так, что значения всех узлов, выполненных до отсечения (находящихся в дереве «левее») считаются константами — запрещается возврат к ним для расчета других значений. Мы уже использовали отсечение при вычислении суммы цифр числа — если число меньше десяти, то оно содержит лишь одну цифру, а значит нет смысла в рекурсивной обработке числа, т.е. переходе ко второму правилу. В связи с этим первое правило вычисления суммы содержит отсечение. Другие примеры использования отсечения [8]. Различают красные и зеленые отсечения [10].

Важной особенностью логических языков программирования является наличие встроенной базы данных. В зависимости от диалекта, встроенная БД может хранить либо только факты (предикаты, правила которых не содержат тело — как рассмотренный выше предикат colour_cost), либо произвольные предикаты. Работа с записями базы данных в Prolog происходит точно также, как и с любыми другими предикатами, однако их можно добавлять и удалять во время выполнения встроенными функциями assert и retract, чтобы это стало возможным в Vusial Prolog факты требуется описать в секции database, а в SWI Prolog — описать динамическими [11]:

:- colour_cost/2.

Тогда добавление записи в базу может быть выполнено командой assert(colour_cost(black, 900)), а удаление — retract(colour_cost(red, Cost)). В остальном работа с ними не изменится. В силу того, что записи базы данных пролога в плане обработки никак не отличаются от других предикатов (обрабатываются в соответствии с механизмом поиска с возвратами) — встроенная база данных имеет существенные отличия от баз данных SQL [12].

Принцип однократного присваивания не позволит изменить значение элемента массива, поэтому базовой структурой данных в логических языках программирования является связный список. При этом изменение элемента списка может реализовываться через удаление старого узла и добавление нового. При обработке списков на Prolog учитывается их рекурсивная природа — любой список из одного или более элемента возможно разделить на первый элемент и другой список, особым видом списка является пустой список. Список может быть задан перечислением элементов в квадратных скобках — [1, 2, 3], для обозначения пустого списка используется конструкция из двух квадратных скобок — []. Основной операцией по работе со списками является разделение списка на голову (первый элемент) и хвост (список из остальных элементов) — обозначается вертикальной чертой: [Head|Tail] = [1, 2, 3] — в результате Head = 1, Tail = [2, 3]. Обработка списка происходит рекурсивно, при этом от исходного списка отделяются первые элементы до тех пор, пока он не станет пустым (такой случай обрабатывается отдельно). Примеры рекурсивной обработки списков [13]. Списки являются тем более важными, что с их помощью в Prolog задаются строки, даже в тех диалектах, где строки не являются списком (например Turbo/Visual Prolog), для обработки их удобно преобразовать в список, т.к. это позволит применять к ним более богатый набор функций [14].

Заключение

Статья призвана объединить и сгруппировать информацию по логическому программированию, размещенную на этом блоге — в связи с этим в ней описано небольшое число примеров, но содержится много ссылок, где такие примеры можно найти. Статья является вводной, поэтому в ней разобраны лишь самые основы языка, но любой желающий читатель без труда найдет больше информации, например по работе с файлами [15]. Кроме того, статья ориентированна на начинающих, я хотел, чтобы после ее прочтения (и беглого просмотра связанных ссылок) неподготовленные читатели смогли писать простые простые программы на языке Prolog — поэтому она не содержит строго математического описания логических языков программирования (которое при желании можно найти в книгах) [2].

Литература по языку Prolog:

  1. Решение логических задач на Prolog: https://pro-prof.com/archives/1299
  2. Сергиевский Г.М., Волченков Н.Г.: Функциональное и логическое программирование. М.: Академия, 2010
  3. Building SWI-Prolog on Android using LinuxOnAndroid: http://www.swi-prolog.org/build/linuxonandroid.html
  4. Jekejeke Prolog Runtime: https://play.google.com/store/apps/details?id=jekpro.platform.headless
  5. Creating Web Applications in SWI-Prolog: http://www.pathwayslms.com/swipltuts/html/
  6. Официальный сайт компании PDC: http://www.pdc.com
  7. Как объяснить своей младшей сестре (9 лет) принципы логического программирования?: https://habrahabr.ru/post/161233/
  8. Принципы построения программ на Prolog: https://pro-prof.com/forums/topic/semantics-prolog
  9. Рекурсия в программировании. Анализ алгоритмов: https://pro-prof.com/archives/813
  10. Красные и зеленые отсечения: https://pro-prof.com/forums/topic/red-green-cut-operator-prolog
  11. Предикаты assert и retract: https://pro-prof.com/forums/topic/assert-retract-permanent-changes
  12. Отличия базы данных SQL от Prolog : https://pro-prof.com/forums/topic/differences_prolog_sql
  13. Списки в Prolog. Теория, примеры: https://pro-prof.com/archives/845
  14. Преобразование строки в список символов. Turbo Prolog: https://pro-prof.com/forums/topic/string_to_list-turbo_prolog
  15. Работа с файлами в SWI Prolog: https://pro-prof.com/forums/topic/read-strings-from-file-swipl

11 thoughts on “Введение в логическое программирование (Prolog)

  1. nick

    Вы один из немногих программистов, профессионально использующих язык ПРОЛОГ.
    Нами (www.exxlog.ru) разработан инструмент для создания экспертных систем на основе Arity/Prolog32. С виду это обычный ПРОЛОГ, только он не зацикливается и имеет массу других полезных свойств. Ориентация — решение задач, требующих поиска вывода в объеме миллионов итераций.
    Не могли бы Вы высказать свое мнение о нашей разработке? Есть ли у Вас возможные варианты ее применения?

    С уважением,
    Наиль Ихсанов
    Semantics Research

    1. admin Post author

      Здравствуйте. Я читал ваши статьи на хабрахабр. Вы пишите, что Exxlog не зацикливается, что вы имеете ввиду? — я помню очень интересное обсуждение статьи [1], в заключении к которой автор рассуждал о возможности обнаружения зацикливания. Вы как-то связаны с тем автором? О каких зацикливаниях у вас идет речь?

      1. Толмачёв Д. Пролог – декларативный язык, способный решать любые ребусы и доказывать теоремы / URL: habrahabr.ru/post/254133/

  2. nick

    Наверное Вы не читали мою последнюю публикацию про Exxlog:
    habrahabr.ru/post/277229/
    Там пишется, что зацикливание возникает естественно в ходе логического вывода при решении неигрушечных задач.
    Еще Зацикливание возникает при использовании левой рекурсии и это не всегда можно обойти как в парсинге
    habrahabr.ru/post/274799/

    1. admin Post author

      Я читал эти стать, по ним и общаемся. Вы пишите:

      В процессе поиска решения все возникающие цели нумеруются…
      Решение — дерево логического вывода для нашей задачи можно записать в виде списка пронумерованных предикатов

      Т.е., насколько я понимаю, если цель foo(5) уже была вычислена, и я повторно к ней обращаюсь — то вместо вычисления будет взято готовое значение?

  3. nick

    Именно так и происходит. В процессе поиска вывода каждое полученное решение заносится в базу данных ПРОЛОГа, а каждая новая цель проверяется на присутствие в базе данных.
    Если скачаете более подробное описание нашей системы у Вас могут появиться новые вопросы.
    Задавайте еще, будем рады ответить.

    1. admin Post author

      Я все скачал и прочитал с ваших сайтов, даже статью про CONST в научном журнале. Ситуацию это не прояснило. Все что вы описываете и даже лучше предлагал товарищ Толмачев (мы с ним долго беседовали, но он куда-то пропал). Некоторые (не все) тезисы нашего с ним диалога:

      1. если писать код нормально, то никакое зацикливание происходить не будет;
      2. то, что вы предлагаете известно с прошлого века и называется табулированием, в общем случае это техника оптимизации. В частности это используется постоянно при решении задач методами динамического программирования;
      3. то, что вы предлагаете легко реализуется для конкретного алгоритма при необходимости (обычно необходимости нет);
      4. то, что вы предлагаете связано с огромными издержками. Например, обрабатываю я файл в несколько гигабайт, при этом считываю из него строки и передаю каждую строку в функцию. Я, допустим, знаю, что маловероятно там будет несколько одинаковых строк и мне нет смысла что-то табулировать (тратить на это компьютерные время и память), но вы предлагаете для каждой обработанной строки запихать в базу данных запись, хранящую результат — это попадет в оперативную память, которая скоро кончится, а профит будет нулевым. Кстати, Толмачев предлагал для частичного решения проблемы хранить вместо реального аргумента функции (вместо строки и набора параметров если их несколько) — некоторый хеш для экономии памяти, но он не сказал как разруливать коллизии в этом случае;
      5. то, что вы предлагаете может сработать только для чистых функций (не использующих никакое глобальное окружение). Что если моя функция работает с базой данных — результаты ее работы будут зависеть не только от аргументов, но и от состояния базы. Что делать с базой Толмачев не придумал;
      6. база данных — это часть проблемы, другая часть — это любой ввод/вывод. Например, функция:
        check_input:-
        read(Number), Number > 5.

        У функции вообще нет аргументов, но результаты ее работы будут зависеть от того, что введет пользователь. Любая попытка протабулировать ее и использовать полученное ранее значение будет ошибкой.
      7. вы говорите о серьезных проектах и миллионах итераций, однако при этом рассматриваете игрушечную задачу о треугольниках, он даже при этом получается приличное такое дерево вызовов, которое надо хранить в ОЗУ.

      И это только часть вопросов.

    1. admin Post author

      Не табуляция, а табулирование (которое еще мемоизацией называется иногда). Это известная техника. И она тут притом, что судя по описанию того, как ваша система борется с зацикливанием — она занимается именно мемоизацией, т.е. сохранением всех вычисленных ранее результатов.

      Мне не понятно как ваша система связана с экспертными системами, в статьях вы пишите только про борьбу с зацикливанием. При этом, мне известно, что обнаружение зацикливания — это неразрешимая (даже не NP-сложная) задача.

      Я написал выше кучу вопросов и был бы рад получить ответы. При этом я хотел попробовать погонять в вашей системе примеры (один приведен выше), а второй, например такой:
      gen(Number):-
      Number is random(100), Number > 50, !; gen(Number).

      Мне вот кажется, что в такого рода примерах система может детектировать зацикливание, причем зависеть этот процесс будет от работы random. Можно придумать массу таких примеров.

      Мне тем более не понятно как это связано с экспертными системами, если они часто должны работать долго (несколько недель и месяцев) без перезапуска. А ваша система сохраняет все результаты промежуточных вычислений (если я правильно понял статьи).

      У меня не получилось попробовать все эти примеры в вашей системе, т.к. во-первых у вас выложена только версия для Windows, во-вторых она криво работает под wine (в частности файл справки не отображается), в-третьих даже на Windows у меня не получилось запустить ни один пример (просто не понятно как, я следовал пунктам справки, но так и не понял куда мне вводить запросы или где указывать точку входа). Как минимум, система выглядит сырой.

      Сам я пишу оптимизирующий транслятор на SWI Prolog и мне важна переносимость кода, ваша система пока что этому требованию не соответствует.

      В любом случае я очень надеюсь на развернутые ответы на мои вопросы с примерами.

    2. admin Post author

      Здравствуйте. Я писал Вам вопросы, но не получил ответов. На всякий случай продублирую:
      — что позволяет ваша система, кроме борьбы с зацикливаниями? (и правильно ли я понял, что она как-то с ними борется?);
      — как сработает Ваша система на функциях check_input и gen, исходный код которых я привел?
      — опишите по шагам куда нажимать чтобы использовать Вашу систему, я пробовал все делать по инструкции, но у меня не заработала ни одна программа (я несколько часов ковырялся и на Linux с wine и даже компьютер с Windows нашел, хотя это было не легко).

      Очень надеюсь на Ваши подробные ответы.

      1. nick Post author

        Извините, что не ответил Вам сразу, т.к. хотел решить проблему переносимости на Windows 7 и более старших версий ОС. К сожалению, мне не удалось пока ее решить.

        Дело в том, что система Exxlog состоит из оболочки (DELPHI 7), и ядра (Arity/Prolog32).

        Ядро от ОС не зависит, т.к. не обращается к системным функциям и библиотекам.

        А работал только с ПРОЛОГом, поэтому не занимался проблемами совместимости с ОС.

        У меня на машине стоит Windows XP.

        Просто мне надо переустановить ОС на своей машине.

        Если хотите запустить программу Exxlog, нужна Windows XP.

        Насчет возможностей Exxlog скажу следующее – это специализированная система и не заменяет PROLOG. Обычные PROLOG-программы писать на ней бесполезно. Она предназначена для создания систем, основанных на выполнении логического вывода. Я вижу следующие применения: решение математических задач, логических задач, автоматизация программирования.

        Может быть, Вы знаете какие-то другие области применения, конечно, мне было бы это интересно.

        Защита от зацикливания основана на трассировке – каждая очередная цель сверяется на наличие в истории вывода (конечно история динамическая — только для текущего вывода). Конечно, для общего случая – это сложная задача из-за унификации целей (текущей цели и целей в истории, но для прикладных задач проблемы нет, поскольку аргументы целей, возникающих в процессе логического вывода, ограничены по сложности.

Добавить комментарий