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

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

4.3. SCHEME с вариациями — недетерминистское вычисление

391

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

легко выражаются при помощи require. Однако по-настоящему достоинства автомати-

ческого поиска с возвратом проявляются тогда, когда мы обращаемся к более сложным

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

Добавим к грамматике список предлогов:

(define prepositions ’(prep for to in by with))

и определим предложную группу (например, for the cat, «для кошки») как последова-

тельность из предлога и именной группы:

(define (parse-prepositional-phrase)

(list ’prep-phrase

(parse-word prepositions)

(parse-noun-phrase)))

Теперь мы можем сказать, что предложение — это именная группа, за которой следует

глагольная группа, а глагольная группа — это либо глагол, либо глагольная группа,

дополненная предложной группой

(define (parse-sentence)

(list ’sentence

(parse-noun-phrase)

(parse-verb-phrase)))

(define (parse-verb-phrase)

(define (maybe-extend verb-phrase)

(amb verb-phrase

(maybe-extend (list ’verb-phrase

verb-phrase

(parse-prepositional-phrase)))))

(maybe-extend (parse-word verbs)))

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

пы и разрешить выражения вроде a cat in the class («кошк а в аудитории»). То, что

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

пой, а именная группа теперь может быть либо простой именной группой, либо именной

группой, которая дополняется предложной группой:

(define (parse-simple-noun-phrase)

(list ’simple-noun-phrase

(parse-word articles)

(parse-word nouns)))

(define (parse-noun-phrase)

(define (maybe-extend noun-phrase)

(amb noun-phrase

(maybe-extend (list ’noun-phrase

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

392

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

noun-phrase

(parse-prepositional-phrase)))))

(maybe-extend (parse-simple-noun-phrase)))

Обновленная грамматика позволяет разбирать более сложные предложен ия. Напри-

мер,

(parse ’(the student with the cat sleeps in the class))

(«студент с кошкой спит в аудитории») дает

(sentence

(noun-phrase

(simple-noun-phrase (article the) (noun student))

(prep-phrase (prep with)

(simple-noun-phrase

(article the) (noun cat))))

(verb-phrase

(verb sleeps)

(prep-phrase (prep in)

(simple-noun-phrase

(article the) (noun class)))))

Заметим, что входное предложение может иметь более одного з аконного анализа. В

предложении The professor lectures to the student with the cat («Профессор читает лек-

цию студенту с кошкой») может иметься в виду, что профессор вместе с кошкой читают

лекцию, или что кошка — у студента. Наша недетерминистская программа находит оба

варианта:

(parse ’(the professor lectures to the student with the cat))

дает

(sentence

(simple-noun-phrase (article the) (noun professor))

(verb-phrase

(verb lectures)

(prep-phrase (prep to)

(simple-noun-phrase

(article the) (noun student))))

(prep-phrase (prep with)

(simple-noun-phrase

(article the) (noun cat)))))

Если попросить интерпретатор поискать еще, получится

(sentence

(simple-noun-phrase (article the) (noun professor))

(verb-phrase

(verb lectures)

4.3. SCHEME с вариациями — недетерминистское вычисление

393

(prep-phrase (prep to)

(noun-phrase

(simple-noun-phrase

(article the) (noun student))

(prep-phrase (prep with)

(simple-noun-phrase

(article the) (noun cat)))))))

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

Согласно заданной выше грамматике, следующее предложение можно проанализировать пятью

различными способами: The professor lectures to the student in the class with the cat («Профессор

читает лекцию студенту в аудитории с кошкой»). Покажите эти пять разборов и объясните разницу

в оттенках значения между ними.

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

Интерпретаторы в разделах 4.1 и 4.2 не определяют, в каком порядке вычисляются операнды при

вызове процедуры. Мы увидим, что amb-интерпретатор вычисляет их слева направо. Объясните,

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

другом порядке.

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

Хьюго Дум говорит, что поскольку глагольная группа — это либо глагол, либо глагольная группа

плюс предложная группа, было бы намного естественнее определить процедуру parse-verb-

phrase так (и то же сделать для именных групп):

(define (parse-verb-phrase)

(amb (parse-word verbs)

(list ’verb-phrase

(parse-verb-phrase)

(parse-prepositional-phrase))))

Работает ли этот вариант? Изменится ли поведение программы, если мы поменяем местами выра-

жения в amb?

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

Дополните описанную выше грамматику так, чтобы она могла работать с более сложными предло-

жениями. Например, можно позволить именным и глагольным группам включать прилагательные

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

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

Лизу П . Хакер больше интересует не анализ предложений, а их порождение. Она замечает, что ес-

ли изменить процедуру parse-word так, чтобы она игнорировала «входное предложение», всегда

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

