Правило декларирования доменов для составных объектов

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

vladeet(vladimir, schet (123456789, 1000000)).

vladeet(vladimir, kvartira("RF","Tula", "Pervomayskaya, 8- 814").

vladeet(vladimir, kvartira("Belarus","Minsk", "Pobedy, 13 - 21").

vladeet(vladimir, kvartira("US","New York", "17 Street, 9- 11").

vladeet(vladimir, boat).

vladeet(vladimir, dog("Lord")).

В том случае, если мы даем запрос в виде: vladeet(vladimir, X), переменная Х может оказаться связанной с различными объектами: счет, квартира, яхта, собака и т.д. Кроме того, мы не можем однозначно описать предикат vladeet, поскольку описание vladeet(symbol, symbol) не будет всегда верно. Вместо этого можно дать иное определение этого предиката: vladeet (name, sobstvennost), а домен sobstvennost в разделе DOMAINS можно описать так:

DOMAINS

sobstvennost =

schet(nomer, summa);

kvartira(strana, gorod, ulitsa_dom);

boat;

dog(name)

strana, gorod, ulitsa_dom, name = symbol

nomer, summa = unsigned

При этом boat – функтор без присоединенных к нему аргументов, а разделитель "; " обозначает логическую связку " или ".

DOMAINS

sobstvennost =

schet(nomer, summa);

kvartira(strana, gorod, ulitsa_dom);

boat;

dog (name)

strana, gorod, ulitsa_dom, name = symbol

nomer = unsigned

summa = real

PREDICATES

vladeet(name, sobstvennost)

CLAUSES

vladeet(vladimir,schet(123456789, 1000000)).

vladeet(vladimir,kvartira("RF","Tula","Pervomayskaya, 8- 814")).

vladeet(vladimir,kvartira("Belarus","Minsk","Pobedy, 13 - 21")).

vladeet(vladimir,kvartira("US","New York", "17 Street, 9- 11")).

vladeet(vladimir,boat).

vladeet(vladimir,dog("Lord")).

GOAL

vladeet(vladimir, X).

При этом выполнение будет иметь вид:

X = schet(123456789,1000000)

X = kvartira("RF","Tula","Pervomayskaya, 8- 814")

X = kvartira("Belarus","Minsk","Pobedy, 13 - 21")

X = kvartira("US","New York","17 Street, 9- 11")

X = boat

X = dog("Lord")

6 Solutions

После обсуждения примера мы можем приступить к формулировке правила объявления доменов для составных объектов в общем виде.

В разделе domains необходимо дать описание нового домена в виде:

nazvanie_domena = alternative1(D1 Name, D2 Name, …);

alternative2(D3 Name, D4 Name, …);

…

alternative# – допустимые, но различные функторы;

D#– стандартные, или объявленные в программе домены;

Name – комментарии.

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

Если функтор не имеет аргументов, то можно записать в программе alternativeN или alternativeN().

Повтор и рекурсия

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

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

Рекурсивная процедура – это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура), могла после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно. Стек на платформе DOS ограничен 64 Kb, на платформе Windows размеры стека не ограничены, но есть ряд других существенных проблем.

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

Пример 3. (слайд 9)

Составить программу, в которой вычисляется число Фибоначчи по его порядковому номеру.

DOMAINS

arg= integer

rez = unsigned

PREDICATES

fibonachchi (arg, rez)

clauses

fibonachchi(0,1).

fibonachchi(1,1).

fibonachchi(N,X):-

PR=N-1, PRR=N-2,

fibonachchi(PR,FPR),

fibonachchi(PRR,FPRR),

X=FPR+FPRR.

GOAL

write("Vvedite nomer chisla \t"),

readint(NOMER),

fibonachchi(NOMER, CHISLO),

writef("\n Nomer %u Chislo = %u",NOMER, CHISLO),

readchar(_).

Данный пример является яркой иллюстрацией обычной рекурсии. n

Пример 4 (слайд 10).

Составить программу вычисления наибольшего общего делителя двух натуральных чисел.

PREDICATES

nod(unsigned,unsigned,unsigned)

CLAUSES

nod(X,0,R):-R=X.

nod(X,Y,R):-

T=X mod Y,

nod(Y,T, R).

GOAL

nod(3345768,677424, D), write("nod=",D), readchar(_).

Этот пример служит демонстрацией хвостовой рекурсии. Обратите внимание на то, что рекурсивное обращение к nod(Y,T,R)является последней подцелью предложения nod(X,Y,R), а выше в этом предложении не было точек возврата. Эти два условия являются основными для распознавания хвостовой рекурсии. Пример 3 не является примером хвостовой рекурсии, поскольку в нем нарушены оба условия.