На этом шаге мы рассмотрим процесс повторения.
Компьютеры способны повторять одно и то же действие снова и снова, Пролог может выражать повторение как в процедурах, так и в структурах данных. Идея повторяющихся структур данных может показаться странной, но Пролог позволяет создвать структуры данных, размер которых не известен во время создания.
Процесс повторения
Программисты на языках Pascal или С, которые начинают использовать Пролог, часто испытывают разочарование, обнаружив, что язык не имеет конструкций For, While или Repeat. He существует прямого способа выражения повтора. Пролог обеспечивает только два вида повторения - откат, с помощью которого осуществляется поиск многих решений в одном запросе, и рекурсию, в которой процедура вызывает сама себя.
Как будет показано, этот недостаток не снижает мощи Пролога. Фактически, Пролог распознает специальный случай рекурсии - хвостовую рекурсию - и компилирует ее в оптимизированную итерационную петлю. Это означает, что хотя программная логика и выражается рекурсивно, скомпилированный код так же эффективен, как если бы программа была написана на Pascal.
Снова поиск с возвратом
Когда выполняется процедура поиска с возвратом (откат), происходит поиск другого решения целевого утверждения. Это осуществляется путем возврата к последней из проверенных подцелей, имеющей альтернативное решение, использования следующей альтернативы этой подцели и новой попытки движения вперед. Программа pro38_1.pro показывает, как иcпольpзуется поиск с возвратом для выполнения повторяющихся операций. Эта программа выводит на печатающее устройство все возможные решения запроса.
predicates
country(symbol)
print_countries
clauses
country("England").
country("France").
country("Germany").
country("Denmark").
print_countries:-
country(X),
write(X), % записать значение Х
nl,% начать новую строку
fail.
print_countries.
goal
print_countries.
Предикат country составляет список названий различных стран, которые являются решениями для поставленного целевого утверждения:
country(X)
print_countries:-
country(X),
write(X),
nl,
fail.
print_countries.
Первое предложение гласит: "Чтобы отпечатать страны, надо найти решения country(X), написать значение X, начать новую строку и инициировать неудачное завершение".
В этом случае "неудачное завершение" (fail) означает:
"Принять, что решение поставленного целевого утверждения не было достигнуто, поэтому вернуться назад и искать альтернативное решение".
Встроенный предикат fail всегда вызывает "неудачное завершение", но можно было бы вызвать поиск с возвратом и обратившись к таким целевым утверждениям, как, например: 5=2+2 или country(shangri_la).
Первый проход выполняется до конца, X присваивается значение England, которое выводится на печать. Затем, наткнувшись на fail, компьютер возвращается в начало. Так как nl или write(X) не имеют альтернативных решений, то компьютер перходит к поиску следующего решения предиката country(X).
При последнем выполнений country(X), ранее свободная переменная X стала связанной. Поэтому, снова выполняя country(X), компьютер освобождает переменную X находит альтернативное решение предиката country(X) и присваивает X новое значение. После этого обработка продолжается, и название другой страны выводится на печать.
В конце концов, первое предложение будет проверено для всех альтернатив. Останется выполнить только второе предложение того же предиката, что происходит без каких-либо дополнительных сложностей. И наконец, целевое утверждение print_countries успешно завершится следующим результатом:
England France Germany Denmark yes
Если бы второго предложения не было, то целевое утверждение print_countries не исполнилось бы, и последнее сообщение было бы nо, при этом результат был бы таким же.
Предварительные и последующие операции
Отметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, и нашем примере программа могла бы:
- Напечатать Some delightful places to live are... (Некоторые восхитительные места для проживания...).
- Напечатать все решения для country(X).
- Завершить печать фразой And maybe others (Могут быть и другие).
Заметьте, что print_countries, определенное в предыдущем примере, уже содержит , предложение вывести на печать все решения country(X) и отпечатать завершающее сообщение.
Первое предложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail - "неудачное завершение"). Можно было бы изменить первое предложение в программе pro38_1.pro.
print_countries:-
write("And maybe others."),nl.
print_countries:-
write("Some delightful places to live are"),nl,
fail.
print_countries:-
country(X),
write(X),nl,
fail.
print_countries:-
write("And maybe others."),nl.
Наличие fail в первом предложении важно, поскольку он обеспечивает после выполнения первого предложения возврат и переход ко второму предложению. Кроме того, это важно, потому что предикаты write и nl не образуют альтернатив. Строго говоря, первое предложение проверяет все возможные решения перед тем, как завершиться неуспехом.
Такая структура из трех предложений более удобна по сравнению с общепринятым подходом. Однако вы можете захотеть еще упростить код и применить такой метод для составления программы:
print_countries_with_captions:-
write("Some delightful places to live are"),nl,
print_countries,
write("And maybe others."),nl.
print_countries:-
country(X),
write(X),nl,
fail.
Но такая программа работать не будет. Проблема в том, что, как написано в последнем примере, print_countries всегда будет "неудачно завершаться", и print_ countries_with_captions никогда не вызовет выполнения подцелей, следующих за print_countries. В результате фраза And maybe others никогда не напечатается.
Все, что необходимо сделать для исправления ошибки, - это восстановить второе предложение print_countries для предиката print_countries в его первоначальное состояние. Если вы хотите, чтобы целевое утверждение print_countries_with_captions было выполнимым, то print_countries должно иметь, по крайней мере, одно предложение, не содержащее fail.
На следующем шаге мы рассмотрим использование отката с петлями.
