(reg unev) (reg exp) (reg env)) (goto (reg continue))

Обратите внимание, как ev-lambda пользуется регистрами unev и exp для параметров и тела лямбда-выражения, которые наряду с окружением в регистре env требуется передать операции make-procedure.

Вычисление вызовов процедур

Вызов процедуры описывается комбинацией, состоящей из оператора и операндов. Оператор - подвыражение, значением которого является процедура, а операнды - подвыражения, значения которых являются аргументами, к которым процедуру следует применить. Метациклический eval при обработке вызовов зовет себя рекурсивно и вычисляет таким образом все элементы комбинации, а затем передает результаты в apply, которая и осуществляет собственно применение процедуры. Вычислитель с явным управлением ведет себя точно так же; рекурсивные вызовы осуществляются командами goto, и при этом на стеке сохраняются регистры, значения которых нужно восстановить после возврата из рекурсивного вызова. Перед каждым вызовом мы тщательно смотрим, какие именно регистры требуется сохранить (поскольку их значения потребуются позже).21

В начале обработки процедурного вызова мы вычисляем оператор и получаем процедуру, которую позже надо будет применить к вычисленным операндам. Для того, чтобы вычислить оператор, мы переносим его в регистр exp и переходим на eval-dispatch. В регистре env уже находится то окружение, в котором оператор требуется вычислить. Однако мы сохраняем env, поскольку его значение нам еще потребуется для вычисления операндов. Кроме того, мы переносим операнды в регистр unev и сохраняем его на стеке. Регистр continue мы устанавливаем так, чтобы после вычисления оператора работа продолжилась с ev-appl-did-operator. Однако перед этим мы сохраняем старое значение continue, поскольку оно говорит нам, куда требуется перейти после вычисления вызова.

21 Это важная, но сложная деталь при переводе алгоритмов из процедурного языка типа Лиспа на язык регистровой машины. В качестве альтернативы сохранению только нужных регистров мы могли бы сохранять их все (кроме val) перед каждым рекурсивным вызовом. Такая тактика называется дисциплиной кадрированного стека (framed-stack discipline). Она работает, но при этом сохраняется больше регистров, чем нужно; в системе, где стековые операции дороги, это может оказаться важным. Кроме того, сохранение регистров, с ненужными значениями может привести к удлиннению жизни бесполезных данных, которые в противном случае освободились бы при сборке мусора.

ev-application (save continue) (save env)

(assign unev (op operands) (reg exp)) (save unev)

(assign exp (op operator) (reg exp))

(assign continue (label ev-appl-did-operator))

(goto (label eval-dispatch))

После того, как вычислено значение подвыражения-оператора, мы вычисляем операнды комбинации и собираем их значения в список, хранимый в регистре argl. Прежде всего мы восстанавливаем невычисленные операнды и окружение. Мы заносим пустой список в argl как начальное значение. Затем заносим в регистр proc процедуру, порожденную при вычислении оператора. Если операндов нет, мы напрямую идем в apply-dispatch. В противном

22

случае сохраняем proc на стеке и запускаем цикл вычисления операндов: 22

ev-appl-did-operator

(restore unev); операнды

(restore env)

(assign argl (op empty-arglist))

(assign proc (reg val)); оператор

(test (op no-operands?) (reg unev))

(branch (label apply-dispatch))

(save proc)

При каждом проходе цикла вычисления аргументов вычисляется один аргумент, и его значение добавляется к argl. Для того, чтобы вычислить операнд, мы помещаем его в регистр exp и переходим к eval-dispatch, установив предварительно continue так, чтобы вычисление продолжилось на фазе сбора аргументов. Но еще до этого мы сохраняем уже собранные аргументы (из argl), окружение (из env) и оставшиеся операнды, подлежащие вычислению (из unev). Вычисление последнего операнда считается особым случаем и обрабатывается кодом по метке ev-appl-last-arg.

ev-appl-operand-loop (save argl)

(assign exp (op first-operand) (reg unev)) (test (op last-operand?) (reg unev)) (branch (label ev-appl-last-arg)) (save env) (save unev)

22К процедурам работы со структурой данных вычислителя из раздела 4.1.3 мы добавляем следующие процедуры для работы со списками аргументов:

(define (empty-arglist) ()) (define (adjoin-arg arg arglist) (append arglist (list arg)))

Кроме того, мы проверяем, является ли аргумент в комбинации последним, при помощи дополнительной синтаксической процедуры:

(define (last-operand? ops) (null? (cdr ops)))

(assign continue (label ev-appl-accumulate-arg)) (goto (label eval-dispatch))

После того, как аргумент вычислен, его значение подсоединяется в конец списка, который хранится в argl. Затем операнд убирается из списка невы-численных операндов в unev, и продолжается цикл вычисления аргументов.

ev-appl-accumulate-arg (restore unev) (restore env) (restore argl)

(assign argl (op adjoin-arg) (reg val) (reg argl)) (assign unev (op rest-operands) (reg unev)) (goto (label ev-appl-operand-loop))

Последний аргумент обрабатывается отдельно. Здесь нет необходимости сохранять окружение и список невычисленных операндов перед переходом в eval-dispatch, поскольку после вычисления последнего операнда они не понадобятся. Поэтому после вычисления мы возвращаемся к метке ev-appl-accum-last-arg, где восстанавливается список аргументов, на него наращивается новый (последний) аргумент, восстанавливается сохраненная процедура, и, наконец, происходит переход к применению процедуры.23

ev-appl-last-arg

(assign continue (label ev-appl-accum-last-arg))

(goto (label eval-dispatch)) ev-appl-accum-last-arg

(restore argl)

(assign argl (op adjoin-arg) (reg val) (reg argl)) (restore proc)

(goto (label apply-dispatch))

Детали цикла вычисления аргументов определяют порядок, в котором интерпретатор вычисляет операнды комбинации (то есть справа налево или слева направо - см. упражнение 3.8). Этот порядок оставался неопределенным в ме-тациклическом интерпретаторе, который наследует свою управляющую структуру из нижележащей Scheme, на которой он написан.24 Поскольку селектор first-operand (который используется в ev-appl-operand-loop для последовательного извлечения операндов из unev) реализован как car, а селектор rest-operands реализуется как cdr, вычислитель с явным управлением будет вычислять операнды комбинации в порядке слева направо.

Применение процедур

Точка входа apply-dispatch соответствует процедуре apply метацик-лического интерпретатора. К тому времени, когда мы попадаем в apply-

23Оптимизация при обработке последнего аргумента известна как хвостовая рекурсия в списке аргументов (evlis tail recursion) (см. Wand 1980). Можно было бы особым образом обрабатывать еще и первый аргумент и получить некоторую дополнительную выгоду. Это позволило бы отложить инициализацию argl до того времени, когда будет вычислен первый операнд, и избежать в этом случае сохранения argl. Компилятор в разделе 5.5 проделывает эту оптимизацию. (Сравните с процедурой construct-arglist из раздела 5.5.3.)

24Порядок вычисления операндов в метациклическом интерпретаторе определяется порядком вычисления аргументов cons в процедуре list-of-values из раздела 4.1.1 (см. упражнение 4.1).