Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 100
Текст из файла (страница 100)
Однако онане должна вычислять аргументы, поскольку это сами аргументы и есть, а не выражения,вычисление которых (на Лиспе) даст нам аргументы. Обратите внимание, что executeреализована с помощью eval и apply из нижележащей Лисп-системы.(define (execute exp)(apply (eval (predicate exp) user-initial-environment)(args exp)))Особая форма always-true порождает запрос, который всегда удовлетворяется.Она игнорирует свое подвыражение (обычно пустое) и попросту пропускает через себя все кадры входного потока.
Always-true используется в селекторе rule-body434Глава 4. Метаязыковая абстракция(раздел 4.4.4.7) чтобы дать тела правилам, для которых тела не определены (то естьправилам, заключения которых всегда удовлетворяются).(define (always-true ignore frame-stream) frame-stream)(put ’always-true ’qeval always-true)Селекторы, которые определяют синтаксис not и lisp-value, определены в разделе 4.4.4.7.4.4.4.3. Поиск утверждений с помощью сопоставления с образцомПроцедура find-assertions, вызываемая из simple-query (раздел 4.4.4.2), принимает на входе образец и кадр.
Она возвращает поток кадров, каждый из которыхрасширяет исходный кадр сопоставлением данного образца с записью базы данных. Онапользуется fetch-assertions (раздел 4.4.4.5), чтобы найти поток всех утвержденийбазы, которые следует проверять на сопоставление с данными образцом и кадром. Мыиспользуем fetch-assertions потому, что часто можно с помощью простых тестовисключить множество записей в базе данных из числа кандидатов на успешное сопоставление. Система продолжала бы работать, если бы мы исключили fetch-assertionsи попросту проверяли поток всех утверждений базы, но при этом вычисление было быменее эффективным, поскольку пришлось бы делать намного больше вызовов сопоставителя.(define (find-assertions pattern frame)(stream-flatmap (lambda (datum)(check-an-assertion datum pattern frame))(fetch-assertions pattern frame)))Процедура check-an-assertion принимает в качестве аргументов образец, объектданных (утверждение) и кадр, и возвращает либо одноэлементный поток с расширеннымкадром, либо, если сопоставление неудачно, the-emptystream.(define (check-an-assertion assertion query-pat query-frame)(let ((match-result(pattern-match query-pat assertion query-frame)))(if (eq? match-result ’failed)the-empty-stream(singleton-stream match-result))))Сопоставитель как таковой возвращает либо символ failed, либо расширение данногокадра.
Основная идея сопоставителя состоит в том, чтобы сравнивать образец с данными, элемент за элементом, и собирать при этом связывания переменных образца. Еслиобразец и объект данных совпадают, то сопоставление оказывается успешным, и мывозвращаем поток собранных связываний. В противном случае, если образец являетсяпеременной, мы расширяем имеющийся кадр, связывая переменную с данными, если этоне противоречит уже имеющимся в кадре связываниям.
Если и образец, и данные являются парами, мы (рекурсивно) сопоставляем car образца с car данных и получаемкадр; затем с этим кадром мы сопоставляем cdr образца с cdr данных. Если ни один4.4. Логическое программирование435из этих случаев не применим, сопоставление терпит неудачу, и мы возвращаем символfailed.(define (pattern-match pat dat frame)(cond ((eq? frame ’failed) ’failed)((equal? pat dat) frame)((var? pat) (extend-if-consistent pat dat frame))((and (pair? pat) (pair? dat))(pattern-match (cdr pat)(cdr dat)(pattern-match (car pat)(car dat)frame)))(else ’failed)))Вот процедура, которая расширяет кадр, добавляя к нему новое связывание, если этоне противоречит уже имеющимся в кадре связываниям:(define (extend-if-consistent var dat frame)(let ((binding (binding-in-frame var frame)))(if binding(pattern-match (binding-value binding) dat frame)(extend var dat frame))))Если для переменной в кадре нет связывания, мы просто добавляем к нему новое связывание этой переменной с элементом данных.
В противном случае мы вызываем сопоставитель в данном кадре от элемента данных и имеющегося значения переменной вкадре. Если хранимое значение содержит только константы, (а это всегда так будет, еслионо само было создано процедурой extend-if-consistent во время сопоставленияс образцом), то это сопоставление просто проверит, совпадает ли хранимое значение сновым. Если да, то кадр вернется неизменным; если нет, вернется символ неудачи. Однако если хранимое в кадре значение было создано при унификации (см.
раздел 4.4.4.4),то оно может содержать переменные образца. Рекурсивное сопоставление хранимого образца с новым элементом данных добавит или проверит связывания переменных в этомобразце. Предположим, к примеру, что у нас есть кадр, в котором переменная ?x связана с выражением (f ?y), а ?y несвязана, и что теперь мы хотим расширить этоткадр, связав ?x со значением (f b). Мы ищем в кадре ?x и видим, что она связана с(f ?y).
Теперь нам нужно сопоставить (f ?y) с предлагаемым новым значением (fb) в том же самом кадре. В конце концов это сопоставление расширяет кадр, добавивсвязывание ?y с b. ?X по-прежнему связано с (f ?y). Мы никогда не изменяем хранимое связывание и никогда не храним более одного связывания для одной и той жепеременной.Процедуры, при помощи которых extend-if-consistent работает со связываниями, определены в разделе 4.4.4.8.Образцы с точечными хвостамиЕсли в образце содержится точка, за которой следует переменная образца, то переменная сопоставляется с остатком списка (а не со следующим его элементом), как436Глава 4. Метаязыковая абстракцияи следовало ожидать от точечной записи, описанной в упражнении 2.20. Несмотря нато, что реализованный нами сопоставитель на занимается специально поиском точек,работает он в этом случае так, как ему следует.
Это происходит потому, что лисповский примитив read, с помощью которого query-driver-loop считывает запрос ипредставляет его в виде списковой структуры, обрабатывает точки особым образом.Когда read встречает точку, вместо того, чтобы сделать следующее выражение очередным элементом списка (car в ячейке cons, cdr которой будет остатком списка),он делает его cdrом списковой структуры. Например, списковая структура, которуюread порождает при чтении образца (компьютеры ?type) могла бы быть построена спомощью выражения (cons ’компьютеры (cons ’?type ’())), а та, которая получается при чтении (компьютеры . ?type), могла бы получиться при вычислении(cons ’компьютеры ’?type).Таким образом, когда pattern-match рекурсивно сравнивает carы и cdrы списка данных и образца, содержащего точку, он в конце концов сопоставляет переменнуюпосле точки (она служит cdr образца) с подсписком списка данных, и связывает переменную с этим списком.
Например, сопоставление образца (компьютеры . ?type)со списком (компьютеры программист стажер) сопоставит переменную ?type сподсписком (программист стажер).4.4.4.4. Правила и унификацияПроцедура apply-rules — это аналог find-assertion (раздел 4.4.4.3). Она принимает на входе образец и кадр, а порождает поток расширенных кадров, применяяправила из базы данных.
Stream-flatmap отображает через apply-rule поток возможно применимых правил (отобранных процедурой fetch-rules из раздела 4.4.4.5)и склеивает получившиеся потоки кадров.(define (apply-rules pattern frame)(stream-flatmap (lambda (rule)(apply-a-rule rule pattern frame))(fetch-rules pattern frame)))Процедура apply-a-rule применяет правила способом, описанным в разделе 4.4.2.Сначала она дополняет кадр-аргумент, унифицируя в его рамках заключение правила собразцом. Если это удается, она выполняет в получившемся кадре тело правила.Однако прежде всего программа переименовывает все переменные в правиле и даетим уникальные новые имена. Это делается потому, что мы не хотим, чтобы переменныеиз различных применений правил смешивались друг с другом. К примеру, если в двухправилах используется переменная ?x, то каждое из них может добавить связываниеэтой переменной к кадру, в котором оно применяется.
Однако эти два ?x не имеют другк другу никакого отношения, и мы не должны обманываться и считать, что два связывания этих переменных обязаны соответствовать друг другу. Вместо переименованияпеременных мы могли бы придумать более хитрую структуру окружений; однако выбранный здесь подход с переименованиями — самый простой, хотя и не самый эффективный.(См.
упражнение 4.79.) Вот процедура apply-a-rule:(define (apply-a-rule rule query-pattern query-frame)(let ((clean-rule (rename-variables-in rule)))4.4. Логическое программирование437(let ((unify-result(unify-match query-pattern(conclusion clean-rule)query-frame)))(if (eq? unify-result ’failed)the-empty-stream(qeval (rule-body clean-rule)(singleton-stream unify-result))))))Селекторы rule-body и conclusion, извлекающие части правил, описаны в разделе 4.4.4.7.Чтобы породить уникальные имена переменных, мы связываем с каждым применением правила уникальный идентификатор (например, число) и цепляем его к исходнымименам переменных.
Например, если идентификатор применения правила равен 7, мыможем заменить все ?x в правиле на ?x-7, а все ?y на ?y-7. (Процедуры make-newvariable и new-rule-application-id содержатся среди синтаксических процедурв разделе 4.4.4.7.)(define (rename-variables-in rule)(let ((rule-application-id (new-rule-application-id)))(define (tree-walk exp)(cond ((var? exp)(make-new-variable exp rule-application-id))((pair? exp)(cons (tree-walk (car exp))(tree-walk (cdr exp))))(else exp)))(tree-walk rule)))Алгоритм унификации реализуется в виде процедуры, которая принимает на входе два образца и кадр, а возвращает либо расширенный кадр, либо символ failed.Унификатор в основном подобен сопоставителю, но только он симметричен — переменные разрешаются с обеих сторон сопоставления. Процедура unify-match подобнаpattern-match, за исключением нового отрезка кода (отмеченного знаком «***»), гдеобрабатывается случай, когда объект на правой стороне сопоставления является переменной.(define (unify-match p1 p2 frame)(cond ((eq? frame ’failed) ’failed)((equal? p1 p2) frame)((var? p1) (extend-if-possible p1 p2 frame))((var? p2) (extend-if-possible p2 p1 frame))((and (pair? p1) (pair? p2))(unify-match (cdr p1)(cdr p2)(unify-match (car p1)(car p2)frame)))(else ’failed))); ***438Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
