Язык ПРОЛОГ: основные конструкции

Общая характеристика языка Пролог

Математическая логика дает нам ясный и точный язык для явного выражения знаний, гипотез и целей. Возможность машинного доказательства теорем, основанного на специальном выводе, названном принципом резолюций, впервые была получена Дж. Робинсон в 1965 году. Это привело к желанию построить язык программирования, который позволил бы реализовать одну из интеллектуальных сторон деятельности человека - проведение рассуждений в виде программ.

В начале 70-х годов прошлого века группой под руководством А. Колмероэ в Марселе на Фортране была написана программа для доказательства теорем, названная Прологом (от Programmation en Logique). Это привело в конце десятилетия к разработке языка Пролог и в дальнейшем развитию этого языка и в целом направления, которое получило название логического программирования.

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

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

Вопрос задачи, называемый запросом, - это также некоторый предикат, истинностью которого мы интересуемся. Если запрос не содержит переменных, то вычисление его значения дает ответ "Да" при его истинности либо ответ "Нет" при его ложности. Если же в предикате запроса есть переменные, то ищутся их значения ( интерпретация ), при которых этот предикат и все предикаты программы становятся истинными. В этом и состоят вычисления программы на Прологе.

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

Итак, в языке Пролог рассматриваются объекты и 3 вида утверждений относительно объектов: факты, правила и запросы. Единственной структурой данных является терм.

Объекты и термы Пролога

Объектами Пролога являются

Завершающий список элемент nil можно при записи опускать, подразумевая его в необходимых случаях. Для конкатенации (соединения) списков и элементов в один список используется точка как бинарная операция соединения левой части (головы списка) и правой части (хвоста списка). В случае операции конкатенации квадратные скобки на нулевом уровне можно опускать. Например, a.X.Y.a при X=b, Y=c есть список [a, b, c, a], также при X=[b], Y=[c] есть тот же список, а при X=[b, [d, e]] и Y=[[c]] есть список [a, b, [d, e], [c], a].

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

f(t1,..., tn),

где f - имя n -арного функтора, а $$t_{i} (i \in \overline {1,n})$$ - аргументы.

Примерами составных термов являются: холодный (вода), отец (иван, петр), list(d, list(b, nil)) и bintree(bintree(nil, 7, nil), L, 12).

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

Во втором примере отношение "иван является отцом петра" задается как булева функция с 2 аргументами-константами.

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

В четвертом примере функция с именем bintree и тремя аргументами возвращает в виде списков бинарное дерево с корнем 7, правым сыном 12 и левым сыном, который определяется переменной L.

Термы, в которые не входят переменные, назовем основными , а термы, содержащие переменные, - неосновными . Так, три первых примера выше являются основными термами, а четвертый пример - неосновным термом.

В логическом программировании основной структурой является предикатная функция, описываемая составным термом, которая имеет истинностное значение (истина или ложь), возможно зависящее от значений аргументов. Такой предикат называется атомарным, или атомом .

Факты

Факты - это простейшие утверждения относительно объектов программы, которые считаются истинными, т. е. имеют смысл аксиом программы. Каждый факт оформляется в виде атомарного предиката и стрелки влево, которая находится справа от него. Так, в следующем примере

мужчина (иван)<-
мужчина (петр)<-
отец (иван, петр)<-
произведение (2, 2, 4)<-

задается, что объекты иван и петр являются мужчинами, что иван является отцом петра и что дважды два - четыре.

Почему ставится стрелка? Общий вид записи продукции "если A, то B ", где A и B - предикаты, выражается на Прологе следующим образом:

B <- A.

Факт не имеет посылки и читается "то B ", т. е. утверждение B рассматривается как истинный факт.

Множество фактов образуют простейшую программу Пролога. Но атомарный предикат факта может содержать переменные в качестве аргументов или неосновные термы. В этом случае по умолчанию считается, что добавлен квантор всеобщности $$\forall$$ с переменными предиката. Такие факты называются универсальными: они истинны для любых значений переменных. Например,

любит (X, яблоко)<-

означает, что любой объект программы "любит яблоко". Универсальные факты сокращают запись программы.

Правила

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

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

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

Правило Пролога есть продукция, посылкой которой является конъюнкция атомарных предикатов, а заключением - 1 атомарный предикат. Правило имеет следующий синтаксис:

