5.2.3 · Выполнение контроллера

Исполнение ассемблированных команд по pc

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

Вопрос для размышления

Как один числовой счетчик команд координирует присваивание, проверку и передачу управления?

Сохранение разрешенных команд в векторе контроллера с прямой индексацией
Хранение n, product, flag и pc в явном регистровом файле
Интерпретация команд assign, test, branch, goto и halt
Ограничение выполнения и сохранение видимой истории состояний

Контроллер использует числовые цели, полученные в предыдущем уроке по ассемблеру. Вектор состояния представляет собой регистровый файл в порядке n, product, flag и pc. На каждом цикле извлекается controller[pc]. Команда assign или test продвигает pc вперед, branch либо выбирает 7, либо продвигается вперед, goto записывает 2, а halt возвращает регистры.

Первая программа выполняет полный контроллер при значении n, равном 2, и оставляет значение product, равным 2. Вторая программа записывает pc, n, product и flag после каждой команды, отличной от halt, начиная с n, равного 1. Оба запуска имеют ограничение в 40 шагов. Исполнитель команд обрабатывает assign, test, branch, goto и halt над вектором разрешенного контроллера.

Код SICP1,876 из 1,048,576 байт UTF-8

(begin
  (define controller
    (vector '(assign n constant 2)
            '(assign product constant 1)
            '(test zero? n)
            '(branch 7)
            '(assign product multiply product n)
            '(assign n sub1 n)
            '(goto 2)
            '(halt)))
  (define state (vector 0 0 #f 0))
  (define (run-machine remaining)
    (if (= remaining 0)
        'step-limit
        (let ((instruction (vector-ref controller (vector-ref state 3))))
          (cond
            ((eq? (car instruction) 'halt)
             (list (vector-ref state 0) (vector-ref state 1)
                   (vector-ref state 2) (vector-ref state 3)))
            ((eq? (car instruction) 'assign)
             (if (eq? (cadr instruction) 'n)
                 (vector-set! state 0
                   (if (eq? (caddr instruction) 'constant)
                       (cadddr instruction)
                       (- (vector-ref state 0) 1)))
                 (vector-set! state 1
                   (if (eq? (caddr instruction) 'constant)
                       (cadddr instruction)
                       (* (vector-ref state 1) (vector-ref state 0)))))
             (vector-set! state 3 (+ (vector-ref state 3) 1))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'test)
             (vector-set! state 2 (= (vector-ref state 0) 0))
             (vector-set! state 3 (+ (vector-ref state 3) 1))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'branch)
             (vector-set! state 3
               (if (vector-ref state 2)
                   (cadr instruction)
                   (+ (vector-ref state 3) 1)))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'goto)
             (vector-set! state 3 (cadr instruction))
             (run-machine (- remaining 1)))))))
  (run-machine 40))

(begin
  (define controller
    (vector '(assign n constant 2)
            '(assign product constant 1)
            '(test zero? n)
            '(branch 7)
            '(assign product multiply product n)
            '(assign n sub1 n)
            '(goto 2)
            '(halt)))
  (define state (vector 0 0 #f 0))
  (define (run-machine remaining)
    (if (= remaining 0)
        'step-limit
        (let ((instruction (vector-ref controller (vector-ref state 3))))
          (cond
            ((eq? (car instruction) 'halt)
             (list (vector-ref state 0) (vector-ref state 1)
                   (vector-ref state 2) (vector-ref state 3)))
            ((eq? (car instruction) 'assign)
             (if (eq? (cadr instruction) 'n)
                 (vector-set! state 0
                   (if (eq? (caddr instruction) 'constant)
                       (cadddr instruction)
                       (- (vector-ref state 0) 1)))
                 (vector-set! state 1
                   (if (eq? (caddr instruction) 'constant)
                       (cadddr instruction)
                       (* (vector-ref state 1) (vector-ref state 0)))))
             (vector-set! state 3 (+ (vector-ref state 3) 1))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'test)
             (vector-set! state 2 (= (vector-ref state 0) 0))
             (vector-set! state 3 (+ (vector-ref state 3) 1))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'branch)
             (vector-set! state 3
               (if (vector-ref state 2)
                   (cadr instruction)
                   (+ (vector-ref state 3) 1)))
             (run-machine (- remaining 1)))
            ((eq? (car instruction) 'goto)
             (vector-set! state 3 (cadr instruction))
             (run-machine (- remaining 1)))))))
  (run-machine 40))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (0 2 #t 7). Вторая возвращает ((1 1 0 #f) (2 1 1 #f) (3 1 1 #f) (4 1 1 #f) (5 1 1 #f) (6 0 1 #f) (2 0 1 #f) (3 0 1 #t) (7 0 1 #t)).

На что обратить внимание в трассе

Следите за vector-ref по текущему значению pc перед каждой командой. Найдите присваивания в product и n, переход flag в значение true при значении pc 2, продвижение ложной ветви к значению pc 4, возврат pc к значению 2 по goto и выбор halt на значении pc 7 истинной ветвью. Трассы выполнения фиксируют этот контроллер с ограничением в 40 шагов.

Попробуйте сами

Измените программу и сравните результат.

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

Показать подсказку

После того как product становится равен 1, test устанавливает flag в значение true, а branch записывает 7 непосредственно в pc.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%