(label fib-done))

(controller

(assign continue fib-loop

(test (op <) (reg n) (const 2)) (branch (label immediate-answer))

;; готовимся вычислить Fib (n - 1) (save continue) (assign continue (save n)

(assign n (op -) (reg n) (goto (label fib-loop)) afterfib-n-1 (restore n) (restore continue)

(label afterfib-n-1))

(const 1))

;сохранить старое значение n

;записать в n n - 1

;произвести рекурсивный вызов

;при возврате val содержит Fib(n - 1)

готовимся вычислить

Fib (n - 2)

(assign n (op -) (reg n) (const 2)) (save continue)

(assign continue (label afterfib-n-2))

(save val)

(goto (label fib-loop)) afterfib-n-2

(assign n (reg val))

(restore val)

(restore continue)

(assign val

(op +) (reg val) (reg n))

(goto (reg continue)) immediate-answer

(assign val (reg n))

(goto (reg continue)) fib-done)

;сохранить Fib(n - 1)

;при возврате val содержит Fib(n - 2)

;теперь n содержит Fib(n - 2)

;теперь val содержит Fib(n - 1)

;Fib(n - 1) + Fib(n - 2)

;возврат, ответ в val

;базовый случай: Fib(n) = n

Рис. 5.12: Контроллер машины для вычисления чисел Фибоначчи.

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

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

a.Рекурсивное возведение в степень:

(define (expt b n)

(if (= n 0) 1

(* b (expt b (- n 1)))))

b.Итеративное возведение в степень:

(define (expt b n)

(define (expt-iter counter product) (if (= counter 0) product

(expt-iter (- counter 1) (* b product)))) (expt-iter n 1))

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

Смоделируйте вручную работу факториальной машины и машины Фибоначчи с каким-нибудь нетривиальным значением на входе (чтобы потребовался хотя бы один рекурсивный вызов). Покажите содержимое стека в каждый момент выполнения.

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

Бен Битобор утверждает, что последовательность команд машины Фибоначчи содержит одну лишнюю команду save и одну лишнюю restore, которые можно убрать и получить более быструю машину. Что это за команды?

5.1.5 Обзор системы команд

Команда контроллера в нашей регистровой машине имеет одну из следующих форм, причем каждый (источник) - это либо (reg (имя-регистра)), либо (const (значение-константы)).

Команды, введенные в разделе 5.1.1:

•(assign (имя-регистра) (reg (имя-регистра)))

•(assign (имя-регистра) (const (значение-константы)))

•(assign (имя-регистра) (op (имя-операции)) (источник) ... (источники))

•(perform (op (имя-операции)) (источник) ... (источники))

•(test (op (имя-операции)) (источник ... (источник))

•(branch (label (имя-метки)))

•(goto (label (имя-метки)))

Использование регистров для хранения меток, введенное в разделе 5.1.3:

•(assign (имя-регистра) (label (имя-метки)))

•(goto (reg (имя-регистра)))

Команды для работы со стеком, введенные в разделе 5.1.4:

•(save (имя-регистра))

•(restore (имя-регистра))

До сих пор единственный вид (значений-константы), который нам встречался - числа, но в дальнейшем мы будем использовать строки, символы и списки. Например, (const "abc") представляет строку "abc", (const abc) представляет символ abc, (const (a b c)) - список (a b c) , а (const ()) - пустой список.

5.2 Программа моделирования регистровых машин

Чтобы как следует разобраться в работе регистровых машин, нам нужно уметь тестировать проектируемые нами машины и проверять, работают ли они в соответствии с ожиданиями. Один из способов проверки проекта состоит в ручном моделировании работы контроллера, как в упражнении 5.5. Однако этот способ подходит только для совсем простых машин. В этом разделе мы строим программу имитационного моделирования, имитатор (simulator), для машин, задаваемых на языке описания регистровых машин. Имитатор представляет собой программу на Scheme с четырьмя интерфейсными процедурами. Первая из них на основе описания регистровой машины строит ее модель (структуру данных, части которой соответствуют частям имитируемой машины), а остальные три позволяют имитировать машину, работая с этой моделью:

•(make-machine (имена-регистров) (операции) (контроллер))

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

•(set-register-contents! (модель-машины) (имя-регистра) (значение)) записывает значение в имитируемый регистр указанной машины.

•(get-register-contents (модель-машины) (имя-регистра))

возвращает содержимое имитируемого регистра указанной машины.

•(start (модель-машины)) имитирует работу данной машины. Машина запускается с начала последовательности команд контроллера и останавливается, когда достигнут конец этой последовательности.

В качестве примера того, как используются эти процедуры, можно определить переменную gcd-machine как модель машины НОД из раздела 5.1.1 следующим образом:

(define gcd-machine (make-machine (a b t)

(list (list rem remainder) (list = =)) (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)))