Логическое программирование на языке ПРОЛОГ

 

Язык Пролог является представителем семейства языков логического программирования и в сравнении с традиционными языками программирования, предназначенными для записи алгоритмов, такими как Бейсик, Фортран, Паскаль, Си, обладает существенными особенностями:

• программа на Прологе не является алгоритмом, а представляет собой запись условия задачи на языке формальной логики (т.е. это дескриптивный, описательный язык программирования);

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

• Пролог требует особого стиля мышления программиста,что затрудняет изучение его теми, кто уже привык к процедурному программированию, поэтому, так называемые, практические программисты не стремятся переходить на этот язык, что мешает росту популярности Пролога; однако во многих странах (Японии, Англии, Франции, Германии, Израиле и т.д.) расширяется практика применения Пролога в образовании как первого изучаемого языка программирования; переход к процедурным языкам типа Паскаля в этом случае трудностей не вызывает.

Все это позволяет отнести Пролог в существующем делении языков программирования на языки низкого и высокого уровня к языкам сверхвысокого уровня. В японском проекте создания в 90-х годах XX века компьютеров 5-го поколения (обладающих искусственным интеллектом) Пролог положен в основу аппаратной организации и разработки программного обеспечения. Нынешний Пролог, безусловно, не является окончательным вариантом языка программирования ЭВМ 5-го поколения и в ближайшие годы получит существенное развитие. По-видимому, он сыграет роль Бейсика дескриптивного программирования: его значение и возможности в популяризации и распространении идей логического программирования чрезвычайно велики.

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

Программирование на Прологе включает в себя следующиеэтапы:

1) объявление фактов об объектах и отношениях между ними;

2) определение правил взаимосвязи объектов и отношений между ними;

3) формулировка вопроса об объектах и отношениях между ними.

Имена - это последовательности букв и цифр, начинающиеся с буквы (строчной !). Системы программирования на Прологе для компьютеров допускают использование лишь латинских строчных и прописных букв: а .. z, A .. Z. Использование русских строчных и прописных букв: а .. я, А .. Я не допускается. При практической работе с интерпретатором рекомендуется, чтобы смысл имен оставался понятным, использовать в качестве имен запись русских слов латинскими буквами. В данном параграфе мы будем записывать все именарусскими буквами, чтобы сделать смысл программ наиболее понятным. При запуске этих программ в «англо-язычных» системах программирования нужно заменять русские буквы в именах на латинские.

Типы данных включают переменные, атомарные значения и структуры (рис. 3.15).

 

Рис.3.1 5. Классификация типов данных Пролога

 

Примеры специальных атомов:

: - ( обозначающая импликацию),

? (вопрос, обозначающий отрицание),

! (предикат отсечения, рассматривается далее).

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

Структура - это конструкция, состоящая из имени структуры и заключенного в скобки списка ее аргументов, разделенных запятыми. Элементами структур могут быть числа, атомы, переменные, другие структуры и списки. Примеры структур: str(A,B,C), носит(юрий,пиджак).

Списки представляют собой объединение элементов произвольных видов, разделенных запятыми и заключенных в квадратные скобки. Списки отличаются от структур тем, что количество элементов может меняться при выполнении программы. Примеры списков: [1,3,5,7], [красный,желтый,зеленый].

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

• константа сопоставляется только с равной ей константой;

• идентичные структуры сопоставляются друг с другом;

• переменная сопоставляется с константой или с ранее связанной переменной (и становится связанной с соответствующим значением);

• две свободные переменныемогут сопоставляться (и связываться) друг с другом. С момента связывания они трактуются как одна переменная: если одна из них принимает какое-либо значение, то вторая немедленно принимает то же значение.

Примеры: 5 сопоставляется с 5, «имеет» сопоставляется с «имеет», «сергей» не сопоставляется с «юрий», «имеет(сергей,машина)» не сопоставляется с «имеет(сергей, телевизор)», «имеет(сергей,машина)» сопоставляется с «имеет(Х,машина)»,в этом случае переменная Х получает в качестве значения атом «сергей».

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

Пример 1. Факты, описывающие телефонные номера:

