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

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

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

521

ляции, должен делать после того, как он закончит выполняться. Описатель типа связи

может потребовать одного из трех следующих действий:

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

сатель типа связи next),

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

return), или

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

описателя связи).

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

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

(aasign val (const 5))

Компиляция того же самого выражения с типом связи return дол жна породить команды

(assign val (const 5))

(goto (reg continue))

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

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

мещено в целевой регистр val.

По следовательности команд и использование стека

Каждый генератор кода возвращает последовательность команд (instruction

sequence), содержащую порожденный для выражения объектный код. Порождение ко-

да для составных выражений достигается путем соче тания более простых сегментов,

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

выражения проходит через вычисление подвыражений.

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

нием append-instruction-sequences. Она принимает в качестве аргументов про -

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

Процедура склеивает их и возвращает полученную последовательность. а именно, если

hпосл

i и hпосл

i — последовательности команд, то вычисление

(append-instruction-sequences hпосл

i hпосл

вернет последовательность

hпосл

Когда требуется сохранять регистры, генераторы кода используют preserving, бо-

лее сложный метод сочетания последовательностей команд. Preserving принимает три

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

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

522

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

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

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

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

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

ды save и restore для этого регистра, прежде чем склеить последовательности. В

противном случае она просто возвращает склеенные последовательности команд. Так,

например,

(preserving (list hрег

i hрег

i) hпосл

i hпосл

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

того, как hпосл

i и hпосл

i используют hрег

i и hрег

hпосл

или

(save hрег

hпосл

(restore hрег

hпосл

или

(save hрег

hпосл

(restore hрег

hпосл

или

(save hрег

hпосл

(restore hрег

hпосл

Сочетая последовательности команд с помощью preserving, компилятор избегает

лишних операций со стеком. Кроме того, при этом з абота о том, стоит ли порождать

save и restore, целиком оказывается заклю ченной в процедуре preserving и от-

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

кода. В сущности, ни одна команда save или restore не порождается генераторами

кода явно.

В принципе мы могли бы представлять последовательность команд просто как спи-

сок отдельных команд. В таком случае append-instruction-sequences могла бы

склеивать последовательности с помощью обычного append для списков. Однако тогда

preserving оказалась бы более сложной операцией, поскольку ей пришлось бы иссле-

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

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

523

Preserving была бы при этом сложной и неэффективной, поскольку она анализировала

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

тельности могли быть созданы вызовами preserving, и в этом случае и х части были

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

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

она использует регистры. При порождении элементарной последовательности мы будем

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

выводить информацию об использовании регистров для составной последовательности

из информации, связанной с ее последовательностями-компонентами.

Последовательность команд буде т содержать три вида информации:

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

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

дается (ne eds) в этих регистрах),

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

• сами команды (называемые также предложениями (statements)) в последователь-

ности.

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

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

(define (make-instruction-sequence needs modifies statements)

(list needs modifies statements))

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

x в текущем окружении, присваивает его val, а затем возвращается , требует, чтобы

были проинициализированы регистры env и continue, и изменяет регистр val. Сле-

довательно, эту последовател ьность можно построить так:

(make-instruction-sequence ’(env continue) ’(val)

’((assign val

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

(goto (reg continue))))

Иногда нам нужно будет строить последовательность без команд:

(define (empty-instruction-sequence)

(make-instruction-sequence ’() ’() ’()))

Процедуры для сочетания последовательностей команд приведены в разделе 5.5.4.

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

Во время вычисления вызова процедуры вычислитель с я вным управлением всегда сохраняет и

восстанавливает регистр env при вычислении оператора, сохраняет и восстанавливает env при

вычислении каждого операнда (кроме последнего), сохраняет и восстанавливает argl при вычис-

лении каждого операнда, а также сохраняет и восстанавливает proc при вычислении последова-

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

save и restore излишни и могут быть исключены с помощью механизма preserving:

524

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

(f ’x ’y)

((f) ’x ’y)

(f (g ’x) y)

(f (g ’x) ’y)

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

С помощью механизма preserving компилятор сможет избежать сохранения и восстановления

env при вычислении оператора комбинации в случае, если это символ. Такие оптимизации можно

было бы встроить и в интерпретатор. В сущности, вычислитель с явным управлением из раз-

дела 5.4 уже проводит одну подобную оптимизацию, поскольку рассматривает комбинацию без

операндов как особый случай.

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

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

использовал это свойство оператора.

б. Лиза П. Хакер говорит, что если заставить интерпретатор рассматривать все больше особых

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

компиляции пропадет. Каково Ваше мнение?

5.5.2. Компиляция выражений

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

процедура compile.

Компиляция связующего кода

В общем случае результат работы каждого генератора кода будет заканчиваться ко-

мандами — порожденными процедурой compile-linkage, — которые реализуют тре-

буемый тип связи. Если это тип return, то нам надо породить команду (goto (reg

continue)). Она нуждае тся в регистре continue и никаких регистров не меняет. Ес-

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

случаях тип связи — переход по метке, и мы порождаем команду goto на эту метку,

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

(define (compile-linkage linkage)

(cond ((eq? linkage ’return)

(make-instruction-sequence ’(continue) ’()

’((goto (reg continue)))))

((eq? linkage ’next)

В этой процедуре используется конструкция Лиспа, называемая обратная кавычка (backquote) или ква-

зикавычка (quasiquote), с помощью которой удобно строить списки. Обратная кавычка перед списком работает

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

ляются.

Например, если значение linkage равно символу branch25, то результатом выражения ‘((goto (label

,linkage))) будет список ((goto (label branch25))). Подобным образом, если значением x является

список (a b c), то ‘(1 2 ,(car x)) дает при вычислении список (1 2 a).

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

525

(empty-instruction-sequence))

(else

(make-instruction-sequence ’() ’()

‘((goto (label ,linkage)))))))

Связующий код добавляется к последовательности команд с сохранением через

preserving регистра continue, поскольку связь return нуждается в этом реги-

стре: если дан ная по следовательность команд изменяет continue, а связующий код в

нем нуждается, continue будет сохранен и восс тановлен.

(define (end-with-linkage linkage instruction-sequence)

(preserving ’(continue)

instruction-sequence

(compile-linkage linkage)))

Компиляция простых выражений

Генераторы кода для самовычисляющихся выражени й, кавычек и переменных строя т

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

затем ведут себя в соответствии с описателем связи.

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

(end-with-linkage linkage

(make-instruction-sequence ’() (list target)

‘((assign ,target (const ,exp))))))

(define (compile-quoted exp target linkage)

(end-with-linkage linkage

(make-instruction-sequence ’() (list target)

‘((assign ,target (const ,(text-of-quotation exp)))))))

(define (compile-variable exp target linkage)

(end-with-linkage linkage

(make-instruction-sequence ’(env) (list target)

‘((assign ,target

(op lookup-variable-value)

(const ,exp)

(reg env))))))

Все эти последовательности команд изменяют целевой регистр, а для поиска значения

переменной требуется регистр env.

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

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

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

ственно присваивает значение переменной или определяет ее, а затем заносит в целевой

регистр значение всего выражен ия (символ ok). Рекурсивная компиляция вызывается с

целевым регистром val и типом связи next, так что порождаемый код положит резуль-

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

идет за ним. При объединении кода сохраняется env, поскольку для опреде ления и

526

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

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

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

образом.

(define (compile-assignment exp target linkage)

(let ((var (assignment-variable exp))

(get-value-code

(compile (assignment-value exp) ’val ’next)))

(end-with-linkage linkage

(preserving ’(env)

get-value-code

(make-instruction-sequence ’(env val) (list target)

‘((perform (op set-variable-value!)

(const ,var)

(reg val)

(reg env))

(assign ,target (const ok))))))))

(define (compile-definition exp target linkage)

(let ((var (definition-variable exp))

(get-value-code

(compile (definition-value exp) ’val ’next)))

(end-with-linkage linkage

(preserving ’(env)

get-value-code

(make-instruction-sequence ’(env val) (list target)

‘((perform (op define-variable!)

(const ,var)

(reg val)

(reg env))

(assign ,target (const ok))))))))

Двухкомандная последовательность в конце нуждается в env и val и изменяет свой це-

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

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

которым з атем воспользуется эта последовательность. (На самом деле сохранение val

было бы ошибкой, поскольку тогда сразу после выполнения get-value-code восста-

новилось бы старое значение val.)

Компиляция условных выражений

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

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

и типом связи nexti

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

(branch (label false-branch))

true-branch

hскомпилированный код для следствия с указанным целевым регистром и

указанным типом связи либо after-ifi

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

527

false-branch

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

и типом связиi

after-if

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

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

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

ветвь и конец условного выражения

. В этом блоке кода нам требуется обойти истинную

ветвь, если предикат ложен. Единственная небольшая сложность состоит в том, какой

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

return или метка, то и истинная, и ложная ветка будут этот тип и использовать. Если

же тип связи next, то истинная ветвь заканчивается переходом, обходящим код для

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

(define (compile-if exp target linkage)

(let ((t-branch (make-label ’true-branch))

(f-branch (make-label ’false-branch))

(after-if (make-label ’after-if)))

(let ((consequent-linkage

(if (eq? linkage ’next) after-if linkage)))

(let ((p-code (compile (if-predicate exp) ’val ’next))

(c-code

(compile

(if-consequent exp) target consequent-linkage))

(a-code

(compile (if-alternative exp) target linkage)))

(preserving ’(env continue)

p-code

(append-instruction-sequences

(make-instruction-sequence ’(val) ’()

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

(branch (label ,f-branch))))

(parallel-instruction-sequences

Просто использовать метки true-branch, false-branch и after-if нельзя, потому что в программе

может быть больше одного if. Компьютер порождает метки при помощи процедуры make-label. Она прини-

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

последовательные вызовы (make-label ’a) будут возвращать a1, a2 и так далее. Процедуру make-label

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

(define label-counter 0)

(define (new-label-number)

(set! label-counter (+ 1 label-counter))

label-counter)

(define (make-label name)

(string->symbol

(string-append (symbol->string name)

(number->string (new-label-number)))))

528

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

(append-instruction-sequences t-branch c-code)

(append-instruction-sequences f-branch a-code))

after-if))))))

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

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

коду в этих ветвях. Код для истинной и ложной ветви (которые не выполняются после-

довательно) склеи вается с помощью особого комбинатора parallel-instruction-

sequences, описанного в разделе 5.5.4.

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

компилятор должен только запустить преобразование cond->if, а затем скомпилиро-

вать получившееся выражение if.

Компиляция последовательностей

Компиляция последовательностей (тел процедур и явных выражений begin) про-

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

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

остальные с типом связи next (для того, чтобы потом выполнялись остальные выраже-

ния последовательности). Последовательности команд для отдельн ых выражений скле-

иваются и образуют единую последовательность, при этом сохраняются env (необходи-

мый для остатка последовательности) и continue (возможно, требуемый для связи в

конце последовательности).

(define (compile-sequence seq target linkage)

(if (last-exp? seq)

(compile (first-exp seq) target linkage)

(preserving ’(env continue)

(compile (first-exp seq) target ’next)

(compile-sequence (rest-exps seq) target linkage))))

Компиляция выражений lambda

Выражения lambda строят процедуры. Объектный код для выражения lambda дол-

жен иметь вид

hпостроить процедурный объект и присвоить его целевому региструi

hсвязьi

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

Несмотря на то, что во время построения процедурного объекта тело исполняться не бу-

дет, удобно вставить его в код сразу после кода для lambda. Если связь для выражения

lambda — метка или return, никаких сложностей при этом не возникает. Если же у

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

рая переходит на метку, вставляемую сразу вслед за те лом. Таким образом , объектный

код принимает вид

hпостроить процедурный объект и присвоить его целевому региструi

hкод для указанной связиi либо (goto (label after-lambda))

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

529

hскомпилированное тело процедурыi

after-lambda

Процедура compile-lambda порождает код, строящий процедурный объект, вслед

за которым идет код тела процедуры. Процедурный объект порождается во время выпол-

нения путем сочетания текущего окружения (окружения, в ко тором исполняется опре-

деление) и точки входа для скомпилирован ного тела процедуры (свежесгенерированной

метки)

(define (compile-lambda exp target linkage)

(let ((proc-entry (make-label ’entry))

(after-lambda (make-label ’after-lambda)))

(let ((lambda-linkage

(if (eq? linkage ’next) after-lambda linkage)))

(append-instruction-sequences

(tack-on-instruction-sequence

(end-with-linkage lambda-linkage

(make-instruction-sequence ’(env) (list target)

‘((assign ,target

(op make-compiled-procedure)

(label ,proc-entry)

(reg env)))))

(compile-lambda-body exp proc-entry))

after-lambda))))

В compile-lambda для того, чтобы добавить тело процедуры к коду lambda-

выражения, используется специальный комбинатор tack-on-instructionsequence

(раздел 5.5.4), а не обыкновенный append-instructionsequences, поскольку тело

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

щую последовательность; оно стоит в последовате льности только потому, что его удобно

было сюда поместить.

Процедура compile-lambda-body строит код для тела процедуры. Этот код на-

чинается с метки для точки входа. Затем идут команды, которые заставят машину во

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

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

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

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

Нам потребуются машинные операции, которые реализуют структуру данных, представляющую скомпи-

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

(define (make-compiled-procedure entry env)

(list ’compiled-procedure entry env))

(define (compiled-procedure? proc)

(tagged-list? proc ’compiled-procedure))

(define (compiled-procedure-entry c-proc) (cadr c-proc))

(define (compiled-procedure-env c-proc) (caddr c-proc))

530

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

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

с результатом в регистре val.

(define (compile-lambda-body exp proc-entry)

(let ((formals (lambda-parameters exp)))

(append-instruction-sequences

(make-instruction-sequence ’(env proc argl) ’(env)

‘(,proc-entry

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

(assign env

(op extend-environment)

(const ,formals)

(reg argl)

(reg env))))

(compile-sequence (lambda-body exp) ’val ’return))))

5.5.3. Компиляция комбинаций

Соль процесса компиляции заключается в компилировании вызовов процедур. Код

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

вид

hскомпилированный код оператора с целевым регистром proc и типом

связи nexti

hвычисление операндов и построение списка аргументов в argli

hскомпилированный код вызова процедуры с указанными целевым

регистром и типом связиi

Во время вычисления оператора и операндов может потребоваться сохранить и восстано -

вить регистры env, proc и argl. Заметим, что это единственное место в компиляторе,

где ук азывается целевой регистр, отличный от val.

Требуем ый код порождается процедурой compile-application. Она рекурсивно

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

в proc, и операнды, порождая код, который по одному вычисляет операнды проце-

дурного вызова. Последовательности команд для операндов собираются (в процедуре

construct-arglist) вместе с кодом, который строит список аргументов в регистре

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

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

с помощью compile-procedure-call). При склеиван ии последовательностей команд

требуется сохранить регистр env на время вычисления оператора (поскольку в это вре-

мя env может измениться, а он еще потребуе тся во время вычисления операндов), а

регистр proc требуется сохранить на время построения списка аргументов (при вычис-

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

процедуры). Наконец, все время следует сохранять continue, поскольку этот регистр

нужен для связующего кода.

(define (compile-application exp target linkage)

(let ((proc-code (compile (operator exp) ’proc ’next))

(operand-codes