Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 73
Текст из файла (страница 73)
Функция x 7→ ex равна своей собственной производной. Отсюда следует, что ex и интеграл exсуть одна и та же последовательность, с точностью до постоянного члена, который равен e0 = 1.Соответственно, можно породить последовательность для ex через(define exp-series(cons-stream 1 (integrate-series exp-series)))Покажите, как породить последовательности для синуса и косинуса, опираясь на то, что производная синуса равна косинусу, а производная косинуса равна минус синусу:(define cosine-stream(cons-stream 1 h??i))(define sine-series(cons-stream 0 h??i))Упражнение 3.60.Если степенной ряд представляется в виде потока своих коэффициентов, как в упражнении 3.59,то сумма последовательностей реализуется посредством add-streams. Завершите определениеследующей процедуры для перемножения последовательностей:(define (mul-series s1 s2)(cons-stream h??i (add-streams h??i h??i)))Можете проверить свою процедуру, убедившись, что 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 так:S·X(1 + SR ) · XX + SR · XX====1111 − SR · XДругими словами, X есть степенной ряд с постоянным членом 1, чьи члены с более высокимистепенями определяются как минус произведение SR и X. Воспользовавшись этим, напишитепроцедуру invert-unit-series, которая вычисляет 1/S для степенного ряда S с постояннымчленом 1.
Вам потребуется mul-series из упражнения 3.60.314Глава 3. Модульность, объекты и состояниеУпражнение 3.62.При помощи результатов упражнений 3.60 и 3.61 определите процедуру div-series, котораяделит один степенной ряд на другой. Div-series должна работать для любых двух рядов, приусловии, что ряд в знаменателе начинается с ненулевого постоянного члена.
(Если в знаменателепостоянный член равен нулю, div-series должна сообщать об ошибке.) Покажите, как припомощи div-series и результата упражнения 3.59 получить степенной ряд для тангенса.3.5.3. Использование парадигмы потоковПотоки с задержкой вычисления могут служить мощным инструментом моделирования. Они дают многие из преимуществ, обычно предоставляемых внутренним состоянием и присваиванием. Более того, они избегают некоторых из теоретических неудобств,связанных с введением присваивания в язык программирования.Потоковый метод может изменять взгляд на вещи, так как он позволяет строитьсистемы с другими границами модулей, не такими, как в системах, основанных на присваивании переменным состояния. Например, можно сосредоточивать внимание на всейвременной последовательности (или сигнале), а не на значении переменных состояния вотдельные моменты.
Оказывается удобно сочетать и сравнивать параметры состояния вразличные моменты времени.Итерация как потоковый процессВ разделе 1.2.1 мы ввели понятие итеративного процесса, по мере исполнения изменяющего переменные состояния. Теперь мы узнали, что можно представлять состояниев виде «вневременного» потока значений, а не набора обновляемых переменных. Давайте примем этот взгляд и заново рассмотрим процедуру поиска квадратного корня израздела 1.1.7. Напомним, что идея процедуры состояла в том, чтобы порождать последовательность все лучших и лучших приближений к квадратному корню x, снова и сноваприменяя процедуру улучшения гипотезы:(define (sqrt-improve guess x)(average guess (/ x guess)))В исходной процедуре sqrt эти гипотезы были последовательными значениями переменной состояния.
Вместо этого можно породить бесконечный поток гипотез, в головекоторого стоит начальная гипотеза 165 :(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))65 Внутреннюю переменную guesses нельзя связать с помощью let, поскольку значение guesses зависитот нее самой.
В упражнении 3.63 рассматривается вопрос, зачем здесь нужна внутренняя переменная.3.5. Потоки31511.51.41666666666666651.41421568627450971.4142135623746899...Можно порождать все больше элементов потока, получая все лучшие приближения.Если нужно, можно написать процедуру, которая бы порождала гипотезы до тех пор,пока ответ не окажется достаточно хорош. (См. упражнение 3.64.)Еще один итеративный процесс, который можно рассматривать подобным образом —аппроксимация числа π, основанная на знакочередующемся ряде, упомянутом в разделе 1.3.1:1 1 1π= 1 − + − + ···43 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.6666666666666673.4666666666666672.89523809523809563.33968253968254032.97604617604617653.28373848373848443.017071817071818...Получается поток все более точных приближений к π, но сходятся эти приближениядовольно медленно. Восемь членов последовательности поместили π между 3.284 и 3.017.Пока что подход с потоком состояний не слишком отличается от потока с переменными состояния. Однако потоки дают нам возможность проделывать некоторые интересныетрюки.
Например, поток можно преобразовать с помощью ускорителя последовательности (sequence accelerator), преобразующего последовательность приближений в новуюпоследовательность, которая сходится к тому же значению, что и исходная, но быстрее.Один такой ускоритель, открытый швейцарским математиком восемнадцатого векаЛеонардом Эйлером, хорошо работает с последовательностями частичных сумм знакочередующихся рядов (рядов, знаки элементов которых чередуются). По методу Эйлера,Глава 3. Модульность, объекты и состояние316если Sn есть n-й член исходного ряда, то ускоренная последовательность имеет элементыSn+1 −(Sn+1 − Sn )2Sn−1 − 2Sn + Sn+1Таким образом, если исходная последовательность представлена как поток значений,преобразованная последовательность дается процедурой(define (euler-transform s)(let ((s0 (stream-ref s 0)); Sn−1(s1 (stream-ref s 1)); Sn(s2 (stream-ref s 2))); Sn+1(cons-stream (- s2 (/ (square (- s2 s1))(+ s0 (* -2 s1) s2)))(euler-transform (stream-cdr s)))))Можно продемонстрировать ускорение Эйлера на нашей последовательности приближений к π:(display-stream (euler-transform pi-stream))3.1666666666666673.13333333333333373.14523809523809563.139682539682543.14271284271284353.14088134088134163.1420718170718183.1412548236077655...Более того, можно ускорить ускоренную последовательность, рекурсивно ускоритьрезультат, и так далее.
То есть, можно создать поток потоков (структуру, которую мыбудем называть табло (tableau)), в котором каждый поток есть результат преобразованияпредыдущего:(define (make-tableau transform s)(cons-stream s(make-tableau transform(transform s))))Табло имеет видs00s01s10s02s11s20s03s12s21s04s13s22............Наконец, можно построить последовательность, членами которой будут первые элементыкаждой строки табло:(define (accelerated-sequence transform s)(stream-map stream-car(make-tableau transform s)))3.5.
Потоки317Можно показать, как работает такое «сверхускорение» на последовательности приближений к π:(display-stream (accelerated-sequence euler-transformpi-stream))4.3.1666666666666673.1421052631578953.1415993573190053.14159271403377853.14159265397529273.14159265359117653.141592653589778...Результат впечатляет. Восемь членов последовательности дают нам верное значение πс точностью до 14 десятичных знаков. Если бы у нас была только исходная последовательность приближений к π, то пришлось бы вычислить порядка 1013 ее элементов (тоесть довести последовательность до такого места, где ее элементы становятся меньше10−13 ), чтобы добиться такой точности!Все эти методы ускорения можно было бы реализовать и без помощи потоков.
Однакоформулировка в терминах потоков обладает особым удобством и изяществом, посколькумы имеем доступ ко всей последовательности состояний в виде структуры данных, скоторой можно работать при помощи единого набора операций.Упражнение 3.63.Хьюго Дум спрашивает, почему нельзя было написать sqrt-stream более простым способом,без внутренней переменной guesses:(define (sqrt-stream x)(cons-stream 1.0(stream-map (lambda (guess)(sqrt-improve guess x))(sqrt-stream x))))Лиза П. Хакер отвечает, что эта версия процедуры значительно менее эффективна, посколькупроизводит избыточные вычисления.
Объясните Лизин ответ. Сохранилось бы отличие в эффективности, если бы реализация delay использовала только (lambda () hвыражениеi), без оптимизации через memo-proc (см. раздел 3.5.1)?Упражнение 3.64.Напишите процедуру stream-limit, которая в качестве аргумента принимает поток и число(погрешность). Она должна просматривать поток, пока не найдется два элемента подряд, различающихся меньше, чем на погрешность, и возвращать второй из этих элементов. При помощи этойпроцедуры можно будет вычислять квадратные корни с заданной точностью так:(define (sqrt x tolerance)(stream-limit (sqrt-stream x) tolerance))Глава 3.
Модульность, объекты и состояние318Упражнение 3.65.С помощью ряда111+ − + ···234породите три последовательности приближений к натуральному логарифму 2, так же, как мы вышесделали это для π. Как быстро сходятся эти последовательности?ln 2 = 1 −Бесконечные потоки парВ разделе 2.2.3 мы видели, как парадигма работы с последовательностями рассматривает вложенные циклы традиционной парадигмы в виде процессов, определенных напоследовательности пар. Если мы обобщим этот метод на бесконечные потоки, то сможем писать программы, которые трудно воспроизвести с помощью обычных циклов,поскольку «цикл» охватывает бесконечное множество.Например, пусть нам хочется обобщить процедуру sum-of-primes из раздела 2.2.3так, чтобы получился поток из всех пар натуральных чисел (i, j), таких, что i ≤ j и i + jпростое. Если int-pairs есть последовательность всех пар натуральных чисел (i, j),где i ≤ j, то необходимый нам поток таков66 :(stream-filter (lambda (pair)(prime? (+ (car pair) (cadr pair))))int-pairs)Задача, следовательно, состоит в том, чтобы породить поток int-pairs.
В болееобщем случае допустим, что у нас есть два потока S = (Si ) и T = (Tj ), и представимсебе бесконечную матрицу(S0 , T0 ) (S0 , T1 ) (S0 , T2 )(S1 , T0 ) (S1 , T1 ) (S1 , T2 )(S2 , T0 ) (S2 , T1 ) (S2 , T2 )............Нам хочется породить поток, который содержит все пары из этой матрицы, лежащие надиагонали или выше, а именно пары(S0 , T0 ) (S0 , T1 ) (S0 , T2 )(S1 , T1 ) (S1 , T2 )(S2 , T2 )............(Если мы возьмем и S, и T равными потоку натуральных чисел, то получим как разнеобходимый нам поток int-pairs.)Назовем общий поток пар (pairs S T), и будем считать, что он состоит из трехчастей: пары (S0 , T0 ), остатка пар в первом ряду, и всех остальных пар67 :(S0 , T0 ) (S0 , T1 ) (S0 , T2 )(S1 , T1 ) (S1 , T2 )(S2 , T2 )66 Как67 В............и в разделе 2.2.3, мы представляем пару натуральных чисел в виде списка, а не лисповской пары.упражнении 3.68 объясняется, почему мы выбрали именно такую декомпозицию.3.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
