где c - произвольная константа. Определите процедуру integrate-series, которая на входе принимает поток a0,ai,a2,..представляющую степенной ряд, и возвращает

поток ао, -ai, -02,... коэффициентов при неконстантных членах интеграла последовательности. (Поскольку в результате отсутствует постоянный член, он не представляет собой степенной ряд; при использовании integrate-series мы через cons будем присоединять к началу соответствующую константу.)

b. Функция x н-► ex равна своей собственной производной. Отсюда следует, что ex и интеграл ex суть одна и та же последовательность, с точностью до постоянного члена, который равен e0 = 1. Соответственно, можно породить последовательность для ex

(define exp-series

(cons-stream 1 (integrate-series exp-series)))

Покажите, как породить последовательности для синуса и косинуса, опираясь на то, что производная синуса равна косинусу, а производная косинуса равна минус синусу:

(define cosine-stream (cons-stream 1 (??)))

(define sine-series (cons-stream 0 (??)))

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

Если степенной ряд представляется в виде потока своих коэффициентов, как в упражнении 3.59, то сумма последовательностей реализуется посредством add-streams. Завершите определение следующей процедуры для перемножения последовательностей:

(define (mul-series s1 s2)

(cons-stream (??) (add-streams (??) (??))))

Можете проверить свою процедуру, убедившись, что sin2 x + cos2 x = 1 с помощью последовательностей из упражнения 3.59.

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

Пусть S будет степенным рядом (упражнение 3.59 с постоянным членом 1. Предположим, что мы хотим найти степенной ряд 1/S, то есть такой ряд X, что S • X = 1. Запишем S = 1 + Sr, где SR - часть S после постоянного члена. Тогда мы можем решить уравнение для X так:

Другими словами, X есть степенной ряд с постоянным членом 1, чьи члены с более высокими степенями определяются как минус произведение SR и X. Воспользовавшись этим, напишите процедуру invert-unit-series, которая вычисляет 1/S для степенного ряда S с постоянным членом 1. Вам потребуется mul-series из упражнения 3.60.

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

При помощи результатов упражнений 3.60 и 3.61 определите процедуру div-series, которая делит один степенной ряд на другой. Div-series должна работать для любых двух рядов, при условии, что ряд в знаменателе начинается с ненулевого постоянного члена. (Если в знаменателе постоянный член равен нулю, div-series должна сообщать об ошибке.) Покажите, как при помощи div-series и результата упражнения 3.59 получить степенной ряд для тангенса.

через

S

(1 + Sr) X + Sr

X X X X

1 1 1

1 - Sr • X

3.5.3 Использование парадигмы потоков

Потоки с задержкой вычисления могут служить мощным инструментом моделирования. Они дают многие из преимуществ, обычно предоставляемых внутренним состоянием и присваиванием. Более того, они избегают некоторых из теоретических неудобств, связанных с введением присваивания в язык программирования.

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

Итерация как потоковый процесс

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

(define (sqrt-improve guess x) (average guess (/ x guess)))

В исходной процедуре sqrt эти гипотезы были последовательными значениями переменной состояния. Вместо этого можно породить бесконечный поток гипотез, в голове которого стоит начальная гипотеза 1: 65

(define (sqrt-stream x) (define guesses (cons-stream 1.0

(stream-map (lambda (guess)

(sqrt-improve guess x)) guesses)))

guesses)

(display-stream (sqrt-stream 2)) 1

1.5

1.4166666666666665 1.4142156862745097 1.4142135623746899

Можно порождать все больше элементов потока, получая все лучшие приближения. Если нужно, можно написать процедуру, которая бы порождала гипо-

65Внутреннюю переменную guesses нельзя связать с помощью let, поскольку значение guesses зависит от нее самой. В упражнении 3.63 рассматривается вопрос, зачем здесь нужна внутренняя переменная.

тезы до тех пор, пока ответ не окажется достаточно хорош. (См. упражнение 3.64.)

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

п111

4=1-3 + 5-7+-Сначала мы порождаем поток элементов ряда (числа, обратные нечетным натуральным, с чередующимся знаком). Затем мы берем поток сумм все большего количества элементов (при помощи процедуры partial-sums из упражнения 3.55) и домножаем результат на 4:

(define (pi-summands n) (cons-stream (/ 1.0 n)

(stream-map - (pi-summands (+ n 2)))))

(define pi-stream

(scale-stream (partial-sums (pi-summands 1)) 4))

(display-stream pi-stream) 4.

2.666666666666667

3.466666666666667

2.8952380952380956

3.3396825396825403

2.9760461760461765

3.2837384837384844

3.017071817071818

Получается поток все более точных приближений к п, но сходятся эти приближения довольно медленно. Восемь членов последовательности поместили п между 3.284 и 3.017.

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

Один такой ускоритель, открытый швейцарским математиком восемнадцатого века Леонардом Эйлером, хорошо работает с последовательностями частичных сумм знакочередующихся рядов (рядов, знаки элементов которых чередуются). По методу Эйлера, если Sn есть n-й член исходного ряда, то ускоренная последовательность имеет элементы

g ($п+1 - Sn)2

Sn-1 - 2Sn + Sn+1

Таким образом, если исходная последовательность представлена как поток значений, преобразованная последовательность дается процедурой

(define (euler-transform s)

(let ((s0 (stream-ref s 0)) ; Sn-i