• Для того, чтобы вычислить комбинацию, нужно:

-Вычислить подвыражения комбинации.12

-Применить значение выражения-оператора к значениям выражений-операндов.

Модель вычисления с окружениями заменяет подстановочную модель, по-своему определяя, что значит применить составную процедуру к аргументам.

В модели вычисления с окружениями процедура всегда представляется в виде пары, состоящей из кода и указателя на некое окружение. Процедура создается единственным способом: вычислением lambda-выражения. Такое вычисление дает в качестве результата процедуру, код которой берется из тела lambda-выражения, а окружение совпадает с окружением, в котором было вычислено выражение, чьим значением является процедура. Например, рассмотрим определение процедуры

(define (square x) (* x x))

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

(define square

(lambda (x) (* x x)))

которое вычисляет (lambda (x) (* x x)) и связывает символ square с полученным значением, все это в глобальном окружении.

Рис. 3.2 показывает результат вычисления lambda-выражения. Объект-процедура представляет собой пару, код которой указывает, что процедура принимает один формальный параметр, а именно x, а тело ее (* x x). Окружение процедуры - это указатель на глобальное окружение, поскольку именно в нем вычислялось lambda-выражение, при помощи которого процедура была порождена. К глобальному кадру добавилось новое связывание, которое сопоставляет процедурный объект символу square. В общем случае define создает определения, добавляя новые связывания в кадры.

Теперь, когда мы рассмотрели, как процедуры создаются, мы можем описать, как они применяются. Модель с окружениями говорит: чтобы применить процедуру к аргументам, создайте новое окружение, которое содержит кадр, связывающий параметры со значениями аргументов. Объемлющим окружением для нового кадра служит окружение, на которое указывает процедура. Теперь требуется выполнить тело процедуры в этом новом окружении.

Чтобы проиллюстрировать, как работает это новое правило, на рис. 3.3 показана структура окружений, которая создается при вычислении выражения

12Присваивание вносит одну тонкость в шаг 1 правила вычисления. Как показано в упражнении 3.8, присваивание позволяет нам писать выражения, которые имеют различные значения в зависимости от того, в каком порядке вычисляются подвыражения комбинации. Таким образом, чтобы быть точными, мы должны были бы указать порядок вычислений на шаге 1 (например, слева направо или справа налево). Однако этот порядок всегда должен рассматриваться как деталь реализации, и писать программы, которые зависят от порядка вычисления аргументов, не следует. К примеру, продвинутый компилятор может оптимизировать программу, изменяя порядок, в котором вычисляются подвыражения.

глобальное

окружение"

другие переменные square: -,

(define (square x)

(* x x))

параметры: x тело: (* x x)

Рис. 3.2: Структура окружений, порождаемая вычислением (define (square x) (* x x)) в глобальном окружении.

глобальное -

окружение

(square 5)

параметры: x тело: (* x x)

(* x x)

Рис. 3.3: Окружение, создаваемое при вычислении (square 5) в глобальном окружении.

(square 5) в глобальном окружении, если square - процедура, порожденная на рисунке 3.2. Применение процедуры приводит к созданию нового окружения, которое на рисунке обозначено как E1, и это окружение начинается с кадра, в котором x, формальный параметр процедуры, связан с аргументом 5. Указатель, который ведет из этого кадра вверх, показывает, что объемлющим для этого окружения является глобальное. Глобальное окружение выбирается потому, что именно на него ссылается процедурный объект square. Внутри E1 мы вычисляем тело процедуры, (* x x) . Поскольку значение x в E1 равно 5, результатом будет (* 5 5) , или 25.

Модель вычисления с окружениями можно вкратце описать двумя правилами:

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

• Процедура создается при вычислении lambda-выражения по отношению к некоторому окружению. Получающийся процедурный объект есть пара, состоящая из текста lambda-выражения и указателя на окружение, в котором процедура была создана.

Кроме того, мы указываем, что когда символ определяется при помощи define, в текущем кадре окружения создается связывание, и символу присваивается указанное значение.13 Наконец, мы описываем поведение set!, операции, из-за которой нам, собственно, и пришлось ввести модель с окружениями. Вычисление выражения (set! (переменная) (значение)) в некотором окружении заставляет интерпретатор найти связывание переменной в окружении и изменить это связывание так, чтобы оно указывало на новое значение. А именно, нужно найти первый кадр окружения, в котором содержится связывание для переменной, и изменить этот кадр. Если переменная в окружении не связана, set! сигнализирует об ошибке.

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

3.2.2 Применение простых процедур

Когда в разделе 1.1.5 мы описывали подстановочную модель, мы показали, как вычисление комбинации (f 5) дает результат 136, если даны следующие определения:

(define (square x) (* x x))

(define (sum-of-squares x y) (+ (square x) (square y)))

(define (f a)

(sum-of-squares (+ai) (* a 2)))

Теперь мы можем проанализировать тот же самый пример, используя модель с окружениями. На рисунке 3.4 изображены три процедурных объекта, созданные вычислением в глобальном окружении определений f, square, и sum-of-squares . Каждый процедурный объект состоит из куска кода и указателя на глобальное окружение.

На рисунке 3.5 мы видим структуру окружений, созданную вычислением выражения (f 5). Вызов f создает новое окружение E1, начинающееся с кадра, в

13Если в текущем кадре уже имелось связывание для указанной переменной, то это связывание изменяется. Это правило удобно, поскольку позволяет переопределять символы; однако оно означает, что при помощи define можно изменять значение символов, а это влечет за собой все проблемы, связанные с присваиванием, без явного использования set! . По этой причине некоторые предпочитают, чтобы переопределение существующего символа вызывало предупреждение или сообщение об ошибке.