Процесс повторения

Программисты на Паскале, Бэйсике или Си, которые начинают использо-

вать Турбо Пролог часто испытывают разочарование, обнаружив, что язык не

имеет конструкций FOR, WHILE или REPEAT. Существует непрямой способ выра-

жения повтора. Пролог позволяет только два вида повтопения - возврат, в

котором осуществляется поиск многих решений в одном запросе и рекурсию в

которой процедура вызывает сама себя.

Как будет показано, этот недостаток не снижает мощи Пролога. Факти-

чески, Турбо Пролог распознает специальный случай рекурсии - хвостовую

рекурсию - и компилирует ее в итерацию на машинном языке. Это означает,

что хотя программная логика и выражается рекурсивно, скомпилированный код

также эффективен, как если бы программа была написана на Паскале или на

Бэйсике.

В этом разделе мы расширим ваше искусство писать повторяющиеся про-

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

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

ми программирования. Перед погружением в рекурсию, однако, рассмотрим еще

раз поиск с возвратом.

Снова поиск с возвратом

Когда выполняется процедура поиска с возвратом, происходит поиск

другого решения целевого утверждения. Это осуществляется путем возврата к

последней основной, имеющей альтернативное решение, подцели, реализации

альтернативы и очередного возврата. Вы можете использовать поиск с возв-

ратом для выполнения повторяющихся процессов.

Пример

Программа CH07EX01.PRO показывает, как используется поиск с возвра-

том для выполнения повторяющихся операций. Эта программа выводит на печа-

тающее устройство все возможные решения определенной задачи.

/* Программа CH07EX01.PRO */

predicates

country(symbol)

print_countries

clauses

country(england).

country(france).

country(germany).

country(denmark).

print_countries :-

country(X),

write(x), /* записать значение X */

nl, /* начать новую строку */

tail.

print_countries.

Предикат country составляет список названий различных стран, которые

являются решениями на поставленное целевое утверждение -

country(X).

Затем предикат print_countries отпечатывает все эти решения. Это оп-

ределено следующим образом:

print_countries :-

country(X), write(x), nl, fail.

print_countries.

Первое предложение гласит:

"Чтобы отпечатать страны - надо найти решения country(X), написать

значение X, начать новую строку и допустить неудачное завершение."

В этом случае "неудачное завершение" (fail) означает:

"Допустить, что решение поставленного целевого утверждения не было

достигнуто, поэтому - вернуться назад и искать альтернативное решение."

Внутренний предикат fail всегда вызывает режим "неудачное заверше-

ние", но можно было бы вызвать поиск с возвратом и обратившись к таким

целевым утверждениям, как например: 5=2+2 или country (shangri_la).

Первый проход выполняется до конца, X присваивается значение

england, которое выводится на печать. Затем компьютер возвращается в на-

чало, и, при отсутствии другого маршрута к выполнению nl или write(X),

переходит к поиску следующего решения предиката country(X).

При этом, выполняя country(X) снова, компьютер освобождает перемен-

ную X, находит альтернативное решение предиката country(X) и присваивает

X новое значение. После этого обработка продолжается и название другой

страны выводится на печать.

В конце концов, первое предложение проверится для всех альтернатив.

Останется выполнить только второе предложение без каких -либо дополни-

тельных сложностей. И наконец целевое утверждение print_countries успешно

завершится следующим результатом

england

france

germany

denmark

Yes

Если бы второго предложения не было, то целевое утверждение

print_countries не выполнилось, и последнее сообщение было бы No, не го-

воря о результате, который был бы таким же.