телефон(иванов,т561532).

телефон(петров,т642645).

телефон(сидоров,т139833).

Это означает: телефон Иванова - 56-15-32 и т.п. Заметим, что перед цифрами номера идет буква 'т". Она делает номер телефона литерной константой, так как числа 561532,642645, 139833 слишком велики, чтобы быть числовыми константами.

Пример 2, Факты, описывающие студентов:

нравится(сергей,рэп).

нравится(юрий,джаз).

носит(сергей,блейзер).

носит(юрий,пиджак).

Это означает: «Сергею нравится рэп», «Юрию нравится джаз» и т.п.

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

 

<голова правила> : - <список подцелей>

 

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

крутойпарень(Х):- нравится(Х,рэп),носит(Х,блейзер).

 

Это означает «любой Х - крутой парень, если Х нравится рэп и Х носит блейзер». Еще примеры правил:

 

ест(Х,Y): - пища(Y), любит(Х,Y). («Каждый Х ест любой Y, если Y - пища,

и Х любит Y»)

владелец(А,В) : - купил(А,В). («Любой А есть владелец каждого В, если А купил В»)

 

В Прологе все предложения программы - факты, правила, вопрос - заканчиваются точкой.

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

Вопрос - отправная точка логического вывода, происходящего при выполнении программы. На любой вопрос компьютер будет пытаться дать ответ «Да» или «Нет» в зависимости от того. согласуется или нет утверждение, стоящее в вопросе, с фактами и правилами базы знаний. Вопрос, не содержащий переменных, является общим: «имеет ли место факт... ?». Так, например, к базе знаний примера 1 можно поставить вопрос

 

?-телефон(иванов,т123456).

 

и ответ будет «Нет», так как константа т123456 не согласуется ни с одним фактом.

Если к базе знаний (пример 3)

 

нравится(сергей ,рэп).

нравится(юрий,джаз).

носит(сергей,блейзер).

носит(юрий,пиджак).

крутойпарень(Х) : - нравится(Х,рэп),носит(Х,блейзер).

 

задать вопрос

 

?-крутойпарень(юрий).

 

то будет получен ответ «Нет». В самом деле, в результате резолюции утверждение в этом вопросе согласно правилу заменится конъюнкцией утверждений

 

нравнтся(юрий,рэп), носит(юрий,блейзер).

 

(переменная Х в правиле получила значение «юрий»). Эти утверждения не согласуются с остальными фактами базы знаний. Для вопроса

 

? - крутойпарень(сергей).

 

будет получен ответ «Да», так как в этом случае противоречий при согласовании вопроса и базы знаний не возникает.

Вопрос, в котором имеются переменные, является частным: «длякаких значенийпеременных факт ... имеет место ?». В процессе сопоставлений при выполнении программы переменные получат значения тех констант (конкретизируются), для которых сопоставление запроса, в целом, успешно, и будут выведены на экран. Так, в ответ на вопрос

 

? - телефон(иванов,Х).

 

к базе знаний примера 1 на экране появится сообщение Х=т561532 и будет дан ответ «Да».

Если к базе знаний примера 3 задать вопрос в форме

 

?- крутойпарень(А).

 

то свободная переменная А в вопросе сопоставляется со свободной переменной Х в правиле и совмещается с ней, т.е. становится одним и тем же. В результате резолюции согласно правилу произойдетзамена

 

крутойпарень(А)

 

на

 

нравится(А,рэп), носит(А,блейзер),

 

а затем предикат «нравнтся(А.рэп)» успешно согласуется с фактом «нравится(сергей,рэп)>>, и при этом переменная А конкретизируется значением «Сергей»; от вопроса теперь остается «носит(сергей,блейзер)», а в базе знаний имеется соответствующий факт. Ответ: «Да» и на экране появится значение присутствовавшей в вопросе переменной А:

 

А=сергей.

 

