Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 90
Текст из файла (страница 90)
Для того,чтобы это работало, amb-интерпретатор при возврате должен отменять действия операций set!.4.3. SCHEME с вариациями —недетерминистское вычисление391Amb-интерпретатор здесь удобно использовать потому, что ограничения на разборлегко выражаются при помощи 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)))Теперь мы можем сказать, что предложение — это именная группа, за которой следуетглагольная группа, а глагольная группа — это либо глагол, либо глагольная группа,дополненная предложной группой52 :(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-phraseverb-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-phrase52 Заметим,что это определение рекурсивно — за глаголом может следовать любое число предложных групп.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-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-verbphrase так (и то же сделать для именных групп):(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 так, чтобы она игнорировала «входное предложение», всегда53 Грамматики такого рода могут быть сколь угодно сложными, но по сравнению с настоящей обработкойестественного языка они остаются игрушкой. Настоящее понимание естественного языка компьютером требует сложного сочетания синтаксического анализа с интерпретацией значения.
С другой стороны, даже простыеанализаторы могут быть полезны для поддержки гибких командных языков в программах вроде систем поискаинформации. Уинстон (Winston 1992) описывает вычислительные подходы к пониманию настоящего естественного языка, а также применение простых грамматик в командных языках.394Глава 4.
Метаязыковая абстракциязаканчивалась успехом и порождала подходящее слово, мы сможем использовать те же программы, которые мы написали для анализа, для порождения предложений. Реализуйте идею Лизы ипокажите первые пять-шесть порожденных предложений54.4.3.3. Реализация amb-интерпретатораВыполнение выражения в обыкновенной Scheme может вернуть результат, можетвообще не завершиться, и, наконец, может закончиться сообщением об ошибке. В недетерминистской Scheme при выполнении выражения, в дополнение ко всему этому, можетеще обнаружиться тупик, и в этом случае вычисление должно откатиться к предыдущей точке выбора. Интерпретация недетерминистской Scheme осложняется из-за этойдополнительной возможности.Мы построим amb-интерпретатор для недетерминистской Scheme, модифицироваванализирующий интерпретатор из раздела 4.1.755 .
Как и в анализирующем интерпретаторе, вычисление выражения происходит путем вызова исполнительной процедуры, котораяполучается при анализе этого выражения. Разница между интерпретацией обыкновенной Scheme и недетерминистской Scheme будет полностью сводиться к исполнительнымпроцедурам.Исполнительные процедуры и продолженияНапомним, что исполнительные процедуры обыкновенного интерпретатора принимают один аргумент: окружение, в котором происходит вычисление выражения. В противоположность этому, исполнительные процедуры amb-интерпретатора принимают три аргумента: окружение и две процедуры, называемые процедурами продолжения (continuationprocedures).
Вычисление выражения будет заканчиваться вызовом одного из этих продолжений: если результатом вычисления является значение, то зовется продолжениеуспеха (success continuation) с этим значением в качестве аргумента; если вычислениенатыкается на тупик, вызывается продолжение неудачи (failure continuation). Построение и вызов соответствующих продолжений служит механизмом, с помощью которого внедетерминистском интерпретаторе реализуется поиск с возвратом.Задача продолжения успеха — принять значение и продолжить вычисление. Помимоэтого значения, продолжение успеха получает дополнительное продолжение неудачи,которое нужно будет вызвать, если использование значения приведет в тупик.Задача продолжения неудачи — попробовать другую ветвь недетерминистского процесса.
Главная особенность недетерминистского языка состоит в том, что выражениямогут представлять собой точки выбора между вариантами. Выполнение такого выражения должно продолжиться согласно одному из указанных взаимоисключающих вариантов, несмотря на то, что заранее неизвестно, какие варианты приведут к приемлемым54 Несмотря на то, что идея Лизы (будучи удивительно простой) дает результат, порождаемые предложенияоказываются довольно скучными — они не отображают возможные предложения нашего языка никаким интересным образом. Дело в том, что грамматика рекурсивна во многих местах, а метод Лизы «проваливается» водну из рекурсий и там застревает. Как с этим можно бороться, Вы увидите в упражнении 4.50.55 В разделе 4.2 мы решили реализовать ленивый интерпретатор как модификацию обыкновенного метациклического интерпретатора из раздела 4.1.1.
Напротив, здесь в основу amb-интерпретатора мы кладем анализирующий интерпретатор из раздела 4.1.7, поскольку исполнительные процедуры этого интерпретатора служатудобной базой для реализации поиска с возвратом.4.3. SCHEME с вариациями —недетерминистское вычисление395результатам. При обработке такой ситуации интерпретатор выбирает один из вариантови передает его значение продолжению успеха.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
