Тема 2 Основные понятия языка prolog Часть 2 Преподаватель –Юлия Александровна Грачёва

Пролог-программы состоят из термов. Терм – это либо константа, либо переменная, либо структура. Терм записывается как последовательность литер, которые делятся на четыре категории, такие, как: ABCDEFGHIJKLMNOPQRSTUVWXYZ abсdefghijklmnopqrstuvwxyz !"#$%&'()=–~^|\{}[] +;*:,.?/

Константами являются поименованные конкретные объекты или конкретные отношения. Существует два вида констант: атомы и целые числа. Целые числа используются для представления числовых данных, что позволяет выполнять над ними арифметические операции. Есть два вида атомов: составленные из букв и цифр и составленные из спецзнаков. Атомы, составленные из спецзнаков, как правило, состоят только из спецзнаков. Специальные символы, используемые Прологом для обозначения вопросов '?-' и правил ':-', также являются атомами.

Если атом заключается в одиночные кавычки, то его имя может содержать любые литеры. Для простоты чтения внутрь атома можно включать специальную литеру – подчеркивание '_'. Примеры атомов: eat cat mouse -- My_bag А вот это – не атомы 2304ieh _Dog Orange-juice Cheese

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

Анонимная переменная – это одиночный знак подчеркивания '_'. Пример ?- eat (cat, _). Если в одно утверждение входят несколько анонимных переменных, их можно интерпретировать неоднозначно. Это характерная особенность, присущая только анонимной переменной. Она позволяет избавить программиста от необходимости придумывать разные имена переменным в тех случаях, когда эти имена в утверждении нигде больше не употребляются.

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

Структуры полезны также в тех случаях, когда имеется общий тип и может существовать много конкретных экземпляров объектов этого типа. Структура записывается на Прологе с помощью указания ее функтора и компонент. Компоненты заключаются в круглые скобки и разделяются запятыми. Функтор записывается перед открывающей круглой скобкой. have (student, comp(pc, acer)). comp(pc, acer) – это структура

Структуры с переменными в качестве компонент могут появляться в вопросах. ?- have (student, comp(pc, Type)). Если переменные в дальнейшем не используются, можно употребить анонимную переменную: ?- have (student, comp(_, acer (_, twelve_inch ))). Анонимные переменные не «сцепляются» друг с другом.

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

Операторы – это особая форма синтаксиса, облегчающая чтение соответствующих структур. x+y*z в виде структуры выглядит так: +(x,*(y,z)) Операторы не вызывают выполнения каких-либо арифметических операций: в Прологе 3+4 и 7 означают разные объекты. Терм другой способ записи терма +(3,4), который является структурой.

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

Для чтения арифметических выражений, содержащих операторы требуется знание трех свойств каждого оператора: его позиции, его приоритета и его ассоциативности. Операторы, подобные знакам сложения (+), вычитания (-), умножения (*) и деления (/), записываются между своими аргументами и называются инфиксными операторами. Операторы, записываемые перед своими аргументами, называются префиксными. Операторы, записанные после своих аргументов, называются постфиксными.

Приоритет оператора определяет, какая операция выполняется первой. В Прологе каждый оператор связан со своим классом приоритета, представляющим собой целое число. Операторы бывают левоассоциативными и право ассоциативным и. Левоассоциативный оператор должен иметь слева операции одинакового или низшего приоритета, а справа – операции низшего приоритета. Структура, образованная арифметическими операторами, подобна любой другой структуре. На самом деле никакие арифметические действия не выполняются до тех пор, пока не встретится предикат 'is' (есть)

В Прологе существует особый предикат равенство, являющийся инфиксным оператором, обозначаемым литерой '='. Когда делается попытка доказать согласованность с базой данных целевого утверждения ?- X = Y. Пролог пытается установить соответствие между X и Y; целевое утверждение «доказуемо», если такое соответствие имеется. Это действие можно представить себе как попытку сделать X и Y равными. Предикат равенства является встроенным, т. е. он уже определен в Пролог-системе. Предикат равенства работает так, словно определен следующий факт: X = X.

При согласовании с базой данных цели вида X = Y, где X и Y любые термы, в которых могут содержаться не- конкретезированные переменные, действуют следующие правила: если X представляет собой неконкретезированную переменную, а Y конкретезирована (её значение неважно), то X и Y равны. Кроме того, X станет конкретезированной – ей будет дано то же значение, что и Y. Пример: ?- go(student, cafe) = X.

целые числа и атомы всегда равны самим себе. Например, попытки согласовать следующие целевые утверждения дадут результаты, показанные справа: taxi = taxi /* верно */ pen = pensil /* ложно */ 1066=1066 /* верно */ 1206=1583 /* ложно */ Две структуры равны, если они имеют один и тот же функтор и одинаковое число аргументов, причем все соответствующие аргументы равны. watch(taxi,tv) = watch(taxi,Х).

Целевое утверждение X=Y всегда верно (согласуется с базой данных), если один из аргументов неконкре- тезирован. Более простой способ записи такого правила заключается в использовании того факта, что переменная равна самой себе. Пролог предоставляет также предикат '\=' соответствующий не равно. Целевое утверждение Х\=Y верно в тех случаях, когда не доказуемо утверждение X=Y, и наоборот.

П ролог предоставляет некоторые «встроенные» предикаты, позволяющие сравнивать числа. Их аргументами могут быть конкретезированные переменные, значениями которых являются целые числа, а также целые числа, записанные в виде констант. X = Y X и Y представляют одно и то же число X \= Y X и Y представляют разные числа X Y X меньше YX Y X больше Y X = Y X меньше или равно Y X = Y X больше или равно Y

Поскольку операторы сравнения являются предикатами, можно было бы предположить, что в Прологе допустим следующий факт: 23. утверждающий, что 2 на самом деле больше 3. Факты, подобные этому, с формальной стороны полностью соответствует правилам Пролога. Однако Пролог не разрешает добавлять факты к «встроенным» предикатам. Такая особенность предотвращает непредсказуемые изменения смысла встроенных предикатов.

Пример. База знаний (для ясности набрано на русском): правил(одри,844,878). правил(анаравд,878,916). правил(хивел_да,916,950). правил(лого_ад_идеал,950,979). правил(хивел_аб_иеуаф,979,985). правил(кадваллон,985,986). правил(маредудд, 986,999). принц (X,Y):-правил(Х,А,В),Y = А,Y = В ?- принц(одри,1979). ?- принц(Х,900).

Рассмотрим инфиксный оператор 'is'. Его правый аргумент – терм, интерпретируемый как арифметическое выражение. Для того чтобы выполнить 'is', Пролог сначала вычисляет его правый аргумент в соответствии с правилами арифметики. Результат вычислений проверяется на соответствие с левыми аргументами, чтобы определить, доказуемо ли целевое утверждение. plotnost(X,Y):-nasel(Х,Р), sqv(Х,А), Y is Р/А. Здесь переменная Y до исполнения is не конкретезирована, и она остается в таком состоянии до вычисления выражения. Когда выражение вычислено, Y принимает значение, равное полученной величине.

База данных: nasel(rus,130). nasel(usa,300). nasel(ind,1300). nasel(chi,1400). sqv(rus,10). sqv(usa,8). sqv(ind,3). sqv(chi,9). plotnost(X,Y):-nasel(Х,Р), sqv(Х,А), Y is Р/А. ?- plotnost(chi,Y). ?- plotnost(tur,Y). Y=156no

Предикат is нужно использовать каждый раз, когда требуется вычислить арифметическое выражение. Если некоторая структура интерпретируется как арифметическое выражение, то к ней применяется операция вычисления арифметического выражения, заключающаяся в фактическом выполнении арифметических действий над двоичными представлениями элементов структуры и получении соответствующего результата. X+Y сумма X и YX–Y разность X и Y X*Y произведение X и YX/Y частное от деления X на Y X mod Y остаток от деления X на Y

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

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

Пример parents (С,M,F):- moth(С,М), fath(C,F). moth(jul,alla). moth(kost,alla). moth(dima,tata). fath(jul, alex). fath(kost, alex). fath(dima, serg). ?-boy(kost), parents(kost,М,F), parents(jul,М,F). Нужно понять, брат ли kost для jul.

boy(kost) parents(kost,М,F) parents(jul,М,F) Эта цель проверяется первой Эта цель проверяется второй Эта цель проверяется последней

Результат выполнения целевого утверждения: boy(kost) parents(kost,alla,alex) parents(jul,alla,alex) Эта цель проверяется первой Эта цель проверяется второй Эта цель проверяется последней

Фрагмент доказатель ства (вторая цель):

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

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

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

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

Предикат '=' пытается сделать свои аргументы равными путем установления соответствия между ними. Задача pr (15). pr (9). pr (a*b). Задаём вопрос ?- pr (2*3). Какой факт соответствует запросу? ?- X is 2*3. а этот вопрос даст вычислить произведение