A <- B1,..., Bm (m >= 0),

где $$A, B_{i} (i \in \overline {1,m})$$ - атомарные предикаты и запятая в правой части правила означает конъюнкцию. Читать правило нужно так: "Если заголовком, а правая часть - телом правила . Совокупность правил с одним и тем же предикатом в заголовке называется процедурой .

Решение вышеописанного примера состоит в определении отношения предок следующим образом: предком лица является либо мать, либо отец, либо мать предка, либо отец предка. Таким образом все решение сводится к следующей процедуре из 4 правил:

предок (X, Y) <- мать (X, Y)
предок (X, Y) <- отец (X, Y)
предок (X, Y) <- предок (Z, Y), мать (X, Z)
предок (X, Y) <- предок (Z, Y), отец (X, Z)

Заметим, что отношение предок определено этими правилами рекурсивно. Теперь для определения родства между двумя лицами достаточно также задать рекурсивно отношение родственники следующей процедурой из 3 правил:

родственники (X, Y) <- предок (X, Y)
родственники (X, Y) <- предок (Y, X)
родственники (X, Y) <- предок (Z, X), предок (Z, Y)

Заметим, что обозначения переменных в правилах несущественны, лишь бы они обозначались одинаково в заголовке и теле процедуры. Но если на все переменные левой части подразумевается наложенным квантор всеобщности $$\forall,$$ то на все переменные правой части, которые отсутствуют в левой, подразумевается наложенным квантор существования $$\exists.$$

Совокупность фактов и правил образует программу Пролога (или базу знаний).

Запросы

Запросы - это цели выполнения программы Пролога. Запрос является атомарным предикатом или конъюнкцией атомарных предикатов и имеет синтаксис:

<- B1,..., Bm (m > 0),

где $$B_{i} (i \in \overline {1,m})$$ - атомарный предикат, а запятая, разделяющая атомы, означает операцию конъюнкции. Обозначение переменных запроса несущественно, и при переобозначении каждой переменной запрос не изменяется.

Если запрос не имеет переменных, то ответом на запрос является значение "Да" в случае, когда истинность конъюнкции предикатов запроса следует из истинности конъюнкции фактов и правил программы, и значение "Нет" в противном случае.

Если запрос имеет переменные, то по умолчанию подразумевается квантор существования перед конъюнкцией предикатов запроса для каждой переменной запроса. Если для какого-либо набора $$\Upsilon$$ значений переменных запроса и какого-либо соответствующего переобозначения переменных в правилах и фактах и придания им согласованных с запросом значений истинность конъюнкции предикатов запроса следует из истинности конъюнкции фактов и правил, то такой набор $$\Upsilon$$ является ответом на запрос. Вычисления Пролога состоят в получении всех ответов $$\Upsilon _{1}, \Upsilon ,..$$. на запрос. Однако если не существует такого набора значений переменных запроса, который ведет к следованию истинности запроса из истинности фактов и правил программы, то ответом на запрос является значение "Нет". Отметим лишь, что данное определение не является достаточно четким и мы его в дальнейшем уточним.

Рассмотрим пример программы, которая образована из следующей совокупности фактов

отец (иван, петр) <-
отец (петр, анна) <-
отец (яков, мария) <-
мать (анна, федор) <-
мать (елена, иван) <-
мать (елена, яков) <-
мать (софья, вера) <-

Пусть имеется запрос

<- родственники (федор, мария).

Этот запрос не имеет переменных. Но правила процедуры предок позволяют установить, что предками федора являются анна, петр, иван и елена, а предками марии являются яков и елена. Поскольку федор и мария имеют общего предка елену, то правила процедуры родственники позволяют установить истинность запроса. Поэтому ответ на него Да.

Для запроса

<- родственники (вера, мария).

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

Пусть теперь имеется запрос

<- предок (X, федор).

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

Рассмотрим другой запрос

<- предок (елена, X).

Этот запрос требует установить всех лиц, для которых елена является предком (потомки елены ). Ответы на запрос образуют список иван, яков, петр, мария, анна, федор.

Наконец, для запроса

<- предок (вера, X)

нет ни одного значения переменной X, при котором мы могли бы вывести это отношение. Поэтому ответом на запрос является Нет, т. е. вера не имеет потомков.

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

Упражнения