Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

5.5. Компиляция

541

hскомпилированный код предиката, цель val, связь nexti

hвосстановить continue, env, если они сохранялисьi

(test (op false?) (reg val))

(branch (label false-branch4)

true-branch5

hскомпилированный код истинной ветви, цель val, связь returni

false-branch4

hскомпилированный код ложной ветви, цель val, связь returni

after-if3

Предикат (= n 1) является вызовом процедуры. Он ищет в окружении оператор

(символ =) и помещает его значение в proc. Затем он собирает аргументы — 1 и

значение n, — в argl. Затем он проверяет, лежит ли в proc примитив или составная

процедура, и соответствующим образом переходит на ветвь элементарной или составной

процедуры. Обе ветви приводят к метке after-call. Требование сохранять регистры

при вычислении оператора и операндов не приводит ни к каким операциям сохранения,

поскольку в этом случае вычисления не трогают нужные регистры.

(assign proc

(op lookup-variable-value) (const =) (reg env))

(assign val (const 1))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

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

(branch (label primitive-branch17))

compiled-branch16

(assign continue (label after-call15))

(assign val (op compiled-procedure-entry) (reg proc))

(goto reg val)

primitive-branch17

(assign val (op apply-primitive-procedure)

(reg proc)

(reg argl))

after-call15

Истинная ветвь, константа 1, компилируется (с целевым регистром val и типом

связи return) в

(assign val (const 1))

(goto (reg continue))

Код для ложной ветви является еще одним вызовом процедуры, где процедурой слу-

жит значение символа *, а аргументами — n и значение еще одного вызова (вызова

factorial). Каждый из этих вызовов устанавливает значения proc и argl, а так-

же свои собственные ветви для элементарных и составных процедур. На рисунке 5.17

показан полный скомпилированный код для опреде ления процедуры factorial. Заме-

тим, что возможные команды save и restore для continue и env при вычислении

предиката, указанные выше, на самом деле порождаются, поскольку эти ре гистры изме-

няются во время вызова процедуры в предикате и нужны для вызова процедуры и связи

return в ве твях.

542

Глава 5. Вычисления на регистровых машинах

;; построить процедуру и обойти ее тело

(assign val (op make-compiled-procedure) (label entry2) (reg env))

(goto (label after-lambda1))

entry2 ; вызовы factorial будут попадать сюда

(assign env (op compiled-procedure-env) (reg proc))

(assign env

(op extend-environment) (const (n)) (reg argl) (reg env))

;; начинается собственно тело процедуры

(save continue)

(save env)

;; вычислить (= n 1)

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

(assign val (const 1))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

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

(branch (label primitive-branch17))

compiled-branch16

(assign continue (label after-call15))

(assign val (op compiled-procedure-entry) (reg proc))

(goto reg val)

primitive-branch17

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call15 ; здесь val содержит результат (= n 1)

(restore env)

(restore continue)

(test (op false?) (reg val))

(branch (label false-branch4))

true-branch5 ; вернуть 1

(assign val (const 1))

(goto (reg continue))

false-branch4

;; вычислить и вернуть (* (factorial (- n 1) n))

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

(save continue)

(save proc) ; сохранить процедуру *

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op list) (reg val))

(save argl) ; сохранить частичный список аргументов для *

Рис. 5.17. Скомпилированный код опреде ления процедуры factorial. (Продолжение

на следующей странице.)

5.5. Компиляция

543

;; вычислить (factorial (- n 1)), еще один аргумент *

(assign proc

(op lookup-variable-value) (const factorial) (reg env))

(save proc) ; сохранить процедуру factorial

;; вычислить (- n 1), аргумент factorial

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

(assign val (const 1))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

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

(branch (label primitive-branch8))

compiled-branch7

(assign continue (label after-call6))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch8

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call6 ; теперь в val содержится результат (- n 1)

(assign argl (op list) (reg val))

(restore proc) ; восстановить factorial

;; применить factorial

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

