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

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

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

В общем случае результат работы каждого генератора кода будет заканчиваться командами - порожденными процедурой compile-linkage, - которые реализуют требуемый тип связи. Если это тип return, то нам надо породить команду (goto (reg continue)) . Она нуждается в регистре continue и никаких регистров не меняет. Если тип связи next, то никаких дополнительных команд порождать не надо. В остальных случаях тип связи - переход по метке, и мы порождаем команду goto на эту метку, команду, которая ни в чем не нуждается и не изменяет никакие регистры.36

(define (compile-linkage linkage) (cond ((eq? linkage return)

(make-instruction-sequence (continue) () ((goto (reg continue))))) ((eq? linkage next)

(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))))))

36 В этой процедуре используется конструкция Лиспа, называемая обратная кавычка (backquote) или квазикавычка (quasiquote), с помощью которой удобно строить списки. Обратная кавычка перед списком работает почти так же, как обычная, но при этом все выражения внутри списка, перед которыми стоит запятая, вычисляются.

Например, если значение linkage равно символу branch25, то результатом выражения ((goto (label ,linkage))) будет список ((goto (label branch25))). Подобным образом, если значением x является список (a b c), то (1 2 ,(car x)) дает при вычислении список (1 2 a).

(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, поскольку для определения и присваивания переменной требуется окружение, а код, вычисляющий значение переменной, может оказаться сложным выражением, которое изменяет регистры произвольным образом.

(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 с указанными целевым регистром и типом связи имеет форму

(скомпилированный код для предиката с целевым регистром val и типом связи next) (test (op false?) (reg val)) (branch (label false-branch)) true-branch

(скомпилированный код для следствия с указанным целевым регистром и указанным типом связи либо after-if) false-branch

(скомпилированный код для альтернативы с указанными целевым регистром и типом связи) after-if

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

37Просто использовать метки 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)))))