scale: 1/L

dvc

integral

Co

add

Рис. 3.37: Диаграмма потока сигналов для решения уравнений последовательной RLC-цепи.

Нормальный порядок вычислений

Примеры из этого раздела показывают, как явное использование delay и force сообщает программированию большую гибкость, однако те же самые примеры показывают, как наши программы от этого могут стать сложнее и запутаннее. Например, новая процедура integral позволяет моделировать системы с циклами, но теперь нам приходится помнить, что звать ее надо с задержанным аргументом, и все процедуры, которые пользуются integral, должны это знать. В результате мы создали два класса процедур: обычные и те, которым требуются задержанные аргументы. В общем случае создание новых классов процедур требует от нас еще и создания новых классов процедур

72

высших порядков.72

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

72Здесь мы получаем в Лиспе слабое отражение тех сложностей, которые возникают при работе с процедурами высших порядков в обыкновенных сильно типизированных языках вроде Паскаля. В таких языках программисту нужно указывать типы данных для аргументов и результата каждой процедуры: число, логическое значение, последовательность и т. д. Следовательно, мы не можем выразить такую абстракцию, как «применить данную процедуру proc ко всем элементам последовательности» в виде единой процедуры высшего порядка вроде stream-map. Вместо этого нам потребуется отдельная процедура для каждой комбинации типов аргументов и результата, которые можно указать для proc. Практическая поддержка понятия «тип данных» при наличии процедур высших порядков приводит ко многим интересным проблемам. Один из способов работы с ними иллюстрирует язык ML (Gordon, Milner, and Wadsworth 1979), в котором «полиморфные типы данных» включают шаблоны для преобразований между типами данных высшего уровня. Более того, для большинства процедур в ML типы данных явно не определяются программистом. Вместо этого в ML встроен механизм вывода типов (type inference), который при помощи контекстной информации вычисляет типы данных для вновь определяемых процедур.

автоматически задерживаются, и вынуждение происходит только тогда, когда их значения реально нужны (например, для выполнения элементарной операции). Таким образом наш язык станет использовать нормальный порядок вычислений, который мы впервые описали, когда разговор шел о подстановочной модели вычислений в разделе 1.1.5. Переход к нормальному порядку вычислений предоставляет нам изящный и единообразный способ упростить использование задержанных вычислений, и если бы нас интересовала только обработка потоков, было бы естественно принять эту стратегию. В разделе 4.2, после того, как мы изучим устройство вычислителя, мы увидим, как можно преобразовать язык именно таким способом. К сожалению, добавив задержки в вызовы процедур, мы совершенно лишили себя возможности строить программы, работа которых зависит от порядка событий, то есть программы, использующие присваивание, изменяющие свои данные или производящие ввод-вывод. Одно-единственное использование delay в форме cons-stream уже может привести к неразберихе, как показано в упражнениях 3.51 и 3.52. Насколько известно, в языках программирования изменение состояния и задержанные вычисления плохо совместимы, и поиск возможностей использовать одновременно и то, и другое является активной областью исследований.

3.5.5 Модульность функциональных программ и модульность объектов

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

Главная задача при обеспечении модульности состояла в том, что нам хотелось спрятать внутреннее состояние генератора случайных чисел от программ, которые пользуются случайными числами. Мы начали с процедуры rand-update, последовательные значения которой служили для нас источником случайных чисел, и уже с ее помощью построили генератор случайных чисел:

(define rand

(let ((x random-init)) (lambda ()

(set! x (rand-update x))

x)))

При формулировке посредством потоков генератора случайных чисел как такового не существует, имеется только поток случайных чисел, полученных вызовами rand-update:

(define random-numbers (cons-stream random-init

(stream-map rand-update random-numbers)))

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

(define cesaro-stream

(map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1))

random-numbers))

(define (map-successive-pairs f s) (cons-stream (f (stream-car s) (stream-car (stream-cdr s))) (map-successive-pairs f (stream-cdr (stream-cdr s)))))

Поток cesaro-stream подается на вход процедуре monte-carlo, которая порождает поток оценок вероятности. Затем этот результат преобразуется, и получается поток оценок значения п. В этой версии программы не требуется параметра, указывающего, сколько испытаний требуется проводить. Более точные оценки п (полученные при большем количестве испытаний) можно получить, дальше заглянув в поток pi:

(define (monte-carlo experiment-stream passed failed) (define (next passed failed) (cons-stream (/ passed (+ passed failed)) (monte-carlo (stream-cdr experiment-stream) passed failed))) (if (stream-car experiment-stream) (next (+ passed 1) failed) (next passed (+ failed 1))))

(define pi

(stream-map (lambda (p) (sqrt (/ 6 p)))

(monte-carlo cesaro-stream 0 0)))

Такой подход достаточно модулен, поскольку мы по-прежнему имеем возможность сформулировать общую процедуру monte-carlo, работающую с произвольными испытаниями. Однако здесь нет ни присваивания, ни внутреннего состояния.

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

В упражнении 3.6 обсуждалась возможность обобщить генератор случайных чисел и позволить пользователю сбрасывать последовательность случайных чисел, так, чтобы можно было порождать воспроизводимые «случайные» последовательности. Постройте потоковый вариант такой же процедуры-генератора, которая работает со входным потоком запросов вида generate - породить новое число, либо reset - сбросить последовательность в нужную точку, и которая порождает требуемый поток случайных чисел. Не используйте в своем решении присваивание.

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

Переделайте на основе потоков упражнение 3.5 на интегрирование методом Монте-Карло. Потоковая версия процедуры estimate-integral не требует аргумента, который говорит, сколько проводить испытаний. Вместо этого она порождает поток оценок, основанных на все большем количестве испытаний.

Взгляд на время в функциональном программировании

Вернемся теперь к вопросам об объектах и изменении, поднятым в начале этой главы, и рассмотрим их в новом свете. Мы ввели присваивание и изме-