Отметим, что машина «не понимает» используемых в программе имен: «нравится», «носит», «сергей» и т.д. Мы могли бы вместо них использовать любые другие обозначения. Для интерпретатора Пролога существенны только совпадения и различия имен, а также связи между предикатами, устанавливаемые с помощью конъюнкций и импликаций. Осмысленные имена мы будем использовать только для того, чтобы облегчить чтение и понимание программ самим себе. Однако, в Прологе существуют предопределенные имена (встроенные предикаты), которые позволяют выполнить арифметические операции, сравнения, графические построения, ввод-вывод и другие полезные операции как побочный продукт выполнения программы. Встроенные предикаты Arity-Prolog описаны в справке по системе программирования, вызываемой нажатием клавиши F1.

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

АЛГОРИТМ ВЫПОЛНЕНИЯ ПРОГРАММ НА ПРОЛОГЕ

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

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

 

А:-В1,В2,...,Вn.

 

можно рассматривать как определение процедуры А, утверждающее, что для ее выполнения надо определить Bl, B2, ... , Вn. Процедуры Bl, B2, ... , Вn должны выполняться в определенном порядке - слева направо. Если выполнение очередной процедуры завершается успешно, то происходит переход к следующей процедуре. Если же по какой-либо причине очередная процедура выполняется неуспешно, то происходит переход к следующему варианту описания этой процедуры, и порядок поиска такого варианта в Прологе задан - сверху вниз. Поиск подходящих для согласования фактов и правил в базе знаний происходит последовательно сверху-вниз, и если подходящих фактов не найдено - ответ отрицательный. Эта стратегия согласования называется «сверху-вниз» и «замкнутый мир».

Рассмотрим процесс выполнения программы более подробно на примере.

Программа 112

а : - b, с, d.

b : - е, f.

с. d. е. f.

? - а.

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

 

Таблица 3.6

К процессу выполнения программы на Прологе

Номер шага резолюции	Целевое предложение	Исходное предложение	Резольвента
	?-а.	a:-b,c,d.	?-b,c,d.
	?-b,c,d.	b:-c,f.	?-e,f,c,d.
		?-е,f,с,d	e. ?-f,c,d.
		?-f,c,d.	f. ?-c.d.
		?-c,d.	c. ?-d.
		?-d.	d. Пустая

 

При выполнении логического вывода, если необходимо, происходит конкретизация переменных. Рассмотрим пример.

Программа 113

любит(юрий,музыку).

любит(сергей,спорт).

любит(А,книги):-читатель(А),любопытный(А).

любит(сергей,книги).

любит(сергей,кино).

читатель(юрий).

любопытный(юрий).

?- любит(X,музыку), любит(X,книги).

Двойной запрос в этой программе может быть представлен целевым деревом:

 

 

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

 

 

Переменная Х конкретизируется значением «юрий». Начинается согласование 2-й подцели запроса с условием Х=юрий. 1-е и 2-е предложения программы не соответствуют подцели. В 3-ем предложении:

 

любит(А,книги):-читатель(А), любопытный(А).

 

аргумент А заголовка есть переменная, поэтому она может соответствоватьX, т.е. получает значение А=юрин; вторые аргументы совпадают. Теперь тело правила образует новое множество целей для согласования. Получаем целевое дерево:

 

 

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

 

Рассмотрим еще один пример.

Программа 114

любит(оля,чтение).

любит(света,бадминтон).

любит(для,бадминтон).

любит(лена,плавание).

любит(лена,чтение).

?- любит(X,чтение), любит(X,плавание).

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

 

любит(оля,чтение).

 

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

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

 

Рис.3.16. Дерево вывода программы на Прологе

 

Обход дерева начинается с движения от вершины (запроса) по самой левой ветви вниз до конца (abed), при этом запоминаются все точки ветвления (точки возврата). При достижении конца ветви решение будет либо найдено, либо нет. В обоих случаях Пролог продолжает дальнейший поиск решений. Выполняется возврат в последнюю точку ветвления с. При этом конкретные значения, присвоенные переменным при движении вниз на сегменте c-d. отменяются, и движение вниз продолжается по расположенной справа ветви с-е до конца дерева вниз. Затем произойдет возврат в предыдущую точку ветвления b и движение продолжится по ветви bfg, и так до тех пор, пока все дерево вывода не будет пройдено.