Упражнение 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 полностью посвящена более детальному рассмотрению такого применения Пролога.
ГЛАВА 4. ВОЗВРАТ И ОТСЕЧЕНИЕ
Давайте подытожим всю информацию, которую мы почерпнули в гл. 1 и 2 о том, что может произойти с целевым утверждением (целью).
1. Может иметь место попытка доказать согласованностьцелевого утверждения с базой данных. В процессе доказательства база данных просматривается, начиная с ее вершины. При этом возможны две ситуации:
(а) Может быть найден факт (или заголовок правила), сопоставимый с целевым утверждением. В этом случае мы говорим, что произошло сопоставлениецели с утверждением (фактом или правилом) в базе данных. Это место отличается в базе данных маркером и конкретизируются (присваиваются значения) соответствующие переменные, если они не были конкретизированы ранее. Если произошло сопоставление с правилом, то прежде всего необходимо попытаться доказать согласованность подцелей, вводимых этим правилом. Если цель согласуется с базой данных, то предпринимается попытка согласовать следующее целевое утверждение. В используемых нами диаграммах это будет цель, указанная в следующем, нижнем прямоугольнике, на который указывает стрелка. Если исходная цель входит в конъюнкцию, то это будет цель, расположенная в программе непосредственно справаот исходной цели.
(б) В базе данных нет факта (или заголовка правила), сопоставимого с целевым утверждением. В этом случае мы говорим, что попытка доказать согласованность целевого утверждения потерпела неудачу(цель не согласуется с базой данных). Тогда будет предпринята попытка (см. п.2) вновь доказать согласованностьцелевого утверждения, указанного в прямоугольнике, расположенном выше стрелки. Если исходное целевое утверждение входит в конъюнкцию, то это будет целевое утверждение, расположенное в программе непосредственно слева от рассматривавшегося целевого утверждения.
2. Мы можем сделать попытку вновь доказать согласованностьцелевого утверждения с базой данных. Для этого прежде всего необходимо попытаться вновь согласовать каждую из его подцелей, при этом стрелка возвращается в некоторую исходную позицию, поднимаясь вверх по странице. Если ни одна из подцелей вновь не может быть согласована каким-либо подходящим образом, делается попытка найти альтернативное утверждение для самой исходной цели. В этом случае необходимо вернуть в исходное (неопределенное) состояние каждую переменную, конкретизированную при выборе предыдущего утверждения. Эти действия мы называем «уничтожением» результатов, полученных ранее при доказательстве согласованности целевого утверждения. Затем возобновляется просмотр базы данных, но начинается этот просмотр с места, отмеченного маркером данной цели. Как и ранее, эта новая цель, выбранная при возврате, может оказаться либо согласованной, либо несогласованной с базой данных. При этом будет иметь место либо шаг (а), либо шаг (б).
В этой главе процесс возврата будет рассмотрен более подробно. Кроме того, будет рассмотрен специальный механизм – «отсечение», который может быть использован в программах на Прологе. Отсечение позволяет указывать, какие из ранее сделанных выборов альтернатив не следует более пересматривать.
4.1. Порождение множественных решений
Простейшая ситуация, в которой некоторое множество фактов допускает несколько ответов на вопрос, возникает, когда в этом множестве имеется несколько фактов, сопоставимых с вопросом. Например, имеются следующие факты:
отец(мэри, джордж).
отец(джон, джордж).
отец(сью,гарри).
отец(джордж,эдуард).
в которых отец(X, Y)обозначает, что Yявляется отцом X. Вопрос
?- отец(X,Y).
имеет несколько возможных ответов. Если мы будем вводить после каждого ответа точку с запятой, то Пролог выдаст следующие ответы:
X = мэри, Y = джордж;
X = джон, Y = джордж;
X = сью, Y = гарри;
X = джордж, Y = эдуард.
Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отеци печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом
?- отец(_,X).
(для каких X верно то, что X является отцом),то мы получим
Х=джордж;
Х=джордж;
Х=гарри;
Х=эдуард.
при этом ответ джорджповторен дважды, так как Джордж является отцом как Мэри, так и Джона. Если Пролог может сделать одно и то же двумя различными способами, то он рассматривает это как два различных решения.
Повторный просмотр выполняется точно таким же способом, если выбор среди альтернатив происходит на более глубоком уровне обработки. Например, для определения отношения «одним из детей Xявляется Y» могло бы быть использовано правило
ребенок(Х,Y):- отец(Y,X).
Тогда вопрос
?- ребенок(Х,Y).
дал бы
X = джордж, Y = мэри;
X = джордж, Y=джон;
X = гарри, Y = сью;
X = эдуард, Y = джордж.
Так как отец(Y, X)имеет четыре решения, то столько же решений имеет и ребенок(Х, Y).Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката ребенок.Аналогично, если мы определили
отец(X):- отец(_,X).
(отец (X) обозначает, что X является чьим-либо отцом), то на вопрос
?- отец(X).
были бы получены ответы:
X = джордж;
X = джордж;
X =гарри;
X = эдуард.
Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:
человек(адам).
человек(X):- мать(X,Y).
человек(ева).
мать(каин,ева).
мать(авель,ева).
мать(иавал,ада).
мать(тувалкаин,цилла).
( адам- человек; объект является человеком, если он имеет мать; ева– человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос
?- человек (X).
то ответом было бы:
X = адам;
X = каин;
X = авель;
X = иавал;
X = тувалкаин;
X = ева.
Давайте рассмотрим более интересный случай, когда имеются два целевых утверждения, для каждого из которых есть несколько решений. Предположим, что мы планируем провести вечеринку и хотим порассуждать о том, кто с кем мог бы танцевать. Мы можем начать писать программу следующим образом:
возможная_пара(X, Y):- парень(Х), девушка(Y).
парень(джон).
парень(мармадук).
парень(бертрам).
парень(чарлз).
девушка(гризелда).
девушка(эрминтруда).
девушка(брунхильда).
В программе определено, что Xи Yобразуют возможную пару, если Xявляется парнем, a Y- девушкой. Теперь давайте посмотрим, какие возможные пары имеются:
?- возможная_пара(X, Y).
X = джон, Y = гризелда;
X = джон, Y = эрминтруда;
X = джон, Y = брунхильда;
X = мармадук, Y = гризелда;
X = мармадук, Y = эрминтруда;
X = мармадук, Y = брунхильда;
X = бертрам, Y = гризелда;
X = бертрам, Y = эрминтруда;
X = бертрам, Y = брунхильда;
X = чарлз, Y = гризелда;
X = чарлз, Y = эрминтруда;
X = чарлз, Y = брунхильда.
Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели парень(X)и находит, что первым парнем является джон.Затем он находит сопоставление для цели девушка(Y), выбирая гризелдав качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения возможная_пара.Обнаруживается альтернативный вариант эрминтруда,и, следовательно, следующим решением является пара джони эрминтруда.Аналогично порождается пара джони брунхильдав качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения девушка(Y)Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения парень(Х),маркер которого был установлен на первый факт предиката парень,и, следовательно, следующим найденным решением, соответствующим второму парню, является мармадук.Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели девушка(Y),осуществляя поиск решения с самого начала базы данных. Так что он выбирает гризелда в качестве первой девушки. Следующие три решения содержат мармадуки имена трех девушек. Очередная попытка найти альтернативное решение для цели девушказаканчивается неудачей. Поэтому ищется другой парень, а поиск среди девушек производится с начала базы данных. Аналогичным образом происходит выполнение программы и далее.
В конце концов сложится ситуация, когда доказательство согласованности целевого утверждения девушказакончится неудачей и при этом будут также исчерпаны все решения для целевого утверждения парень.Программа не может более найти ни одной пары.
Все приведенные примеры являются очень простыми. Они содержат лишь определения большого числа фактов или используют правила для доступа к этим фактам. По этой причине они могут порождать только конечное число возможных решений. В некоторых случаях нам может потребоваться порождать бесконечное число возможных вариантов – не потому, что мы хотим рассмотреть их все, а потому, что мы не знаем заранее, сколько их понадобится. В этом случае необходимо рекурсивное определение (обсуждавшееся в предыдущей главе).
Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_ число(N)согласуется с базой данных, если переменная Nконкретизирована и ее значением является целое число. Если переменная Nнеконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения целое_число (N)приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.
/* 1 */ целое_число(0).
/* 2 */ целое_число (X):- целое_число (Y),X is Y+1)
Если мы зададим вопрос
?- целое_число (X).
то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката целое_числонаходится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На рис. 4.1, 4.2, 4.3 показана последовательность событий, приводящая к порождению трех первых решений. На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано иное решение.Первоначально для ответа на вопрос имеется выбор между фактом 1и правилом 2. Если выбирается факт 1, то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило 2и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт 1, то завершается доказательство целевого утверждения с ответом X=1; в противном случае используется правило 2и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт 1. Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт 1, и выбирает вместо него правило 2. При этом выборе появляется новая подцель. Факт 1представляет первую возможность для сопоставления с этой подцелью.
Рис. 4.1.
Рис. 4.2.
Рис. 4.3.
Большинство правил на Прологе будут порождать альтернативные решения, если они сопоставляются с целями, содержащими большое число неконкретизированных переменных. Например, отношение принадлежности элемента списку:
принадлежит(X,[X |_] ).
принадлежит(X,[_ |Y]):- принадлежит(X,Y).
порождает альтернативные решения. Если мы задаем вопрос
?- принадлежит(а,X).
(обратите внимание, что Xв вопросе является неконкретизированной переменной), то последовательные значения переменной Xбудут представлять частично конкретизированные списки, в которых аявляется первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос
?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).
фактически может быть согласован пятью способами.Очевидно, что имеются приложения предиката принадлежит, в которых требуется найти лишь одно решение, если оно вообще существует, и затем отбросить (обойти) остальные возможные решения. Такое отбрасывание оставшихся решений может быть реализовано с помощью «отсечения».
4.2. Отсечение
Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому «отсечением» [8]. Отсечение позволяет указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений. Существуют две причины, побуждающие включать в программу такие указания:
• Программа будет выполняться быстрее, так как не будет тратиться время на попытки найти новые сопоставления для целей, о которых заранее известно, что они не внесут более ничего нового в решение.
• Программа может занимать меньше места в памяти ЭВМ, так как отсутствие необходимости запоминать точки возврата для последующего анализа позволяет более экономно использовать память.
В некоторых случаях включение отсечения в программу может означать переход от программы, которая не будет работать, к программе, которая будет работать.
Синтаксически использование в правиле отсечения выглядит как вхождение целевого утверждения с предикатом '!', не имеющим аргументов. Как целевое утверждение этот предикат всегда согласуется с базой данных и не может быть вновь согласован. Однако он имеет побочный эффект, который изменяет процесс последующего возврата. Эффект заключается в том, что маркеры некоторых целей становятся недоступными, так что для этих целей нельзя найти новые сопоставления. Рассмотрим, как это происходит на примере. Предположим, что вы заведуете библиотекой и имеете базу данных на Прологе, содержащую информацию о наличии книг, о том, кто и какие книги взял и когда книги должны быть возвращены. Один из вопросов, который мог бы вас интересовать,- это какие виды услуг, предоставляемых библиотекой, доступны каждому из читателей. Некоторые услуги, которые мы могли бы назвать основными, должны быть доступны любому читателю. Они включают пользование каталогом и справочным бюро. С другой стороны, дополнительные услуги, такие как пользование абонементом или получение книг из других библиотек, хотелось бы предоставлять читателю выборочно. Одно из правил могло бы состоять в том, что если читатель не возвратил в указанный срок книгу, то дополнительные виды услуг ему недоступны до тех пор, пока он не вернет книгу. Здесь приведена часть программы, которая использует это правило:
услуги(Читатель,Вид_услуг):-
книга_не_возвращена(Читатель,Книга),!,основные_услуги (Вид_услуг).
услуги(Читатель,Вид_услуг):-общие_услуги(Вид_услуг).
основные_услуги(пользование_каталогом).
основные_услуги(получение_справок).
дополнительные_услуги (абонемент).
дополнительные_услуги(межбиблиотечный_абонемент).