(define (random-gcd-test trials initial-x)

(define (iter trials-remaining trials-passed x) (let ((x1 (rand-update x))) (let ((x2 (rand-update xl))) (cond ((= trials-remaining 0)

(/ trials-passed trials)) ((= (gcd xl x2) 1) (iter (- trials-remaining 1) (+ trials-passed 1)

x2))

(else

(iter (- trials-remaining 1) trials-passed

x2))))))

(iter trials 0 initial-x))

Хотя программа по-прежнему проста, в ней обнаруживается несколько болезненных нарушений принципа модульности. В первой версии программы нам удалось, используя rand, выразить метод Монте-Карло напрямую как обобщенную процедуру monte-carlo, которая в качестве аргумента принимает произвольную процедуру experiment. Во втором варианте программы, где у генератора случайных чисел нет локального состояния, random-gcd-test приходится непосредственно возиться со случайными числами x1 и x2 и передавать в итеративном цикле x2 в качестве нового входа rand-update. Из-за того, что обработка случайных чисел происходит явно, структура накопления результатов тестов начинает зависеть от того, что наш тест использует именно два случайных числа, тогда как для других тестов Монте-Карло может потребоваться, скажем, одно или три. Даже процедура верхнего уровня estimate-pi вынуждена заботиться о том, чтобы предоставить начальное значение случайного числа. Поскольку внутренности генератора случайных чисел просачиваются наружу в другие части программы, задача изолировать идею метода Монте-Карло так, чтобы применять ее затем к другим задачам, осложняется. В первом варианте программы присваивание инкапсулирует состояние генератора случайных чисел внутри процедуры rand, так что состояние генератора остается независимым от остальной программы.

Общее явление, которое мы наблюдаем на примере с методом Монте-Карло, таково: с точки зрения одной части сложного процесса кажется, что другие части изменяются со временем. Они обладают скрытым локальным состоянием. Если мы хотим, чтобы структура программ, которые мы пишем, отражала такое разделение на части, мы создаем вычислительные объекты (например, банковские счета или генераторы случайных чисел), поведение которых изменяется со временем. Состояние мы моделируем при помощи локальных переменных, а изменение состояния - при помощи присваивания этим переменным.

Здесь возникает соблазн закрыть обсуждение и сказать, что, введя присваивание и метод сокрытия состояния в локальных переменных, мы обретаем способность структурировать системы более модульным образом, чем если бы нам пришлось всем состоянием манипулировать явно, с передачей дополнительных параметров. К сожалению, как мы увидим, все не так просто.

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

Интегрирование методом Монте-Карло (Monte Carlo integration) - способ приближенного вычисления определенных интегралов при помощи моделирования методом Монте-Карло. Рассмотрим задачу вычисления площади фигуры, описываемой предикатом P(x, у), который истинен для точек (x,у), принадлежащих фигуре, и ложен для точек вне фигуры. Например, область, содержащаяся в круге с радиусом 3 и центром в точке (5, 7), описывается предикатом, проверяющим (x - 5)2 + (у - 7)2 < 32. Чтобы оценить площадь фигуры, описываемой таким предикатом, для начала выберем прямоугольник, который содержит нашу фигуру. Например, прямоугольник с углами (2, 4) и (8,10), расположенными по диагонали, содержит вышеописанный круг. Нужный нам интеграл - площадь той части прямоугольника, которая лежит внутри фигуры. Мы можем оценить интеграл, случайным образом выбирая точки (x,y), лежащие внутри прямоугольника, и проверяя для каждой точки P(x,y), чтобы определить, лежит ли точка внутри фигуры. Если мы проверим много точек, доля тех, которые окажутся внутри области, даст нам приближенное значение отношения площадей фигуры и прямоугольника. Таким образом, домножив это значение на площадь прямоугольника, мы получим приближенное значение интеграла.

Реализуйте интегрирование методом Монте-Карло в виде процедуры estimate-integral, которая в качестве аргументов принимает предикат P, верхнюю и нижнюю границы прямоугольника xi, x2, yi и y2, а также число проверок, которые мы должны осуществить, чтобы оценить отношение площадей. Ваша процедура должна использовать ту же самую процедуру monte-carlo, которая выше использовалась для оценки значения п. Оцените п при помощи estimate-integral, измерив площадь единичного круга.

Вам может пригодиться процедура, которая выдает число, случайно выбранное внутри данного отрезка. Нижеприведенная процедура random-in-range решает эту задачу, используя процедуру random, введенную в разделе 1.2.6, которая возвращает неотрицательное число меньше своего аргумента.8

(define (random-in-range low high) (let ((range (- high low))) (+ low (random range))))

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

Полезно иметь возможность сбросить генератор случайных чисел, чтобы получить последовательность, которая начинается с некоторого числа. Постройте новую процедуру rand, которая вызывается с аргументом. Этот аргумент должен быть либо символом generate, либо символом reset. Процедура работает так: (rand generate) порождает новое случайное число; ((rand reset) (новое-значение)) сбрасывает внутреннюю переменную состояния в указанное (новое-значение). Таким образом, сбрасывая значения, можно получать повторяющиеся последовательности. Эта возможность очень полезна при тестировании и отладке программ, использующих случайные числа.

3.1.3 Издержки, связанные с введением присваивания

Как мы только что видели, операция set! позволяет моделировать объекты, обладающие внутренним состоянием. Однако за это преимущество приходится платить. Наш язык программирования нельзя больше описывать при помощи подстановочной модели применения процедур, которую мы ввели в

8В MIT Scheme есть такая процедура. Если random на вход дается точное целое число (как в разделе 1.2.6), она возвращает точное целое число, но если ей дать десятичную дробь (как в этом примере), она и возвращает десятичную дробь.

разделе 1.1.5. Хуже того, не существует простой модели с «приятными» математическими свойствами, которая бы адекватно описывала работу с объектами и присваивание в языках программирования.

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

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

(define (make-simplified-withdraw balance) (lambda (amount)

(set! balance (- balance amount)) balance))

(define W (make-simplified-withdraw 25)) (W 20)

5

(W 10)

-5

Сравним эту процедуру со следующей процедурой make-decrementer, которая не использует set!:

(define (make-decrementer balance) (lambda (amount)

(- balance amount)))

make-decrementer возвращает процедуру, которая вычитает свой аргумент из определенного числа balance, но при последовательных вызовах ее действие не накапливается, как при использовании make-simplified-with-draw:

(define D (make-decrementer 25)) (D 20)

5

(D 10) 15

Мы можем объяснить, как работает make-decrementer, при помощи подстановочной модели. Например, рассмотрим, как вычисляется выражение

((make-decrementer 25) 20)

Сначала мы упрощаем операторную часть комбинации, подставляя в теле make-decrementer вместо balance 25. Выражение сводится к