естественного языка они остаются игрушкой. Настоящее понимание естественного языка компьютером требу-

ет сложного сочетания синтаксического анализа с интерпретацией значения. С другой стороны, даже простые

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

информации. Уинстон (Winston 1992) описывает вычислительные подходы к пониманию настоящего естествен-

ного языка, а также применение простых грамматик в командных языках.

394

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

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

мы, ко торые мы написали для анализа, для порождения предложений. Реализуйте идею Лизы и

покажите первые пять-шесть порожденных предложений

4.3.3. Реализация amb-и нт ерпретатора

Выполнение выражения в обыкновенной Scheme может вернуть результат, может

вообще не завершиться, и, наконец, может закончиться сообщением об ошибке. В неде-

терминистской Scheme при выполнении выражения, в дополнение ко всему этому, может

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

щей точке выбора. Интерпретация недетерминистской Scheme осложняется из-за этой

дополнительной возможно сти.

Мы построим amb-интерпретатор для недетерминистской Scheme, модифицировав

анализирующий интерпретатор из раздела 4.1.7

. Как и в анализирующем интерпр етато -

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

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

ной Scheme и недетерминистской Scheme будет полностью сводиться к исполнительным

процедурам.

Исполнительные процедуры и продолжения

Напомним, ч то исполнительные процедуры обыкновенного интерпретатора принима-

ют один аргумент: окружение, в котором происходит вычисление выражения. В противо-

положность этому, исполнительные процедуры amb-интерпретатора принимают три аргу-

мента: окружение и две процедуры, называемые процедурами продолжения (continuation

procedures). Вычисление выражения будет заканчиваться вызовом одного из этих про-

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

успеха (success continuation) с этим значением в качестве аргумента; если вычисление

натыкается на тупик, вызывается продолжение неудачи (failure continuation). Построе-

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

недетерминистском интерпретаторе реализуется поиск с возвратом.

Задача продол жения успеха — принять значение и продолжить вычисление. Помимо

этого значения, продолжение успеха получает дополнительное продолжение неудачи,

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

Задача продолжения неудачи — попробовать другую ветвь неде терминистского про-

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

могут представлять собой точки выбора между вариантами. Выполнение такого выраже-

ния должно продолжиться согласно одному из указанных взаимоисключающих вариан-

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

Несмотря на то, что идея Лизы (будучи удивительно простой) дает результат, порождаемые предложения

оказываются довольно скучными — они не отображают возможные предложения нашего языка никаким инте-

ресным образом. Дело в том, что грамматика рекурсивна во многих местах, а метод Лизы «проваливается» в

одну из рекурсий и там застревает. Как с этим можно бороться, Вы увидите в упражнении 4.50.

В разделе 4.2 мы решил и реализовать ленивый интерпретатор как модификацию обыкновенного метацик-

лического интерпретатора из раздела 4.1.1. Напротив, здесь в основу amb-интерпретатора мы кладем анализи-

рующий интерпретатор из раздела 4.1.7, поскольку исполнительные процедуры этого интерпретатора служат

удобной базой для реализации поиска с возвратом.

4.3. SCHEME с вариациями — недетерминистское вычисление

395

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

и передает его значение продолжению успеха. Кроме того, он с троит и передает вместе

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

другой вариант.

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

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

ваемого варианта (например, вызов require может привести к выпол нению (amb), а

это выражение всегда терпит неудач у — см. раздел 4.3.1). В этом месте продолжение

неудачи вернет нас к последней по времени точке и оттуда направит по другому вариан-

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

в предыду щей точ ке выбора, и так далее. Кроме того, продолжения неудачи запускаются

управляющим циклом в ответ на запрос try-again, чтобы найти еще одно значение

последнего выражения.

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

исходит операци я с побочным эффектом (например, присваивание переменной ), то может

понадобиться отменить побочный эффект, е сли процесс наткнется на неудачу, прежде

чем будет сделан новый выбор. Этого мы добиваемся, застави в операцию с побочным эф-

фектом порождать продол жение неудачи, которое отменяет эффект и отправляет неудачу

дальше.

Итак, продолжения неудачи порождаются

• в выражениях amb — чтобы обеспечить механизм выбора альтернативных вариан-

тов, если текущий выбор, сделанный внутри amb, приведет к тупику;

• в управляющем цикле верхнего уровня — чтобы иметь возможность сообщить о

неудаче, когда перебраны все ал ьтернативы;

• в присваиваниях — чтобы во время отката перехватывать неудачи и отменять при-

сваивания.

Неудачи возбуждаются только тогда, когда программа заходит в тупик. Это происхо-

дит

• если пользовательская программа выполняет выражение (amb);

• если пользователь печатает try-again в управляющем цикле.

Кроме того, продолжения неудачи вызываются при обработке неудачи:

