(define (lisp-value call frame-stream) (stream-flatmap (lambda (frame) (if (execute

(instantiate

call

frame

(lambda (v f)

(error "Неизвестная переменная -- LISP-VALUE" v)))) (singleton-stream frame) the-empty-stream)) frame-stream))

(put lisp-value qeval lisp-value)

Процедура execute, которая применяет предикат к аргументам, должна вызвать eval от предикатного выражения, чтобы получить применяемую процедуру. Однако она не должна вычислять аргументы, поскольку это сами аргументы и есть, а не выражения, вычисление которых (на Лиспе) даст нам аргументы. Обратите внимание, что execute реализована с помощью eval и apply из нижележащей Лисп-системы.

(define (execute exp)

(apply (eval (predicate exp) user-initial-environment) (args exp)))

Особая форма always-true порождает запрос, который всегда удовлетворяется. Она игнорирует свое подвыражение (обычно пустое) и попросту пропускает через себя все кадры входного потока. Always-true используется в селекторе rule-body (раздел 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 данных. Если ни один из этих случаев не применим, сопоставление терпит неудачу, и мы возвращаем символ 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) с предлагаемым новым значением (f b) в том же самом кадре. В конце концов это сопоставление расширяет кадр, добавив связывание ?y с b. ?X по-прежнему связано с (f ?y) . Мы никогда не изменяем хранимое связывание и никогда не храним более одного связывания для одной и той же переменной.

Процедуры, при помощи которых extend-if-consistent работает со связываниями, определены в разделе 4.4.4.8.

Образцы с точечными хвостами

Если в образце содержится точка, за которой следует переменная образца, то переменная сопоставляется с остатком списка (а не со следующим его элементом), как и следовало ожидать от точечной записи, описанной в упражнении 2.20. Несмотря на то, что реализованный нами сопоставитель на занимается специально поиском точек, работает он в этом случае так, как ему следует. Это происходит потому, что лисповский примитив read, с помощью которого query-driver-loop считывает запрос и представляет его в виде списковой структуры, обрабатывает точки особым образом.

Когда read встречает точку, вместо того, чтобы сделать следующее выражение очередным элементом списка (car в ячейке cons, cdr которой будет остатком списка), он делает его cdrом списковой структуры. Например, списковая структура, которую read порождает при чтении образца (компьютеры ?type) могла бы быть построена с помощью выражения (cons компьютеры (cons ?type ())), а та, которая получается при чтении (компьютеры . ?type), могла бы получиться при вычислении (cons компьютеры

?type) .

Таким образом, когда pattern-match рекурсивно сравнивает cart>i и cdrt>i списка данных и образца, содержащего точку, он в конце концов сопоставляет переменную после точки (она служит cdr образца) с подсписком списка данных, и связывает переменную с этим списком. Например, сопоставление образца (компьютеры . ?type) со списком (компьютеры программист стажер) сопоставит переменную ?type с подсписком (программист стажер).