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

Роль такого факта-ловушки выполняет факт заменить(Х,Х), который обозначает, что слово 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. Очередная литера в первом слове предшествует в алфавите соответствующей литере во втором слове. Например, меньше (слово,слон). Буква 'в' в слове слово предшествует в алфавите букве 'н' в слове слон. В этом случае предикат меньше истинен.