(iter (* counter product) (+ counter 1))))

(iter 1 1))

Вместо того, чтобы передавать аргументы во внутреннем итеративном цикле, мы могли бы написать процедуру в более императивном стиле с использованием присваивания для обновления значений переменных product и counter:

(define (factorial n)

(let ((product 1) (counter 1)) (define (iter)

(if (> counter n) product

(begin (set! product (* counter product)) (set! counter (+ counter 1))

(iter))))

(iter)))

Результаты, выдаваемые программой, при этом не меняются, но возникает маленькая ловушка. Как определить порядок присваиваний? В имеющемся виде программа корректна. Однако если бы мы записали присваивания в обратном порядке:

(set! counter (+ counter 1))

(set! product (* counter product))

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

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

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

Рассмотрим объекты-банковские счета, создаваемые процедурой make-account, и снабженные паролями, как это описано в упражнении 3.3. Предположим, что наша банковская система требует от нас умения порождать совместные счета. Напишите процедуру make-joint, которая это делает. Make-joint должна принимать три аргумента. Первый из них - защищенный паролем счет. Второй обязан совпадать с паролем,

"Поэтому странно и смешно, что вводные курсы программирования часто читаются в глубоко императивном стиле. Может быть, сказываются остатки распространенного в 60-е и 70-е годы представления, что программы, которые вызывают процедуры, непременно будут менее эффективны, чем те, которые производят присваивания. (Steele 1977 развенчивает этот аргумент.) С другой стороны, возможно, считается, что новичкам легче представить пошаговое присваивание, чем вызов процедуры. Так или иначе, программистам часто приходится заботиться о вопросе «присвоить сначала эту переменную или ту?», а это усложняет программирование и затемняет важные идеи.

с которым этот счет был создан, иначе make-joint откажется работать. Третий аргумент - новый пароль. Например, если банковский счет peter-account был создан с паролем open-sesame, то

(define paul-acc

(make-joint peter-acc open-sesame rosebud))

позволит нам проводить операции с peter-account, используя имя paul-acc и пароль rosebud. Вам может потребоваться переработать решение упражнения 3.3, чтобы добавить эту новую возможность.

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

Когда в разделе 1.1.3 мы определяли модель вычислений, мы сказали, что первым шагом при вычислении выражения является вычисление его подвыражений. Однако мы нигде не указали порядок, в котором проходит вычисление подвыражений (слева направо или справа налево). Когда мы вводим присваивание, порядок, в котором вычисляются аргументы процедуры, может повлиять на результат. Определите простую процедуру f, так, чтобы вычисление (+ (f 0) (f i)) возвращало 0, если аргументы + вычисляются слева направо, и 1, если они вычисляются справа налево.

3.2 Модель вычислений с окружениями

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

• Чтобы применить составную процедуру к аргументам, нужно вычислить тело процедуры, подставив вместо каждого формального параметра соответствующий ему аргумент.

Как только мы вводим в язык программирования присваивание, это определение перестает быть адекватным. А именно, в разделе 3.1.3 указывалось, что в присутствии присваивания переменную уже нельзя рассматривать просто как имя для значения. Переменная должна каким-то образом обозначать «место», где значение может храниться. В нашей новой модели вычислений такие места будут находиться в структурах, которые мы называем окружениями (environments).

Окружение представляет собой последовательность кадров (frames). Каждый кадр есть (возможно, пустая) таблица связываний (bindings), которые сопоставляют имена переменных соответствующим значениям. (Каждый кадр должен содержать не более одного связывания для каждой данной переменной.) Кроме того, в каждом кадре имеется указатель на объемлющее окружение (enclosing environment), кроме тех случаев, когда в рамках текущего обсуждения окружение считается глобальным (global). Значение переменной (value of a variable) по отношению к данному окружению есть значение, которое находится в связывании для этой переменной в первом кадре окружения, содержащем такое связывание. Если в последовательности кадров ни один не указывает значения для данной переменной, говорят, что переменная несвязана (unbound) в окружении.

На рисунке 3.1 изображена простая структура окружений, которая состоит из трех кадров, помеченных числами I, II и III. На этой диаграмме A, B, C и

AB

Рис. 3.1: Простой пример структуры окружений

D - указатели на окружения. C и D указывают на одно и то же окружение. В кадре II связываются переменные z и x, а в кадре I переменные y и x. В окружении D переменная x имеет значение 3. В окружении B значение переменной x также равно 3. Это определяется следующим образом: мы рассматриваем первый кадр в последовательности (кадр III) и не находим там связывания для переменной x, так что мы переходим к объемлющему окружению D и находим связывание в кадре I. С другой стороны, в окружении A значение переменной x равно 7, поскольку первый кадр окружения (кадр II) содержит связывание x со значением 7. По отношению к окружению A говорится, что связывание x со значением 7 в кадре II скрывает (shadows) связывание x со значением 3 в кадре I.

Окружение играет важную роль в процессе вычисления, поскольку оно определяет контекст, в котором выражение должно вычисляться. В самом деле, можно сказать, что выражения языка программирования сами по себе не имеют значения. Выражение приобретает значение только по отношению к окружению, в контексте которого оно вычисляется. Даже интерпретация столь простого выражения, как (+ 1 1), зависит от нашего понимания, что мы работаем в контексте, где + является символом сложения. Таким образом, в нашей модели мы всегда будем говорить о вычислении выражения относительно некоторого окружения. При описании взаимодействия с интерпретатором мы будем предполагать, что существует глобальное окружение, состоящее из одного кадра (без объемлющего окружения), и что глобальное окружение содержит значения для символов, обозначающих элементарные процедуры. Например, информация о том, что + служит символом сложения, выражается как утверждение, что в глобальном окружении символ + связан с элементарной процедурой сложения.

3.2.1 Правила вычисления

Общее описание того, как интерпретатор вычисляет комбинацию, остается таким же, как оно было введено в разделе 1.1.3: