принадлежит(Х, [X | _]).
принадлежит(Х,[_|Y]):- принадлежит (X,Y).
?- принадлежит(d,[a,b,с,d,e,f,g]).
да
?- принадлежит(2,[3,a,4,f]).
нет
Предположим, мы введем вопрос
?- принадлежит(clugatе,[curraugh_tiр,music_star,раrk_mill, ortland]).
Так как clygateне сопоставимо с curragh_tip,то происходит сопоставление со вторым правилом для принадлежит.Переменная Y получает значение [music_star, park_mill, portland],и порождается следующая цель: определить, принадлежит ли clygateэтому списку. Опять происходит сопоставление со вторым правилом, и снова выделяется хвост списка. Текущей целью становится принадлежит (clugate,[park_mill,portland])Этот процесс рекурсивно повторяется до тех пор, пока мы не доберемся до цели, у которой Xесть clygate,a Yесть [portland].Происходит еще одно сопоставление со вторым правилом, и теперь Yконкретизируется хвостом списка [portland],который является пустым списком. Следующей целью становится принадлежит(clygate,[]).Ни одно из правил в базе данных не сопоставимо с этой целью, так что цель оказывается ложной и ответ на вопрос будет отрицательным.
Важно помнить, что каждый раз, когда при согласовании принадлежитс базой данных выбирается второе утверждение этого предиката, Пролог рассматривает рекурсивное обращение к предикату принадлежиткак попытку найти соответствие для некоторой новой его «копии». Это предотвращает путаницу переменных, соответствующих одному употреблению утверждения, с переменными, соответствующими другому употреблению этого же утверждения.
Предикат отношения принадлежности настолько полезен, что мы еще неоднократно будем использовать его в оставшейся части этой книги. Предикат принадлежитважен еще и потому, что он представляет практически наименьший полезный пример рекурсивного предиката определение предиката принадлежитсодержит утверждения, которые могут быть проверены с помощью только того же самого предиката принадлежит.Рекурсивные определения часто встречаются
может показаться натянутой, но все же осмысленной беседой, очень легко написать программу, выполняющую свою «часть» диалога. Для этого достаточно просто последовательно выполнять следующие действия:
1. Ввести предложение, набранное пользователем на терминале.
2. Заменить каждое вхождение слова youна слово i.
3. Аналогичным образом заменить areна am not.
4. Заменить frenchна german.
5. Заменить doна nо.
Если применить данную схему преобразования кнадлежащим образом подобранным предложениям, подобным использованным в приведенном выше диалоге, то получим осмысленные преобразованные предложения. Однако эта схема применима не ко всем предложениям. Например;
Вы: i do like you (я действительно люблю вас)
Пролог: i no like i (я не люблю себя)
Но если простая программа уже написана, то впоследствии ее можно модифицировать так, чтобы она справлялась и с предложениями, подобными приведенному.
Программа на Прологе, преобразующая одно предложение английского языка в другое, может быть реализована следующим образом. Прежде всего необходимо осознать, что имеется отношение между исходным предложением и преобразованным. В связи с этим нам следует определить предикат, называемый преобразовать. Преобразовать(Х, Y)означает, что предложение Xможет быть преобразовано в предложение Y. Предложения Xи Yудобно представлять в виде списков атомов, обозначающих слова, так что предложения могут быть записаны следующим образом: [this,is,a, sentence](это некоторое предложение). Определив предикат преобразовать,мы могли бы обращаться к Прологу с вопросами вида
?- преобразовать([dо,you,know,french],X). (Знаете ли вы французский)
на что Пролог отвечал бы
X=[no,i,know,german] (нет, я знаю немецкий).
Не следует обращать внимание на то, что вводимое и печатаемое в ответ предложения представлены в такой неестественной форме и не похожи на обычные предложения. В последующих главах мы обсудим способы ввода и вывода структур в виде, удобном для чтения. В данный момент нас интересуют лишь способы преобразования одного списка в другой.
Так как аргументами предиката преобразоватьявляются списки, то прежде всего следует рассмотреть, что произойдет, если исходный список пустой. В этом случае мы скажем, что пустой список преобразуется в пустой список:
преобразовать([], [])
Или, иначе: это факт, что преобразование пустого списка дает пустой список.Если причины для того, чтобы рассматривать пустой список, здесь не очевидны, то последующее изложение прояснит их. Далее нам следует разобраться в том, что основные действия предиката преобразоватьзаключаются в следующем:
1. Заменить голову входного списка соответствующим словом и поместить это слово в выходной список в качестве головы.
2. Преобразовать хвост входного списка и сделать его хвостом выходного списка.
3. Если мы достигли конца входного списка, то к выходному списку больше ничего добавлять не надо, и мы можем завершить выходной список пустым списком [].
Переводя это на язык, более близкий к Прологу, можно сказать:
Преобразование списка с головой H и хвостом T дает список с головой X и хвостом Y, если замена слова H дает слово X, а преобразование списка T дает список Y.