not(P):- call(P),!, fail.
not(P)
Определение предиката notсодержит обращение к аргументу Pкак к целевому утверждению с использованием встроенного предиката call.Предикат callпросто интерпретирует свой аргумент как целевое утверждение и пытается доказать его согласованность. Мы хотим, чтобы первое правило применялось в тех случаях, когда согласуется Pс базой данных, а в противном случае должно применяться второе правило. Таким образом, мы говорим, что если Пролог может согласовать call(P),то он должен прекратить на этом правиле доказательство целевого утверждения not.Другая возможность имеет место, если Пролог не может согласовать call(P).В этом случае он никогда не дойдет до отсечения. Так как доказательство согласованности call(P)потерпело неудачу, то происходит возврат, и Пролог обнаруживает второе правило. Следовательно, доказательство согласованности целевого утверждения not(P)закончится успешно в случае, когда Pнедоказуемо.
Как и в первом случае применения отсечения, мы можем заменить любое употребление комбинации «отсечение- fail»использованием предиката not.Такая замена требует несколько большей реорганизации программы, чем ранее, но при этом не приводит к потере эффективности. Если бы мы стали с этой целью переписывать нашу программу для предиката средний_ налогоплательщик,то следовало бы начать ее примерно так:
средний_налогоплателыцик(X):-
nоt(иностранец(X)),not((супруга(X,Y),доход(Y,Доход), Доход›3000)), доход(Х, Доход1),…
Обратите внимание на то, что в этом примере конъюнкция целей, являющаяся аргументом not,заключена в скобки. Для того чтобы однозначно показать, что запятые разделяют цели в конъюнкции (а не аргументы предиката not),мы заключили аргумент предиката notв дополнительные круглые скобки.
Теперь мы можем рассмотреть последнюю основную область применения отсечения в программах на Прологе – завершение последовательности порождения и проверки вариантов. Очень часто программа состоит из частей, соответствующих следующей общей модели. Имеется последовательность целей, которые могут быть согласованы множеством различных способов и которые порождают много возможных решений при возврате. Кроме того, имеются цели, проверяющие приемлемость порожденных решений для последующего использования. Если поиск сопоставлений для этих целевых утверждений закончится неудачей, то возврат приведет к тому, что будет предложено новое решение. Новое решение будет подвергнуто проверке на пригодность и так далее. Процесс завершится, либо когда будет порождено приемлемое решение (успех), либо когда нельзя больше найти решений (неудача). Мы можем назвать «генератором» целевые утверждения, которые порождают все возможные альтернативы, а целевые утверждения, которые проверяют пригодность решения, - «контролером». Давайте рассмотрим пример такой программы. Приводимый ниже фрагмент мог бы быть частью программы, играющей в крестики-нолики. Эта программа использует встроенные предикаты varи arg,которые подробно рассмотрены в гл. 6.
вынужденный ход(Доска,K):- линия(Клетки), угроза(Клетки,Доска,K),!.
линия([1,2,3]).
линия([4,5,6]).
линия([7,8,9]).
линия([1,4,7]).
линия([2,5,81).
линия([3,6,9]).
линия ([1,5,9]).
линия([3,5,7]).
угроза([X,Y,Z],B,X):- пусто(Х,В), крестик (Х,В), крестик(Z,B).
угроза([X,Y,Z],B,Y):- пусто(Y,B), крестик (Х,В), крестик(Z,B).
угроза([X,Y,Z],B,Z):- пусто(Z,B), крестик(Х,В), крестик(Y,B).
пусто(К,Доска):- arg(K,Дocкa,C), var(C).
крестик(К,Доска):- arg(K,Дocкa,C), nonvar(C), C=X.
нолик(К,Доска):- arg(К,Доска,С), nonvar(C), С=0.
Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок - символ X. Цель игры - расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:
Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат вынужденный_ход используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок Xможет выиграть следую- следующим ходом. Например, в позиции
Игрок 0вынужден поставить 0в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7. Программа работает, пытаясь найти линию, две клетки которой заполнены крестиками, а третья – пустая. Если такая линия имеется, то игрок 0 вынужден сделать ход, поставив нолик в пустую клетку. В утверждении для предиката вынужденный_ходцель
линия(Клетки)
служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:
угроза(Клетки,Доска,К)
В этом целевом утверждении переменная Доскаиспользуется для представления текущей позиции на доске (т. е. какие клетки заняты и какими символами), а переменная К получает в качестве значения номер клетки, в которой игрок 0 должен поставить нолик (при условии что доказательство этой цели завершается успешно).
Основная идея программы очень проста – предикат линиявыдает линию, а затем предикат угрозапроверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения вынужденный_ходзаканчивается успешно. Иначе инициируется возврат, и предикат линияпредполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат линияне может более порождать линии, то доказательство согласованности целевого утверждения вынужденный_ходзакончится неудачей (вынужденных ходов нет).
Теперь рассмотрим, что происходит, если эта программа, являясь частью некоторой большей системы, успешно находит вынужденный ход. Переменная К получит в качестве значения номер клетки, в которой должен быть сделан ход, и эта информация будет использована где нибудь в другом месте в программе. Предположим, что в дальнейшем где-то в программе имеет место неудача при доказательстве согласованности некоторого утверждения и что Пролог в конце концов пытается вновь согласовать целевое утверждение вынужденный_ход.Тогда предикат линияначнет порождение новых возможных линий, которые должны быть проверены. Это бессмысленно, так как нет никакой пользы в том, чтобы искать альтернативный вынужденный ход. Если найден один из таких ходов, то мы не можем сделать ничего лучше, чем сделать этот ход – неудача при его осуществлении гарантировала бы проигрыш игры. В большинстве случаев, однако, альтернативных вынужденных ходов не будет, и при поиске сопоставления для цели вынужденный_ходбудут бесполезно просматриваться все неопробованные линии, прежде чем попытка доказать согласованность цели не закончится неудачей. Однако в случае альтернативных ходов известно, что даже если имеется другое решение, оно не может быть использовано без возникновения проблем с использованием первого решения Мы можем предотвратить потерю времени Прологом на поиск различных вынужденных ходов, поместив отсечение в конце соответствующего утверждения. Это приведет к замораживанию последнего успешного решения для предиката линия.Введение отсечения равносильно следующему заявлению: «если ищутся вынужденные ходы, то важно найти только первое решение».
Чтобы понять такое использование отсечения, необходимо лишь рассмотреть общую структуру этой программы. Однако некоторые из деталей также представляют интерес. В программе предполагается, что игровую доску можно описать с помощью структуры, состоящей из девяти компонент. Каждая компонента представляет содержимое клетки с соответствующим номером. Таким образом, в любой момент времени содержимое четвертой клетки доски может быть получено путем выборки четвертого аргумента структуры, представляющей текущую позицию на доске (для этого мы используем встроенный предикат arg). Если клетка ничем не заполнена, то переменная будет неконкретизи-рованной; иначе ее значение равно одному из атомов Оили X. Мы используем предикаты varи nonvarдля того, чтобы определить, занята клетка или нет.
Давайте рассмотрим другой пример программы, работающей по методу «порождения и проверки». Вернемся к вопросу о делении целых чисел, рассмотренному в разд. 2.5. Большинство Пролог-систем обеспечивают эту возможность автоматически, но здесь представлена программа для целочисленного деления, которая использует лишь операции сложения и умножения.
разделить(N1,N2,Результат):-
целое_число(Результат), Произведение_1 is Результат*N2, Произведение_2 is (Результат + 1)*N2, Произведение_1 =‹ N1, Произведение_2›N1,!.
Это правило использует предикат целое_число(как он определен ранее) для порождения числа Результат,которое является результатом «деления» N1на N2. Так, например, результат деления 27на 6равен 4, так как 4Ч6меньше или равно 27, а 5Ч6больше чем 27.
Приведенное правило использует предикат целое_числокак «генератор», а остальные целевые утверждения выполняют функцию соответствующего «контролера». Мы заранее знаем, что если заданы конкретные значения N1и N2, то предикат разделить(N1, N2, Результат)может иметь значение «истина» лишь для одного возможного значения Результат.Несмотря на то что целое_числоможет породить бесконечное множество кандидатов, лишь для одного из них будут выполняться последние тесты. Мы можем явно выразить это наше знание, вставив отсечение в конце правила. Словами это можно сказать так: «если нам удалось породить число Результаттакое, что оно успешно проходит тесты для числа, являющегося результатом деления, то нет надобности пытаться получить другое решение». В частности, нет необходимости пересматривать какой-либо из выборов, которые были сделаны при поиске правил для разделить, целое_числои так далее. Мы нашли единственное решение, и нет оснований искать другое. Если бы мы "не" добавили отсечение, то любой возврат в конце концов снова инициировал бы поиск альтернатив для целое_число.Так что продолжилось бы порождение значений для переменной Результат.Ни одно из новых значений не было бы правильным результатом деления, и, таким образом, генерация целых чисел продолжалась бы до бесконечности.
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. Ввод и вывод термов
Наиболее удобный способ напечатать некоторый терм на дисплее терминала состоит, по-видимому, в использовании встроенного предиката 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). Затем мы должны отпечатать с помощью ррголову списка, так как она сама может оказаться списком. Далее нужно напечатать все элементы хвоста списка, располагая каждый элемент в той же самой колонке. Это как раз и выполняет предикат ррх.А предикат ррхиспользует рр,поскольку каждый элемент может быть списком. Второе утверждение предиката ррсоответствует случаю, когда нам необходимо напечатать что-либо, не являющееся списком. Мы просто делаем отступ на указанное число позиций, используем предикат