• Когда продолжение неудачи, порожденное присваиванием , заканчивает отмену по-

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

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

сваиванию, либо до верхнего уровня.

• Когда продолжение неудач и для amb исчерпывает все варианты выбора, оно вы-

зывает продолжение неудачи, которое изначально было дано amb, и посредством его

распространяет неудачу до предыдущей точки выбора, либо до верхнего уровня.

Стру ктура инт ерпретатора

Процедуры представления синтаксиса и данных в amb-интерпретаторе, а также базо-

вая процедура analyze, совпадают с соответствующими процедурами в интерпретаторе

396

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

из раздела 4.1.7, только здесь тре буются дополнительные синтаксические процедуры для

анализа особой формы amb

(define (amb? exp) (tagged-list? exp ’amb))

(define (amb-choices exp) (cdr exp))

Кроме того, требуется добавить в процедуру разбора analyze ветку, которая будет рас-

познавать эту особую форму и порождать соответствующую исполнительную процедуру:

((amb? exp) (analyze-amb exp))

Процедура верхнего уровня ambeval (сходная с версией eval?, приведенной в раз-

деле 4.1.7) анализирует данное выражение и применяет полученную исполнительную

процедуру к данному окружению и двум данным продолжениям:

(define (ambeval exp env succeed fail)

((analyze exp) env succeed fail))

Продол жение успеха представляет собой процедуру от двух аргументов: только что

полученного значения и продолжения неудачи, которое нужно будет применить, если

обработка значения впоследствии приведет к неудаче. Продолжение неудачи представ-

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

процедуры такова:

(lambda (env succeed fail)

;; succeed выглядит как (lambda (value fail) ...)

;; fail выглядит как (lambda () ...)

...)

Напри мер,

(ambeval hвыражениеi

the-global-environment

(lambda (value fail) value)

(lambda () ’failed))

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

будет успешным), либо символ failed (если вычисление потерпит неудачу). Вызов

ambeval в нижеприведенном управля ющем цикле использует намного более сложные

процедуры продолжения, которые возвращаются к выполнению цикла и поддерживают

запрос try-again.

Сложность amb-интерпретатора по большей части заключается в механизмах пере-

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

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

щей процедурой обыкновенного интерпретатора из раздела 4.1.7.

Мы предполагаем, что интерпретатор поддерживает let (см. упражнение 4.22), который мы использовали

в недетерминистских программах.

4.3. SCHEME с вариациями — недетерминистское вычисление

397

Простые выражения

Исполнительные процедуры для простейших видов выражений здесь, в сущности, та-

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

продолжениями. Исполнительные процедуры просто зовут продолжение успеха, давая

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

сами.

(define (analyze-self-evaluating exp)

(lambda (env succeed fail)

(succeed exp fail)))

(define (analyze-quoted exp)

(let ((qval (text-of-quotation exp)))

(lambda (env succeed fail)

(succeed qval fail))))

(define (analyze-variable exp)

(lambda (env succeed fail)

(succeed (lookup-variable-value exp env)

fail)))

(define (analyze-lambda exp)

(let ((vars (lambda-parameters exp))

(bproc (analyze-sequence (lambda-body exp))))

(lambda (env succeed fail)

(succeed (make-procedure vars bproc env)

fail))))

Заметим, что поиск переменной всегда «успешен ». Если процедуре lookup-va-

riable-value не удается найти значение, она, как обычно, сообщает об ошибке. Та-

кая «неудача» означает ошибку в программе: ссылку на несвязанную переменную; это

не означает, что нам нужно пробовать какой-либо другой вариант недетерминистского

выбора вместо того, который исполняется сейчас.

Условные выражения и последовательности

Обработка условных выражений также похожа на соответствующий процесс в обыч-

ном интерпретатор е. Исполнительная процедура, порождаемая в analyze-if, зовет ис-

полнительную процедуру предиката pproc с продолжением успеха, которое, проверив,

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

альтернати ву. Если выполнение pproc терпит неудачу, вызывается исходное продолже-

ние неудачи, переданное в выражение if.

(define (analyze-if exp)

(let ((pproc (analyze (if-predicate exp)))

(cproc (analyze (if-consequent exp)))

(aproc (analyze (if-alternative exp))))

(lambda (env succeed fail)

(pproc env

398

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

;; продолжение успеха при вычислении предиката

;; и получении pred-value

(lambda (pred-value fail2)

(if (true? pred-value)

(cproc env succeed fail2)

(aproc env succeed fail2)))

;; продолжение неудачи при вычислении предиката

fail))))

Последовательности тоже обрабатываются так же, как и в предыдущем интерпрета-

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

для передачи продолжений. А именно, чтобы выполнить последовате льно a и b, мы

