5.1.3 · Подпрограммы и связывание continuation

Подпрограммы машины и регистр continue

Разделяемая подпрограмма получает адрес возврата через регистр continue, а сохранение прежнего продолжения бережет исходный вызывающий код.

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

Как регистровая машина возвращает управление из разделяемых и вложенных подпрограмм контроллера без дублирования их команд?

Сохранение адреса возврата для конкретного вызывающего кода в регистре continue
Переход в один разделяемый сегмент контроллера из двух мест вызова
Возврат через goto-register вместо фиксированной метки
Сохранение внешнего continuation перед вызовом вложенной подпрограммы
Восстановление исходного continuation перед возвратом к первому вызывающему коду

Первый контроллер дважды вызывает одну подпрограмму double. Перед каждым goto вызывающий код записывает различное значение pc в continue. Разделяемая подпрограмма изменяет val и выполняет goto-register continue, поэтому те же две команды возвращают управление сначала к команде, сохраняющей левый результат, а затем к команде, складывающей два удвоенных значения. Записанный путь pc показывает оба входа в индексы 9 и 10 без копирования подпрограммы.

Второй контроллер вызывает подпрограмму double-then-add-one, а эта подпрограмма вызывает double. Вложенному вызову требуется continue для собственного адреса возврата, поэтому внешняя подпрограмма сначала сохраняет значение вызывающего кода. После возврата из double операция restore восстанавливает исходный адрес, add1 завершает внешнюю подпрограмму, а goto-register возвращает управление в main. Этот конечный исполнитель моделирует явное связывание и один слот стека из урока.

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

(begin
  (define controller
    (vector
      '(assign val constant 3)
      '(assign continue constant 3)
      '(goto 9)
      '(assign left copy val)
      '(assign val constant 5)
      '(assign continue constant 7)
      '(goto 9)
      '(assign result add left val)
      '(halt)
      '(assign val double val)
      '(goto-register continue)))
  (define (register-index name)
    (cond ((eq? name 'val) 0)
          ((eq? name 'left) 1)
          ((eq? name 'result) 2)
          ((eq? name 'continue) 3)
          ((eq? name 'pc) 4)))
  (define (run-machine)
    (let ((registers (vector 0 0 0 0 0))
          (path '())
          (return-addresses '()))
      (define (get name)
        (vector-ref registers (register-index name)))
      (define (put! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!) (put! 'pc (+ (get 'pc) 1)))
      (define (assignment instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'copy)
                 (get (cadddr instruction)))
                ((eq? operation 'double)
                 (* 2 (get (cadddr instruction))))
                ((eq? operation 'add)
                 (+ (get (cadddr instruction))
                    (get (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((pc (get 'pc))
                   (instruction (vector-ref controller pc))
                   (operation (car instruction)))
              (set! path (cons pc path))
              (cond
                ((eq? operation 'halt)
                 (list (get 'result)
                       (reverse return-addresses)
                       (reverse path)))
                ((eq? operation 'assign)
                 (let ((target (cadr instruction))
                       (value (assignment instruction)))
                   (put! target value)
                   (if (eq? target 'continue)
                       (set! return-addresses
                             (cons value return-addresses)))
                   (advance!)
                   (execute (- remaining-steps 1))))
                ((eq? operation 'goto)
                 (put! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (put! 'pc (get (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 100)))
  (run-machine))

(begin
  (define controller
    (vector
      '(assign val constant 3)
      '(assign continue constant 3)
      '(goto 9)
      '(assign left copy val)
      '(assign val constant 5)
      '(assign continue constant 7)
      '(goto 9)
      '(assign result add left val)
      '(halt)
      '(assign val double val)
      '(goto-register continue)))
  (define (register-index name)
    (cond ((eq? name 'val) 0)
          ((eq? name 'left) 1)
          ((eq? name 'result) 2)
          ((eq? name 'continue) 3)
          ((eq? name 'pc) 4)))
  (define (run-machine)
    (let ((registers (vector 0 0 0 0 0))
          (path '())
          (return-addresses '()))
      (define (get name)
        (vector-ref registers (register-index name)))
      (define (put! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!) (put! 'pc (+ (get 'pc) 1)))
      (define (assignment instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'copy)
                 (get (cadddr instruction)))
                ((eq? operation 'double)
                 (* 2 (get (cadddr instruction))))
                ((eq? operation 'add)
                 (+ (get (cadddr instruction))
                    (get (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((pc (get 'pc))
                   (instruction (vector-ref controller pc))
                   (operation (car instruction)))
              (set! path (cons pc path))
              (cond
                ((eq? operation 'halt)
                 (list (get 'result)
                       (reverse return-addresses)
                       (reverse path)))
                ((eq? operation 'assign)
                 (let ((target (cadr instruction))
                       (value (assignment instruction)))
                   (put! target value)
                   (if (eq? target 'continue)
                       (set! return-addresses
                             (cons value return-addresses)))
                   (advance!)
                   (execute (- remaining-steps 1))))
                ((eq? operation 'goto)
                 (put! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (put! 'pc (get (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 100)))
  (run-machine))

Примеры

Результат—

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

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

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

Программа с разделяемой подпрограммой возвращает (16 (3 7) (0 1 2 9 10 3 4 5 6 9 10 7 8)). Программа с вложенным вызовом возвращает (9 1 0 (3 8) (0 1 2 5 6 7 11 12 8 9 10 3 4)).

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

В первом запуске найдите каждое присваивание в continue, оба перехода к одному и тому же значению pc подпрограммы и два возврата через goto-register к разным вызывающим фрагментам кода. Во втором запуске проследите save перед вложенным присваиванием в continue, внутренний возврат к pc 8, restore исходного pc 3 и окончательный возврат в main. Явный путь и глубина стека описывают только эти конечные контроллеры.

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

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

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

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

Разделяемая подпрограмма по-прежнему начинается с pc 9. Новому вызывающему коду требуется собственная команда сразу после goto, и он должен поместить этот pc в continue.

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

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