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

fail. show_records.

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

___________________________________________________________

В этой программе дополнительно присутствуют три правила. Каждое из них можно использовать в качестве компоненты внутренней цели. (В самой программе в целевом утверждении задействовано правило show_books. По желанию это правило можно заменить другим.)

Первое из правил есть show_misc_things :-

owns(Owner, misc_thing(Whatever)), write(Owner," ",Whatever), nl, fail.

Это правило осуществляет запрос: "Выдать все возможные предметы и их владельцев".

Второе правило есть show_books :-

owns(_,book(_,Title)), write(" ",Title), nl, fail.

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

Третье правило - это show_records :-

owns(Owner,record(_,Album,_)), write(" ",Owner," ",Album), nl, fail.

Перевод этого правила: "Выдать имена всех коллекционеров пластинок и названия альбомов из их коллекций."

Применение альтернативных доменов делает программу более "управляемой", а программирование - более эффективным.

*Упражнение

3.13. Рассмотрим запрос: Перечислить названия всех популярных (popular) музыкальных записей и имена их исполнителей. Постройте правило Пролога для реализации этого запроса, включите его в программу и запустите ее на счет. Что выдаст программа ?

3.4 Арифметика в Турбо-Прологе

Турбо-Пролог располагает двумя числовыми типами доменов: целыми и действительными числами. Четыре основные арифметические операции - это сложение, вычитание, умножение и деление. Для их реализации в Тур- бо-Прологе используются предикаты. Программа "Числа" (листинг 3.11)

66

показывает, как можно при помощи предикатов реализовать эти операции.

____________________________________________________________

Листинг 3.11

/* Программа: Числа */ /* Назначение: Демонстрация реализации арифметики. */

predicates add(integer,integer). substruct(integer,integer). multiply(integer,integer). divide(integer,integer). fadd(real,real). fsubstruct(real,real). fmultiply(real,real). fdivide(real,real).

67

____________________________________________________________

Правилами для реализации сложения, вычитания, умножения и деления целых чисел являются

add(X,Y):-

Z = X + Y, write("Sum = ", Z), nl. substruct(X,Y):-

Z = X - Y, write("Diff = ", Z), nl. multiply(X,Y):-

Z = X * Y, write("Pro = ", Z), nl. divide(X,Y):-

Z = X / Y, write("Quo = ", Z), nl.

а четырьмя правилами для реализации сложения, вычитания, умножения и деления действительных чисел -

fadd(P,Q):-

R = P + Q, write("Fsum = ",R), nl. fsubstruct(P,Q):-

R = P - Q, write("Fdiff = ",R), nl. fmultiply(P,Q):-

R = P * Q, write("Fpro = ",R), nl. fdivide(P,Q):-

R = P / Q, write("Fquo = ",R), nl.

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

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

*Упражнения

3.14.Предположим, что Вы хотите сложить четыре десятичных числа. Предикатом для выполнения этой операции служит

sum(real,real,real,real,real)

Напишите правило для сложения четырех чисел. Включите правило и предикат в программу "Числа".

3.15.Запустите эту модифицированную программу и задайте такую внешнюю цель:

sum(3.9, 4.6, 2.6, 9.7, Z).

Каков будет результат ?

3.5 Заключение

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

68

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

Были представлены способы формирования составных объектов с целью получения иерархических доменных структур. В довершение всего были рассмотрены правила работы с числовой информацией.

Глава 4. Повторение и рекурсия

4.1 Введение

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

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

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

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

4.2 Программирование повторяющихся операций

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

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

Вид правила, выполняющего повторение, следующий: repetitive_rule :- /* правило повторения */

<предикаты и правила>,

69

fail. /* неудача */

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

Вид правила, выполняющего рекурсию, следующий: recursive_rule :- /* правило рекурсии */

<предикаты и правила>, recursive_rule.

Заметьте, что последним правилом в теле данного правила является само правило recursive_rule. Правила рекурсии содержат в теле правила сами себя.

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

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

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

4.3 Повторение и откат

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

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

70