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

Вычислитель запросов и управляющий цикл

Несмотря на сложность встроенных операций сопоставления, система организована подобно интерпретатору любого языка. Процедура, координирующая операции сопоставления, называется qeval и играет роль, аналогичную процедуре eval для Лиспа. Qeval принимает на входе запрос и поток кадров. Ее выходом служит поток кадров, соответствующих успешным сопоставлениям с запросом, которые расширяют какой-либо кадр во входном потоке, как показано на рис. 4.4. Подобно eval, qeval распознает различные типы выражений (запросов) и для каждого из них вызывает соответствующую процедуру. Имеется по процедуре для каждой особой формы (and, or, not и lisp-value) и еще одна для простых запросов.

Управляющий цикл, аналогичный процедуре driver-loop из других интерпретаторов этой главы, считывает запросы с терминала. Для каждого запроса он вызывает qeval с запросом и потоком, состоящим из одного пустого кадра. Получается поток всех возможных сопоставлений (всех возможных расширений пустого кадра). Для каждого кадра в выходном потоке управляющий цикл конкретизирует входной запрос с использованием значений переменных, имеющихся в кадре. Затем этот поток конкретизированных запросов печатает-ся.74

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

(assert! (должность (Битобор Бен) (компьютеры гуру)))

(assert! (rule (шишка ?person)

(and (начальник ?middle-manager ?person) (начальник ?x ?middle-manager))))

4.4.3 Является ли логическое программирование математической логикой?

На первый взгляд может показаться, что средства комбинирования, используемые в языке запросов, совпадают с операторами математической логики - и (and), или (or) и отрицанием (not), а при применении правил языка запросов производится корректный логический вывод.75 Однако такая идентификация

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

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

языка запросов с математической логикой неверна, поскольку язык запросов обладает структурой управления (control structure), которая интерпретирует логические утверждения процедурным образом. Часто из этой структуры управления можно извлечь пользу. Например, чтобы найти начальников всех программистов, можно сформулировать запрос двумя логически эквивалентными способами:

(and (должность ?x (компьютеры программист)) (начальник ?x ?y))

(and (начальник ?x ?y)

(должность ?x (компьютеры программист)))

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

Цель логического программирования состоит в том, чтобы дать программисту способ разбить вычислительную задачу на две отдельные подзадачи: «что» требуется посчитать и «как» это сделать. Этого добиваются, выделив подмножество утверждений математической логики - достаточно мощное, чтобы описать все, что захочется вычислить, но при этом достаточно слабое, чтобы иметь управляемую процедурную реализацию. Идея состоит в том, чтобы, с одной стороны, программа, выраженная на языке логического программирования, была эффективной, и компьютер мог бы ее исполнить. Управление («как» считать) определяется порядком вычислений языка. У нас должна быть возможность определять порядок выражений и порядок подвыражений в них так, чтобы вычисление проходило правильным и эффективным способом. В то же самое время мы должны быть способны рассматривать результат вычислений («что» считать) как простое следствие законов логики.

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

В применении правил используется modus ponens, известный метод вывода, который говорит, что если истинны утверждения A и из A следует B, то можно заключить истинность утверждения B.

76Это утверждение нужно ограничить соглашением: говоря о «выводе», производимом логической программой, мы предполагаем, что вычисление имеет конец. К сожалению, даже это ограниченное утверждение оказывается ложным для нашей реализации языка запросов (а также для программ на Прологе и большинстве других современных математических языков) из-за использования not и lisp-value. Как будет описано ниже, примитив not, реализованный в языке запросов, не всегда имеет то же значение, что отрицание в математической логике, а использование lisp-value вызывает дополнительные сложности. Можно было бы реализовать язык, согласованный с математической логикой, если просто убрать из него not и lisp-value и согласиться писать

и

Бесконечные циклы

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

(assert! (супруг Минни Микки))

Если теперь мы спросим (супруг Микки ?who)

мы не получим ответа, поскольку система не знает, что если A является супругом B, то B является супругом A. Поэтому мы вводим правило

(assert! (rule (супруг ?x ?y)

(супруг ?y ?x))) и снова делаем запрос (супруг Микки ?who)

К сожалению, это вводит систему в бесконечный цикл следующим образом:

•Система обнаруживает, что применимо правило супруг; а именно, заключение (супруг ?x ?y) успешно унифицируется с образцом-запросом (супруг Микки ?who) и получается кадр, в котором переменная ?x связана со значением Микки, а переменная ?y со значением ?who. Интерпретатор должен, таким образом, выполнить в этом кадре запрос (супруг ?y ?x) - в сущности, выполнить запрос (супруг ?who Микки) .

•Один ответ находится как утверждение в базе данных: (супруг Минни Микки) .

•Применимо также и правило супруг, так что интерпретатор снова выполняет его тело, которое теперь равно (супруг Микки ?who) .

Теперь система оказалась в бесконечном цикле. В сущности, найдет ли система простой ответ (супруг Минни Микки) прежде, чем окажется в цикле, зависит от деталей реализации, связанных с порядком, в котором система проверяет записи базы данных. Это простой пример циклов, которые могут возникнуть. Наборы взаимосвязанных правил могут привести к циклам, которые значительно труднее предвидеть, а возникновение цикла может зависеть от порядка подвыражений в and (см. упражнение 4.64) или от низкоуровневых деталей, связанных с порядком обработки запросов в системе. 77

программы с использованием исключительно простых запросов, and и or. Однако при этом оказалась бы ограничена выразительная сила языка. Одна из основных тем исследований в логическом программировании - поиск способов более тесного согласования с математической логикой без чрезмерной потери выразительной силы.

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