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

4.8. Измените программу Эхо так, чтобы она воспринимала целые числа с клавиатуры и дублировала их на экран. Напишите правило так, чтобы программа завершалась при вводе числа 0 (нуль). (Встроенный предикат Турбо-Пролога для считывания целых чисел с клавиатуры - это

readin(Number)

Здесь Number - имя переменной для целых чисел).

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

readreal(Number)

Здесь Number - имя переменной для десятичных чисел). Правило для сложения двух десятичных чисел может быть записано в виде:

sum(X,Y,Z) :- Z = X+Y.

Здесь X, Y, Z - имена переменных для десятичных чисел.

4.5 Методы организации рекурсии

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

4.5.1 Простая рекурсия

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

Пример правила рекурсии: write_srting :- /* выдать строку */

write("МЫ - ЭТО ВЕСЬ МИР"), nl,

write_string.

Это правило состоит из трех компонент. Первые две выдают строку "МЫ - ЭТО ВЕСЬ МИР" и переводят курсор на начало следующей строки экрана. Третья - это само правило. Так как оно содержит само себя, то чтобы быть успешным, правило write_string должно удовлетворять само себе. Это приводит снова к вызову операции выдачи на экран строки и смещение курсора на начало новой строки экрана. Процесс продолжается бесконечно и в результате строки выдается на экран бесконечное число раз.

86

Однако в случае возникновения бесконечной рекурсии число элементов данных, используемых рекурсивным процессом, непрерывно растет и в некоторый момент стек переполнится. На экране появится сообщение об ошибке. Возникновение переполнения во время выполнения программы для пользователя нежелательно, так как в результате могут оказаться утерянными существенные данные. Избегать подобные ситуации можно увеличением размеров стека, для чего служит опция Miscellaneous settings (прочие установки параметров) в меню Setup (установка).

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

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

Программа "Вернись" (листинг 4.7) демонстрирует простое правило рекурсии, в которое включено условие выхода.

Листинг 4.7

________________________________________________________

domains

Char_data = char

predicates write_prompt read_a_character

goal

write_prompt, read_a_character.

clauses write_prompt :-

write("Пожалуйста, введите символы."), nl, nl, write("Для завершения введите # "), nl, nl.

read_a_character :- readchar(Char_data), Char_data <> '#',

87

write(Char_data), read_a_character.

_______________________________________________________

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

read_a_character :- readchar(Char_data), Char_data <> '#', write(Char_data), read_a_character.

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

*Упражнение

4.10.Запустите программу Вернись. После приглашения Goal: введите последовательность символов:

The early bird gets the worm.#

4.5.2 Метод обобщенного правила рекурсии (ОПР)

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

Ниже в символическом виде дан общий вид правила рекурсии:

Хотя структура этого правила сложнее чем структура простого правила рекурсии, рассмотренного в предыдущем разделе, однако принципы, применяемые к первому из них применимы и ко второму.

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

88

новку. Третья компонента - список других предикатов. Аналогично, успех или неудача этих предикатов на рекурсию не оказывает влияния. Четвертая группа - само рекурсивное правило. Успех этого правила вызывает рекурсию. Пятая группа - список предикатов, успех или неудача которых не влияет на рекурсию. Пятая группа также получает значения (если они имеются), помещенные в стек во время выполнения рекурсии.

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

Например, вы хотите написать правило генерации всех целых чисел начиная с 1 и кончая 7. Пусть имя правила будет

write_number(Number).

Для этого примера первая компонента структуры общего правила рекурсии не используется. Второй компонентой, т.е. предикатом выхода, является Number < 8. Когда значение Number равно 8, правило будет успешным и программа завершится.

Третья компонента правила оперирует с числами. В этой части правила число выдается на экран и затем увеличивается на 1. Для увеличенного числа будет использоваться новая переменная Next_Number. Четвертая компонента - вызов самого правила рекурсии write_number(Next_number). Пятая компонента, представленная в общем случае, здесь не используется.

Листинг 4.8

__________________________________________________________

/* Программа: Генерация ряда */ /* Назначение: Демонстрация использования рекурсии для */

domains

number = integer

predicates write_number(number)

goal

write("Here are the numbers:"), nl,nl,

write_number(1), nl,nl,

89

Next_number = Number + 1, write_number(Next_number).

_______________________________________________________

Программа генерации ряда чисел (листинг 4.8) использует следующее правило рекурсии:

write_number(8). write_number(Number) :-

Number < 8, write(Number), nl,

Next_Number = Number + 1, write_number(Next_number).

Программа начинается с попытки вычислить подцель write_number(1). Сначала программа сопоставляет подцель с первым правилом write_number(8). Так как 1 не равно 8, то сопоставление неуспешно. Программа вновь пытается сопоставить подцель, но уже с головой правила write_number(Number). На этот раз сопоставление успешно вследствие того, что переменной Number присвоено значение 1. Программа сравнивает это значение с 8; это условие выхода. Так как 1 меньше 8, то подправило успешно. Следующий предикат выдает значение, присвоенное Number. Переменная Next_Number получает значение 2, а значение Number увеличивается 1. В этот момент правило write_number вызывает само себя с новым значением параметра, равным 2 и присвоенным Next_Number.

Заметим, что необязательно вызывать правило, используя то же имя переменной, что используется в голове правила. Это всего лишь позиция в списке параметров, имеющая значение при передаче значений. Фактически если не передавать значение Next_Number, то приращение основного числа программы невозможно. При рекурсивном вызове головы правила, программа снова пытается выполнить подцель write_number(8). Программа продолжает выполнять цикл сопоставления, присвоения и выдачи значений Number до тех пор, пока значение Number не станет равным 8. В этот момент цель выполнена, правило успешно и программа завершается после выдачи сообщения All done, bye! (Все сделано, привет!). Результат работы этой программы есть список целых чисел, выданных на экран.

*Упражнения

4.11.Измените программу генерации ряда чисел так, чтобы она выдавала все целые числа от 53 до 62.

4.12.Измените подцель и правило рекурсии так, чтобы результатом программы была генерация целых чисел от 1 до 7 в порядке убывания.

Важное свойство правила рекурсии состоит в его расширяемости. Например, оно может быть расширено для подсчета суммы ряда целых чисел.

90