product

(iter (* counter product) (+ counter 1))))

(iter 1 1))

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

a.Вы увидите, что максимальная глубина стека, нужная для вычисления п!, от п не зависит. Какова эта глубина?

b.Составьте на основе своих данных формулу в зависимости от п числа операций сохранения, необходимых для вычисления п! для любого п > 1. Обратите внимание, что число операций - линейная функция от п и, следовательно, определяется двумя константами.

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

Для сравнения с упражнением 5.26, изучите поведение следующей процедуры для рекурсивного вычисления факториала:

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

1

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

Запуская эту процедуру и отслеживая поведение стека, определите как функции от п максимальную глубину стека и общее число сохранений, требуемых для вычисления п!, при п > 1. (Эти функции также будут линейны.) Опишите общие результаты экспериментов, записав в следующую таблицу соответствующие выражения как формулы, зависящие от п:

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

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

Измените в определении вычислителя eval-sequence так, как описано в разделе 5.4.2, чтобы вычислитель перестал обладать хвостовой рекурсией. Заново проведите эксперименты из упражнений 5.26 и 5.27 и покажите, что теперь обе версии процедуры factorial требуют количества памяти, которое линейно зависит от значения аргумента.

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

Проследите за использованием стека в вычислении чисел Фибоначчи с помощью древовидной рекурсии:

(define (fib n) (if (< n 2) n

(+ (fib (- n 1)) (fib (- n 2)))))

a.Дайте формулу, зависящую от n, для максимальной глубины стека, требуемой при вычислении Fib(n) при n > 2. Подсказка: в разделе 1.2.2 мы утверждали, что требуемый объем памяти линейно зависит от n.

b.Постройте формулу для количества сохранений, требуемых при вычислении Fib(n), если n > 2. Вы увидите, что количество сохранений (которое хорошо коррелирует со временем исполнения) экспоненциально растет с ростом n. Подсказка: пусть при вычислении Fib(n) требуется S(n) сохранений. Нужно показать, что имеется формула, которая выражает S(n) в зависимости от S(n - 1), S(n - 2) и некоторой фиксированной «дополнительной» константы к, независимой от n. Приведите эту формулу и найдите, чему равно k. Покажите теперь, что S(n) выражается как a Fib(n + 1) + b и укажите значения a и b.

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

Наш вычислитель отлавливает только два вида ошибок (и сообщает о них) - неизвестные типы выражений и неизвестные типы процедур. При других ошибках он будет выпадать из управляющего цикла. Когда мы запускаем вычислитель с помощью имитатора регистровых машин, эти ошибки будут пойманы нижележащей Scheme-системой. Это похоже на «падение» компьютера в случае ошибки пользовательской программы.32 Построить настоящую систему обработки ошибок - большой проект, но понимание, что за вопросы здесь возникают, стоит затраченных усилий.

a.При ошибках, возникающих в процессе вычисления, например, при попытке получить значение неопределенной переменной, можно заставить операцию просмотра окружения возвращать особый код ошибки, который не может служить значением пользовательской переменной. Тогда вычислитель может проверять этот код и организовывать переход на signal-error. Найдите в вычислителе все места, где нужно провести подобные изменения, и исправьте их. (Потребуется много работы.)

b.Значительно тяжелее проблема, которую представляют ошибки, возникающие в элементарных процедурах, например, попытки поделить на ноль или взять car символа. В профессионально написанной системе высокого качества всякий вызов примитива проверяется на безопасность внутри процедуры-примитива. Например, при всяком вызове car требуется проверить, что аргумент - пара. Если аргумент не является парой, вызов вернет особый код ошибки, который вычислитель может проверить и сообщить об ошибке. В нашем имитаторе регистровых машин этого можно было бы добиться, если бы мы проверяли в каждой элементарной процедуре правильность аргументов и при необходимости возвращали соответствующий код. В таком случае код primitive-apply мог бы проверять этот код и, если надо, переходить на signal-error. Постройте такую структуру и заставьте ее работать. (Это большой проект.)

5.5 Компиляция

Вычислитель с явным управлением из раздела 5.4 - регистровая машина, контроллер которой исполняет Scheme-программы. В этом разделе мы увидим, как выполнять программы на Scheme с помощью регистровой машины, контроллер которой не является интерпретатором Scheme.

Машина-вычислитель с явным управлением универсальна - она способна выполнить любой вычислительный процесс, который можно описать на Scheme. Контроллер вычислителя выстраивает использование своих путей данных так,

32К сожалению, в обычных компиляторных языковых системах, например, C, это обычное дело. В UNIXTM система «кидает дамп», в DOS/WindowsTM впадает в кататонию. Macintosh™, если повезет, рисует на экране взрывающуюся бомбу и предлагает перегрузиться.

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

Коммерческие компьютеры общего назначения представляют собой регистровые машины, построенные на множестве регистров и операций, составляющем эффективный и удобный набор путей данных. Контроллер машины общего назначения - это интерпретатор языка регистровых машин, подобный нашему. Язык называется внутренним языком (native language) машины, или попросту машинным языком (machine language). Программы, написанные на машинном языке - это последовательности команд, использующих пути данных машины. Например, последовательность команд вычислителя с явным управлением можно рассматривать как программу на машинном языке компьютера общего назначения, а не как контроллер специализированной машины-интерпретатора.

Есть две стратегии борьбы с разрывом между языками высокого и низкого уровня. Вычислитель с явным управлением иллюстрирует стратегию интерпретации. Интерпретатор, написанный на внутреннем языке машины, конфигурирует машину так, что она начинает исполнять программы на языке (называемом исходный язык (source language)), который может отличаться от внутреннего языка машины, производящей вычисление. Элементарные процедуры исходного языка реализуются в виде библиотеки подпрограмм, написанных на внутреннем языке данной машины. Интерпретируемая программа (называемая исходная программа (source program)) представляется как структура данных. Интерпретатор просматривает эту структуру и анализирует исходную программу. В процессе анализа он имитирует требуемое поведение исходной программы, вызывая соответствующие элементарные подпрограммы из библиотеки.

В этом разделе мы исследуем альтернативную стратегию - компиляцию (compilation). Компилятор для данного исходного языка и данной машины переводит исходную программу в эквивалентную ей программу (называемую объектной (object program)), написанную на внутреннем языке машины. Компилятор, который мы реализуем в этом разделе, переводит программы, написанные на Scheme, в последовательности команд, которые подлежат исполнению с по-

34

мощью путей данных машины-вычислителя с явным управлением.34

По сравнению с интерпретацией, компиляция может дать большой выигрыш в эффективности исполнения программы. Это будет объяснено ниже, при обзоре компилятора. С другой стороны, интерпретатор предоставляет более мощную среду для интерактивной разработки программы и отладки, поскольку исполняемая исходная программа присутствует во время выполнения, и ее можно исследовать и изменять. В дополнение к этому, поскольку библиотека примитивов присутствует целиком, во время отладки можно конструировать и добавлять в

33Это теоретическое утверждение. Мы не говорим, что пути данных вычислителя как-то особенно удобны или эффективны для компьютера общего назначения. Например, они не слишком хороши для реализации высокоскоростных вычислений с плавающей точкой или для вычислений, интенсивно работающих с битовыми векторами.

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