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

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

(set-register-contents! gcd-machine a 206) done

(set-register-contents! gcd-machine b 40) done

(start gcd-machine) done

(get-register-contents gcd-machine a) 2

Эта модель будет работать значительно медленнее, чем процедура gcd, написанная на Scheme, поскольку она имитирует низкоуровневые команды машины, например, assign, с помощью значительно более сложных операций.

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

Проверьте на имитаторе машины, построенные Вами в упражнении 5.4.

5.2.1 Модель машины

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

Затем make-machine расширяет эту базовую модель (посылая ей сообщения) и добавляет в нее регистры, операции и контроллер для конкретной определяемой машины. Сначала она выделяет в новой машине по регистру на каждое из данных имен регистров и встраивает в нее указанные операции. Затем она с помощью ассемблера (assembler) (описанного в разделе 5.2.2) преобразует список контроллера в команды новой машины и устанавливает их ей в качестве последовательности команд. В качестве результата make-machine возвращает модифицированную модель машины.

(define (make-machine register-names ops controller-text) (let ((machine (make-new-machine))) (for-each (lambda (register-name)

((machine allocate-register) register-name))

register-names) ((machine install-operations) ops) ((machine install-instruction-sequence)

(assemble controller-text machine)) machine))

Регистры

Мы будем представлять регистры в виде процедур с внутренним состоянием, как в главе 3. Процедура make-register создает регистр. Регистр содержит значение, которое можно считать или изменить.

(define (make-register name)

(let ((contents *unassigned*)) (define (dispatch message)

(cond ((eq? message get) contents) ((eq? message set)

(lambda (value) (set! contents value))) (else

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

Для доступа к регистрам используются следующие процедуры:

(define (get-contents register) (register get))

(define (set-contents! register value) ((register set) value))

Стек

Стек также можно представить в виде процедуры с внутренним состоянием. Процедура make-stack создает стек, внутреннее состояние которого состоит из списка элементов на стеке. Стек принимает сообщение push, кладущее элемент на стек, сообщение pop, снимающее со стека верхний элемент и возвращающее его, и сообщение initialize, которое дает стеку начальное пустое значение.

(define (make-stack)

(let ((s ()))

(define (push x)

(set! s (cons x s))) (define (pop)

(if (null? s)

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

top)))

(define (initialize)

(set! s ())

done)

(define (dispatch message)

(cond ((eq? message push) push)

((eq? message pop) (pop)) ((eq? message initialize) (initialize)) (else (error "Неизвестная операция -- STACK" message))))

dispatch))

Для доступа к стеку используются следующие процедуры:

(define (pop stack) (stack pop))

(define (push stack value) ((stack push) value))

Базовая машина

Процедура make-new-machine, приведенная на рисунке 5.13, порождает объект, внутреннее состояние которого состоит из стека, изначально пустой последовательности команд, списка операций, где с самого начала присутствует операция инициализации стека, а также таблицы регистров (register table), в которой изначально содержатся два регистра, flag и pc (от program counter, «счетчик программы»). Внутренняя процедура allocate-register добавляет в таблицу новый элемент, а внутренняя процедура lookup-register ищет регистр в таблице.

Регистр flag используется для управления переходами в имитируемой машине. Команды test присваивают ему результат теста (истину или ложь). Команды branch определяют, нужно ли делать переход, в зависимости от значения регистра flag.

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

В процессе работы каждая исполнительная процедура изменяет pc и указывает, какую следующую команду надо выполнить. Команды branch и goto присваивают регистру pc значение, указывающее на новый адрес. Все остальные команды просто продвигают pc так, чтобы он указывал на следующую команду в последовательности. Заметим, что каждый вызов execute снова зовет execute, но это не приводит к бесконечному циклу, поскольку запуск исполнительной процедуры команды изменяет содержимое pc.

Make-new-machine возвращает процедуру dispatch, которая дает доступ к внутреннему состоянию на основе передачи сообщений. Запуск машины осуществляется путем установки pc в начало последовательности команд и вызова execute.

Ради удобства мы предоставляем альтернативный процедурный интерфейс