(data-paths (registers ((name a)

(buttons((name a<-b) ((name b)

(buttons((name b<-t) ((name t)

(buttons((name t<-r)

(operations ((name rem)

(inputs (register a) ((name =)

(inputs (register b)

(source (register b))))) (source (register t))))) (source (operation rem))))))

(register b))) (constant 0))))

(controller test-b (test =)

(branch (label gcd-done))

(t<-r) (a<-b) (b<-t)

(goto (label test-b)) gcd-done))

;метка

;тест

;условный переход

;нажатие кнопки

;нажатие кнопки

;нажатие кнопки

;безусловный переход

;метка

Рис. 5.3: Описание машины НОД.

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

В этой новой форме записи мы заменим произвольные имена кнопок и операций на описание их поведения. То есть, вместо того, чтобы говорить (в контроллере) «нажать кнопку t<-r» и отдельно (в путях данных) «кнопка t<-r присваивает регистру t значение операции rem», а также «входы операции rem - это содержимое регистров a и b», мы будем говорить (в контроллере) «нажать кнопку, которая присваивает регистру t результат операции rem от содержимого регистров a и b». Подобным образом, вместо «выполнить тест =» (в контроллере) и отдельно (в путях данных) «тест = применяется к содержимому регистра b и константе 0», будем говорить «выполнить тест = над содержимым регистра b и константой 0». Описание путей данных мы будем опускать, оставляя только последовательность команд контроллера. Таким образом, машину НОД можно описать так:

(controller test-b

(test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done)

Запись в такой форме проще читать, чем описания на разновидности языка, показанной на рисунке 5.3, но есть у нее и недостатки:

•Для больших машин такие описания длиннее, поскольку полные определения элементов путей данных повторяются каждый раз, как эти элементы упоминаются в последовательности команд контроллера. (В примере с НОД этой проблемы не возникает, поскольку каждая операция и каждая кнопка используются только по разу.) Более того, повторение описаний путей данных скрывает структуру этих путей в машине; для больших машин становится сложно определить, сколько в них регистров, операций и кнопок, и как они связаны.

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

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

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

С помощью языка регистровых машин опишите итеративную факториал-машину из упражнения 5.1.

Действия

Давайте теперь изменим машину НОД так, чтобы можно было вводить числа, НОД которых мы хотим получить, и видеть результаты, напечатанные на терминале. Мы не будем обсуждать, как построить машину для считывания и печати, а предположим (как и с процедурами read и display в Scheme), что эти действия доступны как элементарные операции.1

Read подобна операциям, которые мы использовали ранее, поскольку она порождает значение, и его можно сохранить в регистре. Однако read не принимает входа ни из каких регистров; ее значение зависит от событий, происходящих за пределами тех компонентов машины, проектированием которых мы заняты. Мы позволим операциям нашей машины вести себя таким образом, и,

1 Такое предположение покрывает большую и сложную область. Обычно значительная часть реализации Лисп-систем посвящена работе ввода и вывода.

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

Print, с другой стороны, фундаментальным образом отличается от тех операций, которыми мы до сих пор пользовались: она не порождает результата, который можно было бы поместить в регистр. Хотя она и производит эффект, этот эффект не касается тех частей машины, которые мы проектируем. Этот тип операций мы будем называть действиями (actions). На диаграмме путей данных мы будем представлять действие так же, как и операции, вычисляющие значение - как трапецию с именем действия. В этот элемент входят стрелки из входов (регистров или констант). Кроме того, мы связываем с действием кнопку. Нажатие кнопки заставляет действие совершиться. Чтобы скомандовать контроллеру нажать кнопку действия, мы вводим новый тип команды perform. Таким образом, действие по распечатке содержимого регистра a представляется в последовательности контроллера командой

(perform (op print) (reg a))

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

5.1.2 Абстракция в проектировании машин

Часто в определении машины мы будем использовать «элементарные» операции, которые на самом деле весьма сложны. Например, в разделах 5.4 и 5.5 мы будем рассматривать операции с окружениями Scheme как элементарные. Такая абстракция полезна, поскольку она позволяет нам игнорировать детали частей машины, так что мы можем сосредоточиться на других сторонах общего плана. Однако, хотя мы и скрываем существенную часть сложности, это не означает, что проект машины нереалистичен. Сложные «примитивы» всегда можно заменить более простыми операциями.

Рассмотрим машину НОД. В ней содержится команда, которая вычисляет остаток от деления содержимого регистров a и b и сохраняет результат в регистре t. Если мы хотим построить машину НОД без использования элементарной операции взятия остатка, нам нужно указать, как вычислять остатки с помощью более простых операций, например, вычитания. Действительно, можно написать на Scheme процедуру нахождения остатка таким образом:

(define (remainder n d)

(if (< n d)

n

(remainder (- n d) d)))

Значит, мы можем заменить операцию взятия остатка в машине НОД операцией вычитания и тестом-сравнением. На рисунке 5.5 показаны пути данных и контроллер уточненной машины.