(assign continue (label proc-return))

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

(assign (целевой регистр) (reg val)) ; включается, если целевой

; регистр не val

(goto (label (связь))); связующий код

либо, если тип связи return, так: (save continue)

(assign continue (label proc-return))

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

(assign (целевой регистр) (reg val)) ; включается, если целевой

; регистр не val

(restore continue)

(goto (label (связь))); связующий код

Этот код устанавливает continue так, чтобы процедура вернулась на метку proc-return, а затем переходит на входную точку процедуры. Код по метке proc-return переносит результат процедуры из val в целевой регистр (если нужно), а затем переходит в место, определяемое типом связи. (Связь всегда return или метка, поскольку процедура compile-procedure-call заменяет связь next для ветви составной процедуры на переход к метке after-call.)

На самом деле, если целевой регистр не равен val, то именно такой код наш компилятор и породит.39 Однако чаще всего целевым регистром является val (единственное место, в котором компилятор заказывает другой целевой регистр - это когда вычисление оператора имеет целью proc), так что результат процедуры помещается прямо в целевой регистр, и возвращаться в особое место, где он копируется, незачем. Вместо этого мы упрощаем код, так устанавливая continue, что процедура «возвращается» прямо на то место, которое указано типом связи вызывающего кода:

(установить continue в соответствии с типом вызова) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val))

Если в качестве связи указана метка, мы устанавливаем continue так, что возврат происходит на эту метку. (Таким образом, в приведенной выше proc-return, команда (goto (reg continue)), которой кончается процедура, оказывается равносильной (goto (label (связь))).)

(assign continue (label (связь))

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

Если тип связи у нас return, нам вообще ничего не надо делать с continue: там уже хранится нужное место возврата. (То есть команда (goto (reg

39Мы сообщаем об ошибке, если целевой регистр не val, а тип связи return, поскольку единственное место, где мы требуем связи return - это компиляция процедур, а по нашему соглашению процедуры возвращают значение в регистре val.

continue)), которой заканчивается процедура, переходит прямо туда, куда перешла бы (goto (reg-continue)), расположенная по метке proc-return.)

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

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

Предположим, однако, что мы реализовали случай вызова процедуры с типом связи return и целевым регистром val так, как показано выше для случая с целью не-val. Хвостовая рекурсия оказалась бы уничтожена. Наша система по-прежнему вычисляла бы то же значение для всех выражений. Однако при каждом вызове процедур мы сохраняли бы continue, а после вызова возвращались бы для (ненужного) восстановления. В гнезде рекурсивных вызовов эти дополнительные сохранения накапливались бы.40

При порождении вышеописанного кода для применения процедуры com-pile-proc-appl рассматривает четыре случая, в зависимости от того, является ли val целевым регистром, и от того, дан ли нам тип связи return. Обратите внимание: указано, что эти последовательности команд изменяют все регистры, поскольку при выполнении тела процедуры регистрам разрешено меняться как угодно.41 Заметим, кроме того, что в случае с целевым регистром val и типом связи return говорится, что участок кода нуждается в continue: хотя в этой двухкомандной последовательности continue явно не упоминается, нам нужно знать, что при входе в скомпилированную процедуру continue будет содержать правильное значение.

(define (compile-proc-appl target linkage)

(cond ((and (eq? target val) (not (eq? linkage return))) (make-instruction-sequence (proc) all-regs ((assign continue (label ,linkage))

(assign val (op compiled-procedure-entry)

(reg proc)) (goto (reg val)))))

40Казалось бы, заставить компилятор порождать код с хвостовой рекурсией - естественная идея. Однако большинство компиляторов для распространенных языков, включая C и Паскаль, так не делают, и, следовательно, в этих языках итеративный процесс нельзя представить только через вызовы процедур. Сложность с хвостовой рекурсией в этих языках состоит в том, что их реализации сохраняют на стеке не только адрес возврата, но еще и аргументы процедур и локальные переменные. Реализации Scheme, описанные в этой книге, хранят аргументы и переменные в памяти и подвергают их сборке мусора. Причина использования стека для переменных и аргументов - в том, что при этом можно избежать сборки мусора в языках, которые не требуют ее по другим причинам, и вообще считается, что так эффективнее. На самом деле изощренные реализации Лиспа могут хранить аргументы на стеке, не уничтожая хвостовую рекурсию. (Описание можно найти в Hanson 1990.) Кроме того, ведутся споры о том, правда ли, что выделение памяти на стеке эффективнее, чем сборка мусора, но тут результат, кажется, зависит от тонких деталей архитектуры компьютера. (См. Appel 1987 и Miller and Rozas 1994, где по этому вопросу высказываются противоположные мнения.)

41 Значением переменной all-regs является список имен всех регистров: (define all-regs (env proc val argl continue))

((and (not (eq? target val))

(not (eq? linkage return))) (let ((proc-return (make-label proc-return))) (make-instruction-sequence (proc) all-regs ((assign continue (label ,proc-return)) (assign val (op compiled-procedure-entry)

(reg proc)) (goto (reg val)) ,proc-return

(assign ,target (reg val)) (goto (label ,linkage)))))) ((and (eq? target val) (eq? linkage return)) (make-instruction-sequence (proc continue) all-regs ((assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val))))) ((and (not (eq? target val)) (eq? linkage return)) (error "Тип связи return, цель не val -- COMPILE"

target))))

5.5.4 Сочетание последовательностей команд

В этом разделе в деталях описывается представление последовательностей команд и их сочетание друг с другом. Напомним, что в разделе 5.5.1 мы решили, что последовательность представляется в виде списка, состоящего из множества требуемых регистров, множества изменяемых регистров, и собственно кода. Кроме того, мы будем считать метку (символ) особым случаем последовательности, которая не требует и не изменяет никаких регистров. Таким образом, для определения регистров, в которых нуждается и которые изменяет данная последовательность, мы пользуемся селекторами

(define (registers-needed s)

(if (symbol? s) () (car s)))

(define (registers-modified s)

(if (symbol? s) () (cadr s)))

(define (statements s)

(if (symbol? s) (list s) (caddr s)))

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

(define (needs-register? seq reg) (memq reg (registers-needed seq)))

(define (modifies-register? seq reg) (memq reg (registers-modified seq)))

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

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