(branch (label external-entry)) ; переход, если установлен flag read-eval-print-loop

(perform (op initialize-stack))

External-entry предполагает, что при запуске машины регистр val содержит местоположение последовательности команд, которая помещает результат в val и заканчивается командой (goto (reg continue)). Запуск машины с этой точки входа приводит к переходу в место, куда показывает val, но сначала continue устанавливается в print-result, которая распечатает значение val, а затем направится в начало управляющего цикла вычислителя.50

external-entry

(perform (op initialize-stack)) (assign env (op get-global-environment)) (assign continue (label print-result)) (goto (reg val))

Теперь с помощью следующей процедуры можно скомпилировать определение, выполнить скомпилированный код и войти в управляющий цикл, откуда мы можем процедуру оттестировать. Поскольку мы хотим, чтобы скомпилированная процедура возвращалась в место, указанное continue, со значением в val, мы компилируем выражение с целевым регистром val и типом связи return. Чтобы преобразовать объектный код, порождаемый компилятором, в исполняемые команды регистровой машины-вычислителя, мы пользуемся процедурой assemble из имитатора регистровых машин (раздел 5.2.2). Затем мы устанавливаем val, чтобы он указывал на список команд, устанавливаем flag, чтобы вычислитель пошел на external-entry, и запускаем вычислитель.

(define (compile-and-go expression) (let ((instructions

(assemble (statements

(compile expression val return)) eceval)))

(set! the-global-environment (setup-environment)) (set-register-contents! eceval val instructions)

(define (start-eceval)

(set! the-global-environment (setup-environment)) (set-register-contents! eceval flag false) (start eceval))

50Поскольку скомпилированная процедура является объектом, который система может попытаться напечатать, нужно еще изменить системную операцию печати user-print (из раздела 4.1.4), чтобы она не пыталась печатать компоненты скомпилированной процедуры:

(define (user-print object)

(cond ((compound-procedure? object)

(display (list compound-procedure

(procedure-parameters object) (procedure-body object) <procedure-env>))) ((compiled-procedure? object)

(display <compiled-procedure>)) (else (display object))))

(set-register-contents! eceval flag true) (start eceval)))

Если мы установим отслеживание стека, как в конце раздела 5.4.4, то сможем исследовать использование стека скомпилированным кодом:

(compile-and-go (define (factorial n) (if (= n 1) 1

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

(total-pushes = 0 maximum-depth = 0) ;;; Значение EC-Eval:

ok

;;; Ввод EC-Eval: (factorial 5)

(total-pushes = 31 maximum-depth = 14) ;;; Значение EC-Eval:

120

Сравните этот пример с вычислением (factorial 5) с помощью интерпретируемой версии той же самой процедуры, приведенным в конце раздела 5.4.4. В интерпретируемой версии потребовалось 144 сохранения и максимальная глубина стека 28. Это показывает, какую оптимизацию удалось получить с помощью нашей стратегии компиляции.

Интерпретация и компиляция

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

51 Можно добиться даже большего, если расширить компилятор так, чтобы скомпилированный код мог вызывать интерпретируемые процедуры. См. упражнение 5.47.

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

Компиляция и интерпретация также ведут к различным стратегиям при переносе языков на новые компьютеры. Предположим, что нам надо реализовать Лисп для новой машины. Одна стратегия будет состоять в том, чтобы взять вычислитель с явным управлением из раздела 5.4 и перевести его команды в команды новой машины. Вторая - в том, чтобы начать с компилятора и изменить генераторы кода так, чтобы они порождали код новой машины. Вторая стратегия позволяет запускать на новой машине любую программу на Лиспе, если сначала скомпилировать ее компилятором, который работает на исходной Лисп-системе, а затем связать со скомпилированной версией рабочей библио-теки.53 Более того, мы можем скомпилировать сам компилятор, и, запустив его на новой машине, компилировать другие программы на Лиспе. 54 Либо же мы можем скомпилировать один из интерпретаторов из раздела 4.1 и получить интерпретатор, который работает на новой машине.

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

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

а. В упражнении 5.27 от Вас требовалось определить как функцию от n число сохранений и максимальную глубину стека, которые требуются вычислителю для того, чтобы получить n! с помощью указанной факториальной процедуры. В упражнении 5.14 Вас просили провести те же измерения для специализированной факториальной машины, показанной на рисунке 5.11. Проведите теперь тот же анализ для скомпилированной процедуры factorial.

Возьмем отношение числа сохранений в скомпилированной версии к числу сохранений в интерпретируемой версии и проделаем то же для максимальной глубины стека. Поскольку число операций и глубина стека при вычислении n! линейно зависят от n, эти отношения должны приближаться к константам при росте n. Чему равны эти константы? Найдите также отношения показателей использования стека в специализированной машине к показателям интерпретируемой версии.

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

Компиляторы для популярных языков программирования, вроде C или C++, почти никаких проверок в работающий код не помещают, чтобы программы выполнялись как можно быстрее. В результате программистам приходится самим проводить проверку на ошибки. К сожалению, многие этим пренебрегают, даже в критических приложениях, где скорость не является существенным ограничением. Их программы ведут бурную и опасную жизнь. Например, знаменитый «Червь», который парализовал Интернет в 1988 году, использовал то, что операционная система UNIXTM не проверяла переполнение буфера в демоне finger. (См. Spafford 1989.)

53Разумеется, как при интерпретации, так и при компиляции придется еще реализовать для новой машины управление памятью, ввод и вывод, а также все операции, которые мы считали «элементарными» при обсуждении интерпретатора и компилятора. Один из способов минимизировать эту работу заключается в том, чтобы как можно большее число этих операций написать на Лиспе, а затем скомпилировать для новой машины. В конце концов все сводится к простому ядру (например, сборка мусора и механизм для применения настоящих машинных примитивов), которое кодируется для новой машины вручную.

54Такая стратегия приводит к забавным проверкам корректности компилятора. Можно, например, сравнить, совпадает ли результат компиляции программы на новой машине, с помощью скомпилированного компилятора, с результатом компиляции той же программы на исходной Лисп-системе. Поиск причин расхождения - занятие интересное, но зачастую довольно сложное, поскольку результат может зависеть от микроскопических деталей.