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

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

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

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

4.4. Проблемы, связанные с использованием отсечения

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

присоединить([],Х,Х):-!.

присоединить[А|В],С,[А|D]:– присоединить(В,С,D).

Когда мы имеем дело с целевыми утверждениями, подобными

присоединить([а,b,с],[d,е],Х)

и

присоединить([а,b,с],Х,Y)

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

присоединить(Х,Y,[а,b,с]).

Это целевое утверждение будет сопоставлено с заголовком первого правила, что даст

X = [], Y = [a,b,c]

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

Приведем другой интересный пример того, что может произойти, если правило, содержащее отсечение, используется незапланированным способом. Давайте определим предикат число_родителей,который дает информацию о том, сколько родителей имеет человек. Мы можем определить его следующим образом:

число_родителей(адам,0):-!.

число_родителей(ева,0) :-!.

число_родителей(Х,2).

то есть число родителей для адами еваравно 0, а для всех остальных равно 2. Если мы всегда используем наше определение предиката число_родителейдля определения числа родителей некоторого данного человека, то все идет нормально. Мы получаем

?– число_родителей(ева,Х).

X = 0; нет

?– число_родителей(джон,Х).

X = 2;

нет

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

?– число_родителей(ева,2).

да

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

число_родителей(адам,N):-!, N=0.

число_родителей(ева,N):-!, N=0.

число_родителей(Х,2).

или

число_родителей(адам,0).

число_родителей(ева,0).

число_родителей(Х,2):– X = адам, X = ева.

Конечно, эти определения по-прежнему не работают, если задать целевое утверждение вида

?– число_родителей(Х,Y).

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

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

ГЛАВА 5 ВВОД И ВЫВОД

В предыдущих главах фигурировал только один способ предоставления информации Пролог-программе – обращение к ней с вопросом. Точно так же единственный способ определить значение переменной на некотором этапе доказательства согласованности целевого утверждения с базой данных состоял в построении вопроса таким образом, чтобы Пролог-система напечатала ответ в виде «Х=ответ». В большинстве случаев такого непосредственного взаимодействия с программой посредством вопросов вполне достаточно, чтобы убедиться в том, что программа работает правильно. Однако во многих ситуациях удобно писать программу на Прологе так, чтобы она сама инициировала диалог с пользователем. Например, предположим, что имеется база данных, содержащая информацию о событиях, происходивших в мире в 16-м веке. Информация представлена в виде фактов, включающих дату события и его краткое содержание. Даты могут быть представлены как целые числа, а содержание – в виде списков атомов. Те атомы в списке, которые начинаются с прописной буквы, будут заключаться в одинарные кавычки, чтобы Пролог не принял их за переменные:

событие(1505, ['Начала','Евклида', переведены, на, латинский, язык]).

событие(1510, ['Начало', спора, между, 'Реучлином', и 'Пфефферкорном']).

 событие(1523, [Кристиан, 'II', покинул, 'Данию']).

. . .

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

?– событие(1505,Х).

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

Х=['Начала', 'Евклида', переведены, на, латинский, язык]

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

когда(Х,Y):– событие(Y,Z), принадлежит (X,Z).

?– когда(Кристиан,D).

D=1523

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

событие(1511, «Лютер посещает Рим»).

событие(1521, "Генри III провозглашен защитником веры").

событие(1524, "Умер Васко да Гама").

событие(1529, "Берквин сожжен в Париже").

событие(1540, "Возобновление войны с Турцией").

. . .

Такая форма представления удобнее для ввода, но посмотрим, что произойдет, если задаться вопросом

?– событие(1524,X).

