Проблемы с not

Еще одна особенность запросной системы связана с not. Рассмотрим следующие два запроса к базе данных из раздела 4.4.1:

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

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

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

Эти два запроса приводят к различным результатам. Первый запрос сначала находит все записи в базе данных, соответствующие образцу (начальник ?x ?y) , затем фильтрует полученные кадры, удаляя те, в которых значение ?x удовлетворяет образцу (должность ?x (компьютеры программист)) . Второй запрос сначала фильтрует входные кадры, пытаясь удалить те, которые удовлетворяют образцу (должность ?x (компьютеры программист)) . Поскольку единственный входной кадр пуст, он проверяет базу данных и смотрит, есть ли там записи, соответствующие (должность ?x (компьютеры программист)) . Поскольку, как правило, такие записи имеются, выражение not удаляет пустой кадр, и остается пустой поток кадров. Следовательно, весь составной запрос также возвращает пустой поток.

Сложность состоит в том, что наша реализация not предназначена только для того, чтобы служить фильтром для значений переменных. Если выражение not обрабатывается с кадром, в котором часть переменных остается несвязанными (как ?x в нашем примере), система выдаст неверный результат. Подобные сложности возникают и с использованием lisp-value - предикат Лиспа не сможет работать, если часть из его аргументов несвязана. См. упражнение 4.77.

Есть еще один, значительно более серьезный аспект, в котором not языка запросов отличается от отрицания в математической логике. В логике мы считаем, что выражение «не Р» означает, что P ложно. Однако в системе запросов «не Р» означает, что P невозможно доказать на основе информации из базы данных. Например, имея базу данных из раздела 4.4.1, система радостно выведет разнообразные отрицательные утверждения, например, что Бен Битобор не любитель бейсбола, что на улице нет дождя, и что 2 + 2 не равно 4.78 Иными словами, операция not в языках логического программирования отражает так называемую гипотезу о замкнутости мира (closed world assumption) и считает, что вся релевантная информация включена в базу данных.79

ширине, а не по глубине. Однако в такой системе оказывается труднее использовать порядок правил в программах. Одна из попыток встроить в такую программу тонкое управление вычислениями описана в deKleer et al. 1977. Еще один метод, который не ведет к столь же сложным проблемам с управлением, состоит в добавлении специальных знаний, например, детекторов для каких-то типов циклов (см. упражнение 4.67). Однако общую схему надежного предотвращения бесконечных путей в рассуждениях построить невозможно. Представьте себе дьявольское правило вида «чтобы доказать истинность P(x), докажите истинность P(f(ж))» для какой-нибудь хитро выбранной функции f.

78 Рассмотрим запрос (not (любитель-бейсбола (Битобор Бен))). Система обнаруживает, что записи (любитель-бейсбола (Битобор Бен)) в базе нет, так что пустой кадр образцу не соответствует и не удаляется из исходного потока кадров. Таким образом, результатом запроса является пустой кадр, он используется для конкретизации запроса, и выходит (not (любитель-бейсбола (Битобор Бен))) .

79Обсуждение и защита такой интерпретации not содержится в статье Кларка (Clark 1978).

Упражнение 4.64.

Хьюго Дум по ошибке уничтожил в базе данных правило подчиняется (раздел 4.4.1). Обнаружив это, он быстро набивает правило заново, только, к сожалению, по ходу дела вносит небольшое изменение:

(rule (подчиняется ?staff-person ?boss)

(or (начальник ?staff-person ?boss)

(and (подчиняется ?middle-manager ?boss)

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

Сразу после того, как Хьюго ввел информацию в систему, Кон Фиден хочет посмотреть, кому подчиняется Бен Битобор. Он вводит запрос

(подчиняется (Битобор Бен) ?who)

После ответа система проваливается в бесконечный цикл. Объясните, почему. Упражнение 4.65.

П.Э. Фект, ожидая собственного продвижения по иерархии, дает запрос, который находит всех шишек (используя правило шишка из раздела 4.4.1):

(шишка ?who)

К его удивлению, система отвечает

;;; Результаты запроса: (шишка (Уорбак Оливер)) (шишка (Битобор Бен)) (шишка (Уорбак Оливер)) (шишка (Уорбак Оливер)) (шишка (Уорбак Оливер))

Почему система упоминает Оливера Уорбака четыре раза? Упражнение 4.66.

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

(sum ?amount

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

В общем случае новая система Бена допускает запросы вида

(accumulation-function (переменная)

(запрос-образец))

где в виде accumulation-function могут выступать sum (сумма), average (среднее) или maximum (максимум). Бен думает, что реализовать это расширение будет проще простого. Он просто скормит образец-запрос функции qeval и получит поток кадров. Затем он пропустит поток через функцию-отображение, которая из каждого кадра извлечет значение указанной переменной, и получившийся поток значений отдаст функции-накопителю. Когда Бен заканчивает свою реализацию и собирается ее опробовать, мимо проходит Пабло, все еще смущенный результатом запроса из упражнения 4.65. Когда Пабло показывает Бену полученный им от системы ответ, Бен хватается за голову: «Моя простая схема накопления не будет работать!» Что понял Бен? Опишите, как он мог бы исправить ситуацию.

Упражнение 4.67.

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

Упражнение 4.68.

Определите правила, с помощью которых реализуется операция reverse из упражнения 2.18, возвращающая список, элементы которого те же, что и в исходном, но идут в обратном порядке. (Подсказка: используйте append-to-form.) Могут ли Ваши правила ответить и на запрос (reverse (1 2 3) ?x), и на (reverse ?x (1 2 3))?

Упражнение 4.69.

Начав с базы данных и правил, сформулированных Вами в упражнении 4.63, постройте правила для добавления приставок «пра» в отношение внук. Система должна уметь понять, что Ирад - правнук Адама, а Иавал и Иувал приходятся Адаму прапрапрапра-правнуками. (Подсказка: представляйте, например, утверждение об Ираде как ((пра внук) Адам Ирад). Напишите правила, которые определяют, заканчивается ли список словом внук. С помощью этого определите правило, которое позволяет вывести отношение ((пра . ?rel) ?x ?y) , где список ?rel оканчивается на внук.) Проверьте свои правила на запросах ((пра внук) ?g ?ggs) и (?relationship Адам Ирад) .

4.4.4 Реализация запросной системы

В разделе 4.4.2 описывалось, как работает запросная система. Теперь мы представляем полную реализацию системы во всех деталях.

4.4.4.1 Управляющий цикл и конкретизация

Управляющий цикл запросной системы читает входные выражения. Если выражение является правилом или утверждением, которое требуется добавить в базу данных, то происходит добавление. В противном случае предполагается, что выражение является запросом. Управляющий цикл передает запрос вычислителю qeval вместе с начальным потоком, состоящим из одного пустого кадра. Результатом вычисления является поток кадров, порожденных заполнением переменных запроса значениями, найденными в базе данных. С помощью этих кадров порождается новый поток, состоящий из копий исходного запроса, в которых переменные конкретизированы значениями из потока кадров. Этот последний поток печатается на терминале:

(define input-promptВвод запроса:")

(define output-promptРезультаты запроса:")

(define (query-driver-loop)

(prompt-for-input input-prompt)

(let ((q (query-syntax-process (read))))