которые следует выполнить последовательно, а возвращает последовательность команд, предложениями которой служат предложения всех последовательностей, склеенные вместе. Сложность состоит в том, чтобы определить регистры, которые требуются, и регистры, которые изменяются в получаемой последовательности. Изменяются те регистры, которые изменяются в какой-либо из подпоследовательностей; требуются те регистры, которые должны быть прои-нициализированы прежде, чем можно запустить первую подпоследовательность (регистры, требуемые первой подпоследовательностью), а также регистры, которые требует любая из оставшихся подпоследовательностей, не измененные (про-инициализированные) одной из подпоследовательностей, идущих перед ней.

Последовательности сливаются по две процедурой append-2-sequences. Она берет две последовательности команд seq1 и seq2, и возвращает последовательность команд, в которой предложениями служат предложения seq1, а затем в конце добавлены предложения seq2. Ее изменяемые регистры - те, которые изменяет либо seq1, либо seq2, а требуемые регистры - те, что требует seq1 плюс те, что требует seq2 и не изменяет seq1. (В терминах операций над множествами, новое множество требуемых регистров является объединением множества требуемых регистров seq1 с множественной разностью требуемых регистров seq2 и изменяемых регистров seq1.) Таким образом, append-instruction-sequences реализуется так:

(define (append-instruction-sequences . seqs) (define (append-2-sequences seql seq2) (make-instruction-sequence (list-union (registers-needed seql)

(list-difference (registers-needed seq2)

(registers-modified seql))) (list-union (registers-modified seql)

(registers-modified seq2)) (append (statements seql) (statements seq2)))) (define (append-seq-list seqs) (if (null? seqs)

(empty-instruction-sequence) (append-2-sequences (car seqs)

(append-seq-list (cdr seqs)))))

(append-seq-list seqs))

В этой процедуре используются некоторые операции для работы с множествами, представленными в виде списков, подобные (неотсортированному) представлению множеств, описанному в разделе 2.3.3:

(define (list-union sl s2)

(cond ((null? sl) s2)

((memq (car sl) s2) (list-union (cdr sl) s2)) (else (cons (car sl) (list-union (cdr sl) s2)))))

(define (list-difference sl s2)

(cond ((null? sl) ())

((memq (car sl) s2) (list-difference (cdr sl) s2)) (else (cons (car sl)

(list-difference (cdr sl) s2)))))

Второй основной комбинатор последовательностей команд, preserving, принимает список регистров regs и две последовательности команд seq1 и

seq2, которые следует выполнить последовательно. Он возвращает последовательность команд, чьи предложения - это предложения seq1, за которыми идут предложения seq2, с командами save и restore вокруг seq1, для того, чтобы защитить регистры из множества regs, изменяемые в seq1, но требуемые в seq2. Для того, чтобы построить требуемую последовательность, сначала preserving создает последовательность, содержащую требуемые команды save, команды из seq1 и команды restore. Эта последовательность нуждается в регистрах, которые подвергаются сохранению/восстановлению, а также регистрах, требуемых seq1. Она изменяет регистры, которые меняет seq1, за исключением тех, которые сохраняются и восстанавливаются. Затем эта дополненная последовательность и seq2 сочетаются обычным образом. Следующая процедура реализует эту стратегию рекурсивно, двигаясь по списку сохраняе-

42

мых регистров:42

(define (preserving regs seql seq2) (if (null? regs)

(append-instruction-sequences seql seq2) (let ((first-reg (car regs)))

(if (and (needs-register? seq2 first-reg)

(modifies-register? seql first-reg)) (preserving (cdr regs) (make-instruction-sequence (list-union (list first-reg)

(registers-needed seql)) (list-difference (registers-modified seql)

(list first-reg)) (append ((save ,first-reg)) (statements seql) ((restore ,first-reg))))

seq2)

(preserving (cdr regs) seql seq2)))))

Еще один комбинатор последовательностей, tack-on-instruction-se-quence, используется в compile-lambda для того, чтобы добавить тело процедуры к другой последовательности. Поскольку тело процедуры не находится «в потоке управления» и не должно выполняться как часть общей последовательности, используемые им регистры никак не влияют на регистры, используемые последовательностью, в которую оно включается. Таким образом, когда мы добавляем тело процедуры к другой последовательности, мы игнорируем его множества требуемых и изменяемых регистров.

(define (tack-on-instruction-sequence seq body-seq) (make-instruction-sequence (registers-needed seq) (registers-modified seq)

(append (statements seq) (statements body-seq))))

В процедурах compile-if и compile-procedure-call используется специальный комбинатор parallel-instruction-sequences, который

42Заметим, что preserving зовет append с тремя аргументами. Хотя определение append, приводимое в этой книге, принимает только два аргумента, в стандарте Scheme имеется процедура append, принимающая любое их количество.

склеивает две альтернативные ветви, следующие за тестом. Эти две ветви никогда не исполняются одна за другой; при каждом исполнении теста будет запущена либо одна, либо другая ветвь. Поэтому регистры, требуемые во второй ветви, по-прежнему требуются составной последовательности, даже если первая ветвь их изменяет.

(define (parallel-instruction-sequences seql seq2) (make-instruction-sequence (list-union (registers-needed seql)

(registers-needed seq2)) (list-union (registers-modified seql)

(registers-modified seq2)) (append (statements seql) (statements seq2))))

5.5.5 Пример скомпилированного кода

Теперь, когда мы рассмотрели все элементы компилятора, можно разобрать пример скомпилированного кода и увидеть, как сочетаются его элементы. Мы скомпилируем определение рекурсивной процедуры factorial с помощью вызова compile:

(compile (define (factorial n) (if (= n 1)

l

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

val

next)

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

Процедура compile распознает выражение как определение, так что она зовет compile-definition, чтобы породить код для вычисления присваиваемого значения (с целью val), затем код для внесения определения в среду, затем код, который помещает значение define (символ ok) в целевой регистр, и, наконец, связующий код. При вычислении значения сохраняется env , поскольку этот регистр требуется, чтобы внести определение в среду. Поскольку тип связи у нас next, никакого связующего кода не порождается. Таким образом, скелет скомпилированного кода таков:

(сохранить env, если его изменяет код для вычисления значения) (скомпилированный код для значения определения, цель val, связь next)

( восстановить env, если он сохранялся) (perform (op define-variable!)

(const factorial)

(reg val)

(reg env)) (assign val (const ok))