(branch (label primitive-branch11))

compiled-branch10

(assign continue (label after-call9))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch11

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call9 ; теперь val содержит результат (factorial (- n 1))

(restore argl) ; восстановить частичный список аргументов для *

(assign argl (op cons) (reg val) (reg argl))

(restore proc) ; восстановить *

(restore continue)

;; применить * и вернуть

;; его результат

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

(branch (label primitive-branch14))

compiled-branch13

;; обратите внимание:

;; скомпилированная процедура здесь зовется

;; с хвостовой рекурсией

Рис. 5.17. Скомпилированный код определения процедуры factorial. Продолжение.

(Окончание на следующей странице.)

544

Глава 5. Вычисления на регистровых машинах

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch14

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

(goto (reg continue))

after-call12

after-if3

after-lambda1

;; присвоить процедуру переменной factorial

(perform

(op define-variable!) (const factorial) (reg val) (reg env))

(assign val (const ok))

Рис. 5.17. Скомпилированный код определения процедуры factorial. Окончание.

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

Рассмотрим следующее определение процедуры для вычисления факториала, которое незначитель-

но отличается от рассмотренного в тексте:

(define (factorial-alt n)

(if (= n 1)

(* n (factorial-alt (- n 1)))))

Скомпилируйте эту процедуру и сравните получившийся код с кодом для factorial. Объясните

обнаруженные различия. Есть ли разница в эффективности программ?

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

Скомпилируйте итеративную процедуру вычисления факториала:

(define (factorial n)

(define (iter product counter)

(if (> counter n)

product

(iter (* counter product)

(+ counter 1))))

(iter 1 1))

Прокомментируйте полученный код и покажите существенное различие между кодом для итера-

тивной и рекурсивной версий factorial, благодаря которому один процесс наращивает глубину

стека, а второй выполняется при фиксированной глубине.

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

При компиляции какого выражения был получен код на рисунке 5.18?

5.5. Компиляция

545

(assign val (op make-compiled-procedure) (label entry16)

(reg env))

(goto (label after-lambda15))

entry16

(assign env (op compiled-procedure-env) (reg proc))

(assign env

(op extend-environment) (const (x)) (reg argl) (reg env))

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

(save continue)

(save proc)

(save env)

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

(save proc)

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

(assign val (const 2))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const x) (reg env))

(assign argl (op cons) (reg val) (reg argl))

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

(branch (label primitive-branch19))

compiled-branch18

(assign continue (label after-call17))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch19

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call17

(assign argl (op list) (reg val))

(restore proc)

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

(branch (label primitive-branch22))

compiled-branch21

(assign continue (label after-call20))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch22

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

Рис. 5.18. Пример вывода компилятора. См. упражнение 5.35. (Продолжение на следую-

щей странице .)

546

Глава 5. Вычисления на регистровых машинах

after-call20

(assign argl (op list) (reg val))

(restore env)

(assign val (op lookup-variable-value) (const x) (reg env))

(assign argl (op cons) (reg val) (reg argl))

(restore proc)

(restore continue)

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

(branch (label primitive-branch25))

compiled-branch24

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch25

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

(goto (reg continue))

after-call23

after-lambda15

(perform (op define-variable!) (const f) (reg val) (reg env))

(assign val (const ok))

Рис. 5.18. Пример вывода компилятора (продолжение).

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

Какой порядок вычисления задает наш компилятор для операндов комбинации — слева напра-

во, справа налево, или какой-либо иной? Где в компиляторе задается этот порядок? Измените

компилятор так, чтобы он порождал какой-нибудь другой порядок вычисления. (См. обсуждение

порядка вычисления для вычислителя с явным управлением из раздела 5.4.1.) Как смена порядка

вычисления операндов влияет на эффективнос ть кода, который строит список аргументов?

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

Вот один из способов понять, как механизм preserving оптимизирует использование стека:

рассмотреть, какие дополнительные операции порождались бы, если бы мы этот механизм не

