Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 75
Текст из файла (страница 75)
Инженерэлектронщик Дайко Поправич предлагает Лизе сгладить сигнал, чтобы отфильтровать шум, прежде, чем отлавливать пересечение нуля. Лиза принимает его совет и решает извлечь переходы324Глава 3. Модульность, объекты и состояниечерез ноль из сигнала, полученного взятием среднего арифметического каждого значения входныхданных с предыдущим значением.
Она объясняет задачу своему помощнику Хьюго Думу, и тотпытается реализовать идею, поправив Лизин текст следующим образом:(define (make-zero-crossings input-stream last-value)(let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))(cons-stream (sign-change-detector avpt last-value)(make-zero-crossings (stream-cdr input-stream)avpt))))Этот код неверно реализует замысел Лизы. Найдите ошибку, внесенную Хьюго, и исправьте ее,не меняя структуру программы. (Подсказка: придется увеличить число аргументов make-zerocrossings.)Упражнение 3.76.Ева Лу Атор недовольна подходом Хьюго из упражнения 3.75.
Написанная им программа немодульна, поскольку смешивает операции сглаживания и отлова пересечений ноля. Например, тестна пересечение не должен изменяться, если Лизе удастся найти другой способ улучшить качествовходного сигнала. Помогите Хьюго и напишите процедуру smooth, которая берет на входе поток, ана выходе выдает поток, элементы которого получены усреднением каждых двух последовательныхэлементов входного потока. Затем используйте smooth как компоненту и реализуйте детекторперехода через ноль в более модульном стиле.3.5.4.
Потоки и задержанное вычислениеПроцедура integral в конце предыдущего раздела показывает, как с помощью потоков можно моделировать системы обработки сигналов, которые содержат циклы обратной связи. Цикл обратной связи для сумматора, показанный на рис. 3.32, моделируетсятем, что внутренний поток int в процедуре integral определяется с использованиемсебя самого:(define int(cons-stream initial-value(add-streams (scale-stream integrand dt)int)))Способность интерпретатора работать с таким косвенным определением зависит отdelay, встроенного в cons-stream.
Без этой задержки интерпретатор не мог бы построить int, не вычислив оба аргумента cons-stream, а для этого нужно, чтобы intуже был определен. В общем случае, delay играет ключевую роль, когда мы моделируем системы обработки сигналов с обратной связью при помощи потоков. В отсутствиезадержки нам приходилось бы формулировать модели так, чтобы вход всякого обрабатывающего блока полностью вычислялся, прежде чем блок выдает что-либо на выходе.Такое условие исключает циклы.К сожалению, потоковые модели систем с циклами могут требовать применения задержек помимо той, которая «спрятана» в cons-stream.
Например, на рисунке 3.34показана система обработки сигналов, решающая дифференциальное уравнение dy/dt =f (y), где f — заданная функция. На рисунке показан отображающий блок, который применяет f ко входному сигналу, связанный в цикл обратной связи с интегратором. Это3.5. Потоки325y0map: fdyintegralyРис.
3.34. «Аналоговая компьютерная цепь», которая решает уравнение dy/dt = f (y).очень похоже на работу аналоговых схем, действительно используемых для решениятакого рода уравнений.Если нам дано начальное значение y0 , мы могли бы попытаться смоделировать этусистему с помощью процедуры(define (solve f y0 dt)(define y (integral dy y0 dt))(define dy (stream-map f y))y)Эта процедура не работает, потому что вызов integral в первой строке solve требует, чтобы был определен входной поток dy, а это происходит только во второй строкепроцедуры solve.С другой стороны, замысл, заключенный в этом определении, вполне здрав, поскольку мы можем, в принципе, начать порождать поток y и не зная dy. Действительно,integral и многие другие операции над потоками обладают свойствами, подобнымиcons-stream, а именно, мы можем породить часть ответа, даже если нам дана толькочастичная информация об аргументах.
В случае integral, первый элемент выходногопотока есть указанное начальное значение initial-value. Таким образом, можно породить первый элемент выходного потока и не вычисляя интегрируемую величину dy. Араз мы знаем первый элемент y, то stream-map во второй строке solve может начатьработать и породить первый элемент dy, а с его помощью мы получим второй элементy, и так далее.Чтобы воспользоваться этой идеей, переопределим integral так, чтобы он ожидалинтегрируемый поток в виде задержанного аргумента (delayed argument). Integralбудет размораживать вычисление входного потока через force только тогда, когда емунужно породить элементы входного потока помимо первого:(define (integral delayed-integrand initial-value dt)(define int(cons-stream initial-value(let ((integrand (force delayed-integrand)))(add-streams (scale-stream integrand dt)int))))int)326Глава 3.
Модульность, объекты и состояниеТеперь можно реализовать процедуру solve, задержав вычисление dy внутри определения y71 :(define (solve f y0 dt)(define y (integral (delay dy) y0 dt))(define dy (stream-map f y))y)Теперь при любом вызове integral необходимо задерживать интегрируемый аргумент.Можно показать, что процедура solve работает, аппроксимируя e ≈ 2.718 вычислениемв точке y = 1 решения дифференциального уравнения dy/dt = y с начальным условиемy(0) = 1:(stream-ref (solve (lambda (y) y) 1 0.001) 1000)2.716924Упражнение 3.77.Вышеприведенная процедура integral была аналогична «непрямому» определению бесконечного потока натуральных чисел из раздела 3.5.2.
В виде альтернативы можно дать определениеintegral, более похожее на integers-starting-from (также в разделе 3.5.2):(define (integral integrand initial-value dt)(cons-stream initial-value(if (stream-null? integrand)the-empty-stream(integral (stream-cdr integrand)(+ (* dt (stream-car integrand))initial-value)dt))))В системах с циклами эта реализациея порождает такие же проблемы, как и наша исходная версияintegral. Модифицируйте процедуру так, чтобы она ожидала integrand как задержанныйаргумент, а следовательно, могла быть использована в процедуре solve.Упражнение 3.78.Рассмотрим задачу проектирования системы обработки сигналов для решения гомогенных линейных дифференциальных уравнений второго порядкаd2 ydy−a− by = 0dt2dtВыходной поток, моделирующий y, порождается сетью, содержащей цикл.
Этот цикл возникаетпотому, что значение d2 y/dt2 зависит от значений y и dy/dt, а они оба получаются интегрированием d2 y/dt2 . Диаграмма, которую нам хотелось бы закодировать, показана на рис. 3.35. Напишитепроцедуру solve-2nd, которая в качестве аргументов берет константы a, b и dt и начальныезначения y0 и dy0 для y и dy, и порождает поток последовательных значений y.71 Не гарантируется, что эта процедура будет работать во всех реализациях Scheme, но для любой реализации должен найтись простой способ заставить подобную процедуру работать.
Проблемы связаны с тонкимиразличиями в том, как реализации Scheme обрабатывают внутренние определения. (См. раздел 4.1.6.)3.5. Потоки327dy0ddyy0dyintegralyintegralscale:aaddscale:baddРис. 3.35. Диаграмма потока сигналов для решения линейного дифференциального уравнения второго порядка.iR+vC-+ vR-iLRiCC+LvL-Рис. 3.36. Последовательная RLC-цепь328Глава 3. Модульность, объекты и состояниеУпражнение 3.79.Обобщите процедуру solve-2nd из упражнения 3.78 так, чтобы с ее помощью можно былорешать дифференциальные уравнения второго порядка общего вида d2 y/dy 2 = f (dy/dt, y).Упражнение 3.80.Последовательная RLC-цепь (series RLC circuit) состоит из резистора, конденсатора и катушкииндуктивности, соединенных последовательно, как показано на рис.
3.36. Если сопротивление,индуктивность и емкость равны, соответственно, R, L и C, то отношения между напряжением vи током i на трех элементах описываются уравнениямиvR = iR RdiLdtdvCiC = CdtvL = Lа цепь диктует соотношенияiR = iL = −iCvC = vL + vRСочетание этих условий показывает, что состояние цепи (характеризуемое через vC , напряжениена конденсаторе, и iL , ток через катушку) описывается парой дифференциальных уравненийdvCiL=−dtC1RdiL= vC − iLdtLLДиаграмма потока сигналов, представляющая эту систему дифференциальных уравнений, показана на рисунке 3.37.Напишите процедуру RLC, которая в качестве аргументов берет параметры цепи R, L и Cи точность по времени dt.
Подобно процедуре RC из упражнения 3.73, RLC должна порождатьпроцедуру, которая берет начальные значения переменных состояния vC0 и iL0 и порождает (черезcons) пару потоков состояния vC и iL . С помощью RLC породите пару потоков, которая моделируетповедение RLC-цепи c K = 1 ом, C = 0.2 фарад, L = 1 генри, dt = 0.1 секунды, и начальнымизначениями iL0 = 0 ампер и vC0 = 10 вольт.Нормальный порядок вычисленийПримеры из этого раздела показывают, как явное использование delay и force сообщает программированию большую гибкость, однако те же самые примеры показывают,как наши программы от этого могут стать сложнее и запутаннее. Например, новая процедура integral позволяет моделировать системы с циклами, но теперь нам приходитсяпомнить, что звать ее надо с задержанным аргументом, и все процедуры, которые пользуются integral, должны это знать.
В результате мы создали два класса процедур:обычные и те, которым требуются задержанные аргументы. В общем случае созданиеновых классов процедур требует от нас еще и создания новых классов процедур высшихпорядков72 .72 Здесь мы получаем в Лиспе слабое отражение тех сложностей, которые возникают при работе с процедурами высших порядков в обыкновенных сильно типизированных языках вроде Паскаля. В таких языках3.5. Потоки329scale: 1/LdvCintegralvCvC0scale: - 1/CdiLaddintegralLiiL0scale: - R/LРис. 3.37. Диаграмма потока сигналов для решения уравнений последовательной RLC–цепи.Один из способов избежать необходимости вводить два класса процедур состоит втом, чтобы заставить все процедуры принимать задержанные аргументы.
Можно принятьмодель вычислений, в которой все аргументы процедур автоматически задерживаются,и вынуждение происходит только тогда, когда их значения реально нужны (например,для выполнения элементарной операции). Таким образом наш язык станет использоватьнормальный порядок вычислений, который мы впервые описали, когда разговор шел оподстановочной модели вычислений в разделе 1.1.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
