Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 99
Текст из файла (страница 99)
Таким образом, результатом запроса является пустой кадр, ониспользуется для конкретизации запроса, и выходит (not (любитель-бейсбола (Битобор Бен))).79 Обсуждение и защита такой интерпретации not содержится в статье Кларка (Clark 1978).4.4. Логическое программирование429(accumulation-function hпеременнаяihзапрос-образецi)где в виде accumulation-function могут выступать sum (сумма), average (среднее) илиmaximum (максимум). Бен думает, что реализовать это расширение будет проще простого. Онпросто скормит образец-запрос функции qeval и получит поток кадров. Затем он пропуститпоток через функцию-отображение, которая из каждого кадра извлечет значение указанной переменной, и получившийся поток значений отдаст функции-накопителю. Когда Бен заканчивает своюреализацию и собирается ее опробовать, мимо проходит Пабло, все еще смущенный результатомзапроса из упражнения 4.65.
Когда Пабло показывает Бену полученный им от системы ответ, Бенхватается за голову: «Моя простая схема накопления не будет работать!»Что понял Бен? Опишите, как он мог бы исправить ситуацию.Упражнение 4.67.Придумайте, как в запросную систему можно вставить детектор циклов, который избегает простыхзацикливаний, вроде показанных в тексте и в упражнении 4.64. Общая идея состоит в том, чтосистема должна хранить в каком-то виде историю текущей цепи рассуждений и не начинатьобработку запроса, если она уже над ним работает. Опишите, информация какого вида (образцыи кадры) включается в историю и как можно проводить проверку.
(После того, как Вы изучите вдеталях реализацию запросной системы из раздела 4.4.4, Вы можете захотеть изменить систему ивключить в нее свой детектор циклов.)Упражнение 4.68.Определите правила, с помощью которых реализуется операция reverse из упражнения 2.18,возвращающая список, элементы которого те же, что и в исходном, но идут в обратном порядке. (Подсказка: используйте append-to-form.) Могут ли Ваши правила ответить и на запрос(reverse (1 2 3) ?x), и на (reverse ?x (1 2 3))?Упражнение 4.69.Начав с базы данных и правил, сформулированных Вами в упражнении 4.63, постройте правиладля добавления приставок «пра» в отношение внук.
Система должна уметь понять, что Ирад —правнук Адама, а Иавал и Иувал приходятся Адаму прапрапрапраправнуками. (Подсказка: представляйте, например, утверждение об Ираде как ((пра внук) Адам Ирад). Напишите правила,которые определяют, заканчивается ли список словом внук. С помощью этого определите правило,которое позволяет вывести отношение ((пра . ?rel) ?x ?y), где список ?rel оканчиваетсяна внук.) Проверьте свои правила на запросах ((пра внук) ?g ?ggs) и (?relationshipАдам Ирад).4.4.4.
Реализация запросной системыВ разделе 4.4.2 описывалось, как работает запросная система. Теперь мы представляем полную реализацию системы во всех деталях.4.4.4.1. Управляющий цикл и конкретизацияУправляющий цикл запросной системы читает входные выражения. Если выражениеявляется правилом или утверждением, которое требуется добавить в базу данных, топроисходит добавление.
В противном случае предполагается, что выражение является430Глава 4. Метаязыковая абстракциязапросом. Управляющий цикл передает запрос вычислителю qeval вместе с начальнымпотоком, состоящим из одного пустого кадра. Результатом вычисления является потоккадров, порожденных заполнением переменных запроса значениями, найденными в базеданных.
С помощью этих кадров порождается новый поток, состоящий из копий исходного запроса, в которых переменные конкретизированы значениями из потока кадров.Этот последний поток печатается на терминале:(define input-prompt ";;; Ввод запроса:")(define output-prompt ";;; Результаты запроса:")(define (query-driver-loop)(prompt-for-input input-prompt)(let ((q (query-syntax-process (read))))(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 qframe(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-syntaxprocess и contract-questionmark (раздел 4.4.4.7).Чтобы конкретизировать выражение, мы его копируем, заменяя при этом все переменные выражения их значениями из данного кадра. Значения сами по себе конкретизируются, поскольку и они могут содержать переменные (например, если ?x внутри expсвязано в результате унификации со значением ?y, а уже ?y связано со значением 5).Действие, которое требуется предпринять, если переменную не удается конкретизировать, задается процедурным аргументом instantiate.4.4. Логическое программирование431(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) сопоставляем образец со всеми утверждениями из базы данных, получая при432Глава 4.
Метаязыковая абстракцияэтом поток расширенных кадров. Кроме того, с помощью 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.4.4. Логическое программирование433ФильтрыЗапросы 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.
Образец расширяется с помощью каждогокадра из входного потока, применяется указанный предикат, и кадры, для которых онвозвращает ложное значение, исключаются из входного потока. Если остаются несвязанные переменные запроса, возникает ошибка.(define (lisp-value call frame-stream)(stream-flatmap(lambda (frame)(if (execute(instantiatecallframe(lambda (v f)(error "Неизвестная переменная -- LISP-VALUE" v))))(singleton-stream frame)the-empty-stream))frame-stream))(put ’lisp-value ’qeval lisp-value)Процедура execute, которая применяет предикат к аргументам, должна вызватьeval от предикатного выражения, чтобы получить применяемую процедуру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