использовали. Измените preserving так, чтобы операции save и restore порождались всегда.

Скомпилируйте несколько простых выражений и отметьте ненужные операции со стеком, которые

станут порождаться. Сравните этот код с тем, который порождается, если механизм preserving

присутствует.

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

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

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

мер, сколько кода порождается для вычисления (+ a 1): код порождает список аргументов в

argl, помещает элементарную процедуру сложения (которую он находит через поиск символа + в

окружении) в proc, затем проверяет, является ли эта процедура элементарной или составной.

Компилятор всегда порождает код э той проверки, а также код для ветви элементарной процедуры

и ветви составной процедуры (из которых только одна будет выполняться). Мы не показали ту

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

зуют элементарные арифметические операции в путях данных машины. Рассмотрим, насколько

5.5. Компиляция

547

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

кода (open coding) — то есть порождать код, который прямо использует эти машинные операции.

Выражение (+ a 1) можно было бы скомпилировать в простую последовательность вроде

(assign val (op lookup-variable-value) (const a) (reg env))

(assign val (op +) (reg val) (const 1))

В этом упражнении мы расширим компилятор так, чтобы он поддерживал явное кодирование

отдельных примитивов. При обращениях к этим примитивам будет порождаться специально напи-

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

мы дополним машину специальными регистрами для арг ументов arg1 и arg2. Элементарные

арифметические операции машины буду т принимать свои аргументы в arg1 и arg2. Они могут

помещать результаты в val, arg1 или arg2.

Компилятор должен уметь распознавать вызов явно кодируемого примитива в исходной про-

грамме. Мы дополним распознаватель в процедуре compile, так, чтобы он узнавал имена этих

примитивов в дополнение к зарезервированным словам (особым формам), которые он узна

ет сей-

час

. Для каждой о собой формы в компиляторе ес ть свой генератор кода. В этом упражнении мы

построим семью генераторов кода для явно кодируемых примитивов.

а. В отличие от особых форм, явно кодируемые примитивы требуют, чтобы их аргументы вычис-

лялись. Напишите генератор кода spread-arguments, который будут использовать генераторы

явного кода. Spread-arguments должен принимать список операндов и компилировать данные

ему операнды, направляя их в последовательные аргументные регистры. Заметим, что операнд

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

придется сохранять аргументные регистры.

б. Для каждой из элементарных процедур =, *, - и + напишите по генератору кода, который

принимает комбинацию, содержащую этот оператор вместе с целевым регистром и описателем свя-

зи, и порождает код, который раскидывает аргументы по регистрам, а затем проводит операцию с

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

с двумя операндами. Заставьте compile передавать управление этим генераторам кода.

в. Опробуйте обновленный компилятор на примере с процедурой factorial. Сравните полу-

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

г. Расширьте свои генераторы кода для + и * так, чтобы они могли обрабатывать выражения с

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

лировать в последовательность операций, каждая из которых работает с двумя входами.

5.5.6. Лексическая адресация

Одна из наиболе е часто встречающихся в компиляторах оптимизаций связана с по -

иском переменных. В нынешнем виде наш компилятор использует операцию lookup-

variable-value машины-вычислителя. Эта операция ищет переменную, сравнивая ее

со всеми переменными, связанными в данный момент, и проходя кадр за кадром по окру-

жению, имеющемуся во время выполнения. Если кадр глубоко вложен или если имеется

Здесь мы одним символом + обозначаем и процедуру исходного языка, и машинную операцию. В общем

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

Вообще говоря, превращение примитивов в зарезервированные слова — плохая идея, потому что тогда

пользователь не может связать эти имена с другими процедурами. Более того, если мы добавим зарезер-

вированные слова в компилятор, который уже используется, перестанут работать существующие программы,

которые определяют процедуры с такими именами . Идеи, как можно избежать этой проблемы, можно найти в

упражнении 5.44.

548

Глава 5. Вычисления на регистровых машинах

