(define (operation-exp? exp)

(and (pair? exp) (tagged-list? (car exp) op)))

(define (operation-exp-op operation-exp) (cadr (car operation-exp)))

(define (operation-exp-operands operation-exp) (cdr operation-exp))

Заметим, что обработка выражений-операций очень напоминает обработку вызовов процедур процедурой analyze-application интерпретатора из раздела 4.1.7, поскольку там и тут мы порождаем исполнительные процедуры для каждого операнда. Во время работы мы вызываем эти процедуры для операндов и применяем процедуру Scheme, которая имитирует операцию, к полученным значениям. Имитирующая процедура получается путем поиска имени операции в таблице операций регистровой машины:

(define (lookup-prim symbol operations) (let ((val (assoc symbol operations)))

(if val

(cadr val)

(error "Неизвестная операция -- ASSEMBLE" symbol)))) Упражнение 5.9.

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

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

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

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

Когда мы в разделе 5.1.4 определяли save и restore, мы не указали, что произойдет, если попытаться восстановить значение не в том регистре, который был сохранен последним, как в последовательности команд

(save y) (save x) (restore y)

Есть несколько разумных вариантов значения restore:

a.(restore y) переносит в y последнее значение, сохраненное на стеке, независимо от того, откуда это значение взялось. Так работает наш имитатор. Покажите, как с помощью такого поведения убрать одну команду из машины Фибоначчи (раздел 5.1.4, рисунок 5.12).

b.(restore y) переносит в y последнее значение, сохраненное на стеке, но только в том случае, когда это значение происходит из регистра y; иначе возникает сообщение об ошибке. Модифицируйте имитатор и заставьте его вести себя таким образом. Придется изменить save так, чтобы он сохранял имя регистра вместе со значением.

c. (restore y) переносит в y последнее значение, сохраненное из y, независимо от того, какие другие регистры были сохранены и не восстановлены после у. Модифицируйте имитатор так, чтобы он вел себя таким образом. С каждым регистром придется связать свой собственный стек. Операция initialize-stack должна инициализировать стеки всех регистров.

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

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

•список всех команд, с удаленными дубликатами, отсортированный по типу команды (assign, goto и так далее).

•список (без дубликатов) регистров, в которых хранятся точки входа (это те регистры, которые упоминаются в командах goto).

•Список (без дубликатов) регистров, к которым применяются команды save или restore.

•Для каждого регистра, список (без дубликатов) источников, из которых ему присваивается значение (например, для регистра val в факториальной машине на рисунке 5.11 источниками являются (const 1) и ((op *) (reg n) (reg val))).

Расширьте интерфейс сообщений машины и включите в него доступ к новой информации. Чтобы проверить свой анализатор, примените его к машине Фибоначчи с рисунка 5.12 и рассмотрите получившиеся списки.

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

Модифицируйте имитатор так, чтобы он определял, какие регистры присутствуют в машине, из последовательности команд контроллера, а не принимал список регистров в качестве аргумента make-machine. Вместо того, чтобы выделять регистры в make-machine заранее, их можно создавать по одному, когда они встречаются в первый раз при ассемблировании команд.

5.2.4 Отслеживание производительности машины

Имитационное моделирование может служить не только для проверки правильности проекта машины, но и для измерения ее производительности. К примеру, можно установить в нашу машину «счетчик», измеряющий количество операций со стеком, задействованных при вычислении. Для этого мы изменяем моделируемый стек и следим, сколько раз регистры сохраняются на стеке, регистрируем максимальную глубину, которой он достигает, а также добавляем к интерфейсу стека сообщение, которое распечатывает статистику, как показано ниже. Кроме того, мы добавляем к базовой машине операцию для распечатки статистики, устанавливая значение the-ops в make-new-machine в

(list (list initialize-stack

(lambda () (stack initialize))) (list print-stack-statistics

(lambda () (stack print-statistics))))

Вот новая версия make-stack:

(define (make-stack)

(let ((s ())

(number-pushes 0) (max-depth 0) (current-depth 0)) (define (push x)

(set! s (cons x s))

(set! number-pushes (+ 1 number-pushes)) (set! current-depth (+ 1 current-depth)) (set! max-depth (max current-depth max-depth))) (define (pop)

(if (null? s)

(error "Пустой стек -- POP") (let ((top (car s))) (set! s (cdr s))

(set! current-depth (- current-depth 1))

top)))

(define (initialize)

(set! s ())

(set! number-pushes 0) (set! max-depth 0) (set! current-depth 0) done)

(define (print-statistics) (newline)

(display (list total-pushes = number-pushes maximum-depth = max-depth))) (define (dispatch message)

(cond ((eq? message push) push) ((eq? message pop) (pop)) ((eq? message initialize) (initialize)) ((eq? message print-statistics)

(print-statistics)) (else

(error "Неизвестная операция -- STACK" message)))) dispatch))

В упражнениях от 5.15 до 5.19 описываются другие полезные возможности для сбора информации и отладки, которые можно добавить к имитатору регистровых машин.

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

Измерьте количество сохранений и максимальную глубину стека, требуемую для вычисления n! при различных малых значениях n с помощью факториальной машины, показанной на рисунке 5.11. По этим данным определите формулы в зависимости от n для числа сохранений и максимальной глубины стека, требуемых для вычисления n! при любом n> 1. Обратите внимание, что это линейные функции от n, и они определяются двумя константами. Чтобы увидеть статистику, Вам придется добавить к факториаль-ной машине команды для инициализации стека и распечатки статистики. Можно также заставить машину в цикле считывать n, вычислять факториал и печатать результат (как для машины НОД с рисунка 5.4), так, чтобы не нужно было все время вызывать get-register-contents, set-register-contents! и start.