goal

print__countnes.

1. Программа ch06e01.pro

1. Предварительные и последующие операции

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

1. Напечатать

Some delightful places to live are... (Некоторые восхитительные места для проживания...).

1. Напечатать все решения для country (X).

2. Завершить печать фразой And maybe others (Могут быть и другие).

Заметьте, что print_countries, определенное в предыдущем примере, уже содержит предложение вывести на печать все решения country (X) и отпечатать завершающее сообщение.

Первое предложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail — "неудачное завершение").

Можно было бы изменить второе предложение в программе ch06e01.pro.

print_countnes :-

write("And maybe others."), nl.

которое выполнило бы шаг 3, как указано.

А что можно сказать о шаге 1? В нем нет смысла, когда print_countnes содержал только 2 предложения. Но в предикате может быть и три предложения:

print_countries :-

write("Some delightful places to live are"), nl,

fail.

pnnt_countnes :-

country(X),

write(X),nl,

fail.

print_countries :-

write("And maybe others."), nl.

Наличие fail в первом предложении важно, поскольку он обеспечивает после выполнения первого предложения возврат и переход ко второму предложению Кроме того, это важно, потому что предикаты write и nl не образуют альтернатив Строго говоря, первое предложение проверяет все возможные решения перед тем, как завершиться неуспехом.

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

1. Использование отката с петлями

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

repeat

repeat - repeat

Этот прием демонстрирует создание структуры управления Пролога (см листинг на рис. 2.), которая порождает бесконечное множество решений. Цель предиката repeat — допустить бесконечность поиска с возвратом (бесконечное количество откатов)

/* Использование repeat для сохранения введенных символов и печатать их до тех пор, пока пользователь не нажмет Enter (Ввод)*/

predicates

repeat

typewriter

clauses

repeat.

repeat -repeat.

typewriter :-

repeat,

readchar(C),% Читать символ, его значение присвоить С

write(С),

С = '\r',% Символ возврат каретки (Enter)? или неуспех

goal

typewriter (), nl.

1. Листинг 13.2. Программа ch06e02.pro

Программа ch06e02 pro показывает, как работает repeat Правило typewriter - описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу ()

Правило typewriter работает следующим образом

1 Выполняет repeat (который ничего не делает, но ставит точку отката).

2 Присваивает переменной с значение символа.

3 Отображает С.

4 Проверяет, соответствует ли с коду возврата каретки.

5 Если соответствует, то — завершение. Если нет — возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar не являются альтернативами,

1. Рекурсивные процедуры

1. Понятие рекурсии

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

Логика рекурсии проста для осуществления. Представьте себе ЭВМ, способную "понять":

Найти факториал числа N:

Если N равно 1, то факториал равен 1

Иначе найти факториал N-1 и умножить его на N.

Этот подход означает следующее:

первое («закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищется без обращения к другим факториалам, т.к. он равен 1, поэтому повторения не начнутся.

второе («раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.

Информация хранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.

1. Преимущества рекурсии

Рекурсия имеет три основных преимущества:

• она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;

• она логически проще метода итерации;

• она широко используется в обработке списков.

Рекурсия — хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).

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

1. Пример рекурсивного определения правил

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

определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый X является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.. В нашем примере на рис. 1. Том - ближайший предок Лиз и отдаленный предок Пат.

1. Пример отношения предок:(а) X - ближайший предок Z; (b) X - отдаленный предок Z.

Первое правило простое и его можно сформулировать так:

Для всех X и Z,

X - предок Z, если X - родитель Z.

Это непосредственно переводится на Пролог как

предок( X, Z) :.-родитель( X, Z).

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

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y), родитель( Y, Z).

предок( X, Z) :-

родитель( X, Y1),

родитель( Y1, Y2),

родитель( Y2, Z).

предок (X, Z) :-

родитель( X, Y1),

родитель( Y1, Y2),

родитель( Y2, Y3),

родитель( Y3, Z).

1. Пары предок-потомок, разделенных разным числом поколений.

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

Существует, однако, корректная и элегантная формулировка отношения предок - корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предок через него самого. Рис. 3 иллюстрирует эту идею:

Для всех X и Z,

X - предок Z, если существует Y, такой, что

(1) X - родитель Y и

(2) Y - предок Z.

Предложение Пролога, имеющее тот же смысл, записывается так:

предок( X, Z) :-

родитель ( X, Y), предок( Y, Z).

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

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

1. Р екурсивная формулировка отношения предок.

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

1. Оптимизация хвостовой рекурсии

У рекурсии есть один большой недостаток — она «съедает» память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, таких как IBM PC, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?

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

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

Например, допустим, что процедура А вызывает процедуру В, а В — С в качестве своего последнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянии С, мы можем переписать старую сохраненную информацию о состоянии В (которая больше не нужна) на текущую информацию о С, сделав соответствующие изменения в хранимой информации. Когда С закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.

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

Эта операция называется оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизацией последнего вызова (last-call optimization) Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.

1. Как задать хвостовую рекурсию

Что означает фраза "одна процедура вызывает другую, выполняя свои самый последний шаг"? На языке Пролог это значит.