соответствии с его значением. Каждый раз, когда вычисляется выражение (* (factorial (- n 1)) n) или подвыражения (factorial (- n 1)) и (- n 1), интерпретатор должен произвести анализ случаев внутри eval, выяснить, что выражение является вызовом процедуры, а также извлечь его оператор и операнды. Такой анализ недёшев. Проделывать его многократно неразумно.

Можно преобразовать интерпретатор так, чтобы синтаксический анализ проводился только один раз, и повысить таким образом эффективность работы.28 Мы разбиваем процедуру eval, которая принимает выражение и окружение, на две части. Analyze берет только выражение. Она выполняет синтаксический анализ и возвращает новую исполнительную процедуру (execution procedure). В этой процедуре упакована работа, которую придется проделать при выполнении выражения. Исполнительная процедура берет в качестве аргумента окружение и завершает вычисление. При этом экономится работа, потому что analyze будет для каждого выражения вызываться только один раз, а исполнительная процедура, возможно, многократно.

После разделения анализа и выполнения eval превращается в

(define (eval exp env) ((analyze exp) env))

Результатом вызова analyze является исполнительная процедура, которая применяется к окружению. Analyze содержит тот же самый анализ, который делал исходный eval из раздела 4.1.1, однако процедуры, между которыми мы выбираем, только анализируют, а не окончательно выполняют выражение.

(define (analyze exp)

(cond ((self-evaluating? exp)

(analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyze-assignment exp)) ((definition? exp) (analyze-definition exp)) ((if? exp) (analyze-if exp)) ((lambda? exp) (analyze-lambda exp))

((begin? exp) (analyze-sequence (begin-actions exp))) ((cond? exp) (analyze (cond->if exp))) ((application? exp) (analyze-application exp)) (else

(error "Неизвестный тип выражения -- ANALYZE" exp))))

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

(define (analyze-self-evaluating exp) (lambda (env) exp))

28Такое преобразование является неотъемлемой частью процесса компиляции, который мы рассмотрим в главе 5. Джонатан Рис написал для проекта T интерпретатор Scheme с похожей структурой приблизительно в 1982 голу (Rees and Adams 1982). Марк Фили (Feeley 1986, см. также Feeley and Lapalme 1987) независимо изобрел этот метод в своей дипломной работе.

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

(define (analyze-quoted exp)

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

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

(define (analyze-variable exp)

(lambda (env) (lookup-variable-value exp env)))

Анализ присваивания, analyze-assignment, также должен отложить само присваивание до времени выполнения, когда будет в наличии окружение. Однако возможность (рекурсивно) проанализировать выражение assignment-valueсразу, на стадии анализа, - это большой выигрыш в эффективности, поскольку теперь это выражение будет анализироваться только однажды. То же верно и для определений:

(define (analyze-assignment exp)

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

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

(set-variable-value! var (vproc env) env)

ok)))

(define (analyze-definition exp)

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

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

(define-variable! var (vproc env) env)

ok)))

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

(define (analyze-if exp)

(let ((pproc (analyze (if-predicate exp))) (cproc (analyze (if-consequent exp))) (aproc (analyze (if-alternative exp)))) (lambda (env)

(if (true? (pproc env)) (cproc env) (aproc env)))))

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

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

(define (analyze-lambda exp)

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

(bproc (analyze-sequence (lambda-body exp)))) (lambda (env) (make-procedure vars bproc env))))

Анализ последовательности выражений (в begin или в теле lambda-выражения) более сложен.30 Каждое выражение в последовательности анализируется, и для каждого получается исполнительная процедура. Эти исполнительные процедуры комбинируются в одну общую исполнительную процедуру, которая принимает в качестве аргумента окружение и последовательно вызывает каждую из частичных исполнительных процедур, передавая ей окружение как аргумент.

(define (analyze-sequence exps)

(define (sequentially proc1 proc2)

(lambda (env) (proc1 env) (proc2 env))) (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))))

Для вызова процедуры мы анализируем оператор и операнды и строим исполнительную процедуру, которая вызывает исполнительную процедуру оператора (получая при этом объект-процедуру, которую следует применить) и исполнительные процедуры операндов (получая аргументы). Затем мы все это передаем в execute-application, аналог apply из раздела 4.1.1. Execute-application отличается от apply тем, что тело составной процедуры уже проанализировано, так что нет нужды в дальнейшем анализе. Вместо этого мы просто вызываем исполнительную процедуру для тела, передавая ей расширенное окружение.

(define (analyze-application exp)

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

(aprocs (map analyze (operands exp)))) (lambda (env)

(execute-application (fproc env)

(map (lambda (aproc) (aproc env))

aprocs)))))

(define (execute-application proc args) (cond ((primitive-procedure? proc)

(apply-primitive-procedure proc args)) ((compound-procedure? proc) ((procedure-body proc) (extend-environment (procedure-parameters proc) args

30См. упражнение 4.23, в котором объясняются некоторые подробности обработки последовательностей.