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

Автор книги: У. Клоксин

Соавторы: К. Меллиш
сообщить о нарушении

Текущая страница: 6 (всего у книги 26 страниц)

3.4. Пример: преобразование предложений

Рассмотрим программу на Прологе, которая в ответ на введенное с терминала предложение (на английском языке) печатает другое предложение, представляющее преобразованное исходное предложение. Эта программа для «ответов» программисту могла бы поддерживать следующий диалог:

Вы: you are a computer (Вы – ЭВМ)

Пролог: i am not a computer (Я – не ЭВМ)

Вы: do you speak french (Вы говорите по-французски?)

Пролог: no i speak german (Нет, я говорю по-немецки)

Хотя этот диалог может показаться натянутой, но все же осмысленной беседой, очень легко написать программу, выполняющую свою «часть» диалога. Для этого достаточно просто последовательно выполнять следующие действия:

1. Ввести предложение, набранное пользователем на терминале.

2. Заменить каждое вхождение слова youна слово i.

3. Аналогичным образом заменить areна am not.

4. Заменить frenchна german.

5. Заменить doна nо.

Если применить данную схему преобразования кнадлежащим образом подобранным предложениям, подобным использованным в приведенном выше диалоге, то получим осмысленные преобразованные предложения. Однако эта схема применима не ко всем предложениям. Например;

Вы: i do like you (я действительно люблю вас)

Пролог: i no like i (я не люблю себя)

Но если простая программа уже написана, то впоследствии ее можно модифицировать так, чтобы она справлялась и с предложениями, подобными приведенному.

Программа на Прологе, преобразующая одно предложение английского языка в другое, может быть реализована следующим образом. Прежде всего необходимо осознать, что имеется отношение между исходным предложением и преобразованным. В связи с этим нам следует определить предикат, называемый преобразовать. Преобразовать(Х, Y)означает, что предложение Xможет быть преобразовано в предложение Y. Предложения Xи Yудобно представлять в виде списков атомов, обозначающих слова, так что предложения могут быть записаны следующим образом: [this,is,a, sentence](это некоторое предложение). Определив предикат преобразовать,мы могли бы обращаться к Прологу с вопросами вида

?– преобразовать([dо,you,know,french],X). (Знаете ли вы французский)

на что Пролог отвечал бы

X=[no,i,know,german] (нет, я знаю немецкий).

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

Так как аргументами предиката преобразоватьявляются списки, то прежде всего следует рассмотреть, что произойдет, если исходный список пустой. В этом случае мы скажем, что пустой список преобразуется в пустой список:

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

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

1. Заменить голову входного списка соответствующим словом и поместить это слово в выходной список в качестве головы.

2. Преобразовать хвост входного списка и сделать его хвостом выходного списка.

3. Если мы достигли конца входного списка, то к выходному списку больше ничего добавлять не надо, и мы можем завершить выходной список пустым списком [].

Переводя это на язык, более близкий к Прологу, можно сказать:

Преобразование списка с головой  H и хвостом  T дает список с головой X и хвостом Y, если замена слова  H дает слово X, а преобразование списка  T дает список Y.

Теперь следует сказать, что значит «заменить» одно слово на другое. Это может быть сделано при наличии в базе данных фактов вида заменить(Х, 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).

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

