Ясности ради, eval реализована как перебор альтернатив через cond. Недостаток этой реализации - наша процедура обрабатывает только несколько указанных типов выражений, и, не меняя определение eval, новые типы добавить нельзя. В большинстве реализаций Лиспа распределение выражений по типам сделано в стиле, управляемом данными. Это дает пользователю возможность добавлять новые типы выражений, которые eval будет способен распознать, не меняя само определение eval. (См. упражнение 4.3.)

Процедура apply принимает два аргумента: процедуру и список аргументов, к которым ее надо применить. Apply делит процедуры на два класса: для применения примитивов она зовет apply-primitive-procedure; составные процедуры она применяет, по очереди вычисляя выражения, составляющие тело процедуры. Окружение, в котором вычисляется тело составной процедуры, получается из базового окружения, хранящегося в процедуре, добалением кадра, где параметры процедуры связываются с аргументами, к которым процедура применяется. Вот определение apply:

(define (apply procedure arguments)

(cond ((primitive-procedure? procedure)

(apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence

(procedure-body procedure) (extend-environment

(procedure-parameters procedure) arguments

(procedure-environment procedure))))

(else (error

"Неизвестный тип процедуры APPLY" procedure))))

Аргументы процедур

Обрабатывая применение процедуры, eval получает список аргументов, к которым процедуру надо применить, при помощи list-of-values. Процедура list-of-values в качестве аргумента берет список операндов комбинации. Она вычисляет каждый аргумент и возвращает список соответствующих значений.5

(define (list-of-values exps env) (if (no-operands? exps) ()

(cons (eval (first-operand exps) env)

(list-of-values (rest-operands exps) env))))

5Ветку application? в eval можно было бы упростить, используя map (и постановив, что operands возвращает список) вместо того, чтобы писать явным образом процедуру list-of-values. Мы решили не использовать здесь map, чтобы подчеркнуть, что интерпретатор можно написать без обращения к процедурам высших порядков (а следовательно, его можно написать на языке, в котором нет таких процедур), притом, что язык, поддерживаемый интерпретатором, содержит процедуры высших порядков.

Условные выражения

Процедура eval-if вычисляет предикатную часть выражения if в данном окружении. Если результат истинен, eval-if выполняет следствие, если нет, - альтернативу:

(define (eval-if exp env)

(if (true? (eval (if-predicate exp) env)) (eval (if-consequent exp) env) (eval (if-alternative exp) env)))

Использование true? в eval-if подчеркивает вопрос о связи между реализуемым языком и языком реализации. Выражение if-predicate выполняется в реализуемом языке, и, следовательно, результат его является значением этого языка. Предикат интерпретатора true? переводит это значение в значение, которое может быть проверено выражением if в языке реализации: мета-циклическое представление истины может не совпадать с ее представлением в нижележащей Scheme.6

Последовательности

Процедура eval-sequence вызывается из apply для выполнения последовательности выражений в теле процедуры, а также из eval для обработки последовательности выражений в выражении begin. Она принимает в виде аргументов последовательность выражений и окружение, и выполняет выражения в том порядке, в котором они ей даны. Возвращаемое значение совпадает со значением последнего выражения.

(define (eval-sequence exps env)

(cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env)

(eval-sequence (rest-exps exps) env))))

Присваивания и определения

Следующая процедура обрабатывает присваивание переменным. При помощи eval она находит значение, которое требуется присвоить, и передает переменную и получившееся значение в процедуру set-variable-value! для включения в текущее окружение.

(define (eval-assignment exp env)

(set-variable-value! (assignment-variable exp)

(eval (assignment-value exp) env) env)

ok)

Определения переменных обрабатываются сходным образом:7

6В нашем случае, язык реализации и реализуемый язык совпадают. Размышления о значении true? расширяют наше сознание безотносительно к материальной сущности истины.

7Эта реализация define не учитывает один тонкий вопрос в обработке внутренних определений, хотя в большинстве случаев работает правильно. В чем состоит проблема и как ее решить, мы увидим в разделе 4.1.6.

(define (eval-definition exp env)

(define-variable! (definition-variable exp)

(eval (definition-value exp) env) env)

ok)

В качестве возвращаемого значения для присваивания или определения мы выбрали символ ok.8

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

Заметим, что мы не можем сказать, вычисляет ли метациклический интерпретатор операнды слева направо или справа налево. Порядок вычисления наследуется от нижележащего Лиспа: если аргументы cons в процедуре list-of-values вычисляются слева направо, то и операнды в list-of-values будут вычисляться слева направо. Если же вычисление аргументов cons происходит справа налево, то и list-of-values будет вычислять операнды справа налево.

Напишите версию list-of-values, которая вычисляет операнды слева направо, вне зависимости от порядка вычислений в нижележащем Лиспе. Напишите также версию, которая вычисляет операнды справа налево.

4.1.2 Представление выражений

Интерпретатор напоминает программу символьного дифференцирования, описанную в разделе 2.3.2. Обе программы работают с символьными выражениями. В обеих результат работы с составным выражением определяется рекурсивной обработкой частей выражения и сочетанием частичных результатов, причем способ сочетания зависит от типа выражения. И там, и там мы использовали абстракцию данных, чтобы отделить общие правила работы от деталей того, как представлены выражения. Для программы дифференцирования это означало, что одна и та же процедура взятия производной могла работать с алгебраическими выражениями в префиксной, инфиксной или какой-либо другой записи. Для интерпретатора это означает, что синтаксис языка определяется исключительно процедурами, которые классифицируют выражения и выделяют их части.

Вот описание синтаксиса нашего языка:

•К самовычисляющимся объектам относятся только числа и строки:

(define (self-evaluating? exp) (cond ((number? exp) true) ((string? exp) true) (else false)))

•Переменные представляются в виде символов: (define (variable? exp) (symbol? exp))

•Выражения с кавычкой имеют форму (quote (закавыченное-выра-жение)):

8 Как мы упоминали при введении define и set!, их значения в Scheme зависят от реализации - то есть, автор реализации имеет право выбрать такое значение, какое он хочет.