Введение в логическое программирование (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 лет) принципы логического программирования?: http://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

    Reply
    1. admin Post author

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

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

      Reply
  2. nick

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

    Reply
    1. admin Post author

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

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

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

      Reply
  3. nick

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

    Reply
    1. admin Post author

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

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

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

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

      Reply
  4. nick

    При чем тут табуляция?
    Система Exxlog предназначена для построения экспертных систем, а не для поиска ошибок в программах.

    Reply
    1. admin Post author

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

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

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

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

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

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

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

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

      Reply
    2. admin Post author

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

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

      Reply
      1. nick Post author

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

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

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

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

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

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

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

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

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

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

        Reply

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы не робот? *