Рекурсивное определение правил

Лекция 7. Общие сведения о структуре языков логического программирования

 

Общие положения

 

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

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

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

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

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

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

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

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

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

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

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

Само название Пролог есть сокращение, означающее программирование в терминах логики. Идея использовать логику в качестве языка программирования возникла впервые в начале 70-x годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-x годов.

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

Язык Пролог характеризуется следующими важными моментами:

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

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

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

• Аргументы отношения могут быть (среди прочего): конкретными объектами, или константами (такими, как том и энн), или абстрактными объектами, такими, как X и Y. Объекты первого типа называются атомами. Объекты второго типа — переменными.

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

Итак:

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

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

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

Это означает «любой X - крутой парень, если X нравится рэп и X носит блейзер».

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

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

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

и ответ будет «Нет»,'так как константа т 123456 не согласуется ни с одним фактом. Если к базе знаний (пример 3)

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

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

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

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

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

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

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

Для вопроса

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

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

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

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

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

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

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

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

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

на

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

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

А=сергей.

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

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

 

На основе вышесказанного можно утверждать:

• Пролог-программы можно расширять, добавляя в них новые предложения.

• Прологовские предложения бывают трех типов: факты, правила и вопросы.

• Факты содержат утверждения, которые являются всегда, безусловно верными.

• Правила содержат утверждения, истинность которых зависит от некоторых условий.

• С помощью вопросов пользователь может спрашивать систему о том, какие утверждения являются истинными.

• Предложения Пролога состоят из головы и тела. Тело — это список целей, разделенных запятыми. Запятая понимается как конъюнкция.

• Факты — это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и (непустое) тело.

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

 

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

Рекурсивное определение правил

 

Добавим к программе о родственных связях еще одно отношение — предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных (ближайших) предков, а второе — отдаленных. Будем говорить, что некоторый является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок.

Если фамильное дерево очень «глубокое», то есть цепочка родственных отношений очень длинна, то пролог- программа тоже будет длинной длинной и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.

Существует, однако, корректная и элегантная формулировка отношения предок — корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь — определить отношение предок через него самого, то есть использование самого отношения предок в его определении. Такое определение может озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны; интуитивно это ясно. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия — один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.

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

Пример: рекурсивное определение натурального числа:

• 1- натуральное число;

• число, на 1 большее натурального числа, также натуральное.

В системах логического программирования рекурсия служит также для описания циклов, повторений и является важнейшим методом программирования.

Рассмотрим простой пример: вычисление факториала натурального числа п (п!). Определение п! рекурсивно:

1) 1! = 1,

2) п! = (п-1)! * п.

Для описания отношения «факториал» между п и п! будем использовать двухар­ный предикат факт(И,М).

Тогда база знаний, соединенная с запросом, приобретает вид (программа 1): Программа 1 факт (1,1).

факт(N,X): - факт(№-1,Y), X is Y*N.

?- факт(3,А);

В данной программе правило «факт» вызывает само себя - это и есть рекурсия. Запись is Y*N представляет собой обращение к встроенному предикату «is» («есть») для описания арифметического действия.

Процесс работы программы можно изобразить следующим образом:

?факт(3,А0).

ОТВЕТ: А=6

?факт(2,А1).

Х1= 2*3 = 6

?факт(1,А2).

Х2= 1*2 = 2

факт(1,1).

Здесь стрелочка вниз означает сопоставление и резолюцию, а стрелочка вверх - возврат и завершение отложенного вычисления.

Правило «факт» вызывает само себя - происходит углубление рекурсии (прямой' ход). При этом в памяти ЭВМ выделяется место для переменных А,А0,А1,А2 и N,N0,N1,N2, образующих стеки. При согласовании вопроса с предикатом факт(1,1) рекурсия прекращается и начинается возврат из рекурсии (обратный ход) - выпол­нение отложенных на прямом ходе согласований. Предикат факт(1,1) играет очень важную роль - это ограничитель рекурсии, условие ее завершения.

Отметим, что Пролог стремится найти все решения поставленной задачи, а зна­чит, после появления ответа А=6 происходит возврат к вопросу?факт(1,А2) и попытке согласовать его с правилом «факт». Это приводит к бесконечному процес­су рекурсии с отрицательными аргументами в «факт», которая завершается при исчерпании глубины зарезервированных интерпретатором Пролога стеков. Уско­рить выход из рекурсии можно, добавив к предикату «факт(1,1)» отсечение!:

факт(1,1): -!.

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

В общем случае последовательность предложений в базе знаний не имеет значе­ния. Однако это не так для рекурсивно-определенных отношений. Например:

родитель(Х):- родитель(У),отец(У,г).

родитель(коля).

отец(коля,петя).

родитель(петя).

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

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

Программа 2 родитель(коля).

родитель (X): - родитель (Y), отец (Y, X). отец(коля,петя).

? - родитель(петя).

 

Неограничено-повторное обращение к предложению может быть и более замас­кированным так, как это получается в программе 3.

Программа 3

выше(А,В): - ниже(В,А). ниже(В,А): - выше(А,В), выше(коля, петя).

?- ниже(петя,коля).

Однако если третье предложение стоит на первом месте, то повторного обраще­ния не произойдет и ответ будет найден.

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

Р(1,-)-

Р(п,...)Q1,..., Qn, P(n-i,...), Rl,... Rm.

Правило P обращается само к себе, при этом происходит углубление рекурсии. Предикаты Q1,..., Qn выполняются на прямом ходе рекурсии, a R1Rm - на обратном; п - это некоторый условный параметр, входящий в условие продолжения рекурсии, а Р(1,...) - факт, завершающий процесс рекурсии.

Особенно простым случаем рекурсии является простое циклическое повторение. Один из способов организации повторения связан с наличием в базе знаний проце­дуры вида repeat, repeat: - repeat.

Использование repeat в качестве подцели некоторого правила приводит к мно­гократному повторению остальных подцелей этого правила.