много переменных, этот поиск може т оказаться дорогим. Рассмотрим , например, задачу

поиска значен ия x при вычислении выражения (* x y z) внутри процедуры, во звра-

щаемой при вычислении

(let ((x 3) (y 4))

(lambda (a b c d e)

(let ((y (* a b x))

(z (+ c d x)))

(* x y z))))

Поскольку выражение let — всего лишь синтаксический сахар для комбинации

lambda, это выражение равносильно

((lambda (x y)

(lambda (a b c d e)

((lambda (y z) (* x y z))

(* a b x)

(+ c d x))))

Каждый раз, когда lookup-variable-value ищет x, она должна убедиться, что сим-

вол x не равен (через eq?) ни y, ни z (в первом кадре), ни a, b, c, d, ни e (во втором).

Предположим, вр еменно, что в наших программах не используется define — что пере-

менные связываются только через lambda. Поскольку в нашем языке лексическая сфера

действия, во время выполнения окружение л юбого выражения будет иметь структуру, па-

раллельную лексической структуре программы, в которой это выражение встречается

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

каждый раз, когда процедура применяется, переменная с именем x будет найдена на два

кадра выше текущего, и в этом кадре будет пер вая.

Мы можем это использовать и ввести новый вид операции поиска переменной,

lexical-address-lookup, который в качестве аргументов берет окружение и лекси-

ческий адрес (lexical address), состоящий из двух чисел: номера кадра (frame number),

который показывает, сколько кадров надо пропустить, и смещения (displacement

number), которое показывает, сколько переменных нужно пропустить в этом кадре.

Lexical-address-lookup будет возвращать значение переменной, которая имеет у ка-

занный лексический адрес по отношению к текущему окружению. Добавив в свою ма-

шину lexical-address-lookup, мы можем научить компилятор порождать код, ко-

торый обращается к переменным через эту операцию, а не через lookup-variable-

value. Подобным образом, скомпилированный код может использовать новую операцию

lexical-address-set! вме сто set-variable-value!.

Для того, чтобы порождать такой код, компилятор должен уметь определять лекси-

ческий адрес переменной, ссылку на которую он намерен скомпилировать. Лексический

адрес переменной зависит от того, где она находится в коде. Например, в следующей

программе адрес x в выражении he1i есть (2,0) — на два к адра назад и первая перемен-

ная в кадре. В этом же месте y имеет адрес (0,0), а c — адрес (1,2). В выражении he2i

x имеет адрес (1,0), y адрес (1,1), а c адрес (0,2).

Это не так, если мы разрешаем внутренние определения и если мы от них не избавляемся. См. упражне-

ние 5.43.

5.5. Компиляция

549

((lambda (x y)

(lambda (a b c d e)

((lambda (y z) he1i)

he2i

(+ c d x))))

Один из способов породить в компил я торе код, который использует лексическую ад-

ресацию, состоит в поддержании структуры данных, называемой окружение времени

компиляции (compile-time environment). Она следит за тем, какие переменные в каких

позициях и в каких кадрах будут находиться в окружении времени выполнения, когда

будет выполняться определенная операция доступа к переменной. Окружение времени

компиляции представляет собой список кадров, каждый из которых содержит список

переменных. (Разумеется, с переменными не буде т связано никаких значений, посколь-

ку во время компиляции значения не вычисляются.) Окружение времени компиляции

становится дополнительным аргументом процедуры compile и передается всем гене-

раторам кода. Вызов compile верхнего уровня использует пустое окружение времени

компиляции. Когда компилируется тело lambda, compile-lambda-body расширяет

это окружение кадром, содержащим параметры процедуры, так что последовательность,

которая является телом, компилируется в этом расширенном окружении. В каждой точ-

ке компиляции compile-variable и compile-assignment используют окружение

времени компиляции для порождения соответствующих лексических адресов.

Упражнения с 5.39 по 5.43 описывают, как завершить этот набросок лексической

адресации и включить в компилятор лексический поиск. В у пражнении 5.44 описывается

еще один способ использовать окружение времени компиляции.

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

Напишите процедуру lexical-address-lookup, которая реализует новую операцию поиска.

Она должна брать два аргумента — лексический адрес и окружение времени компиляции, — и

возвращать значение переменной, находящейся по указанному лексическому адресу. Lexical-

address-lookup должна сообщать об ошибке, если значением переменной является символ

*unassigned*

. Кроме того, напишите процедуру lexical-address-set!, реализующую

операцию, которая изменяет значение переменной по указанному лексическому адресу.

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

Модифицируйте компилятор так, чтобы он поддерживал окружение времени компиляции, как

описано выше. а именно, добавьте аргумент-окружение к compile и всем генераторам кода, и

расш иряйте его в compile-lambda-body.

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

Напишите процедуру find-variable, которая в качестве аргументов принимает переменную и

окружение времени компиляции, а возвращает лексический адрес переменной по отношению к

Эта модификация в поиске переменной требуется в том случае, если мы реализуем просмотр текста и

уничтожение внутренних определений (упражнение 5.43). Чтобы лексическая адресация работала, их следует

уничтожить.

550

Глава 5. Вычисления на регистровых машинах

этому окружению. Например, во фрагменте программы, который приведен выше, окружение вре-

мени компиляции при о бработке выражения he1i равно ((y z) (a b c d e) (x y)). Find-

variable должна давать

(find-variable ’c ’((y z) (a b c d e) (x y)))

(1 2)

(find-variable ’x ’((y z) (a b c d e) (x y)))

(2 0)

(find-variable ’w ’((y z) (a b c d e) (x y)))

not-found

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

С помощ ью find-variable из упражнения 5.41 перепишите compile-variable и compile-

assignment так, чтобы они порождали команды лексической адресации. В случаях, когда find-

variable возвращает not-found (то есть, когда переменной нет в окружении времени компи-

ляции), нужно заставлять генераторы кода использовать, как и раньше, операции вычислителя

для поиска связывания. (Единственное место, где может оказаться переменная, не найденная во

время компиляции — это глобальное окружение, которое является частью окружения времени

выполнения, но не окружения времени компиляции

. Поэтому, если хотите, можете заставить

операции вычислителя искать сразу в глобальном окружении, которое можно получить с помо-

щью операции (op get-global-environment), а не в полном локальном окружении, которое

хранится в env.) Проверьте измененный компилятор на нескольких простых примерах, например,

на вложенной комбинации lambda из начала этого раздела.

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

В разделе 4.1.6 мы показали, что определения внутри блочной структуры не следует рассматри-

вать как «настоящие» define. Вместо этого тело процедуры следует интерпретировать так, как

будто внутренние переменные, определяемые через define, были введены как обыкновенные пе-

ременные lambda, а их настоя щее значение было им присвоено через set!. В разделе 4.1.6 и

упражнении 4.16 показывало сь, как можно изменить метациклический интерпретатор и добиться

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

же преобразование, прежде чем компилировать тело процедуры.

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

В этом разделе мы в основном говорили о том, как с помощью окружения времени компиляции

порождать лексические адреса. Однако такие окружения можно использовать и другими спосо-

бами. Например, в упражнении 5.38 мы повысили эффективность скомпилированного кода путем

явного кодирования элементарных процедур. Наша реализация обрабатывала имена явно кодируе-

мых процедур как зарезервированные слова. Если бы какая-либо программа переопределяла такое

имя, механизм, описанный в упражнении 5. 38, продолжал бы явно кодировать его как примитив

и игнорировал бы новое связывание. Рассмотрим, например, процедуру

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

эти имена можно определять и переопределять интерактивно когда угодно. Если внутренние определения вычи-

щены, как в упражнении 5.43, то компилятор видит только определения верхнего уровня, которые действуют

на глобальное окружение. Компиляция определения не приводит к тому, что определяемое имя вводится в

окружение времени компиляции.