нравится(джон,X):- нравится(Х,вино), нравится(X,пища).
или, другими словами, Джону нравится любой, кому нравятся вино и пища.Или, предположим, что Джону нравится любая женщина, которой нравится вино:
нравится(джон,Х):- женщина(Х), нравится(Х,вино).
Всякий раз, когда мы имеем дело с правилом в Прологе, необходимо отмечать все вхождения переменных. В последнем примере переменная Xиспользована три раза. Всякий раз, как переменная X конкретизируется некоторым объектом (ей присваивается значение), все вхождения Xв пределах области действия этой переменнойстановятся конкретизированными. При каждом употреблении правила область действияпеременной X– это все правило, начиная с заголовка и до точки '.' в конце этого правила. Так, если в приведенном выше правиле переменная X оказалась конкретизированной, принимая значение мэри,то Пролог попытается согласовать с базой данных целевые утверждения женщина(мэри)и нравится(мэри,вино).
Теперь, чтобы продемонстрировать правило, использующее более одной переменной, рассмотрим базу данных, содержащую факты о семействе королевы Виктории. Мы будем использовать предикат родители,имеющий три аргумента. родители(Х, Y, Z)означает: Родителями X являются Y и Z. Переменная Yобозначает мать, а переменная Zобозначает отца. Кроме того, мы будем использовать предикаты женщинаи мужчинав их очевидном значении. Некоторая часть этой базы данных могла бы выглядеть следующим образом:
мужчина(альберт).
мужчина(эдуард).
женщина(алиса).
женщина(виктория).
родители(эдуард,виктория,альберт).
родители(алиса,виктория,альберт).
Здесь мы воспользуемся описанным ранее правилом является_сестрой.Правило определяет предикат является_сестрой, имеющий два аргумента, таким образом, что является_сестрой(X, Y)истинно, если Xявляется сестрой Y. Обратим внимание на использование в имени предиката символа подчеркивания '_'. Хотя до сих пор не было дано полных правил конструирования имен, отметим, что допускается использование подчеркивания в именах, а более подробно об этом будет сказано в следующей главе. Тогда Xявляется сестрой Y, если:
• 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] .Мы будем использовать слово утверждениев случаях, когда мы ссылаемся либо на факт, либо на правило.
В качестве следующего примера, на этот раз не имеющего отношения к монархам, рассмотрим правило: Человек может украсть что-либо, если этот человек вор и ему нравится вещь и эта вещь является ценной.На Прологе это записывается следующим образом:
может_украсть(P,T:- вор(P), нравится(P,T), ценный(T).
Предикат может_украсть,который имеет две переменные Pи T, представляет отношение: некоторый человек P может украсть вещь T. Это правило зависит от утверждений, определяющих предикаты вор, нравитсяи ценный.Они могут быть представлены либо как факты, либо как правила в зависимости от того, что является более подходящим. Например, рассмотрим следующую базу данных, составленную в том числе из утверждений, обсуждавшихся ранее. Мы добавим к ним номера утверждений, заключенные между специальными скобками /*… */. Именно таким образом в Пролог-системе записывается комментарий.Комментарии игнорируются Пролог-системой, но мы можем добавить их в программу для удобства. В последующем обсуждении мы будем ссылаться на номера предложений, представленные в виде комментариев.
/*1*/ вор(джон).
/*2*/ нравится(мэри, пища).
/*3*/ нравится(мэри,вино).
/*4*/ нравится(джон,X):- нравится(X,вино).
/*5*/ может_украсть(X,Y):- вор(X), нравится(X,Y).
Отметим, что определение предиката нравитсясодержит три отдельных утверждения: два факта и правило. Для Пролога это не имеет значения. Единственное различие состоит в том, что когда осуществляется поиск в базе данных, чтобы согласовать с ней некоторую цель, то правило вызывает дальнейший поиск, чтобы согласовать его собственные предикаты-подцели. Факт не имеет подцелей, так что при сопоставлении сфактом поиск либо сразу завершается, либо сразу происходит переход к следующему утверждению. Например, давайте проследим за тем, что получится, если обратиться к Прологу с вопросом: Что Джон может украсть?Прежде всего этот вопрос транслируется на Прологе:
?- может_украсть(джон,Х).
Чтобы ответить на этот вопрос, Пролог осуществляет поиск следующим образом:
1. Прежде всего Пролог ищет в базе данных утверждение, описывающее предикат может_украсть,и находит такое утверждение. Оно представлено в виде правила и имеет номер 5. Пролог отмечает это место в базе данных. Так как это утверждение является правилом, то, чтобы установить, согласуется ли заголовок правила с базой данных, необходимо попытаться согласовать с ней тело правила. Тогда переменной Xв правиле 5 присваивается значение джон,которое берется из вопроса. Как и в предыдущих примерах, мы должны сопоставить неконкретизированные переменные ( Xв вопросе и Yв правиле), так что теперь они будут сцеплены.Если вы не уверены, что до конца понимаете, что это значит, то необходимо вернуться назад к примерам с предикатом я вляется_сестрой(X, Y). Для того чтобы правило выполнилось, необходимо согласовать цели с базой данных. Таким образом, теперь проверяется на согласованность с базой данных первое утверждение вор(джон).
2. Эта цель достигается, так как факт вор(джон)содержится в базе данных (утверждение 1). Пролог отмечает это место в базе данных, и при этом присвоения значений переменным не происходит. Далее Пролог пытается достигнуть вторую цель, применяя утверждение 5. Так как X, как и ранее, обозначает джон,то теперь Пролог ищет нравится (джон, Y).Заметим, что к этому моменту Yостается неконкретизированной.
3. Цель нравится(джон, Y)сопоставляется с заголовком правила (утверждение 4). Переменная Y, входящая в цель, сцепляетсяс Xв заголовке правила, и обе эти переменные остаются неконкретизированными. Чтобы доказать это правило, теперь ищется нравится(Х, вино).
4. Эта цель достигается, так как она сопоставляется с нравится (мэри,вино)- фактом, являющимся утверждением с номером 3. Так что теперь Xстановится мэри.
5. Так как цель в утверждении 4 достигнута, то согласовано и правило в целом. Факт нравится(джон, мэри)следует из утверждения 4, так как переменная Yв утверждении 5 сцеплена с X, и ей тоже присваивается значение мэри.
6. Утверждение 5 теперь согласуется с базой данных при Y, имеющем значение мэри.Так как переменная Yбыла сцеплена со вторым аргументом исходного вопроса, то переменная Xв вопросе конкретизируется, принимая значение мэри.Приведем рассуждение, обосновывающее факт Джон может украсть Мэри:
Для того чтобы украсть что-либо, прежде всего Джон должен быть вором. Из утверждения 1 следует, что это имеет место. Далее, Джону должен нравиться похищаемый предмет. Из утверждения 4 мы видим, что Джону нравится любой, кому нравится вино. Из утверждения 3 мы видим, что Мэри нравится вино. Следовательно, Джону нравится Мэри. Поэтому оба условия для похищения некоторого объекта имеют место, а значит, Джон может украсть Мэри.
Заметим, что факт (утверждение 2) о том, что Мэри нравится пища, не имеет никакого отношения к данному конкретному запросу, так как он нигде не понадобился.
В приведенном примере мы повторно использовали переменные Xи Yв различных утверждениях. Например, в правиле может_ украсть Xобозначает объект, который может что-нибудь украсть. Но в правиле нравится Xобозначает объект, которому что-то нравится. Для того чтобы приведенная программа имела смысл, в Прологе должна иметься возможность указывать, что X может обозначать различные вещи в различных употреблениях утверждений. Помните, что знание области действияпеременной может разрешить любые неясности. Мы могли бы использовать более мнемоничные имена, чтобы попытаться предотвратить любые неясности, но мы используем простые имена, такие как X, чтобы продемонстрировать работу принципа области действия переменной.
1.6. Заключение и упражнения
К этому моменту мы уже обсудили большинство основных черт языка Пролог. В частности, мы рассмотрели:
• объявление фактов об объектах;
• задание вопросов относительно известных фактов;
• роль переменных и их области действия;
• конъюнкцию как способ описания и-условий;
• представление отношений в виде правил;
• общую схему поиска с механизмом возврата.
С этим небольшим набором элементарных конструкций можно уже писать полезные программы для работы с простыми базами данных. Скорее всего, наиболее правильно так и поступить, работая над упражнениями, приведенными ниже.
Чтобы понять, как пользоваться этой книгой, вам следует прочитать предисловие, если вы не сделали это до сих пор. Кроме того, когда вы начнете писать программы для имеющейся в вашем распоряжении системы программирования на Прологе, вам следует обратиться к соответствующему приложению, чтобы узнать, как организуется взаимодействие с системой. Вы также найдете несколько практических советов в гл. 8.
Теперь, когда вы имеете в своем распоряжении достаточно большой арсенал средств Пролога, вам следует перейти к следующей главе, в которой обсуждаются некоторые вопросы, не рассматривавшиеся в этой главе. Кроме того, мы покажем, какие средства для работы с числами имеются в Прологе. Черты языка, рассматриваемые в нескольких последующих главах, делают очевидными выразительные возможности и удобство Пролога.
Упражнение 1.2.При применении правила является_сестройк обсуждавшейся ранее базе данных, содержащей информацию о семействе королевы Виктории, может быть получено несколько ответов. Объясните, как могут быть получены все ответы и каковы они.
Упражнение 1.3.В основу этого упражнения положено одно из упражнений из книги Kowalski R. Logic for Problem Solving,North Holland, 1979. Предположим, что кем-то уже написаны на Прологе утверждения, определяющие следующие отношения:
отец(Х,Y) /* X является отцом Y */
мать(Х, Y) /* X является матерью Y */
мужчина(Х) /* X – мужчина */
женщина(Х) /* X - женщина */
родитель(Х,Y) /* X является родителем Y */
различны(Х,Y) /* X и Y различны */
Задача состоит в том, чтобы написать правила для следующих отношений:
является_матерью(Х) /* X является матерью */
является_отцом(Х) /* X является отцом */
является_сыном(Х) /* X является сыном */
является_сестрой(Х,Y) /* X является сестрой Y */
дедушка(Х, Y) /* X является дедушкой Y */
общие_родители(Х,Y) /* X и Y имеют общих родителей*/
Например, мы могли бы написать правило для предиката тетя,при условии что у нас уже имеются правила для женщина, общие_родителии родитель.
тетя(Х,Y):- женщина(Х), общие_родители(X, Z), родитель(Z,Y).
Это можно также записать следующим образом:
тетя(Х,Y):- является_сестрой(Х,Z), родитель(Z, Y).
при условии что мы имеем правило для отношения является_сестрой.
Упражнение 1.4.Используя правило для отношения является_сестрой,определенное в тексте, объясните, каким образом становится возможным, что некто может быть своей собственной сестрой. Как можно было бы изменить это правило, если такое свойство нежелательно? Считайте, что предикат различныиз упр. 1.3 уже определен.
ГЛАВА 2 БОЛЕЕ ДЕТАЛЬНОЕ ОПИСАНИЕ
В данной главе приводится более полное описание тех элементов Пролога, которые были введены в предыдущей главе. Пролог предоставляет средства для структурирования данных, а также средства для структурирования той последовательности,в которой совершаются попытки согласовать целевые утверждения с базой данных. Для структурирования данных необходимо знание синтаксических правил, используемых для обозначения данных. Структурирование последовательности, в которой будут совершаться попытки согласовать целевые утверждения с базой данных, предполагает знание принципов работы механизма возврата.
2.1. Синтаксические правила
Синтаксические правила языка описывают допустимые способы соединения слов. В соответствии с нормами английского языка предложение «I see a zebra» («я вижу зебру») является синтаксически правильным в отличие от предложения «zebra see I а» («зебра видит я»). В первой главе синтаксис Пролога явно не обсуждался, просто показывалось на примерах, как выглядят некоторые элементы Пролога. В данном разделе приводится краткое описание синтаксических правил для уже знакомых нам элементов Пролога.
Пролог-программы состоят из термов.Терм – это либо константа,либо переменная,либо структура.Каждый из этих термов фигурировал в предыдущей главе, но не назывался там таким именем. Терм записывается как последовательность литер.Литеры делятся на четыре категории:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abсdefghijklmnopqrstuvwxyz
0123456789
+-*/\^<>~:.?@#$&
Первая строка состоит из прописных букв.Вторая строка – из строчных букв.В третьей строке – цифры.В четвертой строке перечислены специальные литеры (спецзнаки).В действительности спецзнаков больше, чем показано в четвертой строке, но остальные используются только в особых случаях, обсуждаемых ниже [5] . Для термов каждого типа, таких как константа, переменная, структура, имеются свои правила образования имен термов из литер. Ниже вкратце обсуждаются каждый из типов термов.
Константами являются поименованные конкретные объектыили конкретные отношения.Существует два вида констант: атомыи целые числа.Примерами атомов являются имена, приводившиеся в предыдущей главе:
нравится мэри джон книга вино имеет драгоценности может_украсть
Специальные символы, используемые Прологом для обозначения вопросов '?-' и правил ':-', также являются атомами. Есть два вида атомов: составленные из букв и цифр и составленные из спецзнаков. Первые, как мы видели в предыдущей главе, должны обычно начинаться со строчной буквы. Атомы, составленные из спецзнаков, как правило, состоят толькоиз спецзнаков. Иногда возникает необходимость иметь атом, начинающийся с прописной буквы или цифры. Если атом заключается в одиночные кавычки, то его имя может содержать любыелитеры. И наконец, для простоты чтения внутрь атома можно включать специальную литеру – подчеркивание '_'. Ниже приведено несколько атомов:
а
свободный
=
'джордж-смит'
--›
джордж_смит
ieh2304
Следующие объекты не являются атомами:
2304ieh
джордж-смит
Пустой
_ альфа
Другой вид констант, целые числа, используется для представления числовых данных, что позволяет выполнять над ними арифметические операции. В предыдущей главе не обсуждались способы выполнения арифметических операций в Прологе, такие средства будут определены ниже. Целые числа состоят только из цифр и не могут содержать десятичной запятой. В этой книге будут использоваться сравнительно небольшие положительные числа, такие как
0 1 999 512 8192 14765 6224
Пролог реализован на различных ЭВМ и в зависимости от того, на какой именно ЭВМ работает программист, ему может быть разрешено или не разрешено использовать большие или отрицательные числа. Однако в данной книге приводятся только примеры, допустимые для любой из существующих версий Пролога. Можно утверждать, что всегда разрешается использовать числа из диапазона от 0 до 16 383. Возможно, что на доступной читателю ЭВМ допустимы и другие числа (превышающие 16 383 или отрицательные), однако дальнейшее изложение этого не учитывает. Может быть, это покажется удивительным, однако в задачах, в которых оказался полезным Пролог, как правило, не нужны средства для работы с очень большими, дробными или отрицательными числами. Тем не менее, поскольку Пролог является расширяемым языком, программист, обладающий соответствующими ресурсами, может без особого труда добавить к системе предикаты, определяющие такие возможности. Например, некоторые Пролог-системы предоставляют пользователям библиотечные программы, определяющие операции над рациональными числами и числами произвольной точности.
Второй разновидностью термов в Прологе являются переменные. Переменные внешне похожи на атомы, за исключением того, что они начинаются с прописной буквы или знака подчеркивания '_'. Переменная служит для представления объекта, на который нельзя сослаться по имени. Здесь можно провести аналогию с использованием местоимений в естественном языке. В приведенных выше примерах фигурировали переменные с такими именами как X, Yи Z. Однако имена могут быть сколь угодно длинными, например:
Ответ
Ввод
Большая_Выплата
_3_слепые_мыши
Иногда возникает необходимость в использовании переменной, имя которой не будет нигде употребляться. Например, если необходимо определить, нравится ли кому-нибудь Джон, и при этом не важно, кому именно он нравится, можно использовать анонимную переменную.
Анонимная переменная – это одиночный знак подчеркивания '_'. Наш пример с Джоном записывается на Прологе следующим образом:
?- нравится(_,джон).
Если в одно утверждение входят несколько анонимных переменных, их можно интерпретировать неоднозначно. Это характерная особенность, присущая только анонимной переменной. Она позволяет избавить программиста от необходимости придумывать разные имена переменным в тех случаях, когда эти имена в утверждении нигде больше не употребляются.
Третьим видом терма, присутствующим в Пролог-программах, является структура. Структура – это единый объект, состоящий из совокупности других объектов, называемых компонентами. Компоненты группируются в структуру для удобства их использования.
В реальной жизни одним из примеров структур является карточка-указатель для библиотечной книги. Карточка-указатель содержит несколько компонент: сведения об авторе, название книги, дату издания, место, где книга хранится в библиотеке, и т. д. Некоторые из компонент в свою очередь тоже можно разбить на компоненты. Например, сведения об авторе состоят из фамилии и инициалов.
Структуры служат средством организации данных в программе, поскольку они позволяют рассматривать как единый объект (карточку-указатель) группу отдельных элементов данных. Способ, которым осуществляется разложение данных на компоненты, зависит от решаемой задачи, В книге будут приведены некоторые рекомендации на этот счет.