Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 102
Текст из файла (страница 102)
Операции над потокамиВ запросной системе используется несколько операций над потоками, помимо представленных в главе 3.Процедуры stream-append-delayed и interleave-delayed подобны streamappend и interleave (раздел 3.5.3), но только они принимают задержанный аргумент(как процедура integral из раздела 3.5.4). В некоторых случаях это откладываетзацикливание (см. упражнение 4.71).(define (stream-append-delayed s1 delayed-s2)(if (stream-null? s1)(force delayed-s2)(cons-stream(stream-car s1)(stream-append-delayed (stream-cdr s1) delayed-s2))))(define (interleave-delayed s1 delayed-s2)(if (stream-null? s1)(force delayed-s2)(cons-stream(stream-car s1)(interleave-delayed (force delayed-s2)(delay (stream-cdr s1))))))4.4.
Логическое программирование443Процедура stream-flatmap, которая многократно используется в интерпретаторе,чтобы применить процедуру ко всем элементам потока кадров и соединить получающиеся потоки кадров, является потоковым аналогом процедуры flatmap для обычныхсписков, введенной в разделе 2.2.3. Однако, в отличие от обычного flatmap, потокимы собираем с помощью чередующего процесса, а не просто сцепляем их (см. упражнения 4.72 и 4.73).(define (stream-flatmap proc s)(flatten-stream (stream-map proc s)))(define (flatten-stream stream)(if (stream-null? stream)the-empty-stream(interleave-delayed(stream-car stream)(delay (flatten-stream (stream-cdr stream))))))Кроме того, интерпретатор пользуется следующей простой процедурой для порождения потока, который состоит из одного элемента:(define (singleton-stream x)(cons-stream x the-empty-stream))4.4.4.7.
Процедуры, определяющие синтаксис запросовПроцедуры type и contents, используемые в qeval (раздел 4.4.4.2), указывают,что особая форма определяется символом в ее car. Это те же процедуры, что type-tagи contents из раздела 2.4.2, с точностью до сообщения об ошибке.(define (type exp)(if (pair? exp)(car exp)(error "Неизвестное выражение TYPE" exp)))(define (contents exp)(if (pair? exp)(cdr exp)(error "Неизвестное выражение CONTENTS" exp)))Следующие процедуры, вызываемые из query-driver-loop (раздел 4.4.4.1), указывают, что утверждения и правила добавляются в базу данных при помощи выраженийвида (assert! hправило-или-утверждениеi):(define (assertion-to-be-added? exp)(eq? (type exp) ’assert!))(define (add-assertion-body exp)(car (contents exp)))Вот синтаксические определения для особых форм and, or, not и lispvalue (раздел 4.4.4.2):444Глава 4.
Метаязыковая абстракция(define (empty-conjunction? exps) (null? exps))(define (first-conjunct exps) (car exps))(define (rest-conjuncts exps) (cdr exps))(define (empty-disjunction? exps) (null? exps))(define (first-disjunct exps) (car exps))(define (rest-disjuncts exps) (cdr exps))(define (negated-query exps) (car exps))(define (predicate exps) (car exps))(define (args exps) (cdr exps))Следующие три процедуры определяют синтаксис правил:(define (rule? statement)(tagged-list? statement ’rule))(define (conclusion rule) (cadr rule))(define (rule-body rule)(if (null? (cddr rule))’(always-true)(caddr rule)))Query-driver-loop (раздел 4.4.4.1) вызывает query-syntax-process, чтобыпреобразовать переменные образца в выражении, имеющие форму ?symbol, к внутреннему формату (? symbol). Это означает, что образец вроде (должность ?x ?y) насамом деле представляется внутри системы как (должность (? x) (? y)).
Это повышает эффективность обработки запросов, потому что позволяет системе проверять,является ли выражение переменной, путем проверки car (не является ли car символом ?), вместо того, чтобы извлекать из символа буквы. Преобразование синтаксисаосуществляется следующей процедурой81 .(define (query-syntax-process exp)(map-over-symbols expand-question-mark exp))(define (map-over-symbols proc exp)(cond ((pair? exp)(cons (map-over-symbols proc (car exp))(map-over-symbols proc (cdr exp))))((symbol? exp) (proc exp))81 Большинство Лисп-систем позволяет пользователю изменять обыкновенную процедуру read и осуществлять такие преобразования путем определения макросимволов ввода (reader macro characters).
Закавыченныевыражения уже обрабатываются таким образом: процедура чтения автоматически переводит ’expression в(quote expression), прежде чем выражение видит интерпретатор. Можно было бы устроить преобразование ?expression в (? expression) таким же образом; однако ради большей ясности мы здесь представилипроцедуру преобразования явно.Expand-question-mark и contract-question-mark используют несколько процедур, имя которыхсодержит string. Это примитивы языка Scheme.4.4.
Логическое программирование445(else exp)))(define (expand-question-mark symbol)(let ((chars (symbol->string symbol)))(if (string=? (substring chars 0 1) "?")(list ’?(string->symbol(substring chars 1 (string-length chars))))symbol)))После того, как переменные таким образом преобразованы, переменные в образцах —это списки, начинающиеся с ?, а константные символы (которые требуется распознаватьдля индексирования базы данных, раздел 4.4.4.5) — это просто символы.(define (var? exp)(tagged-list? exp ’?))(define (constant-symbol? exp) (symbol? exp))Во время применения правил при помощи следующих процедур порождаются уникальные переменные (раздел 4.4.4.4). Уникальным идентификатором правила служитчисло, которое увеличивается при каждом применении правила:(define rule-counter 0)(define (new-rule-application-id)(set! rule-counter (+ 1 rule-counter))rule-counter)(define (make-new-variable var rule-application-id)(cons ’? (cons rule-application-id (cdr var))))Когда query-driver-loop конкретизирует запрос для печати ответа, она преобразует все несвязанные переменные запроса обратно к печатной форме при помощи(define (contract-question-mark variable)(string->symbol(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))446Глава 4. Метаязыковая абстракция(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.4. Логическое программирование447Упражнение 4.74.Лиза П. Хакер предлагает использовать в negate, lisp-value и find-assertions упрощенную версию stream-flatmap. Она замечает, что в этих случаях процедура, которая отображаетпоток кадров, всегда порождает либо пустой поток, либо поток из одного элемента, и поэтому прислиянии этих потоков незачем использовать чередование.а.
Заполните пропущенные выражения в программе Лизы.(define (simple-stream-flatmap proc s)(simple-flatten (stream-map proc s)))(define (simple-flatten stream)(stream-map h??i(stream-filter h??i stream)))б. Если мы изменяем систему таким образом, меняется ли ее поведение?Упражнение 4.75.Реализуйте в языке запросов новую особую форму unique. Выражение unique должно бытьуспешно, если в базе данных ровно одна запись, удовлетворяющая указанному запросу. Напримерзапрос(unique (должность ?x (компьютеры гуру)))должен печатать одноэлементный поток(unique (должность (Битобор Бен) (компьютеры гуру)))поскольку Бен — единственный компьютерный гуру, а(unique (должность ?x (компьютеры программист)))должно печатать пустой поток, поскольку программистов больше одного.
Более того,(and (должность ?x ?j) (unique (должность ?anyone ?j)))должно перечислять все должности, на которых работает по одному человеку, а также самих этихлюдей.Реализация unique состоит из двух частей. Первая заключается в том, чтобы написать процедуру, которая обрабатывает эту особую форму, а вторая в том, чтобы заставить qeval распознавать форму и вызывать ее процедуру.
Вторая часть тривиальна, поскольку qeval написана встиле программирования, управляемого данными. Если Ваша процедура называется uniquelyasserted, то нужно только написать(put ’unique ’qeval uniquely-asserted)и qeval будет передавать управление этой процедуре для всех запросов, у которых в type (car)стоит символ unique.Собственно задача состоит в том, чтобы написать процедуру uniquely-asserted. В качестве входа она должна принимать contents (cdr) запроса unique и поток кадров. Для каждогокадра в потоке она должна с помощью qeval находить поток всех расширений, удовлетворяющихданному запросу.
Потоки, в которых число элементов не равно одному, должны отбрасываться.Оставшиеся потоки нужно собирать в один большой поток. Он и становится результатом запросаunique. Эта процедура подобна реализации особой формы not.Проверьте свою реализацию, сформировав запрос, который находит всех служащих, которыеначальствуют ровно над одним человеком.448Глава 4. Метаязыковая абстракцияУпражнение 4.76.Наша реализация and в виде последовательной комбинации запросов (рисунок 4.5) изящна, нонеэффективна, поскольку при обработке второго запроса приходится просматривать базу данныхдля каждого кадра, порожденного первым запросом.
Если в базе данных N записей, а типичныйзапрос порождает число записей, пропорциональное N (скажем, N/k), то проход базы данных длякаждого кадра, порожденного первым запросом, потребует N 2 /k вызовов сопоставителя. Другойподход может состоять в том, чтобы обрабатывать два подвыражения запроса and по отдельностиа затем искать совместимые пары входных кадров. Если каждый запрос порождает N/k кадров,то нам придется проделать N 2 /k2 проверок на совместимость — в k раз меньше, чем числосопоставлений при нашем теперешнем методе.Постройте реализацию and с использованием этой стратегии. Вам придется написать процедуру, которая принимает на входе два кадра, проверяет связывания в этих кадрах на совместимостьи, если они совместимы, порождает кадр, в котором множества связываний слиты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