вызываем a с продолжением успеха, вызывающим b.

(define (analyze-sequence exps)

(define (sequentially a b)

(lambda (env succeed fail)

(a env

;; продолжение успеха при вызове a

(lambda (a-value fail2)

(b env succeed fail2))

;; продолжение неудачи при вызове a

fail)))

(define (loop first-proc rest-procs)

(if (null? rest-procs)

first-proc

(loop (sequentially first-proc (car rest-procs))

(cdr rest-procs))))

(let ((procs (map analyze exps)))

(if (null? procs)

(error "Пустая последовательность -- ANALYZE"))

(loop (car procs) (cdr procs))))

Определения и присваивания

Определения — еще один случай, когда обработка продолжений сопряжена с извест-

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

значением определяемой переменной, а затем уже ее собственно определить. Ради этого

процедура вычисления значения vproc вызывается со следующими аргументами: окру-

жение, продолжение успеха и продолжение неудачи. Если вычисление vproc происходит

успешно и дает значение val для определяемой переменной, то переменная определяе тся

и успех распространяется далее:

(define (analyze-definition exp)

(let ((var (definition-variable exp))

(vproc (analyze (definition-value exp))))

(lambda (env succeed fail)

(vproc env

(lambda (val fail2)

(define-variable! var val env)

4.3. SCHEME с вариациями — недетерминистское вычисление

399

(succeed ’ok fail2))

fail))))

Присваивания устроены интереснее. Это первый случай, когда м ы действительно ис-

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

ная процедура для присваивания начинается так же, как и процедура для определения.

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

Если вычисление vproc терпит неудачу, неудачно и все присваивание.

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

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

может быть, при ведет к неудаче. Тогда нам понадобится откатиться к моменту до присва-

ивания. Таким образом, нам нужно уметь отменить присваивание в процессе возврата

Этого мы добиваемся, передавая vproc продолжение успеха (отмеченное ниже ком-

ментарием «*1*»), которое сохраняет старое значение переменной, прежде чем присвоить

ей новое значение и продолжить вычисление. Продолжение неудачи, ко торое передается

вме сте со значением присваивания (и отмечено ниже комментарием «*2*»), восстанавли-

вает старое значение переменной, прежде чем продолжить откат. То есть, успешное при -

сваивание дает продолжение неудачи, которое перехватит последующую неудачу; неуда-

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

она отменяет присваивание и уже затем зовет fail2.

(define (analyze-assignment exp)

(let ((var (assignment-variable exp))

(vproc (analyze (assignment-value exp))))

(lambda (env succeed fail)

(vproc env

(lambda (val fail2) ; *1*

(let ((old-value

(lookup-variable-value var env)))

(set-variable-value! var val env)

(succeed ’ok

(lambda () ; *2*

(set-variable-value! var

old-value

env)

(fail2)))))

fail))))

Вызов процедур

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

ных технических деталей работы с продолжениями. Сложность возникает внутри ana-

lyze-application и обусловлена необходимостью следить за продолжениями успеха

и неудачи при вычислении операндов. Мы вычисляем операнды с помощью процедуры

get-args, а не простого map, как в обыкновенном интерпретаторе.

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

изымаются (раздел 4.1.6).

400

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

(define (analyze-application exp)

(let ((fproc (analyze (operator exp)))

(aprocs (map analyze (operands exp))))

(lambda (env succeed fail)

(fproc env

(lambda (proc fail2)

(get-args aprocs

env

(lambda (args fail3)

(execute-application

proc args succeed fail3))

fail2))

fail))))

Заметьте, как в get-args для дви жения через cdr по списку исполнител ьных про-

цедур aproc и сборки через cons получающегося списка аргументов каждая aproc в

списке вызывается с продолжением успеха, которое рекурсивно зовет get-args. Каж-

дый из этих рекурсивных вызовов get-args имеет продолжен ие успеха, значение ко-

торого — cons свежеполученного аргумента со списком уже собранных аргументов:

(define (get-args aprocs env succeed fail)

(if (null? aprocs)

(succeed ’() fail)

((car aprocs) env

;; продолжение успеха для этой aproc

(lambda (arg fail2)

(get-args (cdr aprocs)

env

;; продолжение успеха для

;; рекурсивного вызова get-args

(lambda (args fail3)

(succeed (cons arg args)

fail3))

fail2))

fail)))

Собственно вызов процедуры, который выполняет execute-application, осу-

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

димо управлять продолжениями.

(define (execute-application proc args succeed fail)

(cond ((primitive-procedure? proc)

(succeed (apply-primitive-procedure proc args)

fail))

((compound-procedure? proc)

((procedure-body proc)

(extend-environment (procedure-parameters proc)

args

(procedure-environment proc))

succeed