В ответ Пролог напечатает непонятный список кодов ASCII, соответствующих литерам строки, являющейся значением переменной X! Хотя список литер легче ввести в систему, механизм 'вопрос – ответ' Пролога не позволяет получить ясный ответ. Было бы намного удобнее, если бы вместо того, чтобы обращаться к Прологу с подобными вопросами, можно было написать программу, которая вначале спрашивает, какая дата вас интересует, а затем выводит содержание соответствующего события на терминал. При этом названия событий можно было бы представлять в желаемом виде. Для выполнения задач подобного сорта в Прологе существует ряд встроенных предикатов, которые печатают свои аргументы на терминале. Имеются также предикаты, которые ожидают, пока пользователь введет текст с клавиатуры терминала, и присваивают переменной в качестве значения введенный текст. С помощью этих предикатов программа может взаимодействовать с вами, принимая от вас данные и печатая для вас результат. Когда программа ждет от вас данные, будем говорить, что она читаетили вводитданные. Точно так же, когда программа печатает некоторый результат, будем говорить, что она выводитрезультат. В этой главе мы описываем различные методы ввода и вывода данных. Один из рассматриваемых примеров связан с печатью кратких содержаний событий из базы данных исторических событий, а в заключение будет приведена программа, воспринимающая предложения на естественном языке и преобразующая их в список констант, который впоследствии может быть подвергнут обработке другими программами. Эта преобразующая программа, названная ввести,может использоваться как некий «модуль», с помощью которого можно создавать программы для анализа предложений на естественном языке. Программы, выполняющие такой анализ, обсуждаются в последующих главах, особенно в гл. 9.

5.1. Ввод и вывод термов

5.1.1. Вывод термов

Наиболее удобный способ напечатать некоторый терм на дисплее терминала состоит, по-видимому, в использовании встроенного предиката write.Если значением переменной Xявляется терм, то появление цели write(X)вызовет печать этого терма на дисплее. В случае если переменная Xнеконкретизирована, будет напечатано некоторое уникальное имя, которое состоит из одних цифр (например, '_253'). Однако если две переменные «сцеплены» в пределах одного и того же аргумента предиката write,то им будет соответствовать одна и та же переменная. Предикат writeнельзя согласовать вновь. Этот предикат выполняется лишь один раз, и всякая попытка вновь согласовать его заканчивается неудачей. Нельзя ли использовать writeдля вывода краткого содержания исторических событий в нашем примере? Вспомните, что строка литер в действительности представляется как список кодов литер. Если бы такой список был выведен с помощью предиката write,то он был бы напечатан как заключенная в квадратные скобки последовательность целых чисел, разделенных запятыми!

Прежде чем мы познакомимся с первым примером использования предиката write,нам нужно описать еще два предиката. Встроенный предикат nlприменяется для перехода на новую строку при печати данных на дисплее. Название « nl» образовано от «new line»(новая строка). Как и write,предикат nlвыполняется только один раз. Следующий встроенный предикат tabиспользуется для печати пробелов на экране дисплея. Целевое утверждение tab(X)выполняется только раз и вызывает перемещение курсора на Xпозиций вправо. Предполагается, что значение переменной X– целое число. Возможно, выбор имени tabне очень удачен, так как в действительности этот предикат не имеет ничего общего с табуляцией на обычных пишущих машинках или на дисплеях терминалов.

При печати списков полезно печатать элементы списка таким образом, чтобы получаемый результат можно было легко понять. Списки, которые содержат другие «вложенные» списки, читать особенно трудно, тем более когда внутри них содержатся структуры. Определим предикат рр( pretty print– «хорошая печать») так, что целевое утверждение рр(Х, Y)печатает в удобном виде список, присвоенный в качестве значения переменной X. Смысл второго аргумента предиката рр будет объяснен позднее. Каждый автор программы, реализующей хорошую печать, имеет свой собственный стиль представления списков. Мы воспользуемся методом, при котором элементы списка печатаются в колонку. Если элемент сам является списком, то его элементы печатаются в колонке, которая смещена вправо по отношению к основной колонке. Такая форма представления по существу совпадает с рассмотренным в гл. 3 способом изображения списков. Например, список [1,2,3] «хорошо» печатается в следующем виде:

1

2

3

а список [1,2,[3,4],5,6]печатается как

1

2

   3

   4

5

6

