(cond ((assertion-to-be-added? q)

(add-rule-or-assertion! (add-assertion-body q)) (newline)

(display "Утверждение добавлено в базу данных.") (query-driver-loop)) (else (newline)

(display output-prompt) (display-stream (stream-map (lambda (frame) (instantiate q

frame

(lambda (v f)

(contract-question-mark v)))) (qeval q (singleton-stream ())))) (query-driver-loop)))))

Здесь, как и в других интерпретаторах из этой главы, мы пользуемся абстрактным синтаксисом языка запросов. Реализация синтаксиса выражений, включая предикат assertion-to-be-added? и селектор add-assertion-body, дается в разделе 4.4.4.7. Процедура add-rule-or-assertion! определяется в разделе 4.4.4.5.

Прежде чем обрабатывать входное выражение, управляющий цикл преобразует его синтаксис в форму, которая делает обработку эффективнее. При этом меняется представление переменных образца. Когда запрос конкретизируется, то все переменные, которые остались несвязанными, преобразуются, прежде чем печататься, обратно во входное представление. Эти преобразования производятся процедурами query-syntax-process и contract-questionmark (раздел 4.4.4.7).

Чтобы конкретизировать выражение, мы его копируем, заменяя при этом все переменные выражения их значениями из данного кадра. Значения сами по себе конкретизируются, поскольку и они могут содержать переменные (например, если ?x внутри exp связано в результате унификации со значением ?y, а уже ?y связано со значением 5). Действие, которое требуется предпринять, если переменную не удается конкретизировать, задается процедурным аргументом instantiate.

(define (instantiate exp frame unbound-var-handler) (define (copy exp) (cond ((var? exp)

(let ((binding (binding-in-frame exp frame))) (if binding

(copy (binding-value binding)) (unbound-var-handler exp frame)))) ((pair? exp)

(cons (copy (car exp)) (copy (cdr exp)))) (else exp)))

(copy exp))

Процедуры, управляющие связываниями, определяются в разделе 4.4.4.8.

4.4.4.2 Вычислитель

Процедура qeval, вызываемая из query-driver-loop, является основным вычислителем запросной системы. Она принимает на входе запрос и поток кадров и возвращает поток расширенных кадров. Особые формы она распознает через диспетчеризацию, управляемую данными, при помощи get и put, в точности так же, как мы реализовывали обобщенные операции в главе 2. Все запросы, которые не распознаются как особая форма, считаются простыми запросами и обрабатываются процедурой simple-query.

(define (qeval query frame-stream)

(let ((qproc (get (type query) qeval))) (if qproc

(qproc (contents query) frame-stream) (simple-query query frame-stream))))

Селекторы type и contents, определяемые в разделе 4.4.4.7, реализуют абстрактный синтаксис особых форм.

Простые запросы

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

(define (simple-query query-pattern frame-stream) (stream-flatmap (lambda (frame)

(stream-append-delayed (find-assertions query-pattern frame) (delay (apply-rules query-pattern frame)))) frame-stream))

Для каждого кадра из входного потока мы с помощью find-assertions (раздел 4.4.4.3) сопоставляем образец со всеми утверждениями из базы данных, получая при этом поток расширенных кадров. Кроме того, с помощью apply-rules (раздел 4.4.4.4) мы применяем все подходящие правила и получаем при этом еще один поток расширенных кадров. Два этих потока сливаются (при помощи stream-append-delayed из раздела 4.4.4.6) и дают на выходе поток, перечисляющий все способы, которыми исходный запрос можно удовлетворить в соответствии с исходным кадром (см. упражнение 4.71). Потоки от отдельных входных кадров соединяются через stream-flatmap (раздел 4.4.4.6) в один большой поток, содержащий все способы, которыми можно расширить кадры из входного потока и получить сопоставление с исходным запросом.

Составные запросы

Запросы с операцией and обрабатываются так, как показано на рис. 4.5, процедурой conjoin. Conjoin принимает в качестве аргументов конъюнкты и поток кадров, а возвращает поток расширенных кадров. Сначала она обрабатывает поток кадров и получает поток всех их возможных расширений, удовлетворяющих первому запросу конъюнкции. Затем, используя этот новый поток кадров, она рекурсивно применяет conjoin к остальным конъюнктам.

(define (conjoin conjuncts frame-stream) (if (empty-conjunction? conjuncts) frame-stream

(conjoin (rest-conjuncts conjuncts)

(qeval (first-conjunct conjuncts) frame-stream))))

Выражение

(put and qeval conjoin)

настраивает процедуру qeval так, чтобы она при обнаружении формы and вызывала conjoin.

Запросы or обрабатываются подобным же образом, как показано на рис. 4.6. Выходные потоки отдельных дизъюнктов or вычисляются раздельно и смешиваются при помощи процедуры interleave-delayed из раздела 4.4.4.6. (См. упражнения 4.71 и 4.72.)

(define (disjoin disjuncts frame-stream) (if (empty-disjunction? disjuncts) the-empty-stream (interleave-delayed (qeval (first-disjunct disjuncts) frame-stream) (delay (disjoin (rest-disjuncts disjuncts) frame-stream)))))

(put or qeval disjoin)

Предикаты и селекторы для синтаксиса конъюнктов и дизъюнктов даны в разделе 4.4.4.7.

Фильтры

Запросы not обрабатываются так, как описано в разделе 4.4.2. Мы пытаемся расширить каждый кадр входного потока так, чтобы удовлетворялся отрицаемый запрос, и включаем данный кадр в поток-результат только в том случае, если расширить его нельзя.

(define (negate operands frame-stream) (stream-flatmap (lambda (frame)

(if (stream-null? (qeval (negated-query operands)

(singleton-stream frame))) (singleton-stream frame) the-empty-stream)) frame-stream))

(put not qeval negate)

Lisp-value - фильтр, подобный not. Образец расширяется с помощью каждого кадра из входного потока, применяется указанный предикат, и кадры, для которых он возвращает ложное значение, исключаются из входного потока. Если остаются несвязанные переменные запроса, возникает ошибка.