Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 76
Текст из файла (страница 76)
Переход к нормальному порядкувычислений предоставляет нам изящный и единообразный способ упростить использование задержанных вычислений, и если бы нас интересовала только обработка потоков,было бы естественно принять эту стратегию. В разделе 4.2, после того, как мы изучим устройство вычислителя, мы увидим, как можно преобразовать язык именно такимспособом. К сожалению, добавив задержки в вызовы процедур, мы совершенно лишили себя возможности строить программы, работа которых зависит от порядка событий,программисту нужно указывать типы данных для аргументов и результата каждой процедуры: число, логическое значение, последовательность и т.
д. Следовательно, мы не можем выразить такую абстракцию, как«применить данную процедуру proc ко всем элементам последовательности» в виде единой процедуры высшего порядка вроде stream-map. Вместо этого нам потребуется отдельная процедура для каждой комбинациитипов аргументов и результата, которые можно указать для proc. Практическая поддержка понятия «типданных» при наличии процедур высших порядков приводит ко многим интересным проблемам. Один из способов работы с ними иллюстрирует язык ML (Gordon, Milner, and Wadsworth 1979), в котором «полиморфныетипы данных» включают шаблоны для преобразований между типами данных высшего уровня.
Более того,для большинства процедур в ML типы данных явно не определяются программистом. Вместо этого в MLвстроен механизм вывода типов (type inference), который при помощи контекстной информации вычисляеттипы данных для вновь определяемых процедур.330Глава 3. Модульность, объекты и состоянието есть программы, использующие присваивание, изменяющие свои данные или производящие ввод-вывод. Одно-единственное использование 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)))При формулировке посредством потоков генератора случайных чисел как таковогоне существует, имеется только поток случайных чисел, полученных вызовами randupdate:(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)))))3.5.
Потоки331Поток 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 не требует аргумента, который говорит, сколькопроводить испытаний. Вместо этого она порождает поток оценок, основанных на все большемколичестве испытаний.Взгляд на время в функциональном программированииВернемся теперь к вопросам об объектах и изменении, поднятым в начале этой главы, и рассмотрим их в новом свете.
Мы ввели присваивание и изменяемые объекты,чтобы иметь механизм для модульного построения программ, которые моделируют обладающие состоянием системы. Мы порождали вычислительные объекты с внутреннимипеременными состояния и изменяли эти объекты при помощи присваивания. Мы моделировали временно́е поведение объектов мира через временное поведение соответствующихвычислительных объектов.332Глава 3. Модульность, объекты и состояниеТеперь мы видим, что потоки дают альтернативный способ моделирования объектов,обладающих внутренним состоянием. Можно моделировать изменяющуюся величину,например, внутреннее состояние какого-либо объекта, через поток, который представляетдинамику изменений состояния. В сущности, с помощью потоков мы представляем времяявно, так что время в моделируемом мире оказывается отделено от последовательностисобытий, происходящих во время вычисления.
Действительно, благодаря наличию delayмежду имитируемым временем модели и последовательностью событий при вычисленииможет быть весьма мало общего.Чтобы сопоставить эти два подхода к моделированию, рассмотрим еще раз «обработчик снятия денег», следящий за значением баланса на банковском счету. В разделе 3.1.3мы реализовали упрощенную версию такой программы обработки:(define (make-simplified-withdraw balance)(lambda (amount)(set! balance (- balance amount))balance))Вызовы make-simplified-withdraw порождают вычислительные объекты, и каждыйиз них содержит внутреннюю переменную balance, которая уменьшается при каждомобращении к объекту.
Этот объект принимает в качестве аргумента количество денегamount, а возвращает новый баланс. Можно представить себе, как пользователь банковского счета печатает последовательность входных данных для такого объекта и рассматривает на экране дисплея последовательность возвращаемых данных.С другой стороны, можно смоделировать обработчик снятия денег и в виде процедуры, которая принимает на входе баланс и поток снимаемых сумм, а порождает потокпоследовательных балансов на счету:(define (stream-withdraw balance amount-stream)(cons-streambalance(stream-withdraw (- balance (stream-car amount-stream))(stream-cdr amount-stream))))Stream-withdraw реализует хорошо определенную математическую функцию, выход которой полностью определяется входом.
Однако предположим, что вход amountstream есть поток последовательных значений, вводимых пользователем, и что получающийся поток балансов выводится на печать. В таком случае, с точки зрения пользователя, который печатает значения и смотрит на результаты, потоковый процесс обладает темже поведением, что и объект, созданный при помощи make-simplified-withdraw.Однако в потоковой версии нет ни присваивания, ни внутренней переменной состояния,и, следовательно, она не вызывает никаких теоретических сложностей из описанных вразделе 3.1.3. И все-таки система обладает состоянием!Это достижение достойно внимания.
Несмотря на то, что stream-withdraw реализует хорошо определенную математическую функцию, поведение которой не меняется,у пользователя создается впечатление, что он взаимодействует с системой, обладающейизменяющимся состоянием. Один из способов разрешить парадокс заключается в том,чтобы понять, что именно существование пользователя во времени навязывает системе состояние. Если бы пользователь мог принять более отстраненную точку зрения и3.5.
Потоки333запросы Петразапросы ПавласлияниебанковскийсчетРис. 3.38. Совместный банковский счет, смоделированный через слияние двух потоковсобытий-транзакций.думать в терминах потоков и балансов, а не отдельных актов взаимодействия, системавыглядела бы как объект без состояния73 .С точки зрения одной части сложного процесса кажется, что другие его части меняются со временем. Они содержат скрытое изменчивое внутреннее состояние. Еслимы хотим писать программы, моделирующие такой тип естественной декомпозиции нашего мира (как мы видим его со своей точки зрения, будучи частицами этого мира)при помощи структур в нашем компьютере, мы строим вычислительные объекты, неявляющиеся функциональными, — они обязаны меняться со временем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
