(string-append "?"

(if (number? (cadr variable))

(string-append (symbol->string (caddr variable))

"-"

(number->string (cadr variable))) (symbol->string (cadr variable))))))

4.4.4.8 Кадры и связывания

Кадры представляются как списки связываний, которые, в свою очередь, являются парами вида «переменная-значение»:

(define (make-binding variable value) (cons variable value))

(define (binding-variable binding) (car binding))

(define (binding-value binding) (cdr binding))

(define (binding-in-frame variable frame) (assoc variable frame))

(define (extend variable value frame)

(cons (make-binding variable value) frame))

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

Хьюго Дум не понимает, почему процедуры simple-query и disjoin реализованы через явные операции delay, а не следующим образом:

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

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

frame-stream))

(define (disjoin disjuncts frame-stream) (if (empty-disjunction? disjuncts) the-empty-stream (interleave

(qeval (first-disjunct disjuncts) frame-stream) (disjoin (rest-disjuncts disjuncts) frame-stream))))

Можете ли Вы дать примеры запросов, с которыми эти простые определения приведут к нежелательному поведению?

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

Почему adjoin и stream-flatmap чередуют потоки, а не просто их сцепляют? Приведите примеры, которые показывают, что чередование работает лучше. (Подсказка: зачем мы пользовались interleave в разделе 3.5.3?)

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

Почему flatten-stream использует delay явно? Что было бы неправильно в таком определении:

(define (flatten-stream stream) (if (stream-null? stream) the-empty-stream (interleave (stream-car stream)

(flatten-stream (stream-cdr stream)))))

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

Лиза П. Хакер предлагает использовать в negate, lisp-value и find-assertions упрощенную версию stream-flatmap. Она замечает, что в этих случаях процедура, которая отображает поток кадров, всегда порождает либо пустой поток, либо поток из одного элемента, и поэтому при слиянии этих потоков незачем использовать чередование.

a.Заполните пропущенные выражения в программе Лизы.

(define (simple-stream-flatmap proc s) (simple-flatten (stream-map proc s)))

(define (simple-flatten stream) (stream-map {??)

(stream-filter {??) stream)))

b.Если мы изменяем систему таким образом, меняется ли ее поведение? Упражнение 4.75.

Реализуйте в языке запросов новую особую форму unique. Выражение unique должно быть успешно, если в базе данных ровно одна запись, удовлетворяющая указанному запросу. Например запрос

(unique (должность ?x (компьютеры гуру)))

должен печатать одноэлементный поток

(unique (должность (Битобор Бен) (компьютеры гуру)))

поскольку Бен - единственный компьютерный гуру, а (unique (должность ?x (компьютеры программист)))

должно печатать пустой поток, поскольку программистов больше одного. Более того, (and (должность ?x ?j) (unique (должность ?anyone

должно перечислять все должности, на которых работает по одному человеку, а также самих этих людей.

Реализация unique состоит из двух частей. Первая заключается в том, чтобы написать процедуру, которая обрабатывает эту особую форму, а вторая в том, чтобы заставить qeval распознавать форму и вызывать ее процедуру. Вторая часть тривиальна, поскольку qeval написана в стиле программирования, управляемого данными. Если Ваша процедура называется uniquely-asserted, то нужно только написать

(put unique qeval uniquely-asserted)

и qeval будет передавать управление этой процедуре для всех запросов, у которых в type (car) стоит символ unique.

Собственно задача состоит в том, чтобы написать процедуру uniquely-asserted. В качестве входа она должна принимать contents (cdr) запроса unique и поток кадров. Для каждого кадра в потоке она должна с помощью qeval находить поток всех расширений, удовлетворяющих данному запросу. Потоки, в которых число элементов не равно одному, должны отбрасываться. Оставшиеся потоки нужно собирать в один большой поток. Он и становится результатом запроса unique. Эта процедура подобна реализации особой формы not.

Проверьте свою реализацию, сформировав запрос, который находит всех служащих, которые начальствуют ровно над одним человеком.

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

Наша реализация and в виде последовательной комбинации запросов (рисунок 4.5) изящна, но неэффективна, поскольку при обработке второго запроса приходится просматривать базу данных для каждого кадра, порожденного первым запросом. Если в базе данных N записей, а типичный запрос порождает число записей, пропорциональное N (скажем, N/k), то проход базы данных для каждого кадра, порожденного первым запросом, потребует N2/k вызовов сопоставителя. Другой подход может состоять в том, чтобы обрабатывать два подвыражения запроса and по отдельности а затем искать совместимые пары входных кадров. Если каждый запрос порождает N/k кадров, то нам придется проделать N2/k2 проверок на совместимость - в k раз меньше, чем число сопоставлений при нашем теперешнем методе.

Постройте реализацию and с использованием этой стратегии. Вам придется написать процедуру, которая принимает на входе два кадра, проверяет связывания в этих кадрах на совместимость и, если они совместимы, порождает кадр, в котором множества связываний слиты. Эта операция подобна унификации.

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

В разделе 4.4.3 мы видели, что выражения not и lisp-value могут заставить язык запросов выдавать «неправильные» значения, если эти фильтрующие операции применяются к кадрам с несвязанными переменными. Придумайте способ избавиться от этого недостатка. Одна из возможностей состоит в том, чтобы проводить «задержанную» фильтрацию, цепляя к кадру «обещание» провести ее, которое выполняется только тогда, когда связано достаточно переменных, чтобы операция стала возможна. Можно ждать и проводить фильтрацию только тогда, когда выполнены все остальные операции. Однако из соображений эффективности хотелось бы фильтровать как можно раньше, чтобы уменьшить число порождаемых промежуточных кадров.

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

Перестройте язык запросов в виде недетерминистской программы, реализуемой интерпретатором из раздела 4.3, а не в виде процесса обработки потоков. При таком подходе каждый запрос будет порождать один ответ (а не поток всех возможных ответов), а пользователь может ввести try-again и получить следующий ответ. Вы увидите, что существенная часть механизмов, которые мы построили в этом разделе, заменяется недетерминистским поиском и перебором с возвратами. Однако помимо этого, Вы обнаружите, что новый язык запросов отличается в тонких деталях поведения от реализованного нами в этом разделе. Можете ли Вы привести примеры, показывающие эти отличия?