Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 74
Текст из файла (страница 74)
Потоки319Заметим, что третья часть этой декомпозиции (пары, не лежащие в первом ряду) сутьпары, получаемые (рекурсивно) из (stream-cdr S) и (stream-cdr T). Заметимтакже, что вторая часть (остаток первого ряда) есть(stream-map (lambda (x) (list (stream-car s) x))(stream-cdr t))Таким образом, мы можем сформировать наш поток пар так:(define (pairs s t)(cons-stream(list (stream-car s) (stream-car t))(hкак-нибудь смешатьi(stream-map (lambda (x) (list (stream-car s) x))(stream-cdr t))(pairs (stream-cdr s) (stream-cdr t)))))Чтобы закончить определение процедуры, нужно выбрать какой-нибудь способ смешать два внутренних потока. В голову приходит воспользоваться потоковым аналогомпроцедуры append из раздела 2.2.1:(define (stream-append s1 s2)(if (stream-null? s1)s2(cons-stream (stream-car s1)(stream-append (stream-cdr s1) s2))))Однако эта идея не срабатывает с бесконечными потоками, поскольку, прежде чем перейти ко второму потоку, нужно пройти весь первый поток до конца.
В частности, еслимы попробуем породить все пары натуральных чисел при помощи(pairs integers integers)то получившийся поток сначала попытается перечислить все пары, где первый элементравен 1, а следовательно, никогда не породит ни одной пары с другим значением первогочлена.Для работы с бесконечными потоками требуется придумать способ смешения, который гарантировал бы, что каждый элемент будет достигнут, если программе дать достаточно времени. Изящный способ добиться этого состоит в том, чтобы воспользоватьсяследующей процедурой interleave68 :(define (interleave s1 s2)(if (stream-null? s1)s2(cons-stream (stream-car s1)(interleave s2 (stream-cdr s1)))))68 Точная формулировка требования, которому должен удовлетворять порядок слияния, выглядит так: должнасуществовать функция от двух аргументов f , такая, что пара, соответствующая i-му элементу первого потокаи j-му элементу второго, появится в качестве элемента выходного потока под номером f (i, j).
Трюк с чередованием через interleave нам показал Дэвид Тёрнер, который использовал его в языке KRC (Turner 1981).320Глава 3. Модульность, объекты и состояниеПоскольку interleave чередует элементы из двух потоков, всякий элемент второгопотока рано или поздно попадет в смешанный поток, даже если первый поток бесконечен.Таким образом, мы можем породить требуемый поток пар так:(define (pairs s t)(cons-stream(list (stream-car s) (stream-car t))(interleave(stream-map (lambda (x) (list (stream-car s) x))(stream-cdr t))(pairs (stream-cdr s) (stream-cdr t)))))Упражнение 3.66.Рассмотрим поток (pairs integers integers) Можете ли Вы что-то сказать о порядке, вкотором пары попадают в поток? Например, сколько приблизительно пар предшествуют паре (1,100)? Паре (99, 100)? (100, 100)? (Если Вы способны предоставить точные математические утверждения, — прекрасно. Однако если Вы увязаете в деталях, достаточно качественных оценок.)Упражнение 3.67.Измените процедуру так, чтобы (pairs integers integers) порождало поток из всех парнатуральных чисел (i, j), без дополнительного условия i ≤ j.
Подсказка: потребуется примешатьеще один поток.Упражнение 3.68.Хьюго Дум считает, что построение потока пар из трех частей — процедура слишком сложная.Он предлагает вместо того, чтобы отделять пару (S0 , T0 ), работать с первой строкой целиком:(define (pairs s t)(interleave(stream-map (lambda (x) (list (stream-car s) x))t)(pairs (stream-cdr s) (stream-cdr t))))Будет ли такой код работать? Посмотрите, что произойдет, если мы попытаемся вычислить (pairsintegers integers), используя определение Хьюго.Упражнение 3.69.Напишите процедуру triples, которая берет три бесконечных потока S, T и U , и порождает поток троек (Si , Tj , Uk ), таких, что i ≤ j ≤ k.
С помощью triples породите поток всехПифагоровых троек натуральных чисел, т. е. таких троек (i, j, k), что i ≤ j и i2 + j 2 = k2Упражнение 3.70.Интересно было бы уметь порождать потоки в каком-либо полезном порядке, а не в порядке,задаваемом к случаю придуманным процессом чередования. Можно воспользоваться методом, подобным процедуре merge из упражнения 3.56, если мы определим способ сказать, что одна парацелых чисел «меньше» другой. Один из способов состоит в том, чтобы определить «функциювзвешивания» W (i, j) и постановить, что (i1 , j1 ) меньше, чем (i2 , j2 ), если W (i1 , j1 ) ≤ W (i2 , j2 ).Напишите процедуру merge-weighted, которая во всем подобна merge, но только в качестве3.5.
Потоки321initial-valueinputscale: dtaddconsРис. 3.32. Процедура integral в виде системы преобразования сигналовдополнительного аргумента принимает процедуру weight, которая вычисляет вес пары, и используется для определения порядка, в котором элементы должны появляться в получающемсясмешанном потоке69 . При помощи merge-weighted напишите процедуру weighted-pairs,обобщающую pairs. Она должна принимать два потока и процедуру, вычисляющую функциювзвешивания, и порождать поток пар, упорядоченных по весу.
Породите, используя эту процедуру:а. Поток всех пар натуральных чисел (i, j) где i ≤ j, упорядоченных по сумме i + j.б. поток всех пар натуральных чисел (i, j), где i ≤ j, ни i, ни j не делится ни на 2, ни на 3, нина 5, и пары упорядочены по значению суммы 2i + 3j + 5ij.Упражнение 3.71.Числа, которые можно выразить в виде суммы двух кубов более, чем одним способом, иногданазывают числами Рамануджана (Ramanujan numbers), в честь математика Шринивасы Рамануджана70 . Упорядоченные потоки пар предлагают изящное решение для задачи порождения такихчисел.
Чтобы найти число, которое можно двумя разными способами записать в виде суммы двухкубов, требуется только породить поток пар натуральных чисел (i, j), взвешенных согласно сумме i3 + j 3 (см. упражнение 3.70), и искать в этом потоке две пары подряд с одинаковым весом.Напишите процедуру для порождения чисел Рамануджана. Первое такое число 1729. Каковы следующие пять?Упражнение 3.72.Используя метод, подобный описанному в упражнении 3.71, породите поток всех чисел, которыеможно записать как сумму двух квадратов тремя различными способами (и покажите, каковы этиспособы).Потоки как сигналыМы начали обсуждение потоков с того, что описали их как вычислительные аналоги«сигналов» в системах обработки сигналов.
На самом деле с помощью потоков такие69 Мы будем требовать от функции взвешивания, чтобы вес пары возрастал при движении вправо по строкеили вниз по столбцу в матрице пар.70 Цитата из некролога на смерть Рамануджана, написанного Г. Х. Харди (Hardy 1921): «Кажется, это мистерЛитлвуд заметил, что «каждое натуральное число было ему другом». Я помню, как однажды навестил его,когда он лежал больной в Путни.
Я приехал в такси номер 1729, сказал, что число показалось мне скучным, ивыразил надежду, что это не было несчастливым знаком. «Нет, — ответил он, — это очень интересное число;это наименьшее число, которое можно двумя различными способами выразить как сумму двух кубов». Трюкс использованием взвешенных пар для порождения чисел Рамануджана нам показал Чарльз Лейзерсон.Глава 3. Модульность, объекты и состояние322v+iR-Cv = v0 + 1/CR10idt + Riscale:Riaddscale:1/Cvintegralv0Рис. 3.33. RC-цепь и связанная с ней диаграмма потока сигналов.системы можно моделировать самым непосредственным образом, представляя значениясигнала в последовательные моменты времени как последовательные элементы потока.Например, можно реализовать интегратор (integrator), или сумматор (summer), который, для входного потока x = (xi ), начального значения C и малого приращения времениdt, собирает суммуiXxj dtSi = C +j=1и возвращает поток значений S = (Si ).
Следующая процедура integral напоминает«неявное» определение потока целых (раздел 3.5.2):(define (integral integrand initial-value dt)(define int(cons-stream initial-value(add-streams (scale-stream integrand dt)int)))int)На рисунке 3.32 показана система преобразования сигналов, соответствующая процедуреintegral. Входной поток делится на отрезки dt и пропускается через сумматор, а выводсумматора опять направляется на его вход.
Ссылка на самого себя в определении intотражена на диаграмме в виде цикла обратной связи, соединяющего выход сумматора содним из его входов.Упражнение 3.73.Можно моделировать электрические цепи с помощью потоков, представляющих значения тока илинапряжения в определенные моменты времени. Допустим, например, что у нас имеется цепь RC3.5. Потоки323(RC circuit), состоящая из резистора с сопротивлением R и конденсатора емкостью C, соединенных последовательно. Значение напряжения v в зависимости от заданного тока i определяетсяформулой, показанной на рис.
3.33. Структура формулы показана на прилагаемой диаграмме потока сигналов.Напишите процедуру RC, моделирующую эту цепь. На входе RC должна получать значенияR, C и dt, и выдавать процедуру, которая принимает на входе поток значений тока i и начальное значение напряжения v0 , а на выходе выдает поток значений напряжения v. Например, уВас должна быть возможность смоделировать при помощи RC RC-цепь с R = 5 ом, C = 1 фараде, и временным шагом в 0,5 секунды, вычислив (define RC1 (RC 5 1 0.5)).
Здесь RC1определяется как процедура, которая принимает на входе поток, представляющий временную последовательность токов, и исходное напряжение на конденсаторе, а на выходе дает временнойпоток напряжений.Упражнение 3.74.Лиза П. Хакер разрабатывает систему для обработки сигналов, приходящих от физических сенсоров. Один из важных инструментов, который она хочет построить, — это сигнал, описывающийпереходы входного сигнала через ноль (zero crossings). Выходной сигнал должен равняться +1,когда сигнал на входе меняется с отрицательного на положительный, -1, когда сигнал меняется сположительного на отрицательный, и 0 в остальных случаях. (Допустим, что знак нулевого входаположителен).
Например, типичный входной сигнал и связанный с ним сигнал перехода через нольмогут выглядеть так:. . .1 2 1.5 1 0.5 −0.1−2 −3 −2 −0.5 0.2 3 4 . . .... 0 00 00−100001 0 0. . .В Лизиной системе сигнал от сенсора представляется как поток sense-data, а zerocrossings представляет соответствующий поток пересечений нуля. Для начала Лиза пишетпроцедуру sign-change-detector, которая берет два значения в качестве аргументов и, сравнив их знаки, выдает 0, 1 или -1. Затем она строит поток переходов через ноль следующимобразом:(define (make-zero-crossings input-stream last-value)(cons-stream(sign-change-detector (stream-car input-stream) last-value)(make-zero-crossings (stream-cdr input-stream)(stream-car input-stream))))(define zero-crossings (make-zero-crossings sense-data 0))Мимо проходит Лизина начальница Ева Лу Атор и замечает, что программа приблизительно равносильна следующей, написанной с использованием обобщенной версии stream-map из упражнения 3.50:(define zero-crossings(stream-map sign-change-detector sense-data hвыражениеi))Завершите программу, вставив необходимое hвыражениеi.Упражнение 3.75.К сожалению, Лизин детектор перехода через ноль из упражнения 3.74 оказывается недостаточным, потому что зашумленный сигнал от сенсоров приводит к ложным срабатываниям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
