Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 71
Текст из файла (страница 71)
Поэтой же причине delay должен быть особой формой, хотя force может оставаться обычной процедурой.57 Показанные здесь числа на самом деле не появляются в возвращаемом выражении. Возвращается исходноевыражение вместе с окружением, в котором переменным присвоены соответствующие значения. Например, там,где напечатано число 10001, стоит (+ low 1), и переменная low связана со значением 10000.304Глава 3. Модульность, объекты и состояние(cons 10001(delay (stream-enumerate-interval 10002 1000000)))Теперь stream-filter смотрит на stream-car этого потока, 10001, видит, что иэто не простое число, снова зовет stream-cdr и так далее, пока stream-enumerateinterval не выдаст простое число 10007.
Тогда streamfilter, в соответствии сосвоим определением, вернет(cons-stream (stream-car stream)(stream-filter pred (stream-cdr stream)))что в данном случае равняется(cons 10007(delay(stream-filterprime?(cons 10008(delay(stream-enumerate-interval 100091000000))))))Теперь этот результат передается в stream-cdr из нашего исходного выражения.При этом вызывается задержанный stream-filter, который, в свою очередь, вынуждает задержанные вызовы stream-enumerate-interval, пока не доберется до следующего простого числа, а именно 10009. Наконец, результат, передаваемый в streamcar нашего исходного выражения, равен(cons 10009(delay(stream-filterprime?(cons 10010(delay(stream-enumerate-interval 100111000000))))))Stream-car возвращает 10009, и вычисление закончено.
На простоту было проверено ровно столько чисел, сколько было необходимо, чтобы найти второе простое числона интервале, и сам интервал был перебран только до того места, которое было нужнофильтру простых чисел.В общем, мы можем считать задержанные вычисления программированием, «управляемым потребностями», в котором каждый шаг вычислений в потоковом процессе активизируется лишь настолько, насколько это нужно для следующего шага. Таким образом,нам удалось отделить реальный порядок событий при вычислении от внешней структурыпроцедур. Мы пишем процедуры так, как будто потоки существуют «все целиком», а насамом деле вычисление происходит пошагово, как и при программировании в традиционном стиле.3.5. Потоки305Реализация delay и forceDelay и force могут казаться таинственными операциями, но на самом деле ихреализация весьма проста.
Delay должно упаковать выражение так, чтобы потом егоможно было выполнить по требованию, и мы добиваемся этого, просто рассматриваявыражение как тело процедуры. Можно сделать delay особой формой, такой, чтобы(delay hвыражениеi)было синтаксическим сахаром для(lambda () hвыражениеi)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 hвыражениеi) равносильно(memo-proc (lambda () hвыражениеi))а определение force не меняется58 .58 Есть много возможных реализаций потоков помимо описанной в этом разделе. Задержанное вычисление,ключевой элемент, который делает потоки практически полезными, было частью метода передачи параметров306Глава 3. Модульность, объекты и состояниеУпражнение 3.50.Закончите следующее определение, которое обобщает процедуру stream-map, чтобы она позволяла использовать процедуры от нескольких аргументов, подобно map из раздела 2.2.1, сноска12.(define (stream-map proc .
argstreams)(if (h??i (car argstreams))the-empty-stream(h??i(apply proc (map h??i argstreams))(apply stream-map(cons proc (map h??i argstreams))))))Упражнение 3.51.Чтобы внимательнее изучить задержанные вычисления, мы воспользуемся следующей процедурой,которая печатает свой аргумент, а затем возвращает его:(define (show x)(display-line x)x)Что печатает интерпретатор в ответ на каждое выражение из следующей последовательности59 ?(define x (stream-map show (stream-enumerate-interval 0 10)))(stream-ref x 5)(stream-ref x 7)Упражнение 3.52.Рассмотрим последовательность выражений(define sum 0)(define (accum x)(set! sum (+ x sum))sum)по имени (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.
С другой стороны, смешение задержанного вычисления с печатью — или, хуже того, с присваиванием, — ужасно запутывает, и преподаватели,читающие курсы по языкам программирования, часто пытают студентов экзаменационными вопросами вродеупражнений из этого раздела. Незачем и говорить, что писать программы, зависящие от таких тонкостей, —показатель чрезвычайно плохого стиля. Отчасти мощность потокового программирования в том и заключается,что можно игнорировать порядок, в котором на самом деле происходят события в программах. К сожалению,ровно этого мы и не можем себе позволить в присутствии присваивания, заставляющего нас думать о времении изменении.3.5.
Потоки307(define seq (stream-map accum (stream-enumerate-interval 1 20)))(define y (stream-filter even? seq))(define z (stream-filter (lambda (x) (= (remainder x 5) 0))seq))(stream-ref y 7)(display-stream z)Каково значение sum после вычисления каждого из этих выражений? Что печатается при вычислении выражений stream-ref и display-stream? Изменился бы этот результат, если бымы реализовали (delay hвыражениеi) просто как (lambda () hвыражениеi), не применяяоптимизацию через memo-proc? Объясните свой ответ.3.5.2. Бесконечные потокиМы видели, как можно поддерживать иллюзию работы с потоками как с цельными объектами, хотя на самом деле мы вычисляем только ту часть потока, к которойнам требуется доступ.
Этот метод можно использовать, чтобы эффективно представлятьпоследовательности в виде потоков, даже если эти последовательности весьма длинны.Еще удивительнее то, что при помощи потоков можно представлять последовательностибесконечной длины. Рассмотрим, например, следующее определение потока положительных целых чисел:(define (integers-starting-from n)(cons-stream n (integers-starting-from (+ n 1))))(define integers (integers-starting-from 1))Такая запись имеет смысл, потому что описывает sequence как пару, у которойcar равен 1, а cdr является обещанием породить целые числа, начиная с 2. Такойпоток бесконечен, но в любой данный момент мы можем работать только с конечной егочастью.
Таким образом, наши программы никогда не узнают, что целиком бесконечногопотока не существует.При помощи integers можно определять другие бесконечные потоки, например,поток чисел, не делящихся на 7:(define (divisible? x y) (= (remainder x y) 0))(define no-sevens(stream-filter (lambda (x) (not (divisible? x 7)))integers))Теперь мы можем искать числа, не делящиеся на 7, просто обращаясь к элементамэтого потока:(stream-ref no-sevens 100)По аналогии с integers, можно определить бесконечный поток чисел Фибоначчи:308Глава 3.
Модульность, объекты и состояние(define (fibgen a b)(cons-stream a (fibgen b (+ a b))))(define fibs (fibgen 0 1))Fibs представляет собой пару, car которой равен 0, а cdr является обещаниемвычислить (fibgen 1 1). Когда мы выполняем это задержанное (fibgen 1 1), онопорождает пару, где car равен 1, а в cdr лежит обещание вычислить (fibgen 1 2),и так далее.Чтобы продемонстрировать пример более интересного потока, можно обобщить nosevens и построить бесконечный поток простых чисел, используя метод, известный какрешето Эратосфена (sieve of Eratosthenes)60 . Сначала мы строим поток чисел, начиная с 2, первого простого числа.
Для того, чтобы найти остальные простые числа, мыфильтруем кратные двойки из потока остальных чисел. Получается поток, который начинается с 3, следующего простого числа. Теперь из остатка потока мы фильтруем числа,кратные 3. Получается поток, начинающийся с 5, следующего простого, и так далее.Другими словами, мы строим простые числа с помощью просеивающего процесса, описываемого так: чтобы просеять поток S, нужно сформировать поток, в котором первыйэлемент совпадает с первым элементом S, а остаток получается фильтрацией множителей первого элемента из оставшейся части S и просеивания того, что получится.
Такойпроцесс нетрудно описать в терминах операций над потоками:(define (sieve stream)(cons-stream(stream-car stream)(sieve (stream-filter(lambda (x)(not (divisible? x (stream-car stream))))(stream-cdr stream)))))(define primes (sieve (integers-starting-from 2)))Теперь, чтобы найти определенное простое число, надо только попросить:(stream-ref primes 50)233Интересно представить себе систему обработки сигналов, соответствующую sieve,показанную на «хендерсоновской диаграмме» на рисунке 3.3161 . Входной поток попадает в «расconsер», который отделяет первый элемент потока от его хвоста. При помощи60 Эратосфен, греческий философ третьего века до н. э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
