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

Клоксин У.

ребенок(Х,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 = брунхильда.

Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели парень(X)и находит, что первым парнем является джон.Затем он находит сопоставление для цели девушка(Y), выбирая гризелдав качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения возможная_пара.Обнаруживается альтернативный вариант эрминтруда,и, следовательно, следующим решением является пара джони эрминтруда.Аналогично порождается пара джони брунхильдав качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения девушка(Y)Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения парень(Х),маркер которого был установлен на первый факт предиката парень,и, следовательно, следующим найденным решением, соответствующим второму парню, является мармадук.Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели девушка(Y),осуществляя

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

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

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

Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_ число(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).

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