Логическое программировыание Презентация 6 Операторы в Прологе. - презентация

1 Логическое программировыание Презентация 6 Операторы в Прологе

2 Содержание Определение оператора Понятие структуры Представление структур Формат определения операторов Встроенные операторы Приоритеты, типы Арифметические, логические операторы Примеры определения новых операторов Сопоставления Общие выводы 2

3 Понятие структуры в Прологе основной формой представления являются структуры. Структура со ­ стоит из функтора ( имени структуры ) и набора компонент ( составных частей структуры ). Число аргументов функтора называется арностью. Для структур удобно использовать графическое представление в виде дерева, корнем дерева является функтор, а ветвями - компоненты. Компоненты могут быть также переменными или структурами. 3 (а) представление в виде дерева; (б) запись на Прологе.

4 Древовидное представление выражений ( структур ) Пример : запишем арифметическое выражение : 2 * a + b / c ~ +(*(2,a), /(b,c)) % альтернативная запись Вычисления в Прологе : ?- A = 3, B=9, C=3, X is 2*A+B/C. ~ ?- A = 3, B=9, C=3, X is +(*(2,A),/(B,C)). A = 3 B = 9 C = 3 X = */ 2ab c

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

6 Типы ( ассоциативность ) операторов 6 если оператор инфиксный, то указывается тип xfx, xfy ( правоассоциативный ) или yfx ( левоассоциативный ). для постфиксного оператора указывается тип xf или yf для префиксного - fx или fy. f указывает расположение функтора, х указывает на аргумент, чей приоритет должен быть строго выше оператора, у обозначает аргумент с приоритетом выше или равным приоритету оператора.

7 Примеры ассоциативности Левая ассоциативность : оператор сложения + определен как op( 500, yfx, +). + обладает левой ассоциативностью. A + B + C + D выполняется как : +(+(+(A,B),C),D) 7 Правая ассоциативность : Оператор коньюнкции целей определен: op( 1100, xfy,,)., обладает правой ассоциативностью. A, B, C, D выполняется как,(A,,(B,,(C,D)))

8 Типы и приоритеты встроенных операторов 8 Приоритет оператора должен быть в диапазоне от 1 до 1200, самый высокий при ­ оритет - 1, самый низкий Тип оператора определяет его позицию и ассоциа ­ тивность. Приоритет оператора должен быть в диапазоне от 1 до 1200, самый высокий приоритет - 1, самый низкий Операторы с более низким приоритетом выполняются раньше остальных. ?- X is * 8. X = 19

9 Пример определения нового оператора Пример оператора : Определив оператор « нравится » как : :-op(600, xfx, likes) можно записать факт того, что Мэри нравится кино likes(mary, cinema). в более естественном виде : mary likes cinema. Т. о., введение новых операторов позволяет записывать правила, факты и т. п. в более привычном ( естественном ) виде, удобном для восприятия и интерпретации ( например, в записи математических формул и теорем ). 9

