Как мы видели в гл. 2, в Прологе существуют предикаты для сравнения целых чисел. В приложениях, имеющих дело со словами, например работа со словарями, полезно иметь предикат для сравнения слов в соответствии с алфавитным порядком.
Рассмотрим предикат, который мы назовем меньше. Если предикат меньше(Х, Y) используется в качестве целевого утверждения, то он истинен (т. е. согласуется с базой данных), если X и Y обозначают атомы и X по алфавиту предшествует Y. Так, предикат меньше(арбуз, букварь) истинен, а меньше(ветер,автомобиль) ложен. Точно так же должен быть ложен и предикат меньше(картина,картина). Сравнивая два слова, мы сравниваем их последовательно, буква за буквой и при сравнении каждой буквы определяем, какое из следующих условий имеет место:
1. Достигнут конец первого слова, но не достигнут конец второго слова. Это имеет место, например, в случае меньше(пар, паровоз). При возникновении такой ситуации предикат меньше должен считаться истинным (т. е. согласованным с базой данных).
2. Очередная литера в первом слове предшествует в алфавите соответствующей литере во втором слове. Например, меньше (слово,слон). Буква ' в ' в слове слово предшествует в алфавите букве ' н ' в слове слон. В этом случае предикат меньше истинен.
3. Литера в первом слове совпадает с соответствующей литерой во втором слове. В этом случае следует использовать предикат меньше для сравнения оставшихся литер в обоих словах. Например, если дано меньше(облако,одеяло), то, так как оба аргумента начинаются с буквы ' о ', необходимо взять в качестве следующей цели меньше(блако,деяло).
4. Одновременно достигнут конец первого и второго слов, как, например, в случае меньше(яблоко,яблоко). При возникновении такого условия предикат меньше должен быть ложным, так как оба слова являются одинаковыми.
5. Обработаны все литеры второго слова, но еще остались литеры в первом слове, как, например, в случае меньше(алфавитный,алфавит). В такой ситуации предикат меньше должен быть ложным.
После того как сформулированы перечисленные выше условия, задача перевода их на Пролог является довольно простой. Будем представлять слова в виде списков литер (целых чисел из некоторого диапазона). Для этого необходим способ преобразования атома в список литер. Эту функцию выполняет встроенный предикат Пролога name(имя) . Целевое утверждение name(X, Y) согласуется с базой данных, когда атом, являющийся значением X , состоит из литер, коды которых образуют список, являющийся значением Y (используются коды ASCII). Отсылаем читателя к гл. 2, если он забыл, что такое коды ASCII. Если один из аргументов не определен, то Пролог предпримет попытку конкретизировать его, создавая соответствующую структуру. Поэтому можно использовать предикат name для преобразования слова в список литер. Например, зная, что код ASCII для 'а' есть 97, код для 'l' – 108 и код для 'p' – 112, можно задавать следующие вопросы:
?- name (Х,[97,108,112])
Х=аlр
?- name (alp,X)
X=[97,108,112]
Первым утверждением в определении предиката меньше является следующее правило:
меньше(Х, Y):- name(X,L),name(Y,M), меньше_l(L,M)
Это правило сначала преобразует слова в списки, используя предикат name, и затем с помощью предиката меньше_1 (будет определен ниже) сравнивает списки на соответствие алфавиту. Определение предиката меньше_1 состоит из утверждений, реализующих приведенный выше набор условий. Первое условие является истинным, когда первый аргумент есть пустой список, а второй аргумент – это произвольный непустой список:
меньше_1([], [_|_]).
Второе условие записывается следующим образом:
меньше_1([X|_],[Y|_]):- X‹Y
Напомним, что аргументами предиката меньше_1 являются списки чисел, так что разрешается сравнивать элементы этих списков, используя предикат '‹'. Третье условие записывается следующим образом:
меньше_1([А|Х],[В|Y]:- А=В, меньше_1(Х,Y).
Наконец, два последних условия описывают ситуации, когда предикат ложен, т. е. не согласуется с базой данных, так что если мы не предусмотрим никаких соответствующих им фактов или правил, то при используемом механизме поиска в базе данных доказательство согласованности любого целевого утверждения, для которого эти условия справедливы, закончится неудачей. Собирая все правила вместе, получим
меньше(Х,Y):- name(X,L), name(Y,M), меньше _1(L,M).
меньше_1([], [_|_]).
меньше_1([X|_],[Y|_]):- Х‹Y.
меньше_1([P|Q], [R|S]):- P = R, меньше_1(Q,S).
Заметим, что третье правило для меньше_1 можно было бы записать более естественно так:
меньше_1([H|Q], [H|S]):- меньше_l(Q,S).
Упражнение 3.1. Подумайте, какое еще утверждение необходимо добавить к этому определению так, чтобы предикат был истинен и в том случае, когда два слова совпадают. В результате получится предикат, проверяющий, меньше или равен первый аргумент второму по алфавиту. Указание: обратите внимание на условие (4), приведенное выше, и вставьте утверждение, обрабатывающее это условие.
Упражнение 3.2. Почему в первом утверждении для предиката меньше_1 в качестве второго аргумента использован список [_|_]? Почему недостаточно использовать список [.]?
http://onlanta.ru/about/ «Онланта» – российский сервис-провайдер, предоставляющий услуги в области ИТ-аутсорсинга. |
Главная
Каталог файлов
