(define ((имя) a b)

(if (> a b) 0

(+ ((терм) a)

((имя) ((следующий) a) b))))

Присутствие такого общего шаблона является веским доводом в пользу того, что здесь скрыта полезная абстракция, которую только надо вытащить на поверхность. Действительно, математики давно выделили абстракцию суммирования последовательности (summation of a series) и изобрели «сигма-запись», например

b

£f (n) = f (а) + ... + f (b)

n=a

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

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

(define (sum term a next b)

(if (> a b) 0

(+ (term a)

(sum term (next a) next b))))

Заметьте, что sum принимает в качестве аргументов как нижнюю и верхнюю границы a и b, так и процедуры term и next. Sum можно использовать так, как мы использовали бы любую другую процедуру. Например, с ее помощью (вместе с процедурой inc, которая увеличивает свой аргумент на 1), мы можем определить sum-cubes:

(define (inc n) (+ n 1))

(define (sum-cubes a b) (sum cube a inc b))

Воспользовавшись этим определением, мы можем вычислить сумму кубов чисел от 1 до 10:

(sum-cubes 1 10) 3025

С помощью процедуры идентичности (которая просто возвращает свой аргумент) для вычисления терма, мы можем определить sum-integers через sum:

(define (identity x) x)

(define (sum-integers a b) (sum identity a inc b))

Теперь можно сложить целые числа от 1 до 10:

(sum-integers 1 10) 55

Таким же образом определяется pi-sum: 50

(define (pi-sum a b) (define (pi-term x)

(/ 1.0 (* x (+ x 2))))

(define (pi-next x)

(+ x 4))

(sum pi-term a pi-next b)) С помощью этих процедур мы можем вычислить приближение к п:

(* 8 (pi-sum 1 1000)) 3.139592655589783

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

Ja f = f (а + y) + f [a + dx + y) + / + 2dx + y) + dx

для малых значений dx. Мы можем прямо выразить это в виде процедуры:

(define (integral f a b dx) (define (add-dx x) (+ x dx)) (* (sum f (+ a (/ dx 2)) add-dx b)

dx))

(integral cube 0 1 0.01)

.24998750000000042

(integral cube 0 1 0.001)

.249999875000001

(Точное значение интеграла cube от 0 до 1 равно 1/4.)

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

Правило Симпсона - более точный метод численного интегрирования, чем представленный выше. С помощью правила Симпсона интеграл функции f между а и b приближенно вычисляется в виде

50Обратите внимание, что мы использовали блочную структуру (раздел 1.1.8), чтобы спрятать определения pi-next и pi-term внутри pi-sum, поскольку вряд ли эти процедуры понадобятся зачем-либо еще. В разделе 1.3.2 мы совсем от них избавимся.

g [уо + Ц)\ + 2у2 + 4у3+2у4 + ...+ 2уп-2 + 4j/„ i + уп]

где h = (b - а)/п, для какого-то четного целого числа п, а yk = f (а+kh). (Увеличение п повышает точность приближенного вычисления.) Определите процедуру, которая принимает в качестве аргументов f, а, b и п, и возвращает значение интеграла, вычисленное по правилу Симпсона. С помощью этой процедуры проинтегрируйте cube между 0 и 1 (с п = 100 и п = 1000) и сравните результаты с процедурой integral, приведенной выше.

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

Процедура sum порождает линейную рекурсию. Ее можно переписать так, чтобы суммирование выполнялось итеративно. Покажите, как сделать это, заполнив пропущенные выражения в следующем определении:

(define (sum term a next b) (define (iter a result) (if (??) (??)

(iter (??) (??))))

(iter (??) (??)))

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

a.Процедура sum - всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков.51 Напишите аналогичную процедуру под названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить factorial. Кроме того, при помощи product вычислите приближенное значение п по формуле52

7г 2 • 4 • 4 • 6 • 6 • 8 • • • 4 ~ 3-3-5-5-7-7---

b.Если Ваша процедура product порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.

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

a. Покажите, что sum и product (упражнение 1.31) являются частными случаями еще более общего понятия, называемого накопление (accumulation), которое комбинирует множество термов с помощью некоторой общей функции накопления

(accumulate combiner null-value term a next b)

51 Смысл упражнений 1.31-1.33 состоит в том, чтобы продемонстрировать выразительную мощь, получаемую, когда с помощью подходящей абстракции обобщается множество операций, казалось бы, не связанных между собой. Однако, хотя накопление и фильтрация - изящные приемы, при их использовании руки у нас пока что несколько связаны, поскольку пока что у нас нет структур данных, которые дают подходящие к этим абстракциям средства комбинирования. В разделе 2.2.3 мы вернемся к этим приемам и покажем, как использовать последовательности (sequences) в качестве интерфейсов для комбинирования фильтров и накопителей, так что получаются еще более мощные абстракции. Мы увидим, как эти методы сами по себе становятся мощным и изящным подходом к проектированию программ.

52Эту формулу открыл английский математик семнадцатого века Джон Уоллис.