(cond ((var? e)

(if (equal? var e) true

(let ((b (binding-in-frame e frame)))

(if b

(tree-walk (binding-value b))

false))))

((pair? e) (or (tree-walk (car e)) (tree-walk (cdr e)))) (else false))) (tree-walk exp))

4.4.4.5 Ведение базы данных

Одна из важных задач при разработке логических языков программирования - так организовать работу, чтобы при проверке каждого образца просматривалось как можно меньше ненужных записей из базы. В нашей системе, помимо того, что мы храним все утверждения в одном большом потоке, мы в отдельных потоках храним утверждения, cart>i которых являются константными символами, в таблице, индексируемой по этим символам. Чтобы получить утверждения, которые могут сопоставляться с образцом, мы сначала смотрим, не является ли car образца константным символом. Если это так, то мы возвращаем (сопоставителю для проверки) все хранимые утверждения с тем же car. Если car образца не является константным символом, мы возвращаем все хранимые утверждения. Более изысканные методы могли бы использовать еще информацию из кадра, либо пытаться оптимизировать и тот случай, когда car образца не является константным символом. Мы избегаем встраивания критериев для индексации (использование car, обработка только случая с константными символами) в программу: вместо этого мы вызываем предикаты и селекторы, реализующие эти критерии.

(define THE-ASSERTIONS the-empty-stream)

(define (fetch-assertions pattern frame) (if (use-index? pattern)

(get-indexed-assertions pattern) (get-all-assertions)))

(define (get-all-assertions) THE-ASSERTIONS)

(define (get-indexed-assertions pattern)

(get-stream (index-key-of pattern) assertion-stream))

Процедура get-stream ищет поток в таблице и, если ничего там не находит, возвращает пустой поток.

(define (get-stream key1 key2)

(let ((s (get key1 key2)))

(if s s the-empty-stream)))

Правила хранятся подобным же образом, с использованием car заключения правила. Однако в заключениях правил могут стоять произвольные образцы,

и таким образом, они отличаются от утверждений тем, что могут содержать переменные. Образец, в car которого стоит константный символ, может сопоставляться не только с правилами, у которых car заключения содержит тот же символ, но и с правилами, где в начале заключения стоит переменная. Таким образом, при поиске правил, которые могут сопоставляться с образцом, у которого в начале константный символ, мы возвращаем как правила с этим символом в car заключения, так и правила с переменной в начале заключения. Ради этого мы храним правила с переменными в начале заключения в отдельном потоке, который находится в таблице под индексом ? .

(define THE-RULES the-empty-stream)

(define (fetch-rules pattern frame) (if (use-index? pattern)

(get-indexed-rules pattern) (get-all-rules)))

(define (get-all-rules) THE-RULES)

(define (get-indexed-rules pattern) (stream-append (get-stream (index-key-of pattern) rule-stream) (get-stream ? rule-stream)))

Процедура add-rule-or-assertion! вызывается из query-driver-loop, когда требуется добавить к базе данных правило или утверждение. Каждая запись сохраняется в индексе, если это требуется, а также в общем потоке правил либо утверждений базы данных.

(define (add-rule-or-assertion! assertion) (if (rule? assertion)

(add-rule! assertion) (add-assertion! assertion)))

(define (add-assertion! assertion) (store-assertion-in-index assertion) (let ((old-assertions THE-ASSERTIONS)) (set! THE-ASSERTIONS

(cons-stream assertion old-assertions))

ok))

(define (add-rule! rule) (store-rule-in-index rule)

(let ((old-rules THE-RULES))

(set! THE-RULES (cons-stream rule old-rules))

ok))

Чтобы вставить в базу утверждение или правило, мы проверяем, можно ли его проиндексировать. Если да, то мы сохраняем его в соответствующем потоке.

(define (store-assertion-in-index assertion) (if (indexable? assertion)

(let ((key (index-key-of assertion))) (let ((current-assertion-stream

(get-stream key assertion-stream))) (put key

assertion-stream (cons-stream assertion

current-assertion-stream))))))

(define (store-rule-in-index rule) (let ((pattern (conclusion rule))) (if (indexable? pattern)

(let ((key (index-key-of pattern))) (let ((current-rule-stream

(get-stream key rule-stream))) (put key

rule-stream (cons-stream rule

current-rule-stream)))))))

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

(define (indexable? pat)

(or (constant-symbol? (car pat)) (var? (car pat))))

Ключ, под которым образец сохраняется в таблице - это либо ? (если он начинается с переменной), либо константный символ из его начала.

(define (index-key-of pat) (let ((key (car pat)))

(if (var? key) ? key)))

Для поиска записей, которые могут соответствовать образцу, используется индекс в том случае, когда образец начинается с константного символа.

(define (use-index? pat)

(constant-symbol? (car pat)))

Упражнение 4.70.

Какова цель выражений let в процедурах add-assertion! и add-rule!? Что неправильно в следующем варианте add-assertion!? Подсказка: вспомните определение бесконечного потока единиц из раздела 3.5.2: (define ones (cons-stream 1 ones)) .

(define (add-assertion! assertion) (store-assertion-in-index assertion)

(set! THE-ASSERTIONS

(cons-stream assertion THE-ASSERTIONS))

ok)

4.4.4.6 Операции над потоками

В запросной системе используется несколько операций над потоками, помимо представленных в главе 3.