Операторная запись

Использование функторов для записи ариф. выражений не удобно, мы обычно в математике исп инфиксную запись 1+2*3.

Для того чтобы вычислить выражение, предст в виде дерева

+

/ \

1 *

/ \

2 3

Для того, чтобы это построить, нужно знать приоритеты операций и их ассоциативность.

Мы знаем, что 6-2-1=3 . Эта операция ассоциативна влево.

Операции могут быть ассоциативные влево, вправо и не ассоциативные.

Например, операция больше >

6 > 2 > 5 // запрещено

Мы можем определить свои операторы.

Для этого нужно задать приоритет и ассоциативность.

Задается спец.инструкцией :- up(приор,тип,список операторов). (ключ слово) (правило без головы)

:-op(500, yfx, [+,-]). // y слабее Xa

:- op(500, fx, [+,-,not]). // префиксный оператор, не ассоц.

:-op(400, yfx, [*,/,div]). //влево

Чем меньше знач приоритета тем сильнее операция связывает …

Операция взятия остатка от деления не ассоциативна, но более сильный приоритет

:-op(500, xfx, mod).

Теперь о типах оператора.

Yfx yfx

6 - 2 - 1

Ассоциативность зад выраж yfx

( 6 – 2 ) – 1

Xfx xfx

6 mod 2 mod 3 // ошибка

Префиксные унарные операции могут быть вида fx и fy.

--2 // запрещено

Если xfy то можно.

Есть и постфиксные операции вида xf yf

Возведение в квадрат к примеру

X²

Пусть есть факт

Студент(Иван).

:- op(200, xf, студент).

Иван студент.

*Факты как и структуры можно опис в операторной форме.

Операторы позв строить ближе к есстевст языку приложения.

Управление перебором

(по слайду)

Процедура просмотр перебирает возможные предложения так, чтобы найти нужное предложение для решения задачи.

Это универсальный алгоритм. Но в некоторых случаях требуется сократить число перебираемых вариантов.

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

Рассмотрим предикат, реал студент функцию

F арность 2.

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

Когда применится первое правило, то…

Уже после первой ветви видно, что искать больше нечего. Потому что правила альтернативны. Если выполнилось одно правило, то другие смотреть бесполезно.

Для того, чтобы сообщить пролог системе, что дальнейший перебор таких правил бесполезен, можно воспользоваться спец.оператором !, это оператор отсечения.

Такая программа будет эквивалента предыдущей программе, но отрицательные ответы она будет давать быстрее.

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

Оператор отсечения можно представить себе как оператор goto loop, который передает управление за пределы цикла просмотр для порождающей цели.

В нашей новой программе правила стали альтернативными. Учитывая это, программу можно сократить. Если попали во 2, то оно было не удачным… Можно и последнюю проверку тоже исключить, она будет как факт уже. Мы еще больше повысили эффективность программы.

Оператор отсечения позволяет запрограммировать команты похожие на if then else.

ite :- p ! q

ite:- r

ite = if p then q else r

Оператор отсечения, как и goto в паскале нужно исп осторожно, потому что применяя его можно утратить декларативный смысл программы.

Утратила свой декларативный смысл!!!

Если убрать !

Если

f(1,Y).

То получим все три ответа

Y=0; y=2; y=4

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

*Уточнения.

1) исключаются из рассмотрения все расположенные ниже предложения, сопоставимые с порождающей целью.

2) конъюнкция подцелей, стоящих до предиката отсечения, P, Q, R, фиксируются, для них больше сопоставления не ищутся.

Отсечение не запрещает многократно согласовывать цели, стоящие после него. Цели S,T,U будут работать в обычном режиме.

Рассмотрим примеры применения оператора отсечения.

Предикат, проверяет принадлежность элемента списку. Этот предикат дважды ответит ДА.

Как быть чтобы был один ответ все время?

Рассмотрим еще один пример, в котором напишем процедуру слияния упорядоченных списков.

?- merge ([1,3,5], [2,3], X).

X = [1,2,3,4,5]

Лекция

*(Тут можно не ставить операторы отсечения, но они повышают эффективность программы)

*(если поставили оператор отсечения то проверку на неравенство можно не ставить потому, что имеем случай когда неудачно прошло сопоставление с головой исходного списка, но исключение этой проверки исключает декларативный смысл программы)

?- Delete([a,b,a,c], a, X).

1. Такой предикат легко определить рекурсивно. Если голова исходного списка совпадает с заданным элементом, то результатом будет результат удаления этого элемента из хвоста.

