Основы программирования на языке Turbo Prolog

Goal

   sister(ann,X),write(”Ann — сестра ”,X), nl

Вначале будет согласован предикат sister и переменная X означена значением pat, затем встроенный предикат write напечатает Ann — сестра pat, затем предикат nl переведет строку, и на этом выполнение программы завершится.

Рассмотрим подробно применение дизъюнкции в качестве связки между подцелями.

Пусть дизъюнкция разделяет подцели в теле правила:

ancestor(X,Y):-

   pearent(X,Y);

   pearent(X,Z), ancestor(Z,Y).

Конъюнкция связывает сильнее, чем дизъюнкция, поэтому это равносильно

  pearent(X,Y);

(pearent(X,Z), ancestor(Z,Y))

и, в свою очередь, равносильно двум правилам:

ancestor(X,Y):-

   pearent(X,Y).

ancestor(X,Y):-

   pearent(X,Z), ancestor(Z,Y).

Если дизъюнкция разделяет подцели внешней цели:

Goal: sister(ann,X); pearent(X,ann)

то это будет аналогично последовательному выполнению двух разных запросов: вначале система найдет всех, для кого ann сестра, затем родителей ann.

Если бы предыдущий запрос был переформулирован как внутренняя цель (с добавлением предикатов write), то система не стала бы согласовывать цель о родителях ann, так как остановка произошла поcле первого успешного согласования подцели sister.

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

3. ВСТРОЕННЫЙ ПРЕДИКАТ FAIL

Предикат fail вызывает неудачное завершение правила, в результате чего внутренние унификационные процедуры выполняют возврат в предыдущую подцель и пытаются найти для нее другое решение.

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

Goal

   sister(ann,X),write(“Ann — сестра “,X),

   nl, fail

Дойдя до предиката fail, система будет осуществлять возврат к предикату sister и будет находить для Х новое значение. В конечном итоге цель так и не будет согласована, но при попытках ее доказать будут напечатаны все, для кого ann — сестра.

Для того, чтобы заставить систему выдавать еще и обоих родителей ann, запрос нужно составить так:

Goal

(sister(ann,X), write(”Ann- сестра ”,X), nl;

  pearent(X,ann), write(X,” — родитель Ann”)),

fail

Или так:

Goal

sister(ann,X), write(”Ann-сестра ”,X),nl,fail;

 pearent(X,ann), fail

4. СОКРАЩЕННЫЕ ВАРИАНТЫ ВНУТРЕННИХ  ЗАПРОСОВ

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

Goal

who_is_the_sister ,fail

who_is_the_sister:-

               sister(X,Y),

               write(X,”- сестра ”,Y),nl.

Для определения всех родственников девушки составим запрос:

Goal

   family,fail

И следующие правила:

family:-

   write(” Tell me girl, please ”),nl,

   readln(X),

   family_of_girl(X).

family_of_girl(Girl):-       % сестры Girl

   sister(X, Girl),

   write(X,”- сестра”), nl.

family_of_girl(Girl):-       % мать Girl

   mother(X,Girl),

   write(X,”- мать”),nl.

Аналогично составляются правила для определения братьев и отца.

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

Упражнение 2.1.

Модифицируйте программу «Родственники» из примера 1.2 главы 1 так, чтобы печатались все родственники девушки по имени Бэт.

5. Использование в запросах анонимных  переменных

Пусть потребовалось узнать имена всех лиц, имеющих сестер, причем имена сестер нас не интересуют.

Goal

write(”Имеют сестер: ”),nl, sister(_,X),

 write(X), nl, fail.

Знак подчеркивания обозначает анонимную переменную, чье значение нас не интересует. Если в одном предикате имеется несколько знаков подчеркивания, то каждый обозначает свою анонимную переменную, то есть все они различны.

6. МЕХАНИЗМ ВОЗВРАТА

Турбо-Пролог пытается вычислить цель при помощи сопоставления цели с утверждениями базы данных. Сопоставление выполняется СЛЕВА НАПРАВО, причем, в процессе доказательства основной цели, Турбо-Пролог сам генерирует подцели. Некоторые сопоставления подцелей с какими-то утверждениями, вероятно, будут неуспешными.

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

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

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

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

/* Программа 2.1 «РОДСТВЕННИКИ».

Назначение: демонстрация механизма возврата */

domains

   name=symbol

 

predicates

   pearent(name,name)

   feminin(name)

   male(name)

   sister(name,name)

 

clauses

       pearent(mary,bob).  

(2)    pearent(mary,beth).

(1)    pearent(tom,beth).

(4)(5) pearent(tom,bob).

(6)    pearent(tom,liz).

(7)    pearent(bob,ann).

       pearent(bob,pat).

       pearent(pat,jim).

 

       feminin(mary).      

       feminin(beth).

(3)    feminin(liz).

       feminin(ann).

       feminin(pat).

       male(tom).         

       male(bob).

       male(jim).

 

       sister(X,Y):-         

          pearent(Z,X),

          pearent(Z,Y),

          feminin(X),

          X<>Y .   

/*          Конец программы                   */

Будем вычислять цель

Goal: sister(beth,X)

Первым правилом, сопоставимым с нашей целью, является правило sister(X,Y). Так как других утверждений для предиката sister нет, то нет и альтернативных путей. Поэтому указатель возврата не ставится, а система генерирует первую подцель pearent(Z,beth). Эта подцель успешно согласуется с фактом pearent(mary,beth). Так как для предиката pearent есть другие утверждения, то указатель возврата (1) устанавливается на факт, следующий за фактом pearent(mary,beth).

Затем система генерирует подцель pearent(mary,Y) и начинает просматривать сначала всю базу данных. Первым утверждением, согласующим данную подцель, будет pearent(mary,bob). Указатель возврата (2) при этом устанавливается на следующее за ним утверждение pearent(mary,beth). Подцели feminin(beth) и beth<>bob успешно согласуются, цель вычисляется со значением X=bob.

Так как для feminin есть другие утверждения, то указатель возврата (3) устанавливается на feminin(liz) и к нему возвращается система, пытаясь передоказать feminin(beth). Передоказать его не удается, указатель (3) снимается, а система возвращается на указатель (2). X означивается beth, успешно доказывается feminin(beth), но beth<>beth неуспешно.Так как для pearent(mary,_) больше утверждений нет, то возвращаемся на (1). Цель pearent(tom,beth) успешно согласуется, на следующее утверждение устанавливается указатель (4), система генерирует подцель pearent(tom,Y).

Эта цель успешно доказывается с Y=beth, указатель (5) устанавливается на pearent(tom,bob), и к нему мы возвращаемся, потерпев неудачу при доказательстве beth<>beth. (5) снимается, на pearent(tom,liz) устанавливается (6). Так как beth<>bob цель успешно доказывается (получаем повторно X=bob) и возвращаемся на (6). Y получает значение liz, указатель (7) устанавливается на pearent(bob,ann). Успешно получив решение X=liz, возвращаемся на (7), потерпев неудачу, возвращаемся еще на шаг назад — на (4). bob не согласуется с beth, больше указателей нет, выходим из системы.

ГЛАВА 3. ТИПЫ ДАННЫХ И АРИФМЕТИКА Turbo Prolog

1. СТАНДАРТНЫЕ ТИПЫ ДАННЫХ

Турбо-Пролог требует указания типов для всех аргументов (объектов) каждого предиката программы. В разделе predicates НУЖНО ОПИСАТЬ ТИП ОБЪЕКТОВ ДЛЯ КАЖДОГО ПРЕДИКАТА.

Турбо-Пролог позволяет конструировать свои собственные типы объектов из базисных типов доменов. Рассмотрим вначале базисные типы доменов.

Турбо-Пролог имеет 6 встроенных типов доменов: СИМВОЛЫ, ЦЕЛЫЕ ЧИСЛА, ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА, СТРОКИ, СИМВОЛИЧЕСКИЕ ИМЕНА И ФАЙЛЫ. Тип каждого из доменов должен быть объявлен в разделе программы domains.

В таблице 3.1 приведены все 6 стандартных типов доменов Турбо-Пролога.

Таблица 3.1.

Тип данных	Ключевое слово	Диапазон значений	Примеры использования
Символы	сhar	Все возможные символы	'b', '#', '%', 'B', '\13'
Целые числа	integer	От —32768 до 32767	-84,2349
Действи-тельные числа	real	от +1Е-307 до +1Е308	-42769, 093, 1.25Е23, 5.15Е-9
Строки	string	Последовательность символов (не более 250)	«PROLOG», «123», «Мзри»
Символи-ческие имена	symbol	1. Последовательность букв, цифр и подчерков; первый символ — строчная буква 2. Последовательность любых символов, заключенная в кавычки	mary, answer_2; «Агата Кристи», «3.1412»
Файлы	file	Допустимое в DOS имя файла	BIRDS.DBA, mail.txt

Операторы ввода:

readchar(X) readint(X) readreal(X) readln(X), где X — переменная соответствующего типа; в операторе readln(X) X может быть string или symbol.

Кроме того, оператор readterm(my_domain,X) позволяет ввести переменную уже описанного в разделе domains типа my_domain.

2. СТРУКТУРЫ, ПРОСТЫЕ И СОСТАВНЫЕ

Объекты утверждений представляют собой данные, тип же простых объектов ограничен 6 базисными типами. Рассмотрим такой пример утверждения:

collection(smith,"Использование  Турбо-Пролога", 
          "Ц.Ин, Д.Соломон", "Мир", "1993").

Его объекты принадлежат к базисным типам доменов:

predicates

  collection(symbol,symbol,symbol,symbol,integer)

Первый объект smith имеет простую структуру: он представляет сам себя. То же можно сказать и про остальные объекты.

Любой объект, представляющий сам себя, называется простым объектом.

Аналогично, СТРУКТУРА, СОСТОЯЩАЯ ИЗ ПРОСТЫХ ОБЪЕКТОВ, НАЗЫВАЕТСЯ ПРОСТОЙ СТРУКТУРОЙ.

Можно было бы не пользоваться в описании предиката collection базисными типами, а описать свои:

domains

   name,title,author,publisher = symbol

   year = integer

predicates

   collection(name,title,author,publisher,year)

В этом описании 4 последних объекта обозначают атрибуты книги. Правило, которое оперирует с персональными библиотеками, рассматривает эти 4 последних объекта как независимые сущности. Чтобы сделать код программы более простым, а запись предиката collection более компактной, соберем эти объекты в структуру с названием book:

collection(smith, book("Alice in Wonderland", 
"Lewis Carroll", "The New American library", 1960)).

В данном примере book является составным объектом. Терм book в этом утверждении называется функтором. Функтор составного объекта есть на самом деле предикат, хотя он и вставлен внутрь другого предиката. главным функтором здесь является предикат collection.

Объект, представляющий другой объект или совокупность объектов, называется составным объектом.

Записанные же таким образом предикаты collection называются составными структурами, поскольку они скомпонованы из составных объектов.

Турбо-Пролог позволяет объявлять составные объекты (доменные структуры) в разделе domains. Функтор структуры personal_library имеет имя book. Описание таково:

domains

   personal_library = book(title, author,

                           publisher,  year)

   name,title,author,publisher = symbol

   year = integer

Предикат, использующий эту структуру, определяется так:

predicates

   collection(name, personal_library)

Описание содержит два имени объектов. Первое имя относится к обычному объекту, второе — к структуре из нескольких объектов.

Структура обеспечивает средство сортировки объектов по категориям. ССЫЛКИ НА ДОМЕННУЮ СТРУКТУРУ ОСУЩЕСТВЛЯЮТСЯ ПО ИМЕНИ ФУНКТОРА (в нашем примере — по имени book).

3. СТРУКТУРНЫЕ ДИАГРАММЫ

Диаграммы — средство анализа и наглядного представления составных структур. На рис. 3.1 показана доменная структурная диаграмма (ДСД) программы 3.1.

рис 3.1

Имя домена здесь personal_library, имя структуры — book. Структура содержит четыре объекта: title, author, publisher и year.

рис 3.2

Отметим, что ДСД является компонентой ПСД. book здесь является функтором. Как видно из рисунка, ПСД программы содержит 2 уровня.

Эти диаграммы хорошо демонстрируют организацию доменов и предикатов. ДСД и ПСД являются удобным средством при разработке и документировании программ Турбо-Пролога. Они также могут оказать помощь при написании эффективных правил.

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

4. ИСПОЛЬЗОВАНИЕ В ЗАПРОСАХ АНОНИМНЫХ  ПЕРЕМЕННЫХ

/* Программа 3.1 «Библиотека».  Назначение:   */

/* демонстрация  одноуровневого                */