Мы использовали тот факт, что сохранять информацию необязательно. Если бы мы до этого не додумались, можно было бы реализовать eval-sequence так, что все выражения в последовательности обрабатываются одинаково - сохранение регистров, вычисление выражения, возврат с сохранением регистров,

27

и повторение до тех пор, пока не вычислятся все выражения:27

ev-sequence

(test (op no-more-exps?) (reg unev)) (branch (label ev-sequence-end)) (assign exp (op first-exp) (reg unev)) (save unev) (save env)

(assign continue (label ev-sequence-continue)) (goto (label eval-dispatch)) ev-sequence-continue (restore env) (restore unev)

(assign unev (op rest-exps) (reg unev)) (goto (label ev-sequence)) ev-sequence-end

(restore continue) (goto (reg continue))

Может показаться, что это мелкое изменение в предыдущем коде для выполнения последовательности: единственная разница состоит в том, что мы проходим через цикл сохранения-восстановления для последнего выражения последовательности так же, как и для остальных. Интерпретатор по-прежнему будет возвращать для всех выражений то же самое значение. Однако такое изменение теряет свойство хвостовой рекурсии, поскольку теперь после вычисления последнего выражения в последовательности нам придется возвращаться и отменять (бесполезные) сохранения регистров. Эти дополнительные сохранения будут накапливаться в гнезде рекурсивных вызовов. Следовательно, процессы вроде sqrt-iter потребуют памяти пропорционально количеству итераций, а не фиксированного объема. Такая разница может быть существенна. Например, при наличии хвостовой рекурсии можно выразить бесконечный цикл с помощью одного только механизма вызова процедур:

(define (count n) (newline) (display n) (count (+ n 1)))

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

5.4.3 Условные выражения, присваивания и определения

Как и в метациклическом интерпретаторе, особые формы обрабатываются путем частичного выполнения частей выражения. В выражении if нам нужно

27Можно определить no-more-exps? как (define (no-more-exps? seq) (null? seq))

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

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

ev-if

(save exp); сохраняем выражение

(save env) (save continue)

(assign continue (label ev-if-decide))

(assign exp (op if-predicate) (reg exp))

(goto (label eval-dispatch)) ; вычисляем предикат

Вернувшись после вычисления предиката, мы смотрим, является ли его значение истиной или ложью, в зависимости от этого переносим в регистр exp следствие либо альтернативу, и идем на eval-dispatch. Заметим, что после восстановления env и continue eval-dispatch будет выполняться в правильном окружении и вернется после вычисления выражения в правильное место.

ev-if-decide

(restore continue) (restore env) (restore exp)

(test (op true?) (reg val))

(branch (label ev-if-consequent)) ev-if-alternative

(assign exp (op if-alternative) (reg exp))

(goto (label eval-dispatch)) ev-if-consequent

(assign exp (op if-consequent) (reg exp))

(goto (label eval-dispatch))

Присваивания и определения

Присваивания обрабатываются по метке ev-assignment, на которую переход происходит из eval-dispatch с выражением-присваиванием в регистре exp. Код ev-assignment сначала вычисляет значение присваиваемого выражения, а затем заносит это значение в окружение. Предполагается, что set-variable-value! дана как машинная операция.

ev-assignment

(assign unev (op assignment-variable) (reg exp)) (save unev); сохранить переменную

(assign exp (op assignment-value) (reg exp)) (save env) (save continue)

(assign continue (label ev-assignment-1))

(goto (label eval-dispatch)) ; вычислить присваиваемое значение ev-assignment-1

(restore continue) (restore env) (restore unev) (perform

(op set-variable-value!) (reg unev) (reg val) (reg env)) (assign val (const ok)) (goto (reg continue))

Подобным образом обрабатываются и определения:

ev-definition

(assign unev (op definition-variable) (reg exp)) (save unev); сохранить переменную

(assign exp (op definition-value) (reg exp)) (save env) (save continue)

(assign continue (label ev-definition-1))

(goto (label eval-dispatch)) ; вычислить значение переменной ev-definition-1

(restore continue) (restore env) (restore unev) (perform

(op define-variable!) (reg unev) (reg val) (reg env)) (assign val (const ok)) (goto (reg continue))

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

Расширьте вычислитель так, чтобы обрабатывались производные выражения cond, let и тому подобные (раздел 4.1.2). Можно «сжульничать» и считать, что синтаксические трансформации вроде cond->if имеются как машинные операции.28

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

Реализуйте cond как новую особую форму, не сводя его к if. Придется организовать цикл, проверяющий предикаты последовательных ветвей cond, пока один не окажется истинным, а затем с помощью ev-sequence выполнять действия этой ветви.

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

Измените вычислитель так, чтобы он использовал нормальный порядок вычислений, на основе ленивого интерпретатора из раздела 4.2.

5.4.4 Запуск вычислителя

Реализовав вычислитель с явным управлением, мы подходим к концу сюжета, начатого в главе 1 - построения все более точных моделей для процесса вычисления. Мы начали с относительно неформальной подстановочной модели, затем в главе 3 расширили ее до модели с окружениями, позволившей работать с состоянием и его изменением. В метациклическом интерпретаторе из

28На самом деле это не жульничество. В настоящей реализации, построенной с нуля, мы бы на синтаксическом этапе, происходящем раньше собственно выполнения, интерпретировали при помощи вычислителя с явным управлением Scheme-программу, которая производит трансформации исходного кода вроде cond->if.