Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 70
Текст из файла (страница 70)
С этой цельюмы вводим новую структуру данных, называемую поток (stream). С абстрактной точки зрения, поток — это просто последовательность. Однако, как мы увидим, прямоепредставление потоков в виде списков (как в разделе 2.2.1) не полностью раскрываетмощь работы с потоками. В качестве альтернативы мы введем метод задержанных вычислений (delayed evaluation), который позволит нам представлять очень большие (дажебесконечные) последовательности в виде потоков.Работа с потоками позволяет моделировать системы, обладающие состоянием, совершенно не используя присваивание и изменяемые данные. Отсюда есть важные следствия, как теоретические, так и практические, поскольку мы приобретаем возможностьстроить модели, лишенные недостатков, связанных с присваиванием.
С другой стороны,парадигма потоков вызывает свои собственные трудности, и вопрос, какой из методовмоделирования ведет к построению более модульных и легко поддерживаемых систем,остается открытым.3.5.1. Потоки как задержанные спискиКак мы видели в разделе 2.2.3, последовательности можно использовать как стандартные интерфейсы для комбинирования программных модулей. Мы сформулировалимощные абстракции для работы с последовательностями, такие как map, filter иaccumulate, с помощью которых можно описать широкий класс действий одновременно коротко и изящно.52 Физики иногда принимают эту точку зрения, вводя «мировые линии» частиц в рассуждениях о движении.Кроме того, мы уже упоминали (в разделе 2.2.3), что это естественный ход мысли при рассужднениях осистемах обработки сигналов.
Мы рассмотрим приложение потоков к обработке сигналов в разделе 3.5.3.300Глава 3. Модульность, объекты и состояниеК сожалению, если представлять последовательности в виде списков, за это изящество приходится расплачиваться чрезвычайной неэффективностью как с точки зрениявремени, так и с точки зрения объема памяти, который требуется нашим вычислениям.Когда мы представляем операции над последовательностями в виде трансформаций списков, программам приходится на каждом шагу строить и копировать структуры данных(которые могут быть громадными).Чтобы понять, почему это так, сравним две программы для вычисления суммы всехпростых чисел на интервале.
Первая программа написана в стандартном итеративномстиле53 :(define (sum-primes a b)(define (iter count accum)(cond ((> count b) accum)((prime? count) (iter (+ count 1) (+ count accum)))(else (iter (+ count 1) accum))))(iter a 0))Вторая программа производит то же самое вычисление с помощью операций надпоследовательностями из раздела 2.2.3:(define (sum-primes a b)(accumulate +0(filter prime? (enumerate-interval a b))))Во время вычисления первая программа должна хранить только накапливаемуюсумму.
Напротив, фильтр во второй программе не может начать тестировать, покаenumerate-interval не создала полного списка чисел на интервале. Фильтр порождает еще один список, который, в свою очередь, передается accumulate, прежде, чемон сожмется в сумму. Первой программе не требуется такого количества промежуточнойпамяти, — мы можем считать, что она просто проходит интервал снизу вверх, добавляяк сумме каждое простое число, которое ей встретится.Неэффективность использования списков становится болезненно очевидной, если мывоспользуемся парадигмой последовательностей для вычисления второго простого числав интервале от 1000 до 1 000 000 при помощи следующего выражения:(car (cdr (filter prime?(enumerate-interval 10000 1000000))))Это выражение находит второе простое число, однако на это затрачивается возмутительное количество вычислительных ресурсов.
Мы строим список из почти миллионацелых чисел, фильтруем этот список, проверяя каждый его элемент на простоту, а затемпочти весь результат игнорируем. При более традиционном программистском подходе мыбы чередовали перечисление и фильтрацию, и остановились бы по достижении второгопростого числа.53 Мы предполагаем, что у нас имеется предикат prime? (например, из раздела 1.2.6), который проверяет,является ли число простым.3.5. Потоки301Потоки представляют собой прием, который дает возможность работать с последовательностями и при этом ничего не терять на представлении последовательностей в видесписков. Потоки сочетают лучшее из обоих подходов: мы можем изящно формулироватьпрограммы в терминах операций с последовательностями и при этом сохранять эффективность пошагового вычисления. Основная идея состоит в том, чтобы строить списоктолько частично и передавать частично построенный список программе, потребляющейпоток. Если потребитель запросит доступ к той части потока, которая еще не сконструирована, поток автоматически достроит ровно такую часть себя самого, какая нужна, исохранит таким образом иллюзию, что он существует целиком.
Другими словами, хотяпрограммы будут писаться так, как будто обрабатываются полные последовательности,мы так спроектируем реализацию потоков, что построение потока будет автоматическии незаметно для пользователя чередоваться с его использованием.На первый взгляд, потоки — это просто списки, у которых процедуры работы с нимипереименованы. Имеется конструктор, cons-stream, и два селектора, stream-car иstream-cdr, причем выполняются уравнения(stream-car (cons-stream x y)) = x(stream-cdr (cons-stream x y)) = yИмеется специальный объект, the-empty-stream, который не может быть результатом никакой операции cons-stream, и который можно распознать процедуройstream-null?54.
Таким образом, можно создавать и использовать потоки, точно также, как списки, для представления составных данных, организованных в виде последовательности. В частности, можно построить потоковые аналоги операций со списками изглавы 2, таких, как list-ref, map и for-each55 :(define (stream-ref s n)(if (= n 0)(stream-car s)(stream-ref (stream-cdr s) (- n 1))))(define (stream-map proc s)(if (stream-null? s)the-empty-stream(cons-stream (proc (stream-car s))(stream-map proc (stream-cdr s)))))(define (stream-for-each proc s)(if (stream-null? s)’done(begin (proc (stream-car s))(stream-for-each proc (stream-cdr s)))))54 В реализации MIT the-empty-stream совпадает с пустым списком ’(), а процедура stream-null?совпадает с null?.55 Здесь у Вас должно возникнуть беспокойство.
То, что мы определяем столь сходные процедуры для потокови списков, показывает, что мы упускаем некую глубинную абстракцию. К сожалению, чтобы использовать этуабстракцию, нам нужно более точное управление процессом вычисления, чем у нас сейчас есть. Мы подробнееобсудим этот вопрос в конце раздела 3.5.4. В разделе 4.2 мы разработаем среду, в которой списки и потокиобъединяются.Глава 3. Модульность, объекты и состояние302С помощью stream-for-each потоки можно печатать:(define (display-stream s)(stream-for-each display-line s))(define (display-line x)(newline)(display x))Чтобы заставить реализацию потоков автоматически и незаметно чередовать построение потока с его использованием, мы сделаем так, чтобы cdr потока вычислялся тогда,когда к нему обращается процедура stream-cdr, а не тогда, когда поток создаетсяпроцедурой cons-stream. Такое проектное решение заставляет вспомнить обсуждениерациональных чисел в разделе 2.1.2, где мы увидели, что можно приводить рациональные числа к наименьшему знаменателю либо во время создания числа, либо во времяобращения к нему.
Две реализации рациональных чисел предоставляют одну и ту жеабстракцию, однако наш выбор влияет на эффективность работы. Существует подобнаясвязь и между потоками и обычными списками. В качестве абстракции данных потоки не отличаются от списков. Разница состоит в том, когда вычисляются их элементы.В обычных списках и car, и cdr вычисляются во время построения.
У потоков cdrвычисляется при обращении.Наша реализация потоков основана на особой форме под названием delay. Выполнение (delay hвыражениеi) не вычисляет hвыражениеi, а вместо этого возвращает такназываемый задержанный объект (delayed object).
Мы можем считать, что это «обещание» вычислить выражение когда-нибудь в будущем. В качестве пары к delay имеетсяпроцедура force, которая берет задержанный объект в качестве аргумента и вычисляетего — фактически, заставляя delay выполнить обещание. Ниже мы увидим, как можнореализовать delay и force, но сначала давайте посмотрим, как с их помощью строитьпотоки.Cons-stream — это особая форма, такая, что(cons-stream hai hbi)эквивалентно(cons hai (delay hbi))Это означает, что мы строим потоки при помощи пар. Однако вместо того, чтобыпоместить значение остатка потока в cdr пары, мы кладем туда обещание вычислитьостаток, если нас об этом попросят. Теперь можно определить stream-car и streamcdr как процедуры:(define (stream-car stream) (car stream))(define (stream-cdr stream) (force (cdr stream)))Streams-car возвращает car пары.
Stream-cdr берет cdr пары и вычисляетхранящееся там задержанное выражение, чтобы получить остаток потока56 .56 Вотличие от stream-car и stream-cdr, которые можно определить в виде процедур, cons-stream3.5. Потоки303Реализация потоков в действииЧтобы посмотреть, как ведет себя эта реализация, давайте проанализируем «возмутительное» вычисление с простыми числами, переформулированное через потоки:(stream-car(stream-cdr(stream-filter prime?(stream-enumerate-interval 10000 1000000))))Мы увидим, что теперь вычисления происходят эффективно.Вначале зовется процедура stream-enumerate-interval с аргументами 1000и 1000000.
Stream-enumerate-interval — это потоковый аналог процедурыenumerateinterval (раздел 2.2.3):(define (stream-enumerate-interval low high)(if (> low high)the-empty-stream(cons-streamlow(stream-enumerate-interval (+ low 1) high))))и, таким образом, результат, возвращаемый stream-enumerate-interval,сформированный cons-stream внутри нее, равен57(cons 10000(delay (stream-enumerate-interval 10001 1000000)))А именно, stream-enumerate-interval возвращает поток, представленный в виде пары, car которой равен 10000, а cdr является обещанием вычислить остаток интервала, когда попросят. Теперь этот поток отфильтровывается на предмет поиска простыхчисел с помощью потокового аналога процедуры filter (раздел 2.2.3):(define (stream-filter pred stream)(cond ((stream-null? stream) the-empty-stream)((pred (stream-car stream))(cons-stream (stream-car stream)(stream-filter pred(stream-cdr stream))))(else (stream-filter pred (stream-cdr stream)))))Stream-filter проверяет stream-car потока (то есть car пары, то есть 10000).Поскольку это не простое число, stream-filter смотрит на streamcdr своего входного потока.
Вызов stream-cdr приводит к вычислению задержанного вызова streamenumerate-interval, возвращающегообязан быть особой формой. Если бы он был процедурой, то, согласно нашей модели вычислений, выполнение(cons-stream hai hbi) автоматически приводило бы к вычислению hbi, а именно этого мы и не хотим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
