Программа не может более найти ни одной пары.
Все приведенные примеры являются очень простыми. Они содержат лишь определения большого числа фактов или используют правила для доступа к этим фактам. По этой причине они могут порождать только конечное число возможных решений. В некоторых случаях нам может потребоваться порождать бесконечное число возможных вариантов – не потому, что мы хотим рассмотреть их все, а потому, что мы не знаем заранее, сколько их понадобится. В этом случае необходимо рекурсивное определение (обсуждавшееся в предыдущей главе).
Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_число(N) согласуется с базой данных, если переменная N конкретизирована и ее значением является целое число. Если переменная N неконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения целое_число (N) приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.
/* 1 */ целое_число(0).
/* 2 */ целое_число (X):- целое_число (Y),X is Y+1)
Если мы зададим вопрос
?- целое_число (X).
то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката целое_число находится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На рис. 4.1, 4.2, 4.3 показана последовательность событий, приводящая к порождению трех первых решений. На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано иное решение. Первоначально для ответа на вопрос имеется выбор между фактом 1 и правилом 2. Если выбирается факт 1, то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило 2 и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт 1, то завершается доказательство целевого утверждения с ответом X=1; в противном случае используется правило 2 и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт 1. Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт
