(set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (if (eq? env the-empty-environment)

(error "Несвязанная переменная -- SET!" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env))

Чтобы определить переменную, мы просматриваем первый кадр в поисках связывания для нее, и изменяем связывание, если его удается найти (так же, как в set-variable-value!). Если связывания не существует, мы присоединяем его к первому кадру.

(define (define-variable! var val env) (let ((frame (first-frame env))) (define (scan vars vals) (cond ((null? vars)

(add-binding-to-frame! var val frame)) ((eq? var (car vars)) (set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (scan (frame-variables frame) (frame-values frame))))

Описанный здесь метод - только один из многих способов представления окружений. Поскольку мы при помощи абстракции данных отделили конкретную реализацию от остальных частей интерпретатора, при желании мы можем сменить представление окружений. (См. упражнение 4.11.) В Лисп-системе промышленного качества быстрота операций над окружениями - особенно обращения к переменной - очень сильно влияет на общую производительность. Представление, описанное здесь, при всей своей концептуальной простоте неэффективно и, скорее всего, его не стали бы использовать в рабочей системе.15

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

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

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

Процедуры set-variable-value! , define-variable! и lookup-variable-value можно выразить посредством более абстрактных процедур для просмотра структуры окружений. Определите абстракции, которые фиксируют общую схему поведения, и с их помощью перепишите эти три процедуры.

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

Scheme позволяет создавать новые связывания через define, но не дает никакого способа избавиться от связывания. Реализуйте в интерпретаторе особую форму make-

15Недостаток этого представления (как и варианта из упражнения 4.11) состоит в том, что вычислителю может понадобиться просматривать слишком много кадров, чтобы найти связывание конкретной переменной. (Такой подход называется глубокое связывание (deep binding).) Один из способов избежать такой потери производительности - использовать стратегию под названием лексическая адресация (lexical addressing), которая обсуждается в разделе 5.5.6.

unbound! , которая изымает связывание данного символа из окружения, в котором make-unbound! выполняется. Задача определена не до конца. Например, нужно ли удалять связывания в других кадрах, кроме первого? Дополните спецификацию и объясните свой выбор вариантов.

4.1.4 Выполнение интерпретатора как программы

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

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

Нам нужно иметь связывание для каждого имени элементарной процедуры, чтобы, когда eval выполняет вызов примитива, у него был объект, который можно передать в apply. Поэтому мы выстраиваем глобальное окружение, связывающее особые объекты с именами элементарных процедур, которые могут появляться в вычисляемых нами выражениях. Кроме того, глобальное окружение включает связывания для символов true и false, так что их можно использовать как переменные в вычисляемых выражениях.

(define (setup-environment) (let ((initial-env

(extend-environment (primitive-procedure-names)

(primitive-procedure-objects) the-empty-environment))) (define-variable! true true initial-env) (define-variable! false false initial-env) initial-env))

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

Как именно мы представляем объекты-элементарные процедуры, не имеет значения. Требуется только, чтобы их можно было распознавать и применять, вызывая процедуры primitive-procedure? и apply-primitive-procedure. Мы решили представлять примитивы в виде списка, начинающегося с символа primitive и содержащего процедуру нижележащего Лиспа, которая реализует данный примитив.

(define (primitive-procedure? proc) (tagged-list? proc primitive))

(define (primitive-implementation proc) (cadr proc))

Setup-environment получит имена и реализации элементарных процедур из списка:16

16Любую процедуру, определенную в нижележащем Лиспе, можно использовать как примитив

(define primitive-procedures (list (list car car) (list cdr cdr) (list cons cons)

(list null? null?)

другие примитивы

))

(define (primitive-procedure-names) (map car

primitive-procedures))

(define (primitive-procedure-objects)

(map (lambda (proc) (list primitive (cadr proc))) primitive-procedures))

Чтобы вызвать элементарную процедуру, мы просто применяем процедуру-реализацию к аргументам, используя нижележащую Лисп-систему:17

(define (apply-primitive-procedure proc args) (apply-in-underlying-scheme (primitive-implementation proc) args))

Для удобства работы с метациклическим интерпретатором мы организуем управляющий цикл (driver loop), который моделирует цикл чтения-выполнения-печати нижележащей Лисп-системы. Этот цикл печатает подсказку (prompt), считывает входное выражение, вычисляет это выражение в глобальном окружении и распечатывает результат. Перед каждым результатом мы помещаем подсказку вывода (output prompt), чтобы отличить значение выражения от всего прочего, что может быть напечатано.18

(define input-promptВвод M-Eval:")

(define output-promptЗначение M-Eval:")

(define (driver-loop)

для метациклического интерпретатора. Имя примитива, установленного в интерпретаторе, не обязательно должно совпадать с именем его реализации в нижележащем Лиспе; здесь имена одни и те же потому, что метациклический интерпретатор реализует саму Scheme. Так, например, мы могли бы написать в списке primitive-procedures что-нибудь вроде (list first car) или (list square (lambda (x) (* x x))).

17Apply-in-underlying-scheme - это процедура apply, которой мы пользовались в предыдущих главах. Процедура apply метациклического интерпретатора (раздел 4.1.1) имитирует работу этого примитива. Наличие двух процедур с одинаковым именем ведет к технической проблеме при запуске интерпретатора, поскольку определение apply метациклического интерпретатора загородит определение примитива. Можно избежать этого, переименовав метациклический apply, и избавиться таким образом от конфликта с именем элементарной процедуры. Мы же вместо этого приняли решение сохранить ссылку на исходный apply, выполнив

(define apply-in-underlying-scheme apply)

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

18Элементарная процедура read ожидает ввода от пользователя и возвращает ближайшее полное выражение, которое он напечатает. Например, если пользователь напечатает (+ 23 x), результатом read будет трехэлементный список из символа +, числа 23 и символа x. Если пользователь введет x, результатом read будет двухэлементный список из символа quote и символа x.