Упражнение 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.

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

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

Лизу П. Хакер больше интересует не анализ предложений, а их порождение. Она замечает, что если изменить процедуру parse-word так, чтобы она игнорировала «входное предложение», всегда заканчивалась успехом и порождала подходящее слово, мы сможем использовать те же программы, которые мы написали для анализа, для порождения предложений. Реализуйте идею Лизы и покажите первые пять-шесть порожденных предложений.54

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

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

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

53Грамматики такого рода могут быть сколь угодно сложными, но по сравнению с настоящей обработкой естественного языка они остаются игрушкой. Настоящее понимание естественного языка компьютером требует сложного сочетания синтаксического анализа с интерпретацией значения. С другой стороны, даже простые анализаторы могут быть полезны для поддержки гибких командных языков в программах вроде систем поиска информации. Уинстон (Winston 1992) описывает вычислительные подходы к пониманию настоящего естественного языка, а также применение простых грамматик в командных языках.

54 Несмотря на то, что идея Лизы (будучи удивительно простой) дает результат, порождаемые предложения оказываются довольно скучными - они не отображают возможные предложения нашего языка никаким интересным образом. Дело в том, что грамматика рекурсивна во многих местах, а метод Лизы «проваливается» в одну из рекурсий и там застревает. Как с этим можно бороться, Вы увидите в упражнении 4.50.

55В разделе 4.2 мы решили реализовать ленивый интерпретатор как модификацию обыкновенного метациклического интерпретатора из раздела 4.1.1. Напротив, здесь в основу amb-интерпретатора мы кладем анализирующий интерпретатор из раздела 4.1.7, поскольку исполнительные процедуры этого интерпретатора служат удобной базой для реализации поиска с возвратом.

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

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

Напомним, что исполнительные процедуры обыкновенного интерпретатора принимают один аргумент: окружение, в котором происходит вычисление выражения. В противоположность этому, исполнительные процедуры amb-интерпретатора принимают три аргумента: окружение и две процедуры, называемые процедурами продолжения (continuation procedures). Вычисление выражения будет заканчиваться вызовом одного из этих продолжений: если результатом вычисления является значение, то зовется продолжение успеха (success continuation) с этим значением в качестве аргумента; если вычисление натыкается на тупик, вызывается продолжение неудачи (failure continuation). Построение и вызов соответствующих продолжений служит механизмом, с помощью которого в недетерминистском интерпретаторе реализуется поиск с возвратом.

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

Задача продолжения неудачи - попробовать другую ветвь недетерминистского процесса. Главная особенность недетерминистского языка состоит в том, что выражения могут представлять собой точки выбора между вариантами. Выполнение такого выражения должно продолжиться согласно одному из указанных взаимоисключающих вариантов, несмотря на то, что заранее неизвестно, какие варианты приведут к приемлемым результатам. При обработке такой ситуации интерпретатор выбирает один из вариантов и передает его значение продолжению успеха. Кроме того, он строит и передает вместе со значением продолжение неудачи, которое потом можно вызвать, чтобы рассмотреть другой вариант.

Неудача возникает во время вычисления (то есть, зовется продолжение неудачи), когда пользовательская программа явным образом отказывается от текущего рассматриваемого варианта (например, вызов require может привести к выполнению (amb), а это выражение всегда терпит неудачу - см. раздел 4.3.1). В этом месте продолжение неудачи вернет нас к последней по времени точке и оттуда направит по другому варианту. Если же в этой точке выбора больше не осталось вариантов, то запускается неудача в предыдущей точке выбора, и так далее. Кроме того, продолжения неудачи запускаются управляющим циклом в ответ на запрос try-again, чтобы найти еще одно значение последнего выражения.

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

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

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

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

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

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

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

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

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

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

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

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

Процедуры представления синтаксиса и данных в amb-интерпретаторе, а также базовая процедура analyze, совпадают с соответствующими процедурами в интерпретаторе из раздела 4.1.7, только здесь требуются дополнительные синтаксические процедуры для анализа особой формы amb:56

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

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