У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

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

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

Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_ число(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. Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт 1, и выбирает вместо него правило 2. При этом выборе появляется новая подцель. Факт 1представляет первую возможность для сопоставления с этой подцелью.

Рис. 4.1.

Рис. 4.2.

Рис. 4.3.

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

принадлежит(X,[X |_] ).

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

порождает альтернативные решения. Если мы задаем вопрос

?- принадлежит(а,X).

(обратите внимание, что Xв вопросе является неконкретизированной переменной), то последовательные значения переменной Xбудут представлять частично конкретизированные списки, в которых аявляется первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос

?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).

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