gcd

(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 gcd)) gcd-done

(test (op =) (reg continue) (const 0)) (branch (label after-gcd-1)) (goto (label after-gcd-2))

;; Прежде, чем перейти к gcd из первого места, где ;; он нужен, заносим 0 в регистр continue

(assign continue (const 0))

(goto (label gcd)) after-gcd-1

;; Перед вторым использованием gcd помещаем 1 в регистр continue. (assign continue (const 1)) (goto (label gcd)) after-gcd-2

Рис. 5.9: Использование регистра continue ради избежания повторяющейся последовательности команд с рисунка 5.8.

gcd

(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 gcd)) gcd-done (goto (reg continue))

;; Перед вызовом gcd заносим в continue ;; метку, на которую gcd должен вернуться.

(assign continue (label after-gcd-1))

(goto (label gcd)) after-gcd-1

;; Второй вызов gcd, с другим продолжением. (assign continue (label after-gcd-2)) (goto (label gcd)) after-gcd-2

Рис. 5.10: Присваивание регистру continue меток упрощает и обобщает стратегию с рисунка 5.9.

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

Как мы видим из этой процедуры, вычисление n! требует вычисления (n - 1)!. Машина НОД, которая моделирует процедуру

(define (gcd a b)

(if (= b 0)

a

(gcd b (remainder a b))))

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

В случае с факториалом (и в любом другом рекурсивном процессе) ответ на подзадачу-факториал не является решением общей задачи. Значение, полученное для (n - 1)!, требуется еще домножить на n, чтобы получить окончательный ответ. Если мы попытаемся сымитировать решение задачи НОД и решить подзадачу-факториал, уменьшив регистр n и запустив машину заново, у нас больше не будет старого значения n, на которое можно было бы домножить результат. Для решения подзадачи нам бы потребовалась еще одна факториальная машина. Во втором вычислении факториала также есть подзадача-факториал, для нее требуется третья факториальная машина, и так далее. Поскольку внутри каждой факториальной машины содержится другая факториальная машина, в общей машине должно содержаться бесконечное гнездо вложенных друг в друга машин, а следовательно, ее нельзя построить из заранее заданного конечного числа деталей.

Тем не менее реализовать факториальный процесс в виде регистровой машины можно, если использовать одни и те же компоненты для всех встроенных ее экземпляров. А именно, машина, которая вычисляет n!, должна использовать одни и те же детали для работы над подзадачей вычисления (n - 1)!, (n - 2)! и так далее. Такое построение возможно, поскольку, несмотря на то, что факто-риальный процесс требует для своего вычисления неограниченное число одинаковых машин, в каждый момент времени только одна из этих машин активна. Когда машина встречает рекурсивную подзадачу, она может остановить работу над основной задачей, использовать свои физические детали для решения подзадачи, а затем продолжить остановленное вычисление.

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

2Казалось бы, незачем сохранять старое n; после того, как мы его уменьшим на единицу и