already-moved

(assign new (op vector-ref) (reg the-cdrs) (reg old)) (goto (reg relocate-continue))

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

gc-flip

(assign temp (reg the-cdrs)) (assign the-cdrs (reg new-cdrs)) (assign new-cdrs (reg temp)) (assign temp (reg the-cars)) (assign the-cars (reg new-cars)) (assign new-cars (reg temp))

5.4 Вычислитель с явным управлением

В разделе 5.1 мы видели, как простые программы на Scheme можно преобразовывать в описания регистровых машин. Теперь мы проделаем такое преобразование с более сложной программой - метациклическим интерпретатором из разделов 4.1.1-4.1.4, который показал нам, как поведение процедур Scheme можно описать через процедуры eval и apply. Вычислитель с явным управлением (explicit-control evaluator), который мы разработаем в этом разделе, демонстрирует, как механизмы вызова процедур и передачи параметров, используемые в процессе вычисления, могут быть описаны в терминах действий, производимых над регистрами и стеками. В дополнение к этому вычислитель с явным управлением может служить реализацией интерпретатора Scheme, написанной на языке, весьма близком к машинному языку обыкновенных компьютеров. Этот вычислитель можно выполнить на имитаторе регистровых машин из раздела 5.2. С другой стороны, его можно использовать как основу для построения вычислителя Scheme, написанного на машинном языке, или даже специализированной машины для вычисления выражений на Scheme. На рисунке 5.16 показана такая аппаратная реализация: кремниевый чип, который работает как вычислитель Scheme. Проектировщики чипа начали с описания путей данных и контроллера, подобного вычислителю из этого раздела, а затем с помощью программ автоматизированного проектирования построили разводку интегральной микросхемы.14

Регистры и операции

При проектировании вычислителя с явным управлением требуется указать операции, которые будут использоваться в нашей регистровой машине. Мета-циклический интерпретатор мы описали, используя абстрактный синтаксис, с процедурами вроде quoted? и make-procedure. При реализации регистровой машины мы могли бы развернуть эти процедуры в последовательности элементарных операций с памятью, работающих со списковой структурой, и уже эти операции реализовать в нашей регистровой машине. Однако при этом

19Информацию о микросхеме и методе ее проектирования можно найти в Batali et al. 1982.

вычислитель получился бы слишком длинным, а его структура была бы загромождена мелкими деталями. Для большей ясности представления мы будем считать элементарными операциями регистровой машины синтаксические процедуры из раздела 4.1.2, а также процедуры для представления окружений и прочих данных интерпретатора из разделов 4.1.3 и 4.1.4. Для того, чтобы полностью описать вычислитель, который можно было бы запрограммировать на машинном языке низкого уровня или реализовать аппаратно, пришлось бы заменить эти операции более примитивными на основе реализации списковой структуры, которую мы описали в разделе 5.3.

Наша регистровая машина-вычислитель Scheme имеет стек и семь регистров: exp, env, val, continue, proc, argl и unev. В регистре exp хранится выражение, подлежащее вычислению, а в регистре env окружение, в котором нужно это вычисление произвести. В конце вычисления val содержит значение, полученное при вычислении выражения в указанном окружении. Регистр continue используется для реализации рекурсии, как описано в разделе 5.1.4. (Вычислитель вызывает сам себя рекурсивно, поскольку вычисление выражения требует вычисления его подвыражений.) Регистры proc, argl и unev используются при работе с комбинациями.

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

5.4.1 Ядро вычислителя с явным управлением

Центральным элементом вычислителя является последовательность команд, расположенная по метке eval-dispatch. Она соответствует процедуре eval метациклического интерпретатора из раздела 4.1.1. Начиная с eval-dis-patch, контроллер вычисляет выражение, хранящееся в exp, в окружении, которое содержится в env. Когда вычисление заканчивается, контроллер пе-

реходит на точку входа, которая хранится в continue, а значение выражения при этом находится в val. Как и в метациклическом eval, структура eval-dispatch представляет собой анализ случаев по синтаксическому типу

20

выполняемого выражения.20

eval-dispatch

(test (op self-evaluating?) (reg exp))

(branch (label ev-self-eval))

(test (op variable?) (reg exp))

(branch (label ev-variable))

(test (op quoted?) (reg exp))

(branch (label ev-quoted))

(test (op assignment?) (reg exp))

(branch (label ev-assignment))

(test (op definition?) (reg exp))

(branch (label ev-definition))

(test (op if?) (reg exp))

(branch (label ev-if))

(test (op lambda?) (reg exp))

(branch (label ev-lambda))

(test (op begin?) (reg exp))

(branch (label ev-begin))

(test (op application?) (reg exp))

(branch (label ev-application))

(goto (label unknown-expression-type))

Вычисление простых выражений

В числах и строках (значением которых являются они сами), переменных, закавыченных выражениях и выражениях lambda не содержится подлежащих вычислению подвыражений. В этих случаях вычислитель попросту помещает нужное значение в регистр val и продолжает работу с точки, указанной в регистре continue. Вычисление простых выражений производится следующим кодом контроллера:

ev-self-eval

(assign val (reg exp))

(goto (reg continue)) ev-variable

(assign val (op lookup-variable-value) (reg exp) (reg env)) (goto (reg continue)) ev-quoted

(assign val (op text-of-quotation) (reg exp)) (goto (reg continue)) ev-lambda

(assign unev (op lambda-parameters) (reg exp)) (assign exp (op lambda-body) (reg exp)) (assign val (op make-procedure)

20В нашем контроллере анализ случаев написан как последовательность команд test и branch. Можно было бы написать его и в стиле программирования, управляемого данными (в реальной системе так, скорее всего, и было бы сделано). При этом исчезла бы необходимость проводить последовательные проверки, и легче было бы определять новые типы выражений. Машина, рассчитанная на выполнение Лисп-программ, скорее всего, имела бы команду dispatch-on-type, которая бы эффективно выполняла выбор, управляемый данными.