dispatch, в регистре proc содержится подлежащая применению процедура, а в регистре argl список вычисленных аргументов, к которым ее требуется применить. Сохраненное значение continue (исходно оно передается подпрограмме eval-dispatch, а затем сохраняется внутри ev-application), которое определяет, куда нам надо вернуться с результатом применения процедуры, находится на стеке. Когда вызов вычислен, контроллер передает управление в точку входа, указанную в сохраненном continue, а результат при этом хранится в val. Подобно метациклическому apply, нужно рассмотреть два случая. Либо применяемая процедура является примитивом, либо это составная процедура.

apply-dispatch

(test (op primitive-procedure?) (reg proc))

(branch (label primitive-apply))

(test (op compound-procedure?) (reg proc))

(branch (label compound-apply))

(goto (label unknown-procedure-type))

Мы предполагаем, что все примитивы реализованы так, что они ожидают аргументы в регистре argl, а результат возвращают в val. Чтобы описать, как машина обрабатывает примитивы, нам пришлось бы дать последовательность команд, которая реализует каждый примитив, и заставить primitive-apply переходить к этим командам в зависимости от содержимого proc. Поскольку нас интересуют не детали примитивов, а структура процесса вычисления, мы вместо этого будем просто использовать операцию apply-primitive-procedure, которая применяет процедуру, содержащуюся в proc, к аргументам, содержащимся в argl. Чтобы смоделировать вычислитель имитатором из раздела 5.2, мы используем процедуру apply-primitiveprocedure, которая исполняет процедуру с помощью нижележащей Scheme-системы, как мы это делали и в метациклическом интерпретаторе из раздела 4.1.4. После того, как элементарная процедура вычислена, мы восстанавливаем регистр continue и переходим на указанную точку входа.

primitive-apply

(assign val (op apply-primitive-procedure)

(reg proc)

(reg argl)) (restore continue) (goto (reg continue))

Чтобы применить составную процедуру, мы действуем так же, как и в мета-циклическом интерпретаторе. Мы строим кадр, который связывает параметры процедуры с ее аргументами, расширяем этим кадром окружение, хранимое в процедуре, и в этом расширенном окружении вычисляем последовательность выражений, которая представляет собой тело процедуры. Подпрограмма ev-sequence, описанная ниже в разделе 5.4.2, проводит вычисление последовательности.

compound-apply

(assign unev (op procedure-parameters) (reg proc)) (assign env (op procedure-environment) (reg proc)) (assign env (op extend-environment)

(reg unev) (reg argl) (reg env)) (assign unev (op procedure-body) (reg proc)) (goto (label ev-sequence))

Подпрограмма compound-apply - единственное место в интерпретаторе, где регистру env присваивается новое значение. Подобно метациклическому интерпретатору, новое окружение строится из окружения, хранимого в процедуре, а также списка аргументов и соответствующего ему списка связываемых переменных.

5.4.2 Вычисление последовательностей и хвостовая рекурсия

Сегмент кода вычислителя с явным управлением, начинающийся с метки ev-sequence, соответствует процедуре eval-sequence метациклического интерпретатора. Он обрабатывает последовательности выражений в телах процедур, а также явные выражения begin.

Явные выражения begin обрабатываются так: последовательность подлежащих выполнению выражений помещается в unev, регистр continue сохраняется на стеке, а затем происходит переход на ev-sequence.

ev-begin

(assign unev (op begin-actions) (reg exp))

(save continue)

(goto (label ev-sequence))

Неявные последовательности в телах процедур обрабатываются переходом на ev-sequence из compound-apply, причем continue в этот момент уже находится на стеке, поскольку он был сохранен в ev-application.

Метки ev-sequence и ev-sequence-continue образуют цикл, который по очереди вычисляет все выражения в последовательности. Список невычис-ленных пока выражений хранится в unev. Прежде, чем вычислять каждое выражение, мы смотрим, есть ли в последовательности после него еще выражения, подлежащие вычислению. Если да, то мы сохраняем список невычисленных выражений (из регистра unev) и окружение, в котором их надо вычислить (из env), а затем вызываем eval-dispatch, чтобы вычислить выражение. После того, как вычисление закончено, два сохраненных регистра восстанавливаются на метке ev-sequence-continue.

Последнее выражение в последовательности обрабатывается особым образом, на метке ev-sequence-last-exp. Поскольку после этого выражения никаких других вычислять не требуется, не нужно и сохранять unev и env перед переходом на eval-dispatch. Значение всей последовательности равно значению последнего выражения, так что после вычисления последнего выражения требуется только продолжить вычисление по адресу, который хранится на стеке (помещенный туда из ev-application или ev-begin). Мы не устанавливаем continue так, чтобы вернуться в текущее место, восстановить continue со стека и продолжить с хранящейся в нем точки входа, а восстанавливаем continue со стека перед переходом на eval-dispatch, так что после вычисления выражения eval-dispatch передаст управление по этому

адресу.

ev-sequence

(assign exp (op first-exp) (reg unev)) (test (op last-exp?) (reg unev)) (branch (label ev-sequence-last-exp)) (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-last-exp (restore continue) (goto (label eval-dispatch))

Хвостовая рекурсия

В главе 1 мы говорили, что процесс, который описывается процедурой вроде

(define (sqrt-iter guess x) (if (good-enough? guess x) guess

(sqrt-iter (improve guess x)

x)))

итеративен. Несмотря на то, что синтаксически процедура рекурсивна (определена через саму себя), вычислителю нет логической необходимости сохранять информацию при переходе от одного вызова sqrt-iter к другому.25Про вычислитель, который способен вычислить процедуру типа sqrt-iter, не требуя дополнительной памяти по мере ее рекурсивных вызовов, говорят, что он обладает свойством хвостовой рекурсии (tail recursion). Метациклическая реализация вычислителя из главы 4 не указывает, обладает ли вычислитель хвостовой рекурсией, поскольку он наследует механизм сохранения состояния из нижележащей Scheme. Однако в случае вычислителя с явным управлением мы можем проследить процесс вычисления и увидеть, когда вызовы процедур приводят к росту информации на стеке.

Наш вычислитель обладает хвостовой рекурсией, поскольку при вычислении последнего выражения последовательности мы напрямую переходим к eval-dispatch, никакую информацию не сохраняя на стеке. Следовательно, при вычислении последнего выражения последовательности - даже если это рекурсивный вызов (как в sqrt-iter, где выражение if, последнего выражения в теле процедуры, сводится к вызову sqrt-iter) - не происходит никакого роста глубины стека.26

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

26Наша реализация хвостовой рекурсии в ev-sequence - вариант хорошо известного метода оптимизации, используемого во многих компиляторах. При компиляции процедуры, которая заканчивается вызовом процедуры, можно заменить вызов переходом на начало вызываемой процедуры. Встраивание такой стратегии в интерпретатор (как сделано в этом разделе) единым образом распространяет эту оптимизацию на весь язык.