Отсечение и способы его использ-я.

Структура логической программы.

1. Директива компилятора (необязат-й раздел)

2. CONSTANTS- раздел описания констант. имя константы должно быть идентифик-м, тоесть может сост-ть из англ-х букв, цифр и не может нач-ся с цифры. <имя конст>=<знач-е>

3. DOMAINS- раздел опис-я доменов. явл-ся аналогом раздела опис-я типов данных в императивных яз-х прогр-я. в прологе имеются стандартные домены.

4. DATABASE- раздел опис-я предикатов внутренней ?

5. PREDICATES- разд. опис-я предикатов. аналог в традиц-х языках прогр-я- раздел опис-я проц-р и функций.

6. CLAUSES- разд. опис-я предлож-й. можно считать осн-м разд-м прогр-мы, так как в нем сод-ся факты и правила,реализ-е ползоват-е предикаты. все пред-ты,кот-е использ-ся в этом разделе и не явл-ся стандартными, должны быт описаны в разделе описания пред-в.

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

7. GOAL- разд опис-я внутр цели. если гоал присутствует прогр-ме, то предполаг-ся,что в прогр вычисл-ся внутр-яя цель, тоесть запрос формируется непосредственно в тексте прогр.

 

Логические переменные, подст-ки и типы.

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

переменная начинается с прописной буквы. ПРИМЕР:

нравится(василий,ирина).

?-нравится(ирина,х)

х=василий.

 

Описание доменов и предикатов.

DOMAINS- раздел опис-я доменов. явл-ся аналогом раздела опис-я типов данных в императивных яз-х прогр-я. в прологе имеются стандартные домены.пример:

domains

i=integer

если необходимо описать список определенного типа,около имени домена ставится *

 

PREDICATES- разд. опис-я предикатов. аналог в традиц-х языках прогр-я- раздел опис-я проц-р и функций.пример:

predicates

mother(string, string).

в прологе имеются стандартные встроенные предикаты, которые не нужно опис-ть в этом разделе

 

Использование списков в языке пролог.

[‘a’,’b’,’c’]- список с тремя элем-ми типа char. []-пустой сп-к. для того,чтобы предикат исп-ся в качестве аргумента сп-к соотв-го типа необходимо после описания типа данных указать *

domains

i=integer

predicates

s(i,i) где i- список.

Список предст. собой структуру данных, которую можно определить след-м образом: [head/tail]

[1,2,3]=[1[2,3]]=[1/2/[3]]

для того, чтобы орг-ть работу сп-ка необх-мо построить рекурс-ю процедуру, при этом надо задать базис рекурсии(пр-ло или факт,определяющий, что нужно делат с пустым сп-ком), а также рекурсивное правило, установившее порядок перехода от обр-ки всего списка к обр-ке хвоста.ПРИМЕР: создать предикат, позв-й вычислить длину списка(кол-во элементов). восп-ся след-ми фактами:1)в пустом списке кол-во эл-в-0. 2)кол-во элем-в списка, предст-го в виде объед-я первого эл-та и хвоста равно кол-ву эл-в хвоста, увел-му на 1

length([]-список,0)

length(l_/T],l):-length(T,l_T),

l=l_T+1/

goal

length(1[1,2,3],x).

length([x]) x=0

1)T:=[2,3]

2)T:=[3]

3)T:=[]

 

Арифметика в языке лог. прогр-я

пролог-система имеет в кач-ве встроенных ф-ций базовые арифм. операции: +,-,*…, так же <>,>,<,=…

реализация:

domains: i=integer, r=real.

predicates: add(i,i,i) sub(i,i,i) mul(i,i,i) div(i,i,i) fadd(r,r,r) fsub(r,r,r) fmul(r,r,r) fdiv(r,r,r)

clauses: add(x,y,z):-z=x+y. mul(x,y,z):-z=x*y. fadd(x,y,z):-z=x+y. …дальше по аналогии.

goal

add(3,2,z)

 

Отсечение и способы его использ-я.

Анонимная перем-я исп-ся тогда,когда конкретное значение перем-й несущественно для данного утвержд-я. обозн-ся «_». ПРИМЕР: создать предикат, кот будет нах-ть максимум из двух чисел.

вариант такой шлачный без отсечения фу:

clauses: max(x,y,x):-x>y max(x,y,y):-x<=y

goal:max(3,2,z) max(5,6,z)

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

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

а вот и задачка с использованием отсечения:

clauses: max(x,y,x):-x>y,!. max(_,y,y):-x<=y.

goal:max(3,2,z) max(5,6,z)

в первом случае вып-ся только первое предл-е,во втором случае первое предл-е не выполнено,следоват-но переходит ко второму.

ЗЕЛЕНОЕ отсечение в том случае, если его убрать из программы прогр полностью сохранит свою функцион-ть и рез-т выполн-я не изменится.

КРАСНОЕ в обратном случае: программа вып-ся с ошибкой