Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

4.4. Логическое программирование

441

Процедура 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)))))))

Следующие процедуры определяют, как используется индекс базы данных. Образец

(утверждение или заключение правила) сохраняется в таблице, если он начинается с

переменной или константного символа.

442

Глава 4. Метаязыковая абстракция

(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.

Процедуры stream-append-delayed и interleave-delayed подобны stream-

append и 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 симво-

лом ?), вместо того, чтобы извлекать из символа буквы. Преобразование синтаксиса

осуществляется следующей процедурой

(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))

Большинство Л исп-систем позволяет пользователю изменять обыкновенную процедуру 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 написана в

стиле программирования, управляемого данными. Если Ваша процедура называется uniquely-

asserted, то нужно только написать

(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

/k вызовов сопоставителя. Другой

подход может состоять в том, чтобы обрабатывать два подвыражения запроса and по отдельности

а затем искать совместимые пары входных кадров. Если каждый запрос порождает N/k кадров,

то нам придется проделать N

проверок на совместимость — в k раз меньше, чем число

сопоставлений при нашем теперешнем методе.

Постройте реализацию and с использованием этой стратегии. Вам придется написать процеду-

ру, которая принимает на входе два кадра, проверяет связы вания в этих кадрах на совместимость

и, если они совместимы, порождает кадр, в котором множес тва связываний слиты. Эта операция

подобна унификации.

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

В разделе 4.4. 3 мы видели, что выражения not и lisp-value могут заставить язык запросов

выдавать «неправильные» значения, если эти фильтрующие операции применяются к кадрам с

несвязанными переменными. Придумайте способ избавиться от этого недостатка. Одна из возмож-

ностей состоит в том, чтобы проводить «задержанную» фильтрацию, цепляя к кадру «обещание»

провести ее, которое выполняется только тогда, когда связано достаточно переменных, чтобы опе-

рация стала возможна. Можно ждать и проводить фильтрацию только тогда, когда выполнены все

остальные операции. Однако из соображений эффективности хотелось бы фильтровать как можно

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

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

Перестройте язык запросов в виде недетерминистской программы, реализуемой интерпретатором

из раздела 4.3, а не в виде процесса обработки потоков. При таком подходе каждый запрос будет

порождать один ответ (а не поток всех возможных ответов), а пользователь может ввести try-

again и получить следующий ответ. Вы увидите, что существенная часть механизмов, которые

мы построили в этом разделе, заменяется недетерминистским поиском и перебором с возвратами.

Однако помимо этого, Вы обнаружите, что новый язык запросов отличается в тонких деталях по-

ведения от реализованного нами в этом разделе. Можете ли Вы привести примеры, показывающие

эти отличия?

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

Когда мы реализовывали в разделе 4.1 интерпр е татор, мы видели, как можно избежать конфликтов

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

лении

(define (square x)

(* x x))

(define (sum-of-squares x y)

(+ (square x) (square y)))

(sum-of-squares 3 4)

4.4. Логическое программирование

449

не возникает смешения между x из square и x из sum-of-squares, поскольку тело каждой

процедуры мы вычисляем в окружении, которое специально построено для связывания локаль-

ных переменных. В запросной системе мы избегаем конфликтов имен при применении правил

с помощью д ругой стратегии. Каждый раз при применении правила мы переименовываем пере-

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

интерпретаторе Лиспа заключалась бы в том, чтобы отменить внутренние окружения и просто

переименовывать переменные в теле процедуры каждый раз, как м ы ее вызываем.

Реализуйте для языка запросов метод применения правил, который использует не переименова-

ния, а окружения. Рассмотрите, можно ли использовать Вашу систему окружений для построения

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

структуры процедур для правил. Можно ли связать это с проблемой ведения рассуждений в кон-

тексте (например: «Е сли бы я предположил, что истинно P , то я смог бы доказать A и B»)

в качестве метода решения задач? (Это упражнение не имеет однозначного решения. Хороший

ответ, скорее всего, мог бы служить темой диссертации.)

ГЛАВА 5

ВЫЧИСЛЕНИЯ НА РЕГИСТРОВЫХ МАШИНАХ

Моя цель — показать, что небесная

машина не некое божественное живое

существо, а скорее часовой механизм (а

тот, кто верит, что у часов есть душа,

приписывает славу творца творению),

поскольку почти все из ее

многочисленных движений вызываются

простейшей материальной силой, так же,

как все движения часов вызываются

весом гири.

Иоганн Кеплер

(письмо к Герварту фон Гогенбургу, 1605)

Эта книга начинается с изучения процессов и с описания процессов в терминах

процедур, написанных на Лиспе. Чтобы объяснить значение этих процедур, м ы последо-

вательно использовали несколько моделей вычисления: подстановочную модель из гла-

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

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

лиспоподобных языков. Однако даже метациклический интерпретатор оставляет многие

вопросы без ответа, поскольку он не проясняет механизмы управлен ия Лисп-системы.

Напри мер, интерпретатор не показывает, как при вычислении подвыражения удается вер-

нуть значение выражению, это значение использующему, или почему одни рекурсивные

процедуры порождают итеративные процессы (то есть занимают неизменный объем па-

мяти), в то время как другие процедуры порождают рекурсивные процессы. Эти вопросы

остаются без ответа потому, что метациклический интерпретатор сам по себе является

программой на Лиспе, а следовательно, наследует управляющую структуру нижележа-

щей Лисп-системы. Чтобы предоставить более полное описание управляющей структуры

вычислителя Лиспа, нам нужно работать на более элементарном уровне, чем сам Лисп.

В этой главе мы будем описывать процессы в терминах пошаговых операций тради-

ционного компьютера. Такой компьютер, или регистровая машина (register machine),

последовательно выполняет команды (instructions), которые работают с ограниченным

числом элементов памяти, называемых регистрами (registers). Типичная команда реги-

стровой машины применяет элементарную операцию к содержимому нескольких реги-

стров и записывает результат еще в один регистр. Наши описания процессов, выполняе-

мых регистровыми машинами, будут очень похожи на «машинный язык» обыкновенных

компьютеров. Однако вместо того, чтобы сосредоточиться на машинном языке какого-то

конкретного компьютера, мы рассмотрим несколько процедур на Лиспе и спроектируем

специальную регистровую машину для выполнения каждой из этих процедур. Таким об-

разом, мы будем решать задачу с точки зрения архитектора аппаратуры, а не с точки