становится особенно тяжелой при построении больших систем, которые пишут много различных программистов. Например, при построении большой библиотеки численных процедур многие числовые функции вычисляются как последовательные приближения и могут потому иметь в качестве вспомогательных процедуры good-enough? и improve. Нам хотелось бы локализовать под-процедуры, спрятав их внутри sqrt, так, чтобы sqrt могла сосуществовать с другими последовательными приближениями, при том что у каждой из них была бы своя собственная процедура good-enough?. Чтобы сделать это возможным, мы разрешаем процедуре иметь внутренние определения, локальные для этой процедуры. Например, при решении задачи вычисления квадратного корня мы можем написать

(define (sqrt x)

(define (good-enough? guess x)

(< (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))

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

Мы будем часто использовать блочную структуру, чтобы разбивать большие программы на куски разумного размера.28 Идея блочной структуры происходит из языка программирования Алгол 60. Она присутствует в большинстве современных языков программирования. Это важный инструмент, который помогает организовать построение больших программ.

1.2 Процедуры и порождаемые ими процессы

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

процедуры).

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

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

В этом разделе мы рассмотрим некоторые часто встречающиеся «формы» процессов, генерируемых простыми процедурами. Кроме того, мы рассмотрим, насколько сильно эти процессы расходуют такие важные вычислительные ресурсы, как время и память. Процедуры, которые мы будем рассматривать, весьма просты. Они будут играть такую же роль, как простые схемы в фотографии: это скорее упрощенные прототипические шаблоны, а не практические примеры сами по себе.

28 Внутренние определения должны находиться в начале тела процедуры. За последствия запуска программ, перемешивающих определения и их использование, администрация ответственности не несет.

(factorial 6)

(* (* (* (*

(* (* (* (* (* (*

720

(factorial 5))

(* (* (* (* (* (* (* (*

120)

(factorial 4)))

(* (* (* (* (* (*

24))

(factorial 3))))

(* 3

(* 3 (* 3 (* 3 6)))

(factorial 2))))) (* 2 (factorial 1)))))) (* 2 1))))) 2))))

Рис. 1.3: Линейно рекурсивный процесс для вычисления 6!.

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, это наблюдение можно непосредственно перевести в процедуру:

(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.