Выход на граничное условие происходит, когда 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 = эдуард.

Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отец и печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом