(controller test-b

(test (op =) (reg b) (const 0))

(branch (label gcd-done))

(assign t (reg a)) rem-loop

(test (op <) (reg t) (reg b))

(branch (label rem-done))

(assign t (op -) (reg t) (reg b))

(goto (label rem-loop)) rem-done

(assign a (reg b))

(assign b (reg t)) (goto (label test-b)) gcd-done)

Рис. 5.6: Последовательность команд контроллера машины НОД с рисунка 5.5.

Было бы лучше заменить эти две последовательности переходами к единой последовательности - подпрограмме (subroutine), - в конце которой мы возвращаемся обратно к нужному месту в основной последовательности команд. Этого можно добиться так: прежде, чем перейти к gcd, мы помещаем определенное значение (0 или 1) в особый регистр, continue. В конце подпрограммы gcd мы переходим либо к after-gcd-1, либо к after-gcd-2, в зависимости от значения из регистра continue. На рисунке 5.9 показан соответствующий сегмент получающейся последовательности команд контроллера, который содержит только одну копию команд gcd.

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

Чтобы отразить эту возможность, мы расширим команду assign языка регистровых машин и позволим присваивать регистру в качестве значения метку из последовательности команд контроллера (как особого рода константу). Кроме того, мы расширим команду goto и позволим вычислению продолжаться с точки входа, которая описывается содержимым регистра, а не только с точки входа, описываемой меткой-константой. С помощью этих двух команд мы можем завершить подпрограмму gcd переходом в место, хранимое в регистре continue. Это ведет к последовательности команд, показанной на рисунке 5.10.

Машина, в которой имеется более одной подпрограммы, могла бы исполь-

a <-b

b

ю

rem

t <-r

b <-t

Н8ъ

c <-d

i

rem

s <-r

d <-t

gcd-1

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

gcd-2

(test (op =) (reg d) (const 0)) (branch (label after-gcd-2)) (assign s (op rem) (reg c) (reg d)) (assign c (reg d)) (assign d (reg s))

(goto (label gcd-2))

after-gcd-2

d

c

a

0

0

t

s

Рис. 5.7: Части путей данных и последовательностей команд контроллера для машины с двумя вычислениями НОД.

gcd-1

(test (op *) (reg b) (const 0)) (branch (label after-gcd-1)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) after-gcd-2

gcd-1

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

(goto (label gcd-2))

after-gcd-2

Рис. 5.8: Сегменты последовательности команд контроллера для машины, которая использует одни и те же компоненты путей данных для двух различных вычислений НОД.

зовать различные регистры продолжения (например, gcd-continue, factorial-continue), или же мы могли бы для всех подпрограмм использовать один регистр continue. Разделение регистра экономичнее, однако тогда требуется отслеживать случаи, когда из одной подпрограммы (sub1) зовется другая (sub2). Если sub1 не сохранит значение continue в каком-то другом регистре, прежде чем использовать continue при вызове sub2, то sub1 не будет знать, откуда продолжать выполнение после ее конца. Механизм, который разрабатывается в следующем разделе для работы с рекурсией, дает хорошее решение и для проблемы с вложенными вызовами подпрограмм.

5.1.4 Реализация рекурсии с помощью стека

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

Однако реализация рекурсивных процессов требует дополнительного механизма. Рассмотрим следующий рекурсивный метод вычисления факториала, описанный нами в разделе 1.2.1:

(define (factorial n)

(if (= n 1) 1