меньше(Х,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. Так как при каждом обращении к правилу удаляется голова списка, являющегося первым аргументом, то постепенно этот список будет исчерпан и станет пустым, так что произойдет выход на граничное условие.

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

Предположим, что мы работаем на заводе, выпускающем велосипеды, и нам необходимо хранить спецификацию деталей велосипеда. Для того чтобы собрать велосипед, надо знать, какие детали заказать поставщикам. Каждая деталь велосипеда может состоять из более мелких элементов – поддеталей, например каждое колесо имеет спицы, обод и ступицу. Более того, ступица может состоять из оси и шестеренок. Давайте рассмотрим базу данных, организованную в виде дерева, которая позволит нам делать запросы о деталях, необходимых для изготовления некоторой части велосипеда. В одной из следующих глав предложенная здесь программа будет улучшена, с тем чтобы позволить вычислять, сколько экземпляров каждой детали нам потребуется.

Имеются два типа объектов, которые используются для изготовления велосипеда. Это узлыи детали.Каждый узел состоит из некоторого числа деталей, подобно тому как колесо состоит из спиц, обода и ступицы. Детали не имеют еще более мелких частей – они просто соединяются друг с другом, образуя узлы.

Можно представить детали как факты следующим образом:

деталь(обод). деталь(спица).

деталь(задняя_рама). деталь(руль).

деталь(шестерни). деталь(болт).

деталь(гайка). деталь(вилка).

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

узел(велосипед, [колесо, колесо, рама]).

Ниже представлена база данных узлов, необходимых для нашего упрощенного велосипеда:

узел(велосипед, [колесо,колесо,рама]).

узел(колесо, [спица,обод,ступица]).

узел(рама, [задняя_рама, передняя_рама]).

узел(передняя_рама, [вилка,руль]).

узел(ступица, [шестерни,ось]).

узел(ось, [болт,гайка]).

Заметим, что это частное множество утверждений неполностью описывает велосипед. Мы не делаем различия между передней и задней ступицами – обе имеют шестерни! Цепь и педали отсутствуют, и негде сидеть велосипедисту. Не указано также, как соединять детали друг с другом. Это просто перечисление некоторого числа требуемых деталей.

Теперь мы готовы написать программу, которая для заданной части перечислит все детали, необходимые для ее сборки. Если часть, которую мы хотим собрать, является деталью, то для нее ничего больше не требуется. Однако если мы хотим собрать некоторый узел, то необходимо применить этот процесс к каждой составной части узла. Определим предикат часть (X, Y),где X– имя части, a Y– список деталей, необходимых для ее сборки. В первой версии программы мы не будем рассматривать вопрос о количестве деталей каждого типа, необходимых для сборки. Более полная программа будет представлена в гл. 7.

Выход на граничное условие происходит, когда Xявляется деталью. В этом случае Xпросто возвращается в качестве элементарного списка:

часть(Х, [X]):– деталь(Х).

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

часть(Х,Р):– узел(Х,Подчасти),

список_чаcтей(Подчасти, Р).

Предикат список_частейберет список частей (из второго аргумента факта узел, представленного выше) и применяет предикат частьк каждой части в списке. После вызова самого себя, необходимого для обработки хвоста списка, предикат список_частейдолжен склеить полученные списки вместе, используя предикат присоединить:

список_частей([Р|Хвост], Полный_список):– часть(Р,Части_головы)

список_частей(Хвост,Части_хвоста)

присоединить(Части_головы, Части_хвоста, Полный_список)

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

Существуют две идеи, указывающие, как использовать предикат частьдля генерации предложений на английском языке. Во-первых, предложения могут быть представлены в виде иерархических структур: предложение имеет части группа_существительногои группа_глагола; группа_существительногосостоит из определенияи существительногои т. д. Так что любая простая грамматика может быть выражена на языке «частей». Во-вторых, предикат список_частейвсегда обрабатывает элементы списка, представленного его первым аргументом, в порядке слева направо, и его результат (второй аргумент) накапливается в том же порядке. Два указанных свойства предиката частьпоказывают, что можно использовать тот же метод для генерации предложений по некоторой грамматике. Типичный «узел» в этой грамматике мог бы выглядеть так:

узел(предложение,[группа_существительного,группа_глагола]).

узел(группа_существительного,[определение,существительное]).

узел(определение,[thе]).

узел(существительное, [clergyman]).

узел(существительное,[motorcar]).

А слова используемой лексики были бы определены как «детали»:

деталь(сlеrgуmаn).

деталь(motorcar)

Теперь у вас может возникнуть желание поэкспериментировать с таким подходом к генерации предложений. Для этого необходимо составить разумную грамматику и словарь. Убедитесь сами, что измененная таким образом программа будет выдавать все допускаемые грамматикой предложения, которые можно построить по заданным грамматике и словарю. Всякий раз, выдав очередное предложение, Пролог будет ожидать, когда вы введете точку с запятой, указывающую ему, что необходимо выполнить возврат для получения следующего предложения.

На приведенном здесь примере не заканчивается обсуждение проблемы обработки текстов на естественном языке в этой книге. Глава 9 полностью посвящена более детальному рассмотрению такого применения Пролога.