главы 4 мы, используя как язык саму Scheme, сделали более явной структуру окружений, которые строятся при вычислении выражения. Теперь, рассмотрев регистровые машины, мы внимательнее исследовали механизмы вычислителя для работы с памятью, передачи аргументов и управления. На каждом новом уровне нам приходилось сталкиваться с вопросами и разрешать неясности, которые не были заметны при предыдущем, менее строгом описании вычислений. Для того, чтобы понять поведение вычислителя с явным управлением, мы можем построить его имитационную модель и рассмотреть ее работу.

Введем в нашу машину-вычислитель управляющий цикл. Он играет роль процедуры driver-loop из раздела 4.1.4. Вычислитель будет в цикле печатать подсказку, считывать выражение, выполнять его с помощью перехода на eval-dispatch, и печатать результат. Следующая группа команд стоит в начале последовательности команд контроллера в вычислителе с явным управлением:29

read-eval-print-loop

(perform (op initialize-stack)) (perform

(op prompt-for-input) (constВвод EC-Eval:"))

(assign exp (op read))

(assign env (op get-global-environment)) (assign continue (label print-result)) (goto (label eval-dispatch)) print-result (perform

(op announce-output) (constЗначение EC-Eval:"))

(perform (op user-print) (reg val)) (goto (label read-eval-print-loop))

Когда мы сталкиваемся с ошибкой (например, с ошибкой «неизвестный тип процедуры» из apply-dispatch), мы печатаем сообщение об ошибке и возвращаемся в управляющий цикл.30

unknown-expression-type

(assign val (const unknown-expression-type-error))

(goto (label signal-error)) unknown-procedure-type

(restore continue); очистить стек (после apply-dispatch

(assign val (const unknown-procedure-type-error))

(goto (label signal-error))

29Мы предполагаем, что read и различные операции печати имеются как элементарные машинные операции. Такое предположение разумно в целях имитации, но на практике совершенно нереалистично. Эти операции чрезвычайно сложны. На практике они реализовывались бы с помощью низкоуровневых операций ввода-вывода, например, посимвольного ввода и вывода печатных знаков на устройство.

Для поддержки операции get-global-environment мы определяем

(define the-global-environment (setup-environment))

(define (get-global-environment) the-global-environment)

30Хотелось бы обрабатывать и другие типы ошибок, но этого не так легко добиться. См. упражнение 5.30.

signal-error

(perform (op user-print) (reg val)) (goto (label read-eval-print-loop))

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

Если мы соберем все фрагменты кода, представленные в разделах 5.4.15.4.4, то можно создать модель машины-вычислителя, которая запускается имитатором регистровых машин из раздела 5.2.

(define eceval (make-machine

(exp env val proc argl continue unev) eceval-operations

(

read-eval-print-loop

(контроллер машины, как описано выше)

)))

Требуется определить процедуры Scheme, имитирующие операции, которые считаются элементарными в вычислителе. Это те же операции, которые использовались в метациклическом интерпретаторе из раздела 4.1, а также несколько дополнительных, определенных в примечаниях к разделу 5.4.

(define eceval-operations

(list (list self-evaluating? self-evaluating)

(полный список операций машины-вычислителя)))

Наконец, мы можем проинициализировать глобальное окружение и запустить вычислитель:

(define the-global-environment (setup-environment))

(start eceval)

;;; Ввод EC-Eval: (define (append x y)

(if (null? x) y

(cons (car x)

(append (cdr x) y)))) ;;; Значение EC-Eval: ok

;;; Ввод EC-Eval: (append (a b c) (d e f)) ;;; Значение EC-Eval: (a b c d e f)

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

Разумеется, вычисление выражений таким образом занимает намного больше времени, чем если их вводить напрямую в Scheme, по причине многослойной имитации. Наши выражения выполняются регистровой машиной-вычислителем с явным управлением, которая имитируется программой на Scheme, которая, в свою очередь, выполняется интерпретатором Scheme.

Отслеживание производительности вычислителя

Имитационное моделирование может служить мощным инструментом, помогающим в реализации вычислителей. С помощью имитации легко можно не только исследовать варианты построения регистровых машин, но и отслеживать производительность имитируемого вычислителя. Например, один из важных параметров производительности состоит в том, насколько эффективно вычислитель использует стек. Можно отследить количество стековых операций, которые требуются для вычисления различных выражений, если взять версию имитатора, которая собирает статистику по использованию стека (раздел 5.2.4) и добавить на точку входа print-result дополнительную команду, распечатывающую эту статистику:

print-result

(perform (op print-stack-statistics)) ; добавленная команда (perform

(op announce-output) (const ";;; Значение EC-Eval:")) ... ; как и раньше

Теперь работа с вычислителем выглядит так:

; ;; Ввод EC-Eval: (define (factorial n) (if (= n 1)

1

(* (factorial (- n 1)) n))) (total-pushes = 3 maximum-depth = 3) ;;; Значение EC-Eval: ok

;;; Ввод EC-Eval: (factorial 5)

(total-pushes = 144 maximum-depth = 28)

;;; Значение EC-Eval:

120

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

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

С помощью отслеживания стека исследуйте хвостовую рекурсию в нашем вычислителе (раздел 5.4.2). Запустите вычислитель и определите итеративную процедуру factorial из раздела 1.2.1:

(define (factorial n)

(define (iter product counter) (if (> counter n)