Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 91
Текст из файла (страница 91)
Кроме того, он строит и передает вместесо значением продолжение неудачи, которое потом можно вызвать, чтобы рассмотретьдругой вариант.Неудача возникает во время вычисления (то есть, зовется продолжение неудачи),когда пользовательская программа явным образом отказывается от текущего рассматриваемого варианта (например, вызов require может привести к выполнению (amb), аэто выражение всегда терпит неудачу — см. раздел 4.3.1). В этом месте продолжениенеудачи вернет нас к последней по времени точке и оттуда направит по другому варианту.
Если же в этой точке выбора больше не осталось вариантов, то запускается неудачав предыдущей точке выбора, и так далее. Кроме того, продолжения неудачи запускаютсяуправляющим циклом в ответ на запрос try-again, чтобы найти еще одно значениепоследнего выражения.Помимо того, если на какой-то ветке процесса, возникшей в результате выбора, происходит операция с побочным эффектом (например, присваивание переменной), то можетпонадобиться отменить побочный эффект, если процесс наткнется на неудачу, преждечем будет сделан новый выбор. Этого мы добиваемся, заставив операцию с побочным эффектом порождать продолжение неудачи, которое отменяет эффект и отправляет неудачудальше.Итак, продолжения неудачи порождаются• в выражениях amb — чтобы обеспечить механизм выбора альтернативных вариантов, если текущий выбор, сделанный внутри amb, приведет к тупику;• в управляющем цикле верхнего уровня — чтобы иметь возможность сообщить онеудаче, когда перебраны все альтернативы;• в присваиваниях — чтобы во время отката перехватывать неудачи и отменять присваивания.Неудачи возбуждаются только тогда, когда программа заходит в тупик.
Это происходит• если пользовательская программа выполняет выражение (amb);• если пользователь печатает try-again в управляющем цикле.Кроме того, продолжения неудачи вызываются при обработке неудачи:• Когда продолжение неудачи, порожденное присваиванием, заканчивает отмену побочного эффекта, оно вызывает то предложение неудачи, которое оно само перехватило,и посредством его отправляет неудачу назад до точки выбора, которая привела к присваиванию, либо до верхнего уровня.• Когда продолжение неудачи для amb исчерпывает все варианты выбора, оно вызывает продолжение неудачи, которое изначально было дано amb, и посредством егораспространяет неудачу до предыдущей точки выбора, либо до верхнего уровня.Структура интерпретатораПроцедуры представления синтаксиса и данных в amb-интерпретаторе, а также базовая процедура analyze, совпадают с соответствующими процедурами в интерпретаторе396Глава 4.
Метаязыковая абстракцияиз раздела 4.1.7, только здесь требуются дополнительные синтаксические процедуры дляанализа особой формы amb56 :(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выражениеithe-global-environment(lambda (value fail) value)(lambda () ’failed))попытается вычислить данное выражение, и вернет либо его значение (если вычислениебудет успешным), либо символ failed (если вычисление потерпит неудачу). Вызовambeval в нижеприведенном управляющем цикле использует намного более сложныепроцедуры продолжения, которые возвращаются к выполнению цикла и поддерживаютзапрос try-again.Сложность amb-интерпретатора по большей части заключается в механизмах передачи продолжений, когда исполнительные процедуры вызывают друг друга.
Читая код вэтом разделе, следует сравнивать каждую исполнительную процедуру с соответствующей процедурой обыкновенного интерпретатора из раздела 4.1.7.56 Мы предполагаем, что интерпретатор поддерживает 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-variable-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Глава 4.
Метаязыковая абстракция398;; продолжение успеха при вычислении предиката;; и получении 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));; продолжение неудачи при вызове afail)))(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 выполняется удачно, и мы действительно выполняем присваивание, то нам нужно рассмотреть возможность, что текущая ветка вычисления позже,может быть, приведет к неудаче. Тогда нам понадобится откатиться к моменту до присваивания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
