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

Язык программирования Пролог (PROgramming LOGic) предполагает получение решения задачи при помощи логического вывода из ранее известных фактов. Программа на языке Пролог не является последовательностью действий – она представляет собой набор фактов и правил, обеспечивающих получение логических заключений из данных фактов. Поэтому Пролог считается декларативным языком программирования.

Пролог базируется на фразах (предложениях) Хорна, являющихся подмножеством формальной системы, называемой логикой предикатов.

Пролог использует упрощенную версию синтаксиса логики предикатов, он прост для понимания и очень близок к естественному языку.

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

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

Программист на Прологе описывает объекты и отношения, а также правила, при которых эти отношения являются истинными.

Объекты рассуждения в Прологе называются термами – синтаксическими объектами одной из следующих категорий:

· константы,

· переменные,

· функции (составные термы или структуры), состоящие из имени функции и списка аргументов-термов, имена функций начинаются со строчной буквы.

Константа в Прологе служит для обозначения имен собственных и начинается со строчной буквы.

Переменная в Прологе служит для обозначения объекта на который нельзя сослаться по имени.

Пролог не имеет оператора присваивания.

Переменные в Прологе инициализируются при сопоствлении с константами в фактах и правилах.

До инициализации переменная свободна, после присвоения ей значения она становится связанной. Переменная остается связанной только то время, которое необходимо для получения решения по запросу, затем Пролог освобождает ее и ищет другое решение.

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

В Прологе программист свободен в выборе имен констант, переменных, функций и предикатов. Исключения составляют резервированные имена и числовые константы. Переменные от констант отличаются первой буквой имени: у констант она строчная, у переменных – заглавная буква или символ подчеркивания.

Область действия имени представляет собой часть программы, где это имя имеет один и тот же смысл:

· для переменной областью действия является предложение (факт, правило или цель), содержащее данную переменную;

· для остальных имен (констант, функций или предикатов) – вся программа.

Специальным знаком «_» обозначается анонимная переменная, которая используется тогда, когда конкретное значение переменной не существенно для данного предложения. Анонимные переменные не отличаются от обычных при поиске соответствий, но не принимают значений и не появляются в ответах. Различные вхождения знака подчеркивания означают различные анонимные переменные.

Отношения между объектами в Прологе называются фактами. Факт соответствует фразе Хорна, состящей из одного положительного литерала.

Факт – это простейшая разновидность предложения Пролога.

Любой факт имеет соответствующее значение истинности и определяет отношение между термами.

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

мать(мария, анна).

отец(иван, анна).

Точка, стоящая после предиката, указывает на то, что рассматриваемое выражение является фактом.

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

Цель: мать (мария, юлия).

В данном случае программе задан вопрос, является ли мария матерью юлии. Если необходимо задать вопрос, кто является матерью юлии, то цель будет иметь следующий вид:

Цель: мать(X, юлия).

Сложные цели представляют собой конъюнкцию простых целей и имеют следующий вид:

Цель: Q₁, Q₂,…,Q_n, где запятая обозначает операцию конъюнкции, а Q₁, Q₂,…,Q_n – подцели главной цели.

Конъюнкция в Прологе истинна только при истинности всех компонент, однако, в отличие от логики, в Прологе учитывается порядок оценки истинности компонент (слева направо).

Пример 1.

Пусть задана семейная база данных (БД) при помощи перечисления родительских отношений в виде списка фактов:

мать(мария, анна).

мать(мария, юлия).

мать(анна, петр).

отец(иван, анна).

отец(иван, юлия).

Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели:

Цель: отец(иван, X), мать(X, петр).

На самом деле БД Пролога включает не только факты, но и правила. Факты и правила представляют собой не множество, а список. Для получения ответа БД просматривается по порядку, то есть в порядке следования фактов и предикатов в тексте программы.

Цель достигнута, если в БД удалось найти факт или правило, который (которое) удовлетворяет предикату цели, то есть превращает его в истинное высказывание. В нашем примере первую подцель удовлетворяют факты отец(иван, анна). и отец(иван, юлия). Вторую подцель удовлетворяет факт мать(анна, петр). Следовательно, главная цель удовлетворена, переменная X связывается с константой анна.

Третьим типом предложения является правило. Правило позволяет вывести один факт из других фактов. Иными словами, правило – это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными.

Правила – это предложения вида

H: - P₁, P₂,…, P_n.

Символ «: -» читается как «если», предикат H называется заключением, а последовательность предикатов P₁, P₂,…, P_n называется посылками. Приведенное правило является аналогом хорновского дизъюнкта ШP₁ЪШ P₂,…,ЪШP_n ЪH. Заключение истинно, если истинны все посылки. В посылках переменные связаны квантором существования, а в заключении - квантором всеобщности.

Пример 2.

Добавим в БД примера 18 правила, задающие отношение «дед»:

мать(мария, анна).

мать(мария, юлия).

мать(анна, петр).

отец(иван, анна).

отец(иван, юлия).

дед (X, Y): - отец(X, Z), мать(Z, Y).

дед (X, Y): - отец(X, Z), отец(Z, Y).

Тогда вопрос, является ли иван дедом петра, можно задать в виде следующей цели:

Цель: дед(иван, петр).

Правила - самые общие предложения Пролога, факт является частным случаем правила без правой части, а цель – правило без левой части.

Все предложения для одного предиката связаны между собой отношением «или».

Очень часто правила в Прологе являются рекурсивными. Например, для нашей семейной БД предикат «предок» определяется рекурсивно:

предок(x, y): - мать(x, y).

предок(x, y): - отец(x, y).

предок(x, y): - мать(x, z), предок(z, y).

предок(x, y): - отец (x, z), предок(z, y).

Рекурсивное определение предиката обязательно должно содержать нерекурсивную часть, иначе оно будет логически некорректным и программа зациклится. Чтобы избежать зацикливания, следует также позаботиться о порядке выполнения предложений, поэтому практически полезно, а порой и необходимо придерживаться принципа: «сначала нерекурсивные выражения».

Программа на Прологе - это конечное множество предложений.

К комментарию на Прологе относится всё, что находится между знаками /* и */.

/* Это комментарий. */

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

% И это тоже комментарий.