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

Теперь следует сказать, что значит «заменить» одно слово на другое. Это может быть сделано при наличии в базе данных фактов вида заменить(Х, Y), означающих, что слово Xможет быть заменено словом Y. В конце базы данных следует поместить факт-«ловушку», так как если слово не заменяется другим словом, то его следует заменить самим собой. Если сейчас не совсем понятно назначение «ловушки», то позднее, когда мы объясним, как работает программа, это должно стать ясным.

Роль такого факта-ловушки выполняет факт заменить(Х,Х),который обозначает, что слово Xзаменяется самим собой. Ниже приведена база данных, обеспечивающая указанные выше замены слов:

заменить(уоu,i).

заменить(аrе, [am,not]).

заменить(french,german).

заменить(dо,nо)

заменить(Х,Х). /* это факт-ловушка */

Заметим, что фраза «am not»представлена как список, так что она входит в факт как один аргумент.

Теперь можно перевести приведенный выше текст на псевдо-Прологе в настоящую программу на Прологе, помня, что запись [А|В]обозначает список, имеющий голову А и хвост В. Мы получаем нечто подобное следующему:

преобразовать([],[]).

преобразовать([Н|T],[X|Y]):-заменить(Н, X), преобразовать(Т,Y).

Первое утверждение в приведенной процедуре проверяет, является ли аргумент пустым списком. Оно же проверяет окончание списка. Как? Рассмотрим это на примере:

?- преобразовать([уоu,are,a,computer],Z).

Этот вопрос был бы сопоставлен с основным правилом для преобразовать,при этом переменная Нполучила бы значение you, а переменная Т– значение [are,a,computer]. Затем была бы рассмотрена подцель заменить (you,Х), найден подходящий факт и переменная Xстала бы равной i. Так как Xявляется головой выходного списка (в целевом утверждении преобразовать), то первое слово в выходном списке есть i. Далее, поиск соответствия для подцели преобразовать ([are, a, computer], Y)привел бы к использованию того же правила. Слово are в соответствии с имеющейся базой данных заменяется на список [am,not], и генерируется другая подцель с предикатом преобразовать– преобразовать([а,computer], Y). Ищется факт заменить(а,X), но так как в базе данных нет факта заменить, первый аргумент которого равен а, то будет найден факт-ловушка, расположенный в конце базы данных, заменяющий ' а' на ' а'. Правило преобразовать вызывается еще раз с computerв качестве головы входного списка и пустым списком[] в качестве хвоста входного списка. Как и ранее, заменить(computer, X)сопоставляется с фактом-ловушкой. Наконец, преобразовать вызывается с пустым списком на месте первого аргумента, и происходит сопоставление с первым утверждением предиката преобразовать. Результатом является пустой список, который заканчивает преобразованное предложение (напомним, что список заканчивается пустым хвостом). В заключение Пролог отвечает на вопрос, печатая

Z = [i,[am,not], a, computer]

Отметим, что фраза [am,not]появляется в списке точно в таком же виде, как она была в него вставлена.

Теперь должны быть ясны причины появления в базе данных факта преобразовать ([],[])и факта-ловушки заменить (Х,Х). Факты, подобные этим, часто включаются в программу, когда требуется проверить выполнение граничных условий. Из приведенного выше объяснения должно быть ясно, что выход на граничные условия происходит в случае, когда входной список становится пустым и когда оказываются просмотренными все факты для предиката заменить. В обоих случаях выхода на граничные условия необходимо выполнить определенные действия. В случае когда входной список становится пустым, необходимо завершить выходной список (вставив пустой список в его конец). Если просмотрены все факты для предиката заменить, но при этом не обнаружен факт, содержащий данное слово, то это слово должно остаться неизменным (путем замены его самим собой).

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).

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