Что такое в прологе
Prolog урок 2. Базы фактов, цели и запросы
Нормальная форма Бэкуса-Наура
Для начала вспомним нормальную форму Бэкуса-Наура (БНФ), которая была создана для формального описания синтаксиса языков программирования в 1960 году. Ее авторы — Джон Бэкус и Питер Наур.
Итак, в БНФ приняты следующие обозначения:
Символ ::= читаемый как «по определению» («это», «есть»). Слева от символа располагается объясняемое понятие, справа — разъясняющая конструкция. Например,
Символ | означает логическое «или» и применяется для разделения различных равнозначных альтернативных объяснений определяемого понятия.
Используя данный символ можно, например, определить десятичную цифру:
говорит о том, что целое число можно объяснить как положительное целое число, перед которым может стоять знак минус (а может и не стоять).
Символ * указывает на то, что стоящая перед ним синтаксическая конструкция может повторяться произвольное количество раз (начиная с ноля и выше). Вместо символа * иногда используются фигурные скобки ( <, >), по сути равнозначные ему.
Снова определим положительное целое число, используя нотацию БНФ :
Что означает, что положительное целое число состоит из одной или нескольких цифр.
Структура программы на языке Prolog
Стандартная программа на языке Prolog состоит из следующих разделов:
Необязательный раздел определения констант.
Раздел описания доменов (аналогичен описанию типов данных).
Раздел описания предикатов (аналогичен разделу описания процедур и функций); по сути представляет собой шаблон написания фактов в разделе Clauses.
Утверждения (аналог: тело основной программы).
Целевое утверждение – «цель».
domains a=symbol predicates likes (a,a) clauses likes (mary,apples).
Перейдите в окно Dialog (меню Run ) и введите запрос:
В результате в окне должен появиться ответ true
Факты и правила
Часто программу, написанную на Прологе, называют базой знаний.
Предложения-правила имеют вид:
Где A — это заголовок или голова предложения, а B1. Bn – это тело.
Факт обычно утверждает, что между объектами выполнено некоторое отношение и состоит из:
Пример факта:
Т.к. отношение в математической логике принято называть предикатами, то и мы иногда будем использовать понятие «предикат» вместо «факта» или «правила».
Если факт состоит только из заголовка, то можно сказать, что факт – это предложение, у которого тело пустое.
Аргументом факта или предиката может быть константа, переменная или составной объект; от их числа зависит так называемая местность (n-местность) факта.
Отличие константы от переменной: константа получает свое значение в разделе описания констант, тогда как переменная инициализируется в процессе работы программы.
В следующем примере наводите курсор на части конструкций, и появится подсказка:
Таким образом, в примере likes — это имя двухаргументного предиката (факта), у которого строковая константа « bill » является первым аргументом, а « dogs » — вторым аргументом.
Наберите код программы в компиляторе.
Цель — это формулировка задачи, которую программа должна решить. Цель также служит «триггером» для запуска программы.
Турбо-Пролог использует как внутренние цели, которые содержатся в программе, так и внешние цели, которые вводятся с клавиатуры после запуска программы. Здесь существует два варианта:
Дословно: Мэри любит яблоки.
Дословно: Что любит Мэри?
* Понятие переменной в Прологе будет рассмотрено в следующем уроке.
Так, наш пример может быть как фактом, так и целью:
likes(mary,apples). — Мэри любит яблоки и Любит ли Мэри яблоки?
Алгоритм составления программы
Программа для компилятора TProlog состоит из разделов, рассмотренных в примере:
predicates likes (a,a)
Предикат – это логическая формула от одного или нескольких аргументов
clauses likes (mary,apples). likes(mary,oranges). color(apples,red).
goal likes(mary,X),write(«mary lyubit «, X).
Результатом примера будет: «mary lyubit apples».
В данном примере цель записана в виде раздела GOAL прямо в программе, но нужно иметь в виду, что чаще всего цели, требующие логический ответ (правда или ложь), записываются в окне Dialog (goal в программе тогда не пишется)
Бесконечный цикл
В примере, описанном выше, в результате выдается значение только первого из трех фактов:
clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write(«mary lyubit «, X).
Раздел gaol того же примера, но с бесконечным циклом будет выглядеть так:
goal likes(mary,X),write(«mary lyubit «, X),nl,fail.
nl — означает переход на следующую строку (каждое значение выводится с новой строки).
Результат:
«mary lyubit apples».
«mary lyubit oranges».
Код программы целиком:
domains a=symbol predicates likes (a,a) clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write(«mary lyubit «, X),nl,fail.
Рассмотрим еще один пример.
Код программы без запросов:
domains a=symbol predicates построил (a,a) хранится (a,a) ворует (a,a) ловит (a,a) треплет (a,a) доит (a,a) бранится (a,a) будят (a,a) clauses построил (джек,дом). хранится (пшеница, чулан_дома). ворует (птица_синица, пшеница). ловит (кот, птица_синица). треплет (кот, птица_синица). треплет (пес, кот). доит (старушка, корова). бранится (пастух, старушка). будят (два_петуха, пастух).
? – ловит (кот, Y) /*Кого ловит кот?*/
Ответ: Y= птица_синица
? – бранится (X,Y). /*Кто с кем бранится?*/
Ответ: X =пастух, Y= старушка
? – хранится (X, чулан_дома), ворует (X,Y). /*Что хранится в чулане дома и кто ворует это */
Ответ: X = пшеница, Y= птица_синица
Выполнение запросов в разделе Goal:
Введение в логическое программирование (Prolog)
На блоге я публиковал ряд статей по логическому программированию, а также разбирал решения задач на языке Prolog. Недавно я заметил, что из всего этого могла бы получиться полноценная методичка если добавить введение. Введение написано так, чтобы после его прочтения Вы смогли начать программировать на Prolog, более строгой с математической точки зрения материал стоит искать в книгах по ФЛП [2].
Первые языки логической парадигмы программирования были разработаны в середине 20 века как инструменты для автоматического доказательства теорем, при этом в их основе лежал математический аппарат исчисления предикатов [1]. Позже их стали применять в качестве языков программирования общего назначения, при этом языки были дополнены рядом синтаксических конструкций.
Языки логического программирования имеют небольшое распространение, тем не менее их применяют при разработке трансляторов и искусственного интеллекта [2], они могут использоваться для разработки любых десктопных и мобильных приложений [3, 4], а также сайтов [5]. Компания PDC, разрабатывающая Visual Prolog, применяет его при программировании авиационных и медицинских систем (конкретные проекты можно посмотреть на официальном сайте) [6]. Сам я разрабатываю на Prolog инструменты оптимизации программ — это оказалось гораздо удобнее чем на С++, при этом пользуюсь SWI Prolog (поэтому именно на нем написаны все примеры этой статьи).
Если вы когда-либо программировали на императивных языках, таких как Java — то Prolog покажется вам необоснованно запутанным. Императивные языки создавались для вычислительных машин архитектуры фон Неймана, в которой команды для выполнения выбираются последовательно, а циклы и ветвление реализуются посредством специальных команд перехода. В языках логической парадигмы это работает совсем иначе.
Логическая программа состоит из предикатов, представляющими собой функции, вырабатывающие логические значения — любой предикат содержит вычисления, которые могут быть либо истинными, либо ложными. При этом результаты вычисления предикат возвращает только если вычисления истинны. Предикаты состоят из правил (предложений), описывающих вычисления и соединенных между собой логическими операторами И/ИЛИ, при этом логическому И соответствует оператор запятая, а ИЛИ — оператор точка. Программы на языке Prolog могут содержать также переменные (их имена обязательно должны начинаться с большой буквы — этим они отличаются от других объектов), однако одним из базовых в логическом и функциональном программировании является принцип однократного присваивания, в соответствии с которым переменная может получить значение лишь один раз, все остальные попытки присваивания будут работать как проверка на равенство. Следствием принципа однократного присваивания является отсутствия циклических конструкций в Prolog — вместо них везде применяется рекурсия, что не снижает скорость работы программы, т.к. хвостовая рекурсия также эффективна, как и цикл [9].
Для понимания принципов управления вычислениями в prolog, удобно представлять программу в виде дерева как показано на примере вычисления суммы цифр числа.
дерево вычислений prolog (вычисление суммы цифр числа)
Подобное дерево строится во многих интерпретаторах языка Prolog, т.к. выбор операторов для выполнения в программе должен выполняться в порядке обхода дерева слева направо. Розовым цветом я обозначил предикат, состоящий из двух правил, выделенных зеленым цветом. Листья дерева соответствуют операциям, вычисление которых может завершится либо истиной, либо ложью. В операциях, соединенных логическим И все операции должны вернуть истинное значение чтобы результатом стала истина, поэтому если любая из таких операций завершилась ложью — результат может быть получен сразу (без вычисления остальных). Так например, если Number >= 10, то первое правило сразу завершится ложью и управление будет передано второму правилу, т.к. они соединены с помощью логического ИЛИ.
Чуть позже мы еще раз вернемся к примеру с суммой цифр числа, но сначала рассмотрим механизмы поиска с возвратами ( backtracking ) и сопоставления с образцом ( pattern matching ), которые также лежат в основе логического программирования. Рассмотрим их на примере программы вычисления стоимости покраски плоской поверхности.
Поиск с возвратами в prolog
В данном случае программа состоит из двух предикатов:
Примеры запросов о покраске поверхности на 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]:
Тогда добавление записи в базу может быть выполнено командой 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 — удивительный язык программирования
— Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.
Пролог — уникален. Это единственный язык представляющий парадигму декларативного программирования; это язык, который имеет сотни различных имплементаций, но они все равно называются Prolog, добавляя лишь префиксы и суффиксы к названию; это живой язык в котором не происходит никаких существенных изменений более 20 лет; это, наверное, единственный настолько популярный язык программирования, который не имеет применения в реальном программировании. Почему же Prolog?
Пролог — уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.
В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач. Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций.
Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+, от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток 🙂
Как правильно читать программы на прологе
Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык. Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста.
Понятия
Программа
Программа — это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).
Как видно имя переменной имеет область видимости — это правило. Математически верно, правило звучит: для любой переменной — «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до :- ) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число — простое и нечетное, то Число2 — простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.
Пример — совершенные числа
Программа — как набор определений
Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».
Интересный факт, что в Прологе нет ни циклов, ни присвоения переменных, ни объявления типов, а если вспомнить еще про термы и отсечение, то язык становится алгоритмически полным.
Термы
С точки зрения программирования терм можно объяснить гораздо проще: терм — это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние — переменная.
Пример — целочисленная арифметика
Как Prolog понимает предикаты и как доказывает утверждения
Конечно чтение программ, помогает ощутить стиль Пролог, но не делает понятным для чего и как данные определения могут использоваться. Полноценной программой, примеры приведенные выше, назвать нельзя так как не хватает входной точки. Входной точкой в Пролог является запрос, аналог запроса к базе данных SQL или аналог вызова главной функции в функциональном программировании. Примеры запросов: нат(Число) — найти натуральное число, плюс(0, 0, Результат) — найти результат сложения 0 и 0 в переменной Результат, нат(0) — проверить является ли 0 натуральным числом и др.
Конечно, результаты запросов не трудно предсказать из логических соображений, но крайне важно понять, как программа их получила. Все-таки Пролог не черный ящик, а язык программирования, и в отличие от базы данных, где строится SQL-план и запрос может выполняться по-разному на разных Базах данных, Пролог имеет вполне определенный порядок выполнения. Дело в том, что в Базе данных мы вполне знаем какой ответ мы хотим получить исходя из данных в таблице, к сожалению глядя на Пролог программы достаточно сложно сказать, какие утверждения логически выводимы, поэтому понять как работает Пролог интерпретатор гораздо проще.
Рассмотрим на примере запроса плюс(0, 0, Результат) :
1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число). Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0.
Запрос нат(Число) :
1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.
Грамотное составление правил на языке Пролог, очень сложная штука, но если их составить компактно, то можно получать не только прямые ответы и решения, но и обратные.
Пример запроса плюс(Число, Число, Число): ответ да, Число = 0.
Пример запроса плюс(0, 0, 0): ответ нет, при первой же попытке все резолюции не выполняются.
Пример запроса плюс(Число, Число, число(Число)): ответ да, Число = 1. Решение уравнения X + X = X + 1.
Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число), сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел. Другой пример, запрос плюс(Число, число(0), Число2), будет выдавать последовательность всех пар решения уравнения X + 1 = Y.
Заключение
К сожалению, разумный размер топика, не дал мне подобраться к главной теме, а именно к решению сложных логических задач на языке Пролог, не обладая стратегией их решения. Большие куски кода на Прологе могут отпугнуть не только начинающих, но даже опытных программистов. Цель данной статьи показать, что программы на Прологе могут простым образом читаться на естественном языке, а также исполняться простейшим интерпретатором.
Главная особенность Пролога — это не черный ящик и не библиотека, который решает сложные логические задачи, в Mathematica можно ввести алгебраическое уравнение и она выдаст решение, но последовательность выполняемых шагов — неизвестна. Пролог не может решать общие логические задачи (у него отсутствует логическое «или» и «отрицание»), иначе бы его вывод был недетерминированный как линейной резолюции. Пролог — это золотая середина, между простым интерпретатором и машиной для доказательства теорем, сдвиг в любую сторон приводит к потери одного из свойств.
В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу (решившему первым приз):
Написать предикат, который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3. Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 => X=4.