((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 приводит к вычислению задержанного вызова stream-enumerate-interval, возвращающего

(cons l000l

(delay (stream-enumerate-interval l0002 l000000)))

Теперь stream-filter смотрит на stream-car этого потока, 10001, видит, что и это не простое число, снова зовет stream-cdr и так далее, пока stream-enumerate-interval не выдаст простое число 10007. Тогда streamfilter, в соответствии со своим определением, вернет

(cons-stream (stream-car stream)

(stream-filter pred (stream-cdr stream)))

что в данном случае равняется

(cons l0007 (delay

(stream-filter prime? (cons l0008 (delay

(stream-enumerate-interval l0009

l000000))))))

Теперь этот результат передается в stream-cdr из нашего исходного выражения. При этом вызывается задержанный stream-filter, который, в свою очередь, вынуждает задержанные вызовы stream-enumerate-interval, пока не доберется до следующего простого числа, а именно 10009. Наконец, результат, передаваемый в stream-car нашего исходного выражения, равен

(cons l0009

(delay

(stream-filter prime?

(cons l00l0

(delay

(stream-enumerate-interval l00ll

l000000))))))

Stream-car возвращает 10009, и вычисление закончено. На простоту было проверено ровно столько чисел, сколько было необходимо, чтобы найти второе простое число на интервале, и сам интервал был перебран только до того места, которое было нужно фильтру простых чисел.

В общем, мы можем считать задержанные вычисления программированием, «управляемым потребностями», в котором каждый шаг вычислений в потоковом

процессе активизируется лишь настолько, насколько это нужно для следующего шага. Таким образом, нам удалось отделить реальный порядок событий при вычислении от внешней структуры процедур. Мы пишем процедуры так, как будто потоки существуют «все целиком», а на самом деле вычисление происходит пошагово, как и при программировании в традиционном стиле.

Реализация delay и force

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

(delay (выражение))

было синтаксическим сахаром для

(lambda () (выражение))

Force просто вызывает (безаргументную) процедуру, порожденную delay, так что она может быть реализована как процедура

(define (force delayed-object) (delayed-object))

При такой реализации delay и force работают согласно описанию, однако к ней можно добавить важную оптимизацию. Во многих приложениях мы вынуждаем один и тот же задержанный объект по многу раз. В рекурсивных программах с использованием потоков это может привести к существенной неэффективности (см. упражнение 3.57). Решение состоит в том, чтобы строить задержанные объекты так, чтобы при первом вынуждении они сохраняли вычисленное значение. Последующие обращения будут просто возвращать сохраненное значение без повторения вычислений. Другими словами, мы реализуем delay как особого рода мемоизированную процедуру, подобную описанным в упражнении 3.27. Один из способов этого добиться - использовать следующую процедуру, которая принимает процедуру (без аргументов) и возвращает ее мемоизированную версию. При первом вызове мемоизированная процедура сохраняет результат. При последующих вызовах она просто его возвращает.

(define (memo-proc proc)

(let ((already-run? false) (result false)) (lambda ()

(if (not already-run?)

(begin (set! result (proc))

(set! already-run? true) result)

result))))

Теперь можно определить delay таким образом, что (delay (выражение))

равносильно

(memo-proc (lambda () (выражение)))

а определение force не меняется.58 Упражнение 3.50.

Закончите следующее определение, которое обобщает процедуру stream-map, чтобы она позволяла использовать процедуры от нескольких аргументов, подобно map из раздела 2.2.1, сноска 12.

(define (stream-map proc . argstreams) (if ((??) (car argstreams)) the-empty-stream

( (??)

(apply proc (map (??) argstreams)) (apply stream-map

(cons proc (map ( ?? ) argstreams))))))

Упражнение 3.51.

Чтобы внимательнее изучить задержанные вычисления, мы воспользуемся следующей процедурой, которая печатает свой аргумент, а затем возвращает его:

(define (show x) (display-line x)

x)

Что печатает интерпретатор в ответ на каждое выражение из следующей последователь-ности?59

(define x (stream-map show (stream-enumerate-interval 0 l0))) (stream-ref x 5) (stream-ref x 7)

Упражнение 3.52.

Рассмотрим последовательность выражений (define sum 0)

(define (accum x)

(set! sum (+ x sum))

58Есть много возможных реализаций потоков помимо описанной в этом разделе. Задержанное вычисление, ключевой элемент, который делает потоки практически полезными, было частью метода передачи параметров по имени (by name) в языке Алгол-60. Использование этого механизма для реализации потоков впервые было описано Ландином (Landin 1965). Задержанное вычисление для потоков ввели в Лисп Фридман и Уайз (Friedman and Wise 1976). В их реализации cons всегда задерживает вычисление своих аргументов, так что списки автоматически ведут себя как потоки. Мемоизирующая оптимизация известна также как вызов по необходимости (by need). В сообществе программистов на Алголе задержанные объекты из нашей первой реализации назывались бы санками вызова по имени (call-by-name thunks), а оптимизированный вариант санками вызова по необходимости (call-by-need thunks).

59Упражнения типа 3.51 и 3.52 помогают понять, как работает delay. С другой стороны, смешение задержанного вычисления с печатью - или, хуже того, с присваиванием, - ужасно запутывает, и преподаватели, читающие курсы по языкам программирования, часто пытают студентов экзаменационными вопросами вроде упражнений из этого раздела. Незачем и говорить, что писать программы, зависящие от таких тонкостей, - показатель чрезвычайно плохого стиля. Отчасти мощность потокового программирования в том и заключается, что можно игнорировать порядок, в котором на самом деле происходят события в программах. К сожалению, ровно этого мы и не можем себе позволить в присутствии присваивания, заставляющего нас думать о времени и изменении.