Заметим, что мы решили не печатать квадратные скобки и запятые, разделяющие элементы списка. Если элемент списка является структурой, то он будет обрабатываться точно таким же способом, что и атом. При таком подходе нам не нужно «раскрывать организацию» структур, чтобы «хорошо» напечатать их компоненты. Следующая программа реализует определенный нами способ хорошей печати:

pp([H|T],I):-!, F is I+3, pp(H,F), ppx(T,F),nl.

pp(X,I):– tab (I), write(X), nl.

ppx([],_).

ppx([H|T],I):– pp(H,I), ppx(T,I).

Теперь видно, что второй аргумент предиката ррвыполняет функции счетчика колонок. Целевое утверждение «верхнего уровня» для печати некоторого списка могло бы выглядеть как

… PP(L,0),…

при этом начальное значение счетчика колонок устанавливается равным 0. Первое утверждение предиката рробрабатывает специальный случай – когда первый аргумент является списком. Если это так, то необходимо установить новую колонку, увеличив счетчик на некоторое число (здесь 3). Затем мы должны отпечатать с помощью ррголову списка, так как она сама может оказаться списком. Далее нужно напечатать все элементы хвоста списка, располагая каждый элемент в той же самой колонке. Это как раз и выполняет предикат ррх.А предикат ррхиспользует рр,поскольку каждый элемент может быть списком. Второе утверждение предиката ррсоответствует случаю, когда нам необходимо напечатать что-либо, не являющееся списком. Мы просто делаем отступ на указанное число позиций, используем предикат writeдля печати терма и nlдля перехода на новую строку. Первое утверждение для рртакже заканчивается nl, поскольку печать каждого списка должна завершиться переходом на новую строку.

Отметим, что в предикате ррмы поместили утверждение для обработки особого случая перед утверждением, обрабатывающим выход на граничное условие. Если бы мы поместили второе утверждение перед первым утверждением, то тогда список, являющийся первым аргументом предиката рр, был бы сопоставлен с переменной Xв заголовке второго правила. В результате получилось бы, что список был бы просто напечатан как единое целое без удобств и «хорошей» печати. Поэтому мы хотим, чтобы случай, когда аргумент является списком, проверялся первым. Именно поэтому мы выбрали такой порядок утверждений. Второе утверждение используется как правило-ловушка. Другой способ добиться такого же результата состоит в том, чтобы правило, осуществляющее проверку граничного условия, поставить первым и включить в его тело подцель, которая не выполняется, если первый аргумент является списком:

рр(Х,I):– not(список(Х)), tab(I), write(X), nl.

pp([H|T],I):– J is I+3, pp(H,J), ppx(T,J), nl.

/*ppx как и ранее */

список([]) список([_|_]).

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

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

phh([]):– nl.

phh([H|T]):– write(H), tab(l), phh(T).

Так, при следующем запросе было бы напечатано каждое событие, в содержании которого встречается «Англия»:

?– событие(_,L), принадлежит('Англия',L), phh(L).

Обратим внимание на использование механизма возврата для поиска в базе данных. Каждый раз, когда для целевого утверждения принадлежитне находится сопоставление, делается попытка найти новое сопоставление для целевого утверждения событие. В результате в поисках событий, в которых упоминается атом «Англия», будет целиком просмотрена сверху вниз вся база данных.

Предикат writeпечатает термы с некоторым «пониманием» того, что он делает, так как он учитывает, какие объявления операторов были сделаны. Например, если мы объявили некоторый атом как инфиксный оператор, то терм, имеющий этот атом в качестве функтора структуры с двумя аргументами, будет напечатан таким образом, что атом окажется между аргументами. Существует еще один предикат, который выполняет те же действия, что и write, за тем исключением, что он игнорирует все сделанные объявления операторов. Этот предикат называется display. Различие между writeи displayиллюстрирует следующий пример:

?– write(a+b*c*c),nl, display(a+b*c*c).

a+b*c*c

+(a,*(*(b,c),c))

да

