систему новые программы.

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

Обзор компилятора

Наш компилятор во многом похож на наш интерпретатор, как по структуре, так и по функции, которую он осуществляет. Соответственно, механизмы анализа выражений, используемые компилятором, будут подобны тем же механизмам для интерпретатора. Более того, чтобы упростить взаимодействие компилируемого и интерпретируемого кода, мы построим компилятор так, чтобы порождаемый им код следовал тем же соглашениям, что и интерпретатор: окружение будет храниться в регистре env, списки аргументов будут собираться в argl, применяемая процедура - в proc, процедуры будут возвращать свое значение в val, а место, куда им следует вернуться, будет храниться в регистре continue. В общем, компилятор переводит исходную программу в объектную программу, которая проделывает, в сущности, те же самые операции с регистрами, которые провел бы интерпретатор при выполнении той же самой исходной программы.

Это описание подсказывает стратегию для реализации примитивного компилятора: разбирать выражение таким же образом, как это делает интерпретатор. Когда мы встречаем команду работы с регистром, которую интерпретатор выполнил бы при работе с выражением, мы эту команду не выполняем, а добавляем к порождаемой нами последовательности. Полученная последовательность команд и будет объектным кодом. Отсюда видно преимущество в эффективности, которое компиляция имеет перед интерпретацией. Каждый раз, когда интерпретатор выполняет выражение - например, (f 48 96), - он проделывает работу по распознаванию выражения (определение того, что это вызов процедуры) и проверке, не кончился ли список операндов (определение того, что операндов два). В случае с компилятором выражение анализируется только один раз, когда во время компиляции порождается последовательность команд. Объектный код, порожденный компилятором, содержит только команды, которые вычисляют оператор и два операнда, собирают список аргументов и применяют процедуру (из proc) к аргументам (из argl).

Это тот же самый вид оптимизации, который мы применяли в анализирующем интерпретаторе из раздела 4.1.7. Однако в случае компиляции имеются дополнительные возможности повысить эффективность. Интерпретатор при работе следует процессу, который обязан быть приложимым к любому выражению языка. В противоположность этому, всякий данный сегмент скомпилированного кода должен вычислять только одно выражение. Это может приводить к боль-

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

Рассмотрим в качестве примера выражение (f 84 96). Интерпретатор, прежде чем вычислять оператор комбинации, подготавливается к этому вычислению и сохраняет регистры с операндами и окружением, чьи значения ему потребуются позже. Затем интерпретатор вычисляет оператор, получая значение в val, восстанавливает сохраненные регистры, и, наконец, переносит val в proc. Однако в данном конкретном вычислении оператором служит символ f, и его вычисление осуществляется командой lookup-variable-value, которая никаких регистров не изменяет. Компилятор, который мы разработаем в этом разделе, пользуется этим фактом и порождает код для вычисления оператора командой

(assign proc (op lookup-variable-value) (const f) (reg env))

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

Кроме того, компилятор может оптимизировать доступ к среде. Во многих случаях при анализе кода компилятор может определять, в каком кадре будет находиться конкретная переменная, и обращаться к этому кадру напрямую, а не через поиск lookup-variable-value. Мы рассмотрим, как реализуется такой доступ к переменным, в разделе 5.5.6. До тех пор, впрочем, мы сосредоточим внимание на оптимизациях доступа к регистрам и стеку, описанным выше. Имеются и другие виды оптимизаций, которые может производить компилятор: например, «вставка» кода элементарных операций вместо общего механизма apply (см. упражнение 5.38); однако эти оптимизации мы здесь рассматривать не будем. В этом разделе наша цель - проиллюстрировать процесс компиляции в упрощенном (но все же интересном) контексте.

5.5.1 Структура компилятора

В разделе 4.1.7 мы модифицировали исходный метациклический интерпретатор и отделили анализ от выполнения. При анализе каждого выражения порождалась исполнительная процедура, которая в качестве аргумента принимала окружение и проделывала требуемые операции. В компиляторе мы будем проводить, в сущности, такой же анализ. Однако вместо исполнительных процедур мы будем порождать последовательности команд, предназначенных для исполнения на нашей регистровой машине.

Процедура compile проводит в компиляторе анализ верхнего уровня. Она соответствует процедуре eval из раздела 4.1.1, процедуре analyze из раздела 4.1.7 и точке входа eval-dispatch вычислителя с явным управлением из раздела 5.4.1. Подобно интерпретаторам, компилятор использует процедуры разбора синтаксиса выражений из раздела 4.1.2.35 Процедура compile прово-

35Заметим, однако, что наш компилятор является программой на Scheme, и для анализа син-

дит разбор по случаям на основе синтаксического типа выражения, подлежащего компиляции. Для каждого типа выражения она вызывает специальный генератор кода (code generator).

(define (compile exp target linkage) (cond ((self-evaluating? exp)

(compile-self-evaluating exp target linkage)) ((quoted? exp) (compile-quoted exp target linkage)) ((variable? exp)

(compile-variable exp target linkage)) ((assignment? exp)

(compile-assignment exp target linkage)) ((definition? exp)

(compile-definition exp target linkage)) ((if? exp) (compile-if exp target linkage)) ((lambda? exp) (compile-lambda exp target linkage)) ((begin? exp) (compile-sequence (begin-actions exp) target linkage))

((cond? exp) (compile (cond->if exp) target linkage)) ((application? exp)

(compile-application exp target linkage)) (else

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

Целевые регистры и типы связи

Compile и вызываемые оттуда генераторы кода принимают, помимо подлежащего компиляции выражения, еще два аргумента. Во-первых, целевой регистр (target), в который компилируемый код должен поместить значение выражения. Во-вторых, тип связи (linkage descriptor), который описывает, что код, который получается при компиляции, должен делать после того, как он закончит выполняться. Описатель типа связи может потребовать одного из трех следующих действий:

•продолжить со следующей команды в последовательности (на это указывает описатель типа связи next),

•вернуться из компилируемой процедуры (на это указывает описатель типа связи return), или

•перейти на указанную метку (на это указывает использование метки в качестве описателя связи).

Например, компиляция выражения 5 (значение которого равно ему самому) с целевым регистром val и типом связи next должна породить команду

(aasign val (const 5))

таксиса он использует те же процедуры на Scheme, которые использовал метациклический интерпретатор. Для вычислителя с явным управлением мы, наоборот, предполагали, что эквивалентные синтаксические операции присутствуют как примитивы в регистровой машине. (Разумеется, когда мы имитировали эту машину на Scheme, в модели регистровой машины мы использовали эти же процедуры Scheme.)