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

• Xявляется женщиной,

• Xимеет мать Ми отца Fи

• Yимеет тех же мать и отца, что и X.

Это можно записать в виде следующего правила Пролога:

является_сестрой(X,Y):- женщина(X), родители(X,M,P), родители(Y,M,P).

Мы используем переменные Mи Fдля обозначения материи отца,хотя при желании мы могли бы использовать имена Матьи Отец. Отметим, что мы употребляем переменные, которые не появляются в заголовке правила. Эти переменные, Mи F, обрабатываются таким же образом, как и любая другая переменная. Когда Пролог использует это правило, переменные Mи Fизначально будут неконкретизированными. Этим переменным будет присвоено некоторое значение в момент установления соответствия для предиката родители(X,M,F). Однако, как только они конкретизируются, становятся конкретизированными и всевхождения переменных Mи F, соответствующие текущему использованию правила. Следующий пример должен помочь объяснить, как используются эти переменные. Давайте зададим вопрос:

?- является_сестрой(алиса,эдуард).

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

1. Сначала вопрос сопоставляется с единственным правилом для предиката является_сестрой, приведенным выше. При этом переменная Xконкретизируется, принимая значение алиса, и переменная Yконкретизируется значением эдуард. Правило, с которым произошло сопоставление, отмечается маркером. Теперь Пролог пытается последовательно согласовать с базой данных три предиката, входящие в тело правила.

2.Так как на предыдущем шаге переменной Xприсвоено значение алиса, то первой целью является женщина(алиса). Истинность этого предиката следует из списка фактов, так что цель достигнута. Поскольку данная цель согласована, то Пролог отмечает соответствующее ей место в базе данных (третье утверждение в базе данных).При этом не произошлоникаких присвоений значений переменным. Далее Пролог пытается согласовать следующую цель.

3. Теперь Пролог ищет соответствие для предиката родители(алиса,M,F), где переменные Mи Fсопоставимы с любыми аргументами, так как первоначально они неконкретизированы. Факт, с которым происходит сопоставление, есть родители(алиса, виктория,альберт), и тем самым вторая цель достигнута. Пролог отмечает маркером соответствующее место в базе данных (шестое утверждение сверху) и записывает, что Mприсвоено значение виктория, a F– значение альберт. (Если хотите, вы можете делать соответствующую запись над целевым утверждением в правиле.) Затем Пролог пытается найти соответствие для следующего предиката в правиле.

4. Теперь Пролог ищет в базе данных факт родители(эдуард,виктория,альберт),так как из запроса нам известно, что Y– это эдуард,а из предыдущего шага мы знаем, что Mи Fобозначают викторияи альберт.Эта цель достигается, поскольку найден подходящий факт (пятое утверждение сверху). Так как это последняя цель в конъюнкции, то и полное целевое утверждение является согласованным с базой данных, и тем самым доказано, что факт является_сестрой(алиса, эдуард)является истинным, Пролог отвечает да.

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

?- является_сестрой(алиса,X).

В ответ на вопрос Пролог выполняет следующие действия:

1. Вопрос сопоставляется с заголовком единственного правила для предиката является_сестрой.Переменная X, входящая в это правило, конкретизируется значением алиса.Так как переменная Xв запросе неконкретизирована, то и переменная Yв правиле также будет неконкретизированной. Однако эти две переменные теперь становятся сцепленными.Как только одной из переменных присваивается некоторое значение, другая переменная становится конкретизированной тем же самым значением. Конечно, в данный момент они неконкретизированы.

2. Первая цель – женщина(алиса),которая достигается так же, как и в предыдущем примере.

3. Вторая цель – родители(алиса,М,F).Эта цель сопоставляется с родители(алиса,виктория,альберт).Переменные Mи Fстановятся конкретизированными.

4. Так как переменная Yпока неизвестна, то третьей целью будет родители(Y,виктория,альберт),и она сопоставляется с родители(эдуард, виктория,альберт).Переменная Yконкретизируется значением эдуард.

5. Так как все целевые утверждения согласованы с базой данных, то тем самым согласовано и правило в целом, при этом переменная X(как известно из вопроса) равна алисаи Yравна эдуард.Учитывая, что Y(в правиле) является сцепленнойс X(в вопросе), то Xтакже конкретизирована значением эдуард.Пролог печатает Х=эдуард.

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

Как мы видели до сих пор, существуют два способа предоставить Прологу информацию относительно предиката, подобного предикату нравится.Мы можем сделать это, используя как факты, так и правила. В общем случае предикат будет определен смесью фактов и правил. Эти факты и правила, определяющие предикат, называются утверждениями ^[4] .Мы будем использовать слово утверждениев случаях, когда мы ссылаемся либо на факт, либо на правило.

4

В оригинале – clause for a predicate – термин, определяющий конъюнкты предиката, переменные которых связаны квантором общности. Связь этого понятия с математической логикой обсуждается в гл. 10.- Прим. ред.

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

может_украсть(P,T:- вор(P), нравится(P,T), ценный(T).

Предикат может_украсть,который имеет две переменные Pи T, представляет отношение: некоторый человек P может украсть вещь T. Это правило зависит от утверждений, определяющих предикаты вор, нравитсяи ценный.Они могут быть представлены либо как факты, либо как правила в зависимости от того, что является более подходящим. Например, рассмотрим следующую базу данных, составленную в том числе из утверждений, обсуждавшихся ранее. Мы добавим к ним номера утверждений, заключенные между специальными скобками /*… */. Именно таким образом в Пролог-системе записывается комментарий.Комментарии игнорируются Пролог-системой, но мы можем добавить их в программу для удобства. В последующем обсуждении мы будем ссылаться на номера предложений, представленные в виде комментариев.

/*1*/ вор(джон).

/*2*/ нравится(мэри, пища).

/*3*/ нравится(мэри,вино).

/*4*/ нравится(джон,X):- нравится(X,вино).

/*5*/ может_украсть(X,Y):- вор(X), нравится(X,Y).

Отметим, что определение предиката нравитсясодержит три отдельных утверждения: два факта и правило. Для Пролога это не имеет значения. Единственное различие состоит в том, что когда осуществляется поиск в базе данных, чтобы согласовать с ней некоторую цель, то правило вызывает дальнейший поиск, чтобы согласовать его собственные предикаты-подцели. Факт не имеет подцелей, так что при сопоставлении сфактом поиск либо сразу завершается, либо сразу происходит переход к следующему утверждению. Например, давайте проследим за тем, что получится, если обратиться к Прологу с вопросом: Что Джон может украсть?Прежде всего этот вопрос транслируется на Прологе: