Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 52
Текст из файла (страница 52)
Модульность, объекты и состояние(define acc (make-account 100 ’secret-password))Получившийся объект-счет должен обрабатывать запросы, только если они сопровождаются паролем, с которым счет был создан, а в противном случае он должен жаловаться:((acc ’secret-password ’withdraw) 40)60((acc ’some-other-password ’deposit) 50)"Неверный пароль"Упражнение 3.4.Модифицируйте процедуру make-account из упражнения 3.3, добавив еще одну локальную переменную, так, чтобы, если происходит более семи попыток доступа подряд с неверным паролем,вызывалась процедура call-the-cops (вызвать полицию).3.1.2.
Преимущества присваиванияКак нам предстоит увидеть, введение присваивания в наш язык программированияведет к множеству сложных концептуальных проблем. Тем не менее, представление осистеме как о наборе объектов, имеющих внутреннее состояние, — мощное средство дляобеспечения модульности проекта. В качестве примера рассмотрим строение процедурыrand, которая, будучи вызванной, каждый раз возвращает случайное целое число.Вовсе не так просто определить, что значит «случайное». Вероятно, имеется в виду,что последовательные обращения к rand должны порождать последовательность чисел,которая обладает статистическими свойствами равномерного распределения.
Здесь мыне будем обсуждать способы порождения подобных последовательностей. Вместо этогопредположим, что у нас есть процедура rand-update, которая обладает следующимсвойством: если мы начинаем с некоторого данного числа x1 и строим последовательностьx2 = (rand-update x1 )x3 = (rand-update x2 )то последовательность величин x1 , x2 , x3 .
. . будет обладать требуемыми математическими свойствами6 .Мы можем реализовать rand как процедуру с внутренней переменной состоянияx, которая инициализируется некоторым заранее заданным значением random-init.Каждый вызов rand вычисляет rand-update от текущего значения x, возвращает этозначение как случайное число, и, кроме того, сохраняет его как новое значение x.6 Один из распространенных способов реализации rand-update состоит в том, чтобы положить новое значение x равным ax + b mod m, где a, b и m — соответствующим образом подобранные целые числа.
Глава 3книги Knuth 1981 содержит подробное обсуждение методов порождения последовательностей случайных чисели обеспечения их статистических свойств. Обратите внимание, что rand-update вычисляет математическуюфункцию: если ей дважды дать один и тот же вход, она вернет одинаковый результат. Таким образом, последовательность чисел, порождаемая rand-update, никоим образом не «случайна», если мы настаиваем натом, что в последовательности «случайных» чисел следующее число не должно иметь никакого отношения кпредыдущему. Отношение между «настоящей» случайностью и так называемыми псевдослучайными (pseudorandom) последовательностями, которые порождаются путем однозначно определенных вычислений и тем неменее обладают нужными статистическими свойствами, — непростой вопрос, связанный со сложными проблемами математики и философии.
Для прояснения этих вопросов много сделали Колмогоров, Соломонофф иХайтин; обсуждение можно найти в Chaitin 1975.3.1. Присваивание и внутреннее состояние объектов219(define rand(let ((x random-init))(lambda ()(set! x (rand-update x))x)))Разумеется, ту же последовательность случайных чисел мы могли бы получить безиспользования присваивания, просто напрямую вызывая rand-update. Однако этоозначало бы, что всякая часть программы, которая использует случайные числа, должнаявно запоминать текущее значение x, чтобы передать его как аргумент rand-update.Чтобы понять, насколько это было бы неприятно, рассмотрим использование случайных чисел для реализации т. н. моделирования методом Монте-Карло (Monte Carlosimulation).Метод Монте-Карло состоит в том, чтобы случайным образом выбирать тестовыеточки из большого множества и затем делать выводы на основании вероятностей, оцениваемых по результатам тестов.
Например, можно получить приближенное значение π,используя тот факт, что для двух случайно выбранных целых чисел вероятность отсутствия общих множителей (то есть, вероятность того, что их наибольший общий делительбудет равен 1) составляет 6/π 27 . Чтобы получить приближенное значение π, мы производим большое количество тестов. В каждом тесте мы случайным образом выбираем двачисла и проверяем, не равен ли их НОД единице.
Доля тестов, которые проходят, даетнам приближение к 6/π 2 , и отсюда мы получаем приближенное значение π.В центре нашей программы находится процедура monte-carlo, которая в качествеаргументов принимает количество попыток тестирования, а также сам тест — процедурубез аргументов, возвращающую при каждом вызове либо истину, либо ложь.
Montecarlo запускает тест указанное количество раз и возвращает число, обозначающеедолю попыток, в которых тест вернул истинное значение.(define (estimate-pi trials)(sqrt (/ 6 (monte-carlo trials cesaro-test))))(define (cesaro-test)(= (gcd (rand) (rand)) 1))(define (monte-carlo trials experiment)(define (iter trials-remaining trials-passed)(cond ((= trials-remaining 0)(/ trials-passed trials))((experiment)(iter (- trials-remaining 1) (+ trials-passed 1)))(else(iter (- trials-remaining 1) trials-passed))))(iter trials 0))Теперь попробуем осуществить то же вычисление, используя rand-update вместоrand, как нам пришлось бы поступить, если бы у нас не было присваивания для моделирования локального состояния:7 Эта теорема доказана Э.
Чезаро. Обсуждение и доказательство можно найти в разделе 4.5.2 книги Knuth1981.220Глава 3. Модульность, объекты и состояние(define (estimate-pi trials)(sqrt (/ 6 (random-gcd-test trials random-init))))(define (random-gcd-test trials initial-x)(define (iter trials-remaining trials-passed x)(let ((x1 (rand-update x)))(let ((x2 (rand-update x1)))(cond ((= trials-remaining 0)(/ trials-passed trials))((= (gcd x1 x2) 1)(iter (- trials-remaining 1)(+ trials-passed 1)x2))(else(iter (- trials-remaining 1)trials-passedx2))))))(iter trials 0 initial-x))Хотя программа по-прежнему проста, в ней обнаруживается несколько болезненныхнарушений принципа модульности.
В первой версии программы нам удалось, используя rand, выразить метод Монте-Карло напрямую как обобщенную процедуру montecarlo, которая в качестве аргумента принимает произвольную процедуру experiment.Во втором варианте программы, где у генератора случайных чисел нет локального состояния, random-gcd-test приходится непосредственно возиться со случайными числамиx1 и x2 и передавать в итеративном цикле x2 в качестве нового входа rand-update.Из-за того, что обработка случайных чисел происходит явно, структура накопления результатов тестов начинает зависеть от того, что наш тест использует именно два случайных числа, тогда как для других тестов Монте-Карло может потребоваться, скажем,одно или три. Даже процедура верхнего уровня estimate-pi вынуждена заботиться отом, чтобы предоставить начальное значение случайного числа.
Поскольку внутренностигенератора случайных чисел просачиваются наружу в другие части программы, задачаизолировать идею метода Монте-Карло так, чтобы применять ее затем к другим задачам, осложняется. В первом варианте программы присваивание инкапсулирует состояниегенератора случайных чисел внутри rand, так что состояние генератора остается независимым от остальной программы.Общее явление, наблюдаемое на примере с методом Монте-Карло, таково: с точкизрения одной части сложного процесса кажется, что другие части изменяются со временем.
Они обладают скрытым локальным состоянием. Если мы хотим, чтобы структурапрограмм, которые мы пишем, отражала такое разделение на части, мы создаем вычислительные объекты (например, банковские счета или генераторы случайных чисел), поведение которых изменяется со временем. Состояние мы моделируем при помощи локальныхпеременных, а изменение состояния — при помощи присваивания этим переменным.Здесь возникает соблазн закрыть обсуждение и сказать, что, введя присваивание иметод сокрытия состояния в локальных переменных, мы обретаем способность структурировать системы более модульным образом, чем если бы нам пришлось всем состояниемманипулировать явно, с передачей дополнительных параметров.
К сожалению, как мыувидим, все не так просто.3.1. Присваивание и внутреннее состояние объектов221Упражнение 3.5.Интегрирование методом Монте-Карло (Monte Carlo integration) — способ приближенного вычисления определенных интегралов при помощи моделирования методом Монте-Карло. Рассмотрим задачу вычисления площади фигуры, описываемой предикатом P (x, y), который истинен дляточек (x, y), принадлежащих фигуре, и ложен для точек вне фигуры. Например, область, содержащаяся в круге с радиусом 3 и центром в точке (5, 7), описывается предикатом, проверяющим(x − 5)2 + (y − 7)2 ≤ 32 . Чтобы оценить площадь фигуры, описываемой таким предикатом, для начала выберем прямоугольник, который содержит нашу фигуру.
Например, прямоугольник с углами(2, 4) и (8, 10), расположенными по диагонали, содержит вышеописанный круг. Нужный нам интеграл — площадь той части прямоугольника, которая лежит внутри фигуры. Мы можем оценитьинтеграл, случайным образом выбирая точки (x, y), лежащие внутри прямоугольника, и проверяядля каждой точки P (x, y), чтобы определить, лежит ли точка внутри фигуры. Если мы провериммного точек, доля тех, которые окажутся внутри области, даст нам приближенное значение отношения площадей фигуры и прямоугольника. Таким образом, домножив это значение на площадьпрямоугольника, мы получим приближенное значение интеграла.Реализуйте интегрирование методом Монте-Карло в виде процедуры estimateintegral, которая в качестве аргументов принимает предикат P, верхнюю и нижнюю границы прямоугольникаx1, x2, y1 и 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, котораявызывается с аргументом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
