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

Можно изобразить регистры и операции, требуемые нашей машине, при помощи диаграммы путей данных, показанной на рисунке 5.1. Регистры (a, b и t) на этой диаграмме изображаются в виде прямоугольников. Каждый способ присвоить регистру значение обозначается стрелкой, указывающей из источника данных на регистр, со значком Х позади головки. Можно считать этот Х кнопкой, которая при нажатии позволяет значению из источника «перетечь» в указанный регистр. Метка рядом - это имя для кнопки. Имена эти произвольны, и их можно подбирать с мнемоническим значением (например, a<-b обозначает нажатие кнопки, которая присваивает содержимое регистра b регистру a). Источником данных для регистра может служить другой регистр (как в случае присваивания a<-b), результат операции (как в случае присваивания t<-r) или константа (встроенное значение, которое нельзя изменять и которое представляется на диаграмме путей данных в виде треугольника со значением внутри).

Операция, которая вычисляет значение на основе констант и содержимого регистров, представляется на диаграмме путей данных в виде трапеции, содержащей имя операции. Например, фигура, обозначенная на рисунке 5.1 как rem, представляет операцию, вычисляющую остаток от деления содержимых регистров a и b, к которым она подсоединена. Стрелки (без кнопок) указывают из входных регистров и констант на фигуру, а другие стрелки связывают результат операции с регистрами. Сравнение изображается в виде круга, содержащего имя теста. К примеру, в нашей машине НОД имеется операция, которая проверяет, не равно ли содержимое регистра b нулю. У теста тоже есть входные стрелки, ведущие из входных регистров и констант, но у него нет исходящих стрелок; его значение используется контроллером, а не путями данных. В целом, диаграмма путей данных показывает регистры и операции, которые нужны машине, и как они должны быть связаны. Если мы рассматриваем стрелки как провода, а кнопки Х как переключатели, то диаграмма путей данных оказывается очень похожа на схему машины, которую можно было бы построить из электронных деталей.

Для того, чтобы пути данных вычисляли НОД, нужно нажимать кнопки в правильной последовательности. Мы будем описывать эту последовательность с помощью диаграммы контроллера, показанной на рисунке 5.2. Элементы диаграммы контроллера показывают, как следует работать с компонентами путей данных. Прямоугольные блоки в такой диаграмме указывают, на какие кнопки следует нажимать, а стрелки описывают последовательный переход от одного шага к другому. Ромб на диаграмме обозначает выбор. Произойдет переход по одной из двух исходящих стрелок, в зависимости от значения того теста в потоке данных, имя которого указано в ромбе. Можно интерпретировать контроллер с помощью физической аналогии: представьте себе, что диаграмма - это лабиринт, в котором катается шарик. Когда шарик закатывается в прямоугольник, он нажимает на кнопку, имя которой в прямоугольнике написано. Когда шарик закатывается в узел выбора (например, тест b = 0), он покидает этот узел по

М>-

a <-b

b

rem

t<-r

b <-t

Рис. 5.1: Пути данных в машине НОД.

start

да

done

Рис. 5.2: Контроллер машины НОД.

стрелке, которую определяет результат указанного теста. Взятые вместе, пути данных и контроллер полностью определяют машину для вычисления НОД. Мы запускаем контроллер (катящийся шарик) в месте, обозначенном start, поместив предварительно числа в регистры a и b. Когда контроллер достигает точки, помеченной done, в регистре a оказывается значение НОД.

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

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

a

t

(define (factorial n)

(define (iter product counter) (if (> counter n) product

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

(iter 11))

5.1.1 Язык для описания регистровых машин

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

Мы определяем пути данных (data-paths) машины, описывая регистры (registers) и операции (operations). Чтобы описать регистр, мы даем ему имя (name) и указываем кнопки (buttons), которые присваивают ему значение. Каждой из этих кнопок мы даем имя (name) и указываем источник (source) для данных, которые попадают в регистр, управляемый кнопкой. Источником может служить регистр (register), константа (constant) или операция (operation). Для описания операции нам нужно дать ей имя и указать входы (inputs) - регистры или константы.

Контроллер машины мы определяем как последовательность команд (instructions) с метками (labels), которые определяют точки входа (entry points). Есть следующие виды команд:

•Имя кнопки на пути данных, которую следует нажать и присвоить регистру значение. (Это соответствует прямоугольнику на диаграмме контроллера.)

•Команда test, которая выполняет указанный тест.

•Условный переход (команда branch) в место, определяемое меткой контроллера, на основании предыдущего теста. (Test и branch вместе соответствуют ромбу на диаграмме контроллера.) Если тест дает результат «ложь», контроллер должен выполнять следующую команду в последовательности. В противном случае он должен выполнять команду, которая следует за меткой.

•Безусловный переход (команда goto), указывающий метку, с которой следует продолжить выполнение.

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

На рисунке 5.3 изображена описанная на нашем языке машина НОД. Этот пример служит не более чем намеком на степень общности таких описаний, поскольку машина НОД - очень простой случай: у каждого регистра всего по одной кнопке, и каждая кнопка используется в контроллере только один раз.

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