У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
3.5. Пример: упорядочение по алфавиту
Как мы видели в гл. 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 в качестве второго аргумента использован список [_|_]? Почему недостаточно использовать список [.]?
3.6. Использование предиката присоединить и спецификация деталей
Предикат присоединить, обрабатывающий списки, используется для создания нового списка, являющегося результатом соединения двух других списков. Например, верен следующей факт:
присоединить([а,b,с], [3,2,1], [а,b,с,3,2,1]).
Предикат присоединить наиболее часто используется для создания нового списка в результате конкатенации двух других списков, как в следующем примере:
?- присоединить ([alpha,beta],[gamma,delta],X).
X=[alpha, beta, gamma, delta]
Но он может также использоваться и другим способом;
?- присоединить(Х,[b,c,d],[a,b,c,d]). Х=[а]
Предикат присоединить имеет следующее определение;
присоединить([],L,L).
присоединить([Х|L1],L2,[Х|L3]):- присоединить (L1,L2,L3).
Выход на граничное условие происходит, когда первый аргумент является пустым списком. Любой список, присоединенный к пустому списку, дает тот же самый список. Во всех других случаях будет выполняться второе правило, смысл которого можно описать словами следующим образом:
1. Первый элемент первого списка (X) всегда будет и первым элементом третьего списка.
2. Хвост третьего аргумента (L3) всегда будет представлять результат присоединения второго аргумента (L2) к хвосту первого списка (L1).
3. Для присоединения одного списка к другому, о чем шла речь в пункте 2, необходимо использовать предикат присоединить.
4. Так как при каждом обращении к правилу удаляется голова списка, являющегося первым аргументом, то постепенно этот список будет исчерпан и станет пустым, так что произойдет выход на граничное условие.
В дальнейших примерах будут встречаться ссылки на предикат присоединить с необходимыми дополнительными пояснениями. В последующих главах мы обсудим различные свойства и применения этого предиката. Но сначала давайте применим его в другом простом примере рекурсии.
Предположим, что мы работаем на заводе, выпускающем велосипеды, и нам необходимо хранить спецификацию деталей велосипеда. Для того чтобы собрать велосипед, надо знать, какие детали заказать поставщикам. Каждая деталь велосипеда может состоять из более мелких элементов – поддеталей, например каждое колесо имеет спицы, обод и ступицу. Более того, ступица может состоять из оси и шестеренок. Давайте рассмотрим базу данных, организованную в виде дерева, которая позволит нам делать запросы о деталях, необходимых для изготовления некоторой части велосипеда. В одной из следующих глав предложенная здесь программа будет улучшена, с тем чтобы позволить вычислять, сколько экземпляров каждой детали нам потребуется.
Имеются два типа объектов, которые используются для изготовления велосипеда. Это узлы и детали. Каждый узел состоит из некоторого числа деталей, подобно тому как колесо состоит из спиц, обода и ступицы. Детали не имеют еще более мелких частей – они просто соединяются друг с другом, образуя узлы.
Можно представить детали как факты следующим образом:
