Лекция 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 в качестве подцели некоторого правила приводит к многократному повторению остальных подцелей этого правила.
