Программирование на языке пролог (ЛП)

2. Мы можем сделать попытку вновь доказать согласованностьцелевого утверждения с базой данных. Для этого прежде всего необходимо попытаться вновь согласовать каждую из его подцелей, при этом стрелка возвращается в некоторую исходную позицию, поднимаясь вверх по странице. Если ни одна из подцелей вновь не может быть согласована каким-либо подходящим образом, делается попытка найти альтернативное утверждение для самой исходной цели. В этом случае необходимо вернуть в исходное (неопределенное) состояние каждую переменную, конкретизированную при выборе предыдущего утверждения. Эти действия мы называем «уничтожением» результатов, полученных ранее при доказательстве согласованности целевого утверждения. Затем возобновляется просмотр базы данных, но начинается этот просмотр с места, отмеченного маркером данной цели. Как и ранее, эта новая цель, выбранная при возврате, может оказаться либо согласованной, либо несогласованной с базой данных. При этом будет иметь место либо шаг (а), либо шаг (б).

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

4.1. Порождение множественных решений

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

отец(мэри, джордж).

отец(джон, джордж).

отец(сью,гарри).

отец(джордж,эдуард).

в которых отец(X, Y)обозначает, что Yявляется отцом X. Вопрос

?- отец(X,Y).

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

X = мэри, Y = джордж;

X = джон, Y = джордж;

X = сью, Y = гарри;

X = джордж, Y = эдуард.

Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отеци печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом

?- отец(_,X).

(для какихXверно то, чтоXявляется отцом),то мы получим

Х=джордж;

Х=джордж;

Х=гарри;

Х=эдуард.

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

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

ребенок(Х,Y):- отец(Y,X).

Тогда вопрос

?- ребенок(Х,Y).

дал бы

X = джордж, Y = мэри;

X = джордж, Y=джон;

X = гарри, Y = сью;

X = эдуард, Y = джордж.

Так как отец(Y, X)имеет четыре решения, то столько же решений имеет и ребенок(Х, Y).Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката ребенок.Аналогично, если мы определили

отец(X):- отец(_,X).

(отец (X) обозначает, что X является чьим-либо отцом), то на вопрос

?- отец(X).

были бы получены ответы:

X = джордж;

X = джордж;

X  =гарри;

X = эдуард.

Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:

человек(адам).

человек(X):- мать(X,Y).

человек(ева).

мать(каин,ева).

мать(авель,ева).

мать(иавал,ада).

мать(тувалкаин,цилла).

( адам- человек; объект является человеком, если он имеет мать; ева– человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос

?- человек (X).

то ответом было бы:

X = адам;

X = каин;

X = авель;

X = иавал;

X = тувалкаин;

X = ева.

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

возможная_пара(X, Y):- парень(Х), девушка(Y).

парень(джон).

парень(мармадук).

парень(бертрам).

парень(чарлз).

девушка(гризелда).

девушка(эрминтруда).

девушка(брунхильда).

В программе определено, что Xи Yобразуют возможную пару, если Xявляется парнем, a Y— девушкой. Теперь давайте посмотрим, какие возможные пары имеются:

?- возможная_пара(X, Y).

X = джон, Y = гризелда;

X = джон, Y = эрминтруда;

X = джон, Y = брунхильда;

X = мармадук, Y = гризелда;

X = мармадук, Y = эрминтруда;

X = мармадук, Y = брунхильда;

X = бертрам, Y = гризелда;

X = бертрам, Y = эрминтруда;

X = бертрам, Y = брунхильда;

X = чарлз, Y = гризелда;

X = чарлз, Y = эрминтруда;

X = чарлз, Y = брунхильда.