Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 11
Текст из файла (страница 11)
Процедуры и порождаемые ими процессы47(< (abs (- (square guess) x)) 0.001))(define (improve guess x)(average guess (/ x guess)))(define (sqrt-iter guess x)(if (good-enough? guess x)guess(sqrt-iter (improve guess x) x)))(sqrt-iter 1.0 x))Такое вложение определений, называемое блочной структурой (block structure), даетправильное решение для простейшей задачи упаковки имен. Но здесь таится еще одна идея.
Помимо того, что мы можем вложить определения вспомогательных процедурвнутрь главной, мы можем их упростить. Поскольку переменная x связана в определенииsqrt, процедуры good-enough?, improve и sqrt-iter, которые определены внутриsqrt, находятся в области действия x. Таким образом, нет нужды явно передавать x вкаждую из этих процедур. Вместо этого мы можем сделать x свободной переменной вовнутренних определениях, как это показано ниже.
Тогда x получит свое значение от аргумента, с которым вызвана объемлющая их процедура sqrt. Такой порядок называетсялексической сферой действия (lexical scoping) переменных27 .(define (sqrt x)(define (good-enough? guess)(< (abs (- (square guess) x)) 0.001))(define (improve guess)(average guess (/ x guess)))(define (sqrt-iter guess)(if (good-enough? guess)guess(sqrt-iter (improve guess))))(sqrt-iter 1.0))Мы будем часто использовать блочную структуру, чтобы разбивать большие программы на куски разумного размера28 . Идея блочной структуры происходит из языкапрограммирования Алгол 60. Она присутствует в большинстве современных языков программирования. Это важный инструмент, который помогает организовать построениебольших программ.1.2.
Процедуры и порождаемые ими процессыВ предыдущем разделе мы рассмотрели элементы программирования. Мы использовали элементарные арифметические операции, комбинировали их и абстрагировалиполучившиеся составные операции путем определения составных процедур. Но всего27 Правило лексической сферы действия говорит, что свободные переменные в процедуре ссылаются на связывания этих переменных, сделанные в объемлющих определениях процедур; то есть они ищутся в окружении, вкотором процедура была определена. Мы детально рассмотрим, как это работает, в главе 3, когда будем подробно описывать окружения и работу интерпретатора.28 Внутренние определения должны быть в начале тела процедуры.
За последствия запуска программ, перемешивающих определения и их использование, администрация ответственности не несет.48Глава 1. Построение абстракций с помощью процедурэтого еще недостаточно, чтобы сказать, что мы умеем программировать. Положение, вкотором мы находимся, похоже на положение человека, выучившего шахматные правила,но ничего не знающего об основных дебютах, тактике и стратегии.
Подобно шахматистуновичку, мы пока ничего не знаем об основных схемах использования понятий в нашейобласти знаний. Нам недостает знаний о том, какие именно ходы следует делать (какиеименно процедуры имеет смысл определять), и не хватает опыта предсказания последствий сделанного хода (выполнения процедуры).Способность предвидеть последствия рассматриваемых действий необходима для того, чтобы стать квалифицированным программистом, — равно как и для любой другой синтетической, творческой деятельности.
Например, квалифицированному фотографу нужно при взгляде на сцену понимать, насколько темным каждый ее участок покажется после печати при разном выборе экспозиции и разных условиях обработки.Только после этого можно проводить обратные рассуждения и выбирать кадр, освещение, экспозицию и условия обработки так, чтобы получить желаемый результат.
Чтобыстать специалистами, нам надо научиться представлять процессы, генерируемые различными типами процедур. Только развив в себе такую способность, мы сможем научитьсянадежно строить программы, которые ведут себя так, как нам надо.Процедура представляет собой шаблон локальной эволюции (local evolution) вычислительного процесса. Она указывает, как следующая стадия процесса строится из предыдущей.
Нам хотелось бы уметь строить утверждения об общем, или глобальном (global)поведении процесса, локальная эволюция которого описана процедурой. В общем случаеэто сделать очень сложно, но по крайней мере мы можем попытаться описать некоторыетипичные схемы эволюции процессов.В этом разделе мы рассмотрим некоторые часто встречающиеся «формы» процессов,генерируемых простыми процедурами. Кроме того, мы рассмотрим, насколько сильноэти процессы расходуют такие важные вычислительные ресурсы, как время и память.Процедуры, которые мы будем рассматривать, весьма просты. Они будут играть такуюже роль, как простые схемы в фотографии: это скорее упрощенные прототипическиешаблоны, а не практические примеры сами по себе.1.2.1.
Линейные рекурсия и итерацияДля начала рассмотрим функцию факториал, определяемую уравнениемn! = n · (n − 1) · (n − 2) · · · 3 · 2 · 1Существует множество способов вычислять факториалы. Один из них состоит в том, чтобы заметить, что n! для любого положительного целого числа n равен n, умноженномуна (n − 1)!:n! = n · [(n − 1) · (n − 2) · · · 3 · 2 · 1] = n · (n − 1)!Таким образом, мы можем вычислить n!, вычислив сначала (n − 1)!, а затем умноживего на n. После того, как мы добавляем условие, что 1! равен 1, это наблюдение можнонепосредственно перевести в процедуру:1.2. Процедуры и порождаемые ими процессы49(factorial 6)(* 6 (factorial 5))(* 6 (* 5 (factorial 4)))(* 6 (* 5 (* 4 (factorial 3))))(* 6 (* 5 (* 4 (* 3 (factorial 2)))))(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))(* 6 (* 5 (* 4 (* 3 (* 2 1)))))(* 6 (* 5 (* 4 (* 3 2))))(* 6 (* 5 (* 4 6)))(* 6 (* 5 24))(* 6 120)720Рис.
1.3. Линейно рекурсивный процесс для вычисления 6!.(define (factorial n)(if (= n 1)1(* n (factorial (- n 1)))))Можно использовать подстановочную модель из раздела 1.1.5 и увидеть эту процедуру вдействии при вычислении 6!, как показано на рис. 1.3.Теперь рассмотрим вычисление факториала с другой точки зрения. Мы можем описать правило вычисления n!, сказав, что мы сначала умножаем 1 на 2, затем результатумножаем на 3, затем на 4, и так пока не достигнем n. Мы можем описать это вычисление, сказав, что счетчик и произведение с каждым шагом одновременно изменяютсясогласно правилупроизведение = счетчик · произведениесчетчик = счетчик + 1и добавив условие, что n! — это значение произведения в тот момент, когда счетчикстановится больше, чем n.Опять же, мы можем перестроить наше определение в процедуру вычисления факториала29 :29 В настоящей программе мы, скорее всего, спрятали бы определение fact-iter с помощью блочнойструктуры, введенной в предыдущем разделе:(define (factorial n)(define (iter product counter)(if (> counter n)product(iter (* counter product)(+ counter 1))))(iter 1 1))Здесь мы этого не сделали, чтобы как можно меньше думать о разных вещах одновременно.Глава 1.
Построение абстракций с помощью процедур50(factorial(fact-iter(fact-iter(fact iter(fact-iter(fact-iter(fact-iter(fact-iter7206)1 1 6)1 2 6)2 3 6)6 4 6)24 5 6)120 6 6)720 7 6)Рис. 1.4. Линейно итеративный процесс для вычисления 6!.(define (factorial n)(fact-iter 1 1 n))(define (fact-iter product counter max-count)(if (> counter max-count)product(fact-iter (* counter product)(+ counter 1)max-count)))Как и раньше, мы можем с помощью подстановочной модели изобразить процесс вычисления 6!, как показано на рис. 1.4.Сравним эти два процесса.
С одной стороны, они кажутся почти одинаковыми. Обаони вычисляют одну и ту же математическую функцию с одной и той же областьюопределения, и каждый из них для вычисления n! требует количества шагов, пропорционального n. Действительно, два этих процесса даже производят одну и ту же последовательность умножений и получают одну и ту же последовательность частичныхпроизведений. С другой стороны, когда мы рассмотрим «формы» этих двух процессов,мы увидим, что они ведут себя совершенно по-разномуВозьмем первый процесс. Подстановочная модель показывает сначала серию расширений, а затем сжатие, как показывает стрелка на рис. 1.3.
Расширение происходит помере того, как процесс строит цепочку отложенных операций (deferred operations), вданном случае цепочку умножений. Сжатие происходит тогда, когда выполняются этиотложенные операции. Такой тип процесса, который характеризуется цепочкой отложенных операций, называется рекурсивным процессом (recursive process). Выполнениеэтого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии.
При вычислении n! длина цепочки отложенных умножений, аследовательно, и объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. Такой процесс называетсялинейно рекурсивным процессом (linear recursive process).Напротив, второй процесс не растет и не сжимается.
На каждом шаге при любом значении n необходимо помнить лишь текущие значения переменных product, counter иmax-count. Такой процесс мы называем итеративным (iterative process).1.2. Процедуры и порождаемые ими процессы51В общем случае, итеративный процесс — это такой процесс, состояние которогоможно описать конечным числом переменных состояния (state variables) плюс заранеезаданное правило, определяющее, как эти переменные состояния изменяются от шага кшагу, и плюс (возможно) тест на завершение, который определяет условия, при которыхпроцесс должен закончить работу. При вычислении n! число шагов линейно растет сростом n.
Такой процесс называется линейно итеративным процессом (linear iterativeprocess).Можно посмотреть на различие этих двух процессов и с другой точки зрения. Витеративном случае в каждый момент переменные программы дают полное описаниесостояния процесса. Если мы остановим процесс между шагами, для продолжения вычислений нам будет достаточно дать интерпретатору значения трех переменных программы. С рекурсивным процессом это не так. В этом случае имеется дополнительная«спрятанная» информация, которую хранит интерпретатор и которая не содержится впеременных программы. Она указывает, «где находится» процесс в терминах цепочкиотложенных операций. Чем длиннее цепочка, тем больше информации нужно хранить30 .Противопоставляя итерацию и рекурсию, нужно вести себя осторожно и не смешивать понятие рекурсивного процесса с понятием рекурсивной процедуры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