10 Определения встроенных операторов Множество заранее определенных операций : :-ор(1200, xfx, [:-,-->]). :-op(1200, fx, [:-,?-]). :-op(1100, xfy, ';'). :-ор(1050, xfy, ->). :-ор(1000, xfy, ','). :-ор(900, fy, [not, '\+']). :-op(700, xfx, [=, \=, ==, \==, =..]). :-op(700, xfx, [is, =:=, :-op(500, yfx, [+, -]). :-op(400, yfx, [*, /, //, mod]). :-op(200, xfx, **). :-op(200, xfy, ^). :-op(200, fy, -). 10

11 Основные встроенные арифметические операторы В Прологе выполняются следующие арифметические операции : +- сложение -- вычитание *- умножение /- деление mod - остаток от целочисленного деления. //- целочисленное деление ^- возведение в степень Примеры : f(X, Y, Z):-Z is X*X + Y*Y. ?- f(3,4,X). X=25; 11

12 Операции сравнения К операциям сравнения относятся следующие предикаты : =:=- проверка на равенство =\=- проверка на неравенство >- отношение « больше » =6. NoYes No 12

13 Логические выражения Пролог позволяет формировать сложные логические выражения. Простейшими логическими предикатами являются true ( истина ) и fail ( ложь, неудача ) Согласование цели true всегда успешно. Согласование цели fail всегда неудачно. Для конъюнкции целей используется предикат "," (X,Y), а для дизъюнкции - предикат ";" (X;Y) Приоритет у оператора дизъюнкции ";" выше, чем у оператора конъюнкции ",", поэтому лишние скобки в логических выражениях часто можно опускать. ?- true;(fail,fail). ?- true;fail,fail.?-(true;fail),fail). Yes YesNo Для отрицания используется предикат not(X). Так как запятая служит как для конъюнкции целей, так и для разделения аргументов, требуются дополнительные скобки, если аргумент not не является элементарным выражением. Например, нужно писать not((true,fail)). а не not(true,fail). 13

6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6" title="Примеры определения логических операторов Пример 1: Конструкция " если А то В иначе С " на языке Пролог может быть записана как (A,B;not(A),С) или (А,В;С), а конструкция " если А то В " - как (A,B,true) ?- 5>6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6" class="link_thumb"> 14 Примеры определения логических операторов Пример 1: Конструкция " если А то В иначе С " на языке Пролог может быть записана как (A,B;not(A),С) или (А,В;С), а конструкция " если А то В " - как (A,B,true) ?- 5>6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6,X=1;X=2.X = 1 X = 2Yes Пример 2: Зададим условные операторы и запишем с их помощью определение предиката « max» :-op(1160, fx, if). :-op(1150, xfx, then). :-op(1155, xfx, else). if A then B else C :- A, B; not(A), C. max(X,Y,Z) :- if X>Y then Z is X else Z is Y. ?- max(1,2,X). X = 2 14 6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6"> 6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6,X=1;X=2.X = 1 X = 2Yes Пример 2: Зададим условные операторы и запишем с их помощью определение предиката « max» :-op(1160, fx, if). :-op(1150, xfx, then). :-op(1155, xfx, else). if A then B else C :- A, B; not(A), C. max(X,Y,Z) :- if X>Y then Z is X else Z is Y. ?- max(1,2,X). X = 2 14"> 6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6" title="Примеры определения логических операторов Пример 1: Конструкция " если А то В иначе С " на языке Пролог может быть записана как (A,B;not(A),С) или (А,В;С), а конструкция " если А то В " - как (A,B,true) ?- 5>6,X=1;not(5>6),X=2.?- 5>4,X=1,true. ?- 5>6">

15 Примеры определения логических операторов Пример 3: Теорема эквивалентности / правило де - Моргана : Условная запись : ~( A & B) ~ A V ~B « Отрицание конъюнкции эквивалентно дизъюнкции отрицаний » Можем запись правило в форме предиката на Прологе : equiv((not(A,B)), (not(A);not(B))). Но удобней представить запись в более естественной матем. форме. Подходящий набор операций для данного назначения : :-ор(800, xfx, ). :-op(700, xfy, v). :-op(600, xfy, &). :-op(500, fy, ~). Теперь теорему де Моргана можно записать как следующий факт : ~ ( А & В ) ~А V ~В. 15

16 Понятие сопоставления Сопоставление ( унификация ) является наиболее важной операцией в Прологе. Оно выполняет сравнение двух термов на равенство, при этом неконкретизированные переменные получают значения, при которых термы становятся идентичными. Выполнение сопоставления может производиться либо явно, в теле пра ­ вила с помощью встроенного предиката X=Y, либо неявно, при сопоставлении цели с фактом или головой правила. Сопоставление реализует основные операции обработки данных в логическом про ­ граммировании однократное присваивание, передача параметров, создание структурных объектов, доступ к полям структурных объектов с возможностью одновременного чтения / записи. 16

17 Правило выполнения сопоставлений Сопоставление выполняется согласно следующим правилам Неконкретизированная переменная сопоставима с любым объектом и этот объект становится значением переменной (« конкретизацией »). Если S переменная, а Т - произвольный объект, то ни сопоставимы и S приписывается значение T. Наоборот, если Т - переменная, а S - произвольный объект, то T приписывается значение S: «T конкретизируется значением S». Числа и атомы сопоставимы только с идентичными числами и атомами. Сопоставление структур : Структуры сопоставимы только, если они имеют одинаковый функтор одинаковое число компонентов, и соответствующие компоненты сопоставимы друг с другом. Если S и Т - структуры, то они сопоставимы, если S и Т имеют одинаковый главный функтор и все их соответствующие компоненты сопоставимы. Результирующая конкретизация определяется сопоставлением компонент. 17

18 Примеры сопоставлений Конкретизация переменных при сопоставлении. ?- data(M, D, 1992)=data(may, 3, Y). M = may D = 3 Y = 1992; Сопоставление идентичных атомов. ?- bob=bob. Сопоставление структур. ?- triangle(point(2, 5), A, point(B, 8)) = triangle(X, point(2, 8), point(5, 8)). A = point(2, 8); B = 5; X = point(2, 5); Сопоставление двух структур, содержащих неконкретизированные перемененные. ?- triangle(point(X, 5), point(X, 8), point(5, Z))= triangle(point(2, 5), point(Y, 8), point(5, A)). X = 2;Z = _G777; Y = 2; A = _G777 ; 18

19 Отрицательные сопоставления Итак, в Прологе операция X=Y кроме сравнения выполняет сопоставление двух термов, с конкретизацией переменных. Также в Прологе существует противоположный предикат X\=Y, который истинен только в случае, если терм X не сопоставим с термом Y. При использовании этого предиката в программе рекомендуется, чтобы все переменные в термах X и Y на момент согласования цели были конкретизированными, иначе результат будет зависеть от порядка целей в программе Пример : зависимость результата от порядка конкретизации. ?- X=a, Y=b, X\=Y. ?- X=a, X\=Y, Y=b. YesNo 19

20 Сопоставление выражений на идентичность Иногда требуется проверить точное равенство двух термов, включая соответствие расположения и идентичность неконкретизированных переменных. Это осуществляет ­ ся с помощью встроенного предиката равенства ( идентичности ) X==Y. Этот предикат не выполняет конкретизации переменных, неконкретизированная переменная не равна никакому объекту кроме другой неконкретизированной переменной, уже сцепленной с ней. Предикат равенства остается истинным, какое бы значение не получила в ходе дальнейшего вывода неконкретизированная переменная, входящая в терм. Пример : Проверка двух термов на равенство, без конкретизации. ?- f(2,3)==f(2,X). No Противоположный предикат X\==Y истинен только в случае, если терм X не равен терму Y Пример : Проверка двух термов на равенство, без конкретизации. ?- f(2,3)\==f(2,3). No 20

21 Выводы На основании изложенного можно сделать заключения : Удобство программ для чтения часто можно повысить с помощью записи операторной форме. Операции могут быть инфиксными, префиксными или постфиксными. Со знаками операций не связаны какие - либо операции над данными, если не считать некоторых частных случаев. Определения операций не определяют конкретные действия ; они лишь вводят новые обозначения. Знаки операций ( функторы ) применяются для соединения компонентов структур. Программист может определять свои собственные операции. В определении каждой операции необходимо указать : приоритет ( число в диапазоне от 1 до 1200), тип ( символьное представление отношения функтора и операндов ), знак ( может состоять из одного или нескольких символов ). Для сравнения двух термов на равенство выполняется операция сопоставления, выполняющая конкретизацию их переменных. 21