2 случай. Если не совпадает голова списка….(иначе), результат будет иметь голову, такую же как голова исходного списка, а хвост получится удалением заданного элемента из хвоста исходного списка.

3 базовый случай. Если список пуст, (иначе) то результатом будет пустой список.

…

X = [dsfdsfd];

X = [a,b,a,c].

Отрицание в прологе

(вспомним предикат “добавление элемента без дублирования”, была формулировка: если элемент принадлежит исходному списку, то результатом будет …, а иначе другой вариант)

Иначе – как отрицание.

*Когда есть отрицание и для его реализации исп оператор отсечения, то получается предикат, который без отсечения реализовать нельзя.

! Оператор отсечения расширяет возможности пролога.

Есть особенность отрицательных предложений Пролога: эти предложения исп предположение замкнутости мира. В таких предложениях предполагается, что все то, что задано в программе фактами и правилами истинно, а что не задано – ложно.

В прологе, если предложения нет – то ложная информация.

Для определения отрицательных предложений есть встроенный предикат not. (not / 1). Этот предикат реализуется с помощью оператора отсечения и встроенного предиката Fail /0.

Fail – выполнение всегда неудачно.

Как определяется предикат not.

not(P) :- P ! fail. %здесь выполняется

not(P). % как аргумент

*Мы можем пользоваться предикатом not, можно, зная его определения использовать схему выше.

(Из области ИИ)

Построение плана на Прологе

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

Задача.

В комнате в центре к потолку подвешет банан. У окна в этой команте стоит ящик. Обезьяна взодит в команту и ее цель завладеть бананом.

Этапы решения.

1. Определить множество возможных состояний. Каждое состояние будет иметь 4 компонента.

1ый – положение обезьяны по горизонтали(где она в команте находится).

2ой – положение обезьяны по вертикали(1 она может быть на полу(внизу), 2 и на ящике(вверху)).

3ий – положение ящика(любое в комнате).

4ый – цель, обладание бананом.

Эти 4 компонента объединяем в одну структуру state/4.

Далее нужно описать возможные переходы. Их мы будем перечислять в порядке их предпочтения. Те, что ближе к цели, мы будем…

1ый переход. Если обезьяна находится в центре команты, на ящике, и у нее нет банана, то она может его схватить. 4ый компонент – имеет или нет банан.

Схватить банан

step(state(middle,up,middle,hasno),

take,

state(middle,up,middle,has)).

2.Влезть на ящик, если обезьяна и ящик в одном и том же месте, обезьяна на полу, она может оказаться на ящике.

Влезть на ящик

step(state(P,down,P,H),

up,

state(P,up,P,H)).

3. Если обезьяна и ящик находятся в одном месте, обезьяна на полу(по вертикали внизу), то обезьяна может переместиться с этим ящик в любую точку комнаты.

В начале шага P1 у обезьяны и P1 у ящика, они в одном месте. Об на полу. Moveto – передвинуть, сложный терм, структура. Откуда куда двигать. Получаем новое состояние. В этом правиле заложено движение Об туда, куда она захочет вместе с ящиком.

Передвинуть ящик на новое место

step(state(P1, down,P1,H),

moveto(P1,P2),

state(P2,down,P2,H)).

4. Обезьяна может перейти на новое место, если она стоит на полу.

Перейти на новое место

step(state(P1,down,B,H),

goto(P1,P2),

state(P2,down,B,H)).

Структура goto (перейти), из т.1 в т.2

Step. Первый аргумент – состояние в начале шага. Второй – описание этого шага. Третий – состояние после выполнения шага.

Теперь задача в том, чтобы построить план. Для построения плана нуэно задать прежде всего цель, которую требуется достичь. (Ниже)

canGet(state( _, _, _,has),X,Y) :- reverse(X,Y).

canGet(S,Prot,X) :- step(S,M,SS),canGet(SS,[M|Prot],X).

go(X) :- canGet(state(door,down,window,hasno),[], X).

?- go(X).

X = [goto(door, window), moveto(window,

middle), up, take]

*…3 остальных компонента безразличны.

Теперь нужно задать исходное состояние

Перебор возможных действий мы будет вести предикатом CanGet который рекурсивно будет пробовать применить заданные действия.

* В этом алгоритме результат получается за счет того, что описание шагов идет в порядке предпочтения. Если порядок шагов изменить, то алгоритм может пойти в бесконечный цикл. В системах построения плана важное значение имеет направление движения в пространстве поиска.

Лекция 10.03.12