Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 54
Текст из файла (страница 54)
Скажем, рациональное число мы обычно нерассматриваем как изменяемый объект со своей индивидуальностью, у которого можнобыло бы изменить числитель и по-прежнему иметь дело с «тем же» числом.Ловушки императивного программированияВ противоположность функциональному программированию, стиль программирования, при котором активно используется присваивание, называется императивное программирование (imperative programming). Кроме того, что возникают сложности с вычислительными моделями, программы, написанные в императивном стиле, подверженытаким ошибкам, которые в функциональных программах не возникают.
Вспомним, кпримеру, итеративную программу для вычисления факториала из раздела 1.2.1:(define (factorial n)(define (iter product counter)(if (> counter n)product(iter (* counter product)10 Когда у вычислительного объекта имеется несколько имён, эти имена называются псевдонимами (aliasing).Ситуация с совместным банковским счетом — простой пример псевдонимов.
В разделе 3.3 мы увидим значительно более сложные примеры, скажем, «различные» составные структуры с общими частями. Если мызабудем, что «побочным эффектом» в результате изменения одного объекта может стать изменение «другого»объекта, поскольку «разные» объекты — на самом деле один и тот же под разными псевдонимами, то могутвозникнуть ошибки. Эти так называемые ошибки побочных эффектов (side-effect bugs) настолько трудно обнаруживать и анализировать, что некоторые исследователи выступали с предложениями не допускать в языкахпрограммирования побочные эффекты и псевдонимы (Lampson et al. 1981; Morris, Schmidt, and Wadler 1980).Глава 3. Модульность, объекты и состояние226(+ 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))— получился бы другой, неверный результат. Вообще, программирование с использованием присваивания заставляет нас тщательно следить за порядком присваиваний, так,чтобы в каждом использовалась правильная версия значения переменных, которые меняются.
В функциональных программах такие сложности просто не возникают11 .Сложность императивных программ еще увеличивается, если мы начинаем рассматривать приложения, где одновременно выполняется несколько процессов. К этому мыеще вернемся в разделе 3.4. Однако сначала мы обратимся к задаче построения вычислительной модели для выражений, содержащих присваивание, а также изучим, какиспользовать объекты с локальным состоянием при проектировании моделирующих программ.Упражнение 3.7.Рассмотрим объекты-банковские счета, создаваемые процедурой make-account, и снабженныепаролями, как это описано в упражнении 3.3.
Предположим, что наша банковская система требует от нас умения порождать совместные счета. Напишите процедуру make-joint, которая этоделает. Make-joint должна принимать три аргумента. Первый из них — защищенный паролем11 Поэтому странно и смешно, что вводные курсы программирования часто читаются в глубоко императивномстиле. Может быть, сказываются остатки распространенного в 60-е и 70-е годы представления, что программы,которые вызывают процедуры, непременно будут менее эффективны, чем те, которые производят присваивания. (Steele 1977 развенчивает этот аргумент.) С другой стороны, возможно, считается, что новичкам легчепредставить пошаговое присваивание, чем вызов процедуры. Так или иначе, программистам часто приходитсязаботиться о вопросе «присвоить сначала эту переменную или ту?», а это усложняет программирование изатемняет важные идеи.3.2.
Модель вычислений с окружениями227счет. Второй обязан совпадать с паролем, с которым этот счет был создан, иначе make-jointоткажется работать. Третий аргумент — новый пароль. Например, если банковский счет peteraccount был создан с паролем 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 1))возвращало 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 и D — указателиГлава 3. Модульность, объекты и состояние228x:3y:5Cz:6x:7AIIIDm:1y:2IIIBРис. 3.1.
Простой пример структуры окруженийна окружения. 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:3.2. Модель вычислений с окружениями229• Для того, чтобы вычислить комбинацию, нужно:– Вычислить подвыражения комбинации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 создает определения, добавляя новые связывания в кадры.Теперь, когда мы рассмотрели, как процедуры создаются, мы можем описать, какони применяются.
Модель с окружениями говорит: чтобы применить процедуру к аргументам, создайте новое окружение, которое содержит кадр, связывающий параметры созначениями аргументов. Объемлющим окружением для нового кадра служит окружение,на которое указывает процедура. Теперь требуется выполнить тело процедуры в этомновом окружении.Чтобы проиллюстрировать, как работает это новое правило, на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
