Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 97
Текст из файла (страница 97)
Все кадры, для которых предикатоказывается ложным, мы удаляем из входного потока.УнификацияЧтобы обрабатывать правила языка запросов, нам нужно уметь находить правила,в которых заключения соответствуют данному входному образцу. Заключения правилподобны утверждениям, но только в них могут содержаться переменные, так что намтребуется обобщенный вариант сопоставления с образцом, — называемый унификация(unification), — в котором как «образец», так и «данные» могут содержать переменные.Унификатор берет два образца, в каждом из которых могут быть константы и переменные, и определяет, возможно ли присвоить переменным значения, которые сделаютдва образца одинаковыми.
Если да, то он возвращает кадр, содержащий эти значения.Например, при унификации (?x a ?y) и (?y ?z a) получится кадр, в котором всетри переменные ?x, ?y и ?z связаны со значением a. С другой стороны, унификация(?x ?y a) и (?x b ?y) потерпит неудачу, поскольку не имеется такого значения для?y, которое бы сделало два образца одинаковыми. (Чтобы вторые элементы образцовоказались равными, ?y должно равняться b; однако, чтобы совпали третьи элементы,?y обязан быть a.) Подобно сопоставителю, унификатор, используемый в системе запросов, принимает на входе кадр и проводит унификации, не противоречащие содержимомуэтого кадра.Алгоритм унификации — самая технически сложная часть запросной системы. Приналичии сложных образцов может показаться, что для унификации требуются дедуктивные способности. Например, чтобы унифицировать (?x ?x) и ((a ?y c) (a b?z)), алгоритм обязан вычислить, что ?x должен быть равен (a b c), ?y должен70 Существует тонкое различие между реализацией not в виде фильтра и значением отрицания в математической логике.
См. раздел 4.4.3.422Глава 4. Метаязыковая абстракциябыть ?b, а ?z должен быть равен c. Можно считать, что этот процесс решает системууравнений, описывающую компоненты образцов. В общем случае это будут взаимозависимые уравнения, для решения которых требуются существенные преобразования71 . Кпримеру, унификацию (?x ?x) и ((a ?y c) (a b ?z)) можно рассматривать каксистему уравнений?x = (a ?y c)?x = (a b ?z)Из этих уравнений следует, что(a ?y c) = (a b ?z)а отсюда, в свою очередь, чтоa = a, ?y = b, c = ?zи, следовательно,?x = (a b c)При успешном сопоставлении с образцом все переменные оказываются связанными,и значения, с которыми они связаны, содержат только константы.
Это верно и для всехпримеров унификации, которые мы до сих пор рассмотрели. Однако в общем случаеуспешная унификация может не полностью определить значения переменных; какие-топеременные могут остаться неопределенными, а значения других сами могут содержатьпеременные.Рассмотрим унификацию (?x a) и ((b ?y) ?z). Можно вычислить, что ?x = (b?y), а a = ?z, но ничего больше нельзя сказать о значениях ?x и ?y.
Унификациязаканчивается успешно, поскольку, естественно, можно сделать образцы одинаковыми,присвоив значения ?x и ?y. Поскольку сопоставление никак не ограничивает значение, которое может принимать переменная ?y, никакого ее значения не оказывается вкадре-результате. Однако результат ограничивает значение ?x. Какое бы значение неимела переменная ?y, ?x должен равняться (b ?y).
Таким образом, в кадр помещаетсясвязывание ?x со значением (b ?y). Если позже значение ?y оказывается определенным (путем сопоставления с образцом или унификации, которая должна соответствоватьэтому кадру) и добавляется в кадр, значение, связанное с ?x, будет ссылаться на него72 .Применение правилГлавной операцией в компоненте запросной системы, который производит логическийвывод на основе правил, является унификация.
Чтобы увидеть, как этот компонент работает, рассмотрим обработку запроса, содержащего обращение к правилу, например:71 В одностороннем сопоставлении с образцом все уравнения, которые содержат переменные, заданы явно иуже решены относительно неизвестного (переменной образца).72 Можно считать, что унификация находит наиболее общий образец, который является специализацией двухвходных образцов. А именно, унификация (?x a) и ((b ?y) ?z) равна ((b ?y) a), а унификация (?xa ?y) и (?y ?z a), описанная выше, равна (a a a). Однако в нашей реализации удобнее считать, чторезультатом унификации является не образец, а кадр.4.4. Логическое программирование423(живет-около ?x (Хакер Лиза П))Обрабатывая этот запрос, сначала мы при помощи описанной ранее обыкновенной процедуры сопоставления смотрим, имеются ли в базе данных утверждения, которые сопоставляются с данным образцом.
(В данном случае таковых не окажется, поскольку внашей базе данных нет никаких прямых утверждений о том, кто около кого живет.) Наследующем шаге мы пытаемся унифицировать образец-запрос с заключением каждогоправила. Мы обнаруживаем, что образец унифицируется с заключением правила(rule (живет-около ?person-1 ?person-2)(and (адрес ?person-1 (?town . ?rest-1))(адрес ?person-2 (?town . ?rest-2))(not (same ?person-1 ?person-2))))и получается кадр, в котором переменная ?person-2 связана со значением (ХакерЛиза П), а переменная ?x связана с (должна иметь то же значение, что и) ?person1. Теперь по отношению к этому кадру мы вычисляем составной запрос, содержащийсяв теле правила.
Успешные сопоставления расширят кадр, сообщив значение переменной?person-1, а соответственно, и ?x, которую мы можем использовать при конкретизации исходного образца-запроса.В общем случае обработчик запросов при применении правила, когда он пытаетсяраспознать образец-запрос в кадре, который содержит связывания для некоторых переменных образца, использует следующий метод:• Унифицировать запрос с заключением правила и получить (если унификацияуспешна) расширение исходного кадра.• По отношению к расширенному кадру вычислить запрос, который является теломправила.Обратите внимание, насколько это похоже на метод применения процедуры в интерпретаторе eval/apply для Лиспа:• Связать параметры процедуры с ее аргументами и получить кадр, расширяющийисходное окружение процедуры.• По отношению к расширенному окружению вычислить выражение, которое является телом процедуры.Подобие двух вычислителей неудивительно.
Точно так же, как в Лиспе средствомабстракции являются определения процедур, в языке запросов средством абстракцииявляются определения правил. В каждом случае мы развертываем абстракцию, создаваясоответствующие связывания и вычисляя тело правила либо процедуры по отношению красширенной среде.Простые запросыВ этом разделе мы уже рассматривали, как вычислять простые запросы при отсутствии правил. Теперь, разобравшись, как применяются правила, мы можем описать, какпростые запросы вычисляются с помощью как правил, так и утверждений.Получая запрос-образец и поток кадров, мы порождаем для каждого входного кадрадва новых потока:424Глава 4.
Метаязыковая абстракция• поток расширенных кадров, получаемых сопоставлением образца со всеми утверждениями базы данных (при помощи сопоставителя), а также• поток расширенных кадров, полученных применением всех возможных правил (припомощи унификатора)73 .Соединение двух этих потоков порождает поток, который состоит изо всех способов,которыми данный образец можно удовлетворить в соответствии с исходным кадром.Эти потоки (по одному на каждый кадр входного потока) соединяются, и получаетсяединый большой поток. Окончательный поток, таким образом, состоит изо всех способов,которыми какой-либо кадр входного потока может быть расширен так, чтобы получалосьсопоставление с данным запросом.Вычислитель запросов и управляющий циклНесмотря на сложность встроенных операций сопоставления, система организованаподобно интерпретатору любого языка.
Процедура, координирующая операции сопоставления, называется qeval и играет роль, аналогичную процедуре eval для Лиспа. Qevalпринимает на входе запрос и поток кадров. Ее выходом служит поток кадров, соответствующих успешным сопоставлениям с запросом, которые расширяют какой-либо кадрво входном потоке, как показано на рис. 4.4.
Подобно eval, qeval распознает различные типы выражений (запросов) и для каждого из них вызывает соответствующуюпроцедуру. Имеется по процедуре для каждой особой формы (and, or, not и lispvalue) и еще одна для простых запросов.Управляющий цикл, аналогичный процедуре driver-loop из других интерпретаторов этой главы, считывает запросы с терминала. Для каждого запроса он вызываетqeval с запросом и потоком, состоящим из одного пустого кадра.
Получается потоквсех возможных сопоставлений (всех возможных расширений пустого кадра). Для каждого кадра в выходном потоке управляющий цикл конкретизирует входной запрос сиспользованием значений переменных, имеющихся в кадре. Затем этот поток конкретизированных запросов печатается74 .Кроме того, управляющий цикл распознает особую команду assert!, которая говорит, что на вход поступает не запрос, а новое утверждение или правило, которое следуетдобавить в базу данных.
Например,(assert! (должность (Битобор Бен) (компьютеры гуру)))(assert! (rule (шишка ?person)(and (начальник ?middle-manager ?person)(начальник ?x ?middle-manager))))73 Посколькуунификация является обобщением сопоставления, можно было бы упростить систему и порождать оба потока с помощью унификатора. Однако обработка простого случая с помощью обычного сопоставителя показывает, как сопоставление (а не полноразмерная унификация) может само по себе быть полезным.74 Мы используем потоки (а не списки) кадров потому, что рекурсивное применение правил может порождать бесконечное число значений, удовлетворяющих запросу. Здесь существенно задержанное вычисление,осуществляемое потоками: система будет печатать ответы один за другим по мере их порождения, независимоот того, получается ли конечное или бесконечное количество ответов.4.4.
Логическое программирование4254.4.3. Является ли логическое программирование математическойлогикой?На первый взгляд может показаться, что средства комбинирования, используемыев языке запросов, совпадают с операторами математической логики — и (and), или(or) и отрицанием (not), а при применении правил языка запросов производится корректный логический вывод75 . Однако такая идентификация языка запросов с математической логикой неверна, поскольку язык запросов обладает структурой управления(control structure), которая интерпретирует логические утверждения процедурным образом. Часто из этой структуры управления можно извлечь пользу. Например, чтобынайти начальников всех программистов, можно сформулировать запрос двумя логическиэквивалентными способами:(and (должность ?x (компьютеры программист))(начальник ?x ?y))и(and (начальник ?x ?y)(должность ?x (компьютеры программист)))Если в компании намного больше начальников, чем программистов (обычный случай), топервую форму использовать выгоднее, чем вторую, поскольку для каждого промежуточного результата (кадра), порождаемого первым подзапросом and, требуется просмотретьбазу данных.Цель логического программирования состоит в том, чтобы дать программисту способразбить вычислительную задачу на две отдельные подзадачи: «что» требуется посчитатьи «как» это сделать.
Этого добиваются, выделив подмножество утверждений математической логики — достаточно мощное, чтобы описать все, что захочется вычислить,но при этом достаточно слабое, чтобы иметь управляемую процедурную реализацию.Идея состоит в том, чтобы, с одной стороны, программа, выраженная на языке логического программирования, была эффективной, и компьютер мог бы ее исполнить. Управление («как» считать) определяется порядком вычислений языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
