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

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