Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 72
Текст из файла (страница 72)
из Александрии, знаменит тем, что он дал первуюверную оценку длины окружности Земли, которую он вычислил, наблюдая тени, отбрасываемые в полденьлетнего солнцестояния. Метод решета Эратосфена, несмотря на свою древность, лежал в основе специальныхаппаратных устройств-«решет», которые до недавних пор были самыми мощными устройствами для поискапростых чисел. Однако начиная с 70-х годов такие устройства были вытеснены развитием вероятностныхметодик, обсуждаемых в разделе 1.2.6.61 Мы назвали этот способ изображения потоков в честь Питера Хендерсона, который первым показал намдиаграммы такого вида как способ рассуждений об обработке потоков. Сплошные линии представляют потокипередаваемых сигналов.
Прерывистая линия от car к cons и filter указывает, что здесь передается непоток, а единичное значение.3.5. Потоки309sievecarcdrconsfilter:notdivisible?sieveРис. 3.31. Решето для поиска простых чисел в виде системы обработки сигналов.первого элемента строится фильтр на делимость, и через него пропускается остатоквходного потока, а выход запускается в еще один элемент sieve. Затем исходный первый элемент сочетается при помощи cons с выходом внутреннего sieve, и получаетсявыходной поток. Таким образом, не только входной поток бесконечен, но и обработчиксигналов также бесконечен, поскольку одно решето содержит в себе другое.Неявное определение потоковПотоки integers и fibs были определены при помощи «порождающих» процедур,которые явным образом вычисляют элементы потока один за другим. Однако можноопределять потоки неявно, пользуясь задержанным вычислением.
Например, следующеевыражение определяет ones как бесконечный поток, состоящий из одних единиц:(define ones (cons-stream 1 ones))Это выражение работает примерно так же, как рекурсивная процедура: ones являетсяпарой, чей car есть 1, а cdr представляет собой обещание вычислить ones.
Обращениек cdr дает нам снова 1 и обещание вычислить ones, и так далее.Можно делать и более интересные вещи с помощью операций вроде addstreams,которая порождает поэлементную сумму двух данных потоков62 :(define (add-streams s1 s2)(stream-map + s1 s2))Теперь можно определить поток целых чисел следующим образом:(define integers (cons-stream 1 (add-streams ones integers)))Здесь integers определяются как поток, в котором первый элемент 1, а остаток равенсумме ones и integers.
Таким образом, второй элемент integers равен 1 плюспервый элемент integers, то есть 2; третий элемент равен 1 плюс второй элементintegers, то есть 3, и так далее. Это определение работает потому, что в любой моментсгенерировано достаточно элементов потока integers, чтобы мы могли обратиться кним в определении и породить следующий элемент.В том же стиле можно определить числа Фибоначчи:62 Здесьиспользуется обобщенная версия stream-map из упражнения 3.50.Глава 3. Модульность, объекты и состояние310(define fibs(cons-stream 0(cons-stream 1(add-streams (stream-cdr fibs)fibs))))Это определение говорит, что fibs есть поток, начинающийся с 0 и 1, такой, что остатокпотока порождается сложением fibs с собой самим, сдвинутым на одну позицию:011011213253851382113...
= (stream-cdr fibs)... = fibs12358132134... = fibsЕще одна полезная процедура для подобных определений потоков — scalestream.Она умножает каждый элемент потока на данную константу:(define (scale-stream stream factor)(stream-map (lambda (x) (* x factor)) stream))Например,(define double (cons-stream 1 (scale-stream double 2)))порождает поток степеней двойки: 1, 2, 4, 8, 16, 32 . . .Можно дать альтернативное определение потока простых чисел, начав с потока целыхчисел, и фильтруя его через проверку на простоту.
Вначале нам потребуется первоепростое число, 2:(define primes(cons-stream2(stream-filter prime? (integers-starting-from 3))))Это определение не столь тривиально, как кажется, поскольку мы будем проверятьчисло n на простоту,√проверяя, делится ли n на простые числа (а не на все целые),меньшие или равные n:(define (prime? n)(define (iter ps)(cond ((> (square (stream-car ps)) n) true)((divisible? n (stream-car ps)) false)(else (iter (stream-cdr ps)))))(iter primes))Это рекурсивное определение, поскольку primes определяются посредством предикатаprime?, а он сам использует поток primes.
Работает эта процедура потому, что влюбой момент имеется достаточно элементов потока primes для проверки на простотуследующего требуемого числа. А именно, при проверке n либо оказывается не простым(а в таком случае имеется уже сгенерированное простое число, на которое оно делится),3.5.
Потоки311либо оно простое (а в таком случае, имеется√ уже сгенерированное простое число — тоесть, простое число меньше n, — большее n63 .Упражнение 3.53.Не запуская программу, опишите элементы потока, порождаемого(define s (cons-stream 1 (add-streams s s)))Упражнение 3.54.Определите процедуру mul-streams, аналогичную add-streams, которая порождает поэлементное произведение двух входных потоков. С помощью нее и потока integers закончите следующееопределение потока, n-й элемент которого (начиная с 0) равен факториалу n + 1:(define factorials (cons-stream 1 (mul-streams h??i h??i)))Упражнение 3.55.Определите процедуру partial-sums, которая в качестве аргумента берет поток S, а возвращает поток, элементы которого равны S0 , S0 + S1 , S0 + S1 + S2 , .
. .. Например, (partial-sumsintegers) должно давать поток 1, 3, 6, 10, 15 . . .Упражнение 3.56.Существует знаменитая задача, впервые сформулированная Р. Хэммингом: породить в возрастающем порядке и без повторений все положительные целые числа, у которых нет других простыхделителей, кроме 2, 3 и 5. Очевидное решение состоит в том, чтобы перебирать все натуральныечисла по очереди и проверять, есть ли у них простые множители помимо 2, 3 и 5.
Однако этапроцедура весьма неэффективна, поскольку чем больше числа, тем меньшая их доля соответствуетусловию. Применим альтернативный подход: назовем искомый поток чисел S и обратим вниманиена следующие факты:••••S начинается с 1.Элементы (scale-streams 2) также принадлежат SТо же верно и для (scale-stream S 3) и (scale-stream S 5).Других элементов S нет.Теперь требуется только соединить элементы из этих источников. Для этого мы определяемпроцедуру merge, которая сливает два упорядоченных потока в один упорядоченный поток, убираяпри этом повторения:(define (merge s1 s2)(cond ((stream-null? s1) s2)((stream-null? s2) s1)(else(let ((s1car (stream-car s1))(s2car (stream-car s2)))63 Это тонкая деталь, которая основана на том, что p2n+1 ≤ pn (Здесь pk обозначает k-е простое число.) Такиеоценки достаточно трудно доказать.
Античное доказательство Евклида показывает, что имеется бесконечноеколичество простых чисел, и что pn+1 ≤ p1 p2 · · · pn + 1. Никакого существенно лучшего результата небыло найдено до 1851 года, когда русский математик П. Л. Чебышев доказал, что для всех n, pn+1 ≤ 2pn .Предположение, что это так, было высказано в 1845 году и известно как гипотеза Бертрана (Bertrand’shypothesis). Доказательство можно найти в разделе 22.3 в книге Hardy and Wright 1960.Глава 3.
Модульность, объекты и состояние312(cond ((< s1car s2car)(cons-stream s1car (merge (stream-cdr s1) s2)))((> s1car s2car)(cons-stream s2car (merge s1 (stream-cdr s2))))(else(cons-stream s1car(merge (stream-cdr s1)(stream-cdr s2)))))))))Тогда требуемый поток можно получить с помощью merge таким образом:(define S (cons-stream 1 (merge h??i h??i)))Заполните пропуски в местах, обозначенных знаком h??i.Упражнение 3.57.Сколько сложений происходит при вычислении n-го числа Фибоначчи, в случае, когда мы используем определение f ibs через процедуру add-streams? Покажите, что число сложений вырослобы экспоненциально, если бы мы реализовали (delay hвыражениеi) просто как (lambda ()hвыражениеi), без оптимизации через процедуру memo-proc из раздела 3.5.164 .Упражнение 3.58.Дайте интерпретацию потоку, порождаемому следующей процедурой:(define (expand num den radix)(cons-stream(quotient (* num radix) den)(expand (remainder (* num radix) den) den radix)))(Элементарная процедура quotient возвращает целую часть частного двух целых чисел.) Каковы последовательные элементы потока, порожденного выражением (expand 1 7 10)? Что даетвычисление (expand 3 8 10)?Упражнение 3.59.В разделе 2.5.3 мы увидели, как реализовать систему арифметики многочленов, используя представление многочленов в виде списка термов.
Подобным же образом можно работать со степенными рядами (power series), напримерex = 1 + x +cos x = 1 −sin x = x −x2x3x4+++ ··· ,23·24·3·2x4x2+− ··· ,24·3·2x3x5+− ··· ,3·25·4·3·2представленными в виде бесконечных потоков. Будем представлять последовательность a0 + a1 x +a2 x2 + a3 x3 + · · · как поток, элементами которого являются коэффициенты a0 , a1 , a2 , a3 . .
.64 Это упражнение показывает, как близко связан вызов по необходимости с обычной мемоизацией, описанной в упражнении 3.27. В этом упражнении мы при помощи присваивания явным образом создавали локальную таблицу. Наша оптимизация с вызовом по необходимости, в сущности, автоматически создает такую жетаблицу, сохраняя значения в уже размороженных частях потока.3.5.
Потоки313а. Интеграл последовательности a0 + a1 x + a2 x2 + a3 x3 + · · · есть последовательностьc + a0 x +111a1 x2 + a2 x3 + a3 x4 + · · ·234где c — произвольная константа. Определите процедуру integrate-series, которая навходе принимает поток a0 , a1 , a2 , . . ., представляющую степенной ряд, и возвращает поток11a0 , a1 , a2 , . . . коэффициентов при неконстантных членах интеграла последовательности. (По23скольку в результате отсутствует постоянный член, он не представляет собой степенной ряд; прииспользовании integrate-series мы через cons будем присоединять к началу соответствующую константу.)б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