Обратим внимание на то, что предикат displayобработал атомы + и * – точно так же, как и любые другие атомы, которые он печатает в этом терме. Как правило, нежелательно, чтобы печатаемые структуры выглядели подобным образом, так как наличие операторов обычно делает более понятными при чтении как вводимые, так и выводимые программой данные. Однако иногда, когда мы не совсем уверены в том, что знаем, каков приоритет операторов, использование предиката displayможет оказаться очень полезным.

5.1.2. Ввод термов

Предикат readчитает следующий терм, набираемый пользователем на клавиатуре терминала. После вводимого терма должны следовать точка '.' и непечатаемая литера, такая как пробел или RETURN. Если переменная Xне конкретизирована, то целевое утверждение read(X)приведет к вводу следующего терма и этот терм будет присвоен в качестве значения переменной X, Как и другие предикаты ввода-вывода, с которыми мы уже сталкивались, предикат readвыполняется лишь один раз. Если в момент рассмотрения целевого утверждения read(X)его аргумент конкретизирован, то попытка доказать согласованность этого целевого утверждения с базой данных вызовет чтение следующего терма и попытку сопоставления его с аргументом, заданным в read.Согласованность цели с базой данных зависит от результата этого сопоставления.

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

обращение:-

 phh(['Какая',дата,вас,'интересует?'!),read(D),coбытиe(D,S),pph(S).

Мы определили предикат обращение,не имеющий аргументов. Когда мы обращаемся к системе с вопросом

?– обращение.

Пролог напечатает

Какая дата вас интересует?

 и будет ждать ответа. Предположим, что мы ввели с клавиатуры

1523.

Обратите внимание на то, что после 1523 необходимо ввести точку, так как этого требует предикат read.И, как обычно, мы должны нажать клавишу RETURN, чтобы сообщить ЭВМ, что мы закончили ввод строки текста. После этого Пролог ответит

Кристиан II покинул Данию

Обратите внимание, что в первой строке тела правила обращениеиспользуется предикат phh,хотя в этом случае печатается не краткое содержание исторического события. Это просто показывает, что phhвполне подходит для печати произвольногосписка атомов независимо от того, откуда он взялся.

5.2. Ввод и вывод литер

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

5.2.1. Вывод литер

Если переменная Xимеет в качестве значения некоторую литеру (ее код ASCII), то эта литера будет напечатана при обработке целевого утверждения put(X).Предикат putвсегда выполняется и не может быть пересогласован (это приводит к неудаче). В качестве «побочного эффекта» putпечатает литеру на дисплее терминала. Например, мы можем напечатать слово helloдовольно необычным способом:

?– put(104),put(101),put(108),put(108),put(111).

hello

Результатом такой конъюнкции целей является печать Прологом литер h, е, l, l, онепосредственно под вопросом, как показано выше. Мы уже видели, что имеется возможность начать печать текста с начала следующей строки, использовав для этого предикат без аргументов nl. В действительности nl «печатает» некоторые управляющие литеры, что вызывает перевод курсора на дисплее терминала на начало следующей строки. Вопрос

?– put(104),put(105),nl,put(116),put(104),put(101),put(114), put(1O1).

вызвал бы следующую печать:

hi

there

Другой предикат, с которым мы уже познакомились, – это tab(X),печатающий Xпробелов (ASCII код равен 32). Разумеется, переменной Xдолжно быть присвоено целое число. Отметим, что предикат tab(X)мог бы быть определен так:

tab(0):– !.

tab(N):– put(32), M is N-1, tab(M).

Теперь мы можем определить предикат, который мы назовем печать_строки. Если значением переменной Xявляется список кодов литер (строка), то целевое утверждение печать_строкинапечатает этот список (строку), используя putдля печати каждого элемента списка. Как и во всех подобных программах, граничным условием является появление пустого списка. Это условие мы и используем для завершения рекурсии. При непустом списке с помощью putпечатается голова списка, а затем используем печать_строки– хвост списка:

печать_строки([]).

печать_строки([Н|Т]):– put(H), печать_строки(Т).

?– печать_строки(«Чарлз V отрекся от престола в Брюсселе»).

Чарлз V отрекся от престола в Брюсселе

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