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

(lambda (env succeed fail)

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

Например,

(ambeval (выражение)

the-global-environment (lambda (value fail) value)

(lambda () failed))

попытается вычислить данное выражение, и вернет либо его значение (если вычисление будет успешным), либо символ failed (если вычисление потерпит неудачу). Вызов ambeval в нижеприведенном управляющем цикле использует намного более сложные процедуры продолжения, которые возвращаются к выполнению цикла и поддерживают запрос try-again.

Сложность amb-интерпретатора по большей части заключается в механизмах передачи продолжений, когда исполнительные процедуры вызывают друг друга. Читая код в этом разделе, следует сравнивать каждую исполнительную процедуру с соответствующей процедурой обыкновенного интерпретатора из раздела 4.1.7.

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

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

(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

;; продолжение успеха при вычислении предиката ;; и получении 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) (succeed ok fail2))

fail))))

Присваивания устроены интереснее. Это первый случай, когда мы действительно используем продолжения, а не просто передаем их из процедуры в процедуру. Исполнительная процедура для присваивания начинается так же, как и процедура для определения. Сначала она пытается получить новое значение, которое надо присвоить переменной. Если вычисление vproc терпит неудачу, неудачно и все присваивание.

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

57

присваивание в процессе возврата.57

Этого мы добиваемся, передавая vproc продолжение успеха (отмеченное ниже комментарием «*/*»), которое сохраняет старое значение переменной, прежде чем присвоить ей новое значение и продолжить вычисление. Продолжение неудачи, которое передается вместе со значением присваивания (и отмечено ниже комментарием «*2*»), восстанавливает старое значение переменной, прежде чем продолжить откат. То есть, успешное присваивание дает продолжение неудачи, которое перехватит последующую неудачу; неудача, которая в противном случае вызвала бы fail2, вместо этого зовет эту процедуру, а она отменяет присваивание и уже затем зовет fail2.

(define (analyze-assignment exp)

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

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