(car (cdr (filter prime?

(enumerate-interval 10000 1000000))))

Это выражение находит второе простое число, однако на это затрачивается возмутительное количество вычислительных ресурсов. Мы строим список из почти миллиона целых чисел, фильтруем этот список, проверяя каждый его элемент на простоту, а затем почти весь результат игнорируем. При более традиционном программистском подходе мы бы чередовали перечисление и фильтрацию, и остановились бы по достижении второго простого числа.

Потоки представляют собой прием, который дает возможность работать с последовательностями и при этом ничего не терять на представлении последовательностей в виде списков. Потоки сочетают лучшее из обоих подходов: мы можем изящно формулировать программы в терминах операций с последовательностями и при этом сохранять эффективность пошагового вычисления. Основная идея состоит в том, чтобы строить список только частично и передавать частично построенный список программе, потребляющей поток. Если потребитель запросит доступ к той части потока, которая еще не сконструирована, поток автоматически достроит ровно такую часть себя самого, какая нужна, и сохранит таким образом иллюзию, что он существует целиком. Другими словами, хотя программы будут писаться так, как будто обрабатываются полные последовательности, мы так спроектируем реализацию потоков, что построение потока будет автоматически и незаметно для пользователя чередоваться с его использованием.

На первый взгляд, потоки - это просто списки, у которых процедуры работы с ними переименованы. Имеется конструктор, 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-each:55

(define (stream-ref s n)

(if (= n 0)

(stream-car s)

(stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)

54 В реализации MIT the-empty-stream совпадает с пустым списком (), а процедура stream-null? совпадает с null?.

55Здесь у Вас должно возникнуть беспокойство. То, что мы определяем столь сходные процедуры для потоков и списков, показывает, что мы упускаем некую глубинную абстракцию. К сожалению, чтобы использовать эту абстракцию, нам нужно более точное управление процессом вычисления, чем у нас сейчас есть. Мы подробнее обсудим этот вопрос в конце раздела 3.5.4. В разделе 4.2 мы разработаем среду, в которой списки и потоки объединяются.

(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)))))

С помощью 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 (выражение)) не вычисляет (выражение), а вместо этого возвращает так называемый задержанный объект (delayed object). Мы можем считать, что это «обещание» вычислить выражение когда-нибудь в будущем. В качестве пары к delay имеется процедура force, которая берет задержанный объект в качестве аргумента и вычисляет его - фактически, заставляя delay выполнить обещание. Ниже мы увидим, как можно реализовать delay и force, но сначала давайте посмотрим, как с их помощью строить потоки.

Cons-stream - это особая форма, такая, что

(cons-stream (a) (b))

эквивалентно

(cons (а) (delay (Ь)))

Это означает, что мы строим потоки при помощи пар. Однако вместо того, чтобы поместить значение остатка потока в cdr пары, мы кладем туда обещание вычислить остаток, если нас об этом попросят. Теперь можно определить stream-car и stream-cdr как процедуры:

(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 (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-stream low

(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)

56В отличие от stream-car и stream-cdr, которые можно определить в виде процедур, cons-stream обязан быть особой формой. Если бы он был процедурой, то, согласно нашей модели вычислений, выполнение (cons-stream (а) (b)) автоматически приводило бы к вычислению (6), а именно этого мы и не хотим. По этой же причине delay должен быть особой формой, хотя force может оставаться обычной процедурой.

57Показанные здесь числа на самом деле не появляются в возвращаемом выражении. Возвращается исходное выражение вместе с окружением, в котором переменным присвоены соответствующие значения. Например, там, где напечатано число 10001, стоит (+ low 1), и переменная low связана со значением 10000.