Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 98
Текст из файла (страница 98)
У нас должна бытьвозможность определять порядок выражений и порядок подвыражений в них так, чтобывычисление проходило правильным и эффективным способом. В то же самое время мыдолжны быть способны рассматривать результат вычислений («что» считать) как простоеследствие законов логики.Наш язык запросов можно рассматривать в качестве именно такого процедурно интерпретируемого подмножества математической логики. Утверждение представляет простой факт (атомарную пропозицию). Правило представляет импликацию, говорящую,что заключение истинно в случаях, когда истинно тело правила. Правило обладает естественной процедурной интерпретацией: чтобы доказать заключение правила, требуетсядоказать его тело. Следовательно, правила описывают вычисления. Однако поскольку75 То, что конкретный метод логического вывода корректен — утверждение не тривиальное. Требуется доказать, что исходя из истинных посылок, можно придти только к истинным заключениям.
В применении правилиспользуется modus ponens, известный метод вывода, который говорит, что если истинны утверждения A и изA следует B, то можно заключить истинность утверждения B.426Глава 4. Метаязыковая абстракцияправила можно рассматривать и как формулы математической логики, мы можем оправдать любой «вывод», производимый логической программой, показав, что того же результата можно достичь, работая строго в рамках логики76 .Бесконечные циклыВследствие процедурной интерпретации логических программ для решения некоторых задач можно построить безнадежно неэффективные программы. Частным случаемнеэффективности является ситуация, когда программа при работе над выводом впадает вбесконечный цикл. Возьмем простой пример: предположим, что мы строим базу данныхзнаменитых супружеских пар, в том числе(assert! (супруг Минни Микки))Если теперь мы спросим(супруг Микки ?who)мы не получим ответа, поскольку система не знает, что если A является супругом B, тоB является супругом A.
Поэтому мы вводим правило(assert! (rule (супруг ?x ?y)(супруг ?y ?x)))и снова делаем запрос(супруг Микки ?who)К сожалению, это вводит систему в бесконечный цикл следующим образом:• Система обнаруживает, что применимо правило супруг; а именно, заключение (супруг ?x ?y) успешно унифицируется с образцом-запросом (супруг Микки?who) и получается кадр, в котором переменная ?x связана со значением Микки, апеременная ?y со значением ?who.
Интерпретатор должен, таким образом, выполнить вэтом кадре запрос (супруг ?y ?x) — в сущности, выполнить запрос (супруг ?whoМикки).• Один ответ находится как утверждение в базе данных: (супруг Минни Микки).• Применимо также и правило супруг, так что интерпретатор снова выполняет еготело, которое теперь равно (супруг Микки ?who).76 Это утверждение нужно ограничить соглашением: говоря о «выводе», производимом логической программой, мы предполагаем, что вычисление имеет конец. К сожалению, даже это ограниченное утверждение оказывается ложным для нашей реализации языка запросов (а также для программ на Прологе и большинстведругих современных математических языков) из-за использования not и lisp-value.
Как будет описанониже, примитив not, реализованный в языке запросов, не всегда имеет то же значение, что отрицание вматематической логике, а использование lisp-value вызывает дополнительные сложности. Можно было быреализовать язык, согласованный с математической логикой, если просто убрать из него not и lisp-valueи согласиться писать программы с использованием исключительно простых запросов, and и or.
Однако приэтом оказалась бы ограничена выразительная сила языка. Одна из основных тем исследований в логическомпрограммировании — поиск способов более тесного согласования с математической логикой без чрезмернойпотери выразительной силы.4.4. Логическое программирование427Теперь система оказалась в бесконечном цикле.
В сущности, найдет ли система простой ответ (супруг Минни Микки) прежде, чем окажется в цикле, зависит от деталейреализации, связанных с порядком, в котором система проверяет записи базы данных.Это простой пример циклов, которые могут возникнуть. Наборы взаимосвязанных правил могут привести к циклам, которые значительно труднее предвидеть, а возникновениецикла может зависеть от порядка подвыражений в and (см. упражнение 4.64) или отнизкоуровневых деталей, связанных с порядком обработки запросов в системе77 .Проблемы с 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 ложно. Однако в системе запросов «не P » означает, что P невозможно доказать на основе информации из базы данных.
Например, имея базу данных77 Это проблема не собственно логики, а процедурной интерпретации логики, которую дает наш интерпретатор. В данном случае можно написать интерпретатор, который не попадет в цикл. Например, можно пронумеровать доказательства, выводимые из наших утверждений и правил, по ширине, а не по глубине. Однако втакой системе оказывается труднее использовать порядок правил в программах. Одна из попыток встроить втакую программу тонкое управление вычислениями описана в deKleer et al. 1977. Еще один метод, который неведет к столь же сложным проблемам с управлением, состоит в добавлении специальных знаний, например, детекторов для каких-то типов циклов (см. упражнение 4.67).
Однако общую схему надежного предотвращениябесконечных путей в рассуждениях построить невозможно. Представьте себе дьявольское правило вида «чтобыдоказать истинность P (x), докажите истинность P (f (x))» для какой-нибудь хитро выбранной функции f .428Глава 4. Метаязыковая абстракцияиз раздела 4.4.1, система радостно выведет разнообразные отрицательные утверждения,например, что Бен Битобор не любитель бейсбола, что на улице нет дождя, и что 2 + 2не равно 478 . Иными словами, операция not в языках логического программированияотражает так называемую гипотезу о замкнутости мира (closed world assumption) исчитает, что вся релевантная информация включена в базу данных79 .Упражнение 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)))В общем случае новая система Бена допускает запросы вида78 Рассмотрим запрос (not (любитель-бейсбола (Битобор Бен))). Система обнаруживает, что записи (любитель-бейсбола (Битобор Бен)) в базе нет, так что пустой кадр образцу не соответствуети не удаляется из исходного потока кадров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
