Материал: Терёхин В. В. Turbo Prolog

Задача программы определить, в какую игру одновременно играют Джон и Том.

Утверждение цели следующее: plays(john,G),plays(tom,G).

Заметьте, что эта цель есть связка двух подцелей. Каждая подцель содержит переменную G. Задача заключается в нахождении значения для G, удовлетворяющего обеим подцелям.

Чтобы вычислить первую подцель plays(john,G), Турбо-Пролог ищет в базе данных сопоставимое утверждение. Первый объект утверждения plays(john, soccer) сопоставим с первым объектом первой подцели, так что подцель успешно вычисляется и переменная G получает значение soccer. Существуют другие утверждения для plays, которые могут быть использованы для вычисления этой же подцели. Поэтому Турбо-Пролог должен сохранить след этих утверждений на случай неуспешного вычисления второй подцели со значением G равным soccer. Для этого внутренние унификационные подпрограммы устанавливают указатель отката на точку, с которой могут быть продолжены усилия по вычислению первой подцели.

Теперь Турбо-Пролог пытается вычислить вторую подцель. Так как G имеет значение soccer, то эта подцель есть plays(tom, soccer). ТурбоПролог просматривает базу данных в поиске утверждения, сопоставимого с этой подцелью. Сопоставимых утверждений нет, поэтому подцель неуспешна.

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

Турбо-Пролог пытается вычислить вторую подцель plays(tom,volleyball). Во время этой попытки удается найти сопоставимое утверждение. Присвоение переменной G значения volleyball приводит к успеху. Обе подцели удовлетворены. Больше подцелей нет, поэтому вся исходная цель оказывается успешно вычисленной.

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

71

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

цели есть G=volleyball.

Откат является автоматическим инициируемым системой процессом, если не используются средства управления им. Для управления процессом отката в Турбо-Прологе предусмотрены два встроенных предиката fail (неудача) и cut (отсечение). Использование этих предикатов рассматривается ниже в разделах, посвященных методу Отката После Неудачи (ОПН) и

методу Отсечения и Отката (ОО).

Во время выполнения программы Турбо-Пролог создает необходимые внутренние структуры данных (такие как списки и деревья) для выполнения обработки программы. Эта обработка включает такие процессы как поиск, сопоставление с образцом, создание экземпляра, означивание и освобождение переменных, откаты. Вы должны вспомнить сказанное в главе 2 о том, что эти процессы выполняются внутренними подсистемами языка, которые называются внутренними унификационными подпрограммами. Во время выполнения программы эти подпрограммы всегда находятся в рабочем состоянии во время выполнения программы. Вы встретите много ссылок на них при объяснении работы элементов программ.

4.4 Методы повторения

Вспомните, что оператор внешней цели побуждает переменные получать все возможные значения одно вслед за другим. (Вы можете прочитать об этом в гл. 2 и 3). Если полученных значений не много (скажем меньше 10), то выдача их на экран компьютера дело несложное. Но если их число велико, то текст на экране будет быстро меняться. Поэтому прочитать его очень трудно или даже невозможно.

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

4.4.1 Метод отката после неудачи

В данном разделе вы увидите, как метод отката после неудачи (ОПН) может быть использован для управления вычислением внутренней цели при поиске всех возможных ее решений. Метод ОПН использует предикат fail. Программа о городах (листинг 4.1) демонстрирует использование этого предиката.

Назначение программы о городах состоит в перечислении названий десяти городов США. Утверждение первой подцели выдает заголовок Here are the cities (Это названия городов). Вторая подцель является правилом

72

для перечисления названий городов. Подправило cities(City) означивает переменную City (город) названием города. Затем это значение выдается на экран. Предикат fail вызывает откат к следующему утверждению, которое может обеспечить вычисление цели.

Листинг 4.1

__________________________________________________________

domains

name=symbol

predicates

cities(name) show_cities

goal

write("Here are the cities:"),nl show_cities

clauses cities("ANN ARBOR "). cities("ATLANTA"). cities("NEW HAVEN").

cities("INDIANAPOLIS"). cities("BOSTON"). cities("MESA"). cities("MINEAPOLIS"). cities("SAN ANTONIO"). cities("SAN DIEGO"). cities("TAMPA").

show_cities :- cities(City),

write(" ", City), nl, fail.

_____________________________________________________

Из листинга 4.1 видим, что имеется 10 предикатов, каждый из которых является альтернативным утверждением для предиката cities(name). Во время попытки вычислить цель, внутренние унификационные подпрограммы означивают переменную City объектом первого утверждения, который есть ANN ARBOR (название города в США). Так как существует следующее утверждение, которое может обеспечить вычисление подцели cities(сity), то

73

указатель отката помещается в следующую точку. Значение ANN ARBOR выводится на экран.

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

*Упражнения

4.1.Измените программу о городах таким образом, что бы результатом была выдача на экран целых чисел 66, 46, 32, 93, 44, 98, 37, 16, 12. Выдавайте только одно число на строке.

4.2.Какие необходимы модификации для выдачи целых чисел на одну строку так, что бы они были разделены двумя пробелами?

Программа о городах показывает, что использование метода ОПН позволяет извлекать данные из каждого утверждения базы данных. Если в программе содержатся утверждения для 10 вариантов, то результат так же содержит 10 строк. Данные извлекаются из каждого утверждения, так как каждый вариант удовлетворяет подцели cities(сity). Но добавив дополнительные условия на значения объектов для одной или более переменных предиката, можно извлекать данные только из определенных утверждений. Программа о служащих (листинг 4.2) демонстрирует этот метод.

Листинг 4.2

_______________________________________________________________

predicates employee(name,sex,department,pay_rate) show_male_part_time show_data_proc_dept

goal

write("Служащие мужского пола с почасовой оплатой"), nl, nl, show_male_part_time.

74

employee("Sheila Burton ","F","ADVE",5.00). employee("Kelly Smith ","F","ACCT",5.00). employee("Diana Prince ","F","DATA",5.00).

/* Правило для генерации списка служащих мужского пола */ show_male_part_time :-

employee(Name, "M", Dept, Pay_rate), write(Name, Dept, "$", Pay_rate),

nl,

fail.

/* Правило для генерации списка служащих отдела обработки данных */ show_data_proc_dept :-

employee(Name, _, "DATA", Pay_rate), write(Name, "$", Pay_rate),

nl,

fail.

___________________________________________________________

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

employee(name, sex, department, pay_rate)

/* служащий(имя, пол, отдел, почасовая_оплата) */

Следующее правило выдает содержимое всей базы данных: show_all_part_time_employees :- /* выдать_служаших */

employee(Name,Sex,Dept,Pay_rate), write(Name, " ", Sex, " ", Dept, " ", Pay_rate), nl,

fail.

Переменные Name (имя), Sex (пол), Dept (отдел), Pay_rate (почасовая оплата) не означены, и следовательно, все они могут получить значения. Если бы это правило являлось целью программы, то результатом выполнения этой программы был бы список всех служащих с неполным рабочим днем.

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

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

show_male_part_time :-

employee(Name,"M", Dept, Pay_rate), write(Name,Dept, "$",Pay_rate),

nl, fail.

75