Каждый вызов acc возвращает локально определенную процедуру deposit или withdraw, которая затем применяется к указанной сумме. Точно так же, как это было с make-withdraw, второй вызов make-account

(define acc2 (make-account i00))

создает совершенно отдельный объект-счет, который поддерживает свою собственную переменную balance.

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

Накопитель (accumulator) - это процедура, которая вызывается с одним численным аргументом и собирает свои аргументы в сумму. При каждом вызове накопитель возвращает сумму, которую успел накопить. Напишите процедуру make-accumulator, порождающую накопители, каждый из которых поддерживает свою отдельную сумму. Входной параметр make-accumulator должен указывать начальное значение суммы; например,

(define A (make-accumulator 5))

(A i0)

15

(A i0)

25

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

При тестировании программ удобно иметь возможность подсчитывать, сколько раз за время вычислений была вызвана та или иная процедура. Напишите процедуру make-monitored, принимающую в качестве параметра процедуру f, которая сама по себе принимает один входной параметр. Результат, возвращаемый make-monitored - третья процедура, назовем ее mf, которая подсчитывает, сколько раз она была вызвана, при помощи внутреннего счетчика. Если на входе mf получает специальный символ how-many-calls?, она возвращает значение счетчика. Если же на вход подается специальный символ reset-count, mf обнуляет счетчик. Для любого другого параметра mf возвращает результат вызова f с этим параметром и увеличивает счетчик. Например, можно было бы сделать отслеживаемую версию процедуры sqrt:

(define s (make-monitored sqrt))

(s i00) 10

(s how-many-calls?)

1

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

Измените процедуру make-account так, чтобы она создавала счета, защищенные паролем. А именно, make-account должна в качестве дополнительного аргумента принимать символ, например

(define acc (make-account i00 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, которая обладает следующим свойством: если мы начинаем с некоторого данного числа xi и строим последовательность

x2= (rand-update x1) x3= (rand-update x2)

то последовательность величин x1 ,х2,хз... будет обладать требуемыми математическими свойствами.6

Мы можем реализовать rand как процедуру с внутренней переменной состояния x, которая инициализируется некоторым заранее заданным значением random-init. Каждый вызов rand вычисляет rand-update от текущего значения x, возвращает это значение как случайное число, и, кроме того, сохраняет его как новое значение x.

(define rand

(let ((x random-init))

6Один из распространенных способов реализации rand-update состоит в том, чтобы положить новое значение x равным ax + b mod m, где a, b и m - соответствующим образом подобранные целые числа. Глава 3 книги Knuth 1981 содержит подробное обсуждение методов порождения последовательностей случайных чисел и обеспечения их статистических свойств. Обратите внимание, что rand-update вычисляет математическую функцию: если ей дважды дать один и тот же вход, она вернет одинаковый результат. Таким образом, последовательность чисел, порождаемая rand-update, никоим образом не «случайна», если мы настаиваем на том, что в последовательности «случайных» чисел следующее число не должно иметь никакого отношения к предыдущему. Отношение между «настоящей» случайностью и так называемыми псевдослучайными (pseudo-random) последовательностями, которые порождаются путем однозначно определенных вычислений и тем не менее обладают нужными статистическими свойствами, - непростой вопрос, связанный со сложными проблемами математики и философии. Для прояснения этих вопросов много сделали Колмогоров, Соломонофф и Хайтин; обсуждение можно найти в Chaitin 1975.

(lambda ()

(set! x (rand-update x)) x)))

Разумеется, ту же последовательность случайных чисел мы могли бы получить без использования присваивания, просто напрямую вызывая rand-update. Однако это означало бы, что всякая часть программы, которая использует случайные числа, должна явно запоминать текущее значение x, чтобы передать его как аргумент rand-update. Чтобы понять, насколько это было бы неприятно, рассмотрим использование случайных чисел для реализации т. н. моделирования методом Монте-Карло (Monte Carlo simulation).

Метод Монте-Карло состоит в том, чтобы случайным образом выбирать тестовые точки из большого множества и затем делать выводы на основании вероятностей, оцениваемых по результатам тестов. Например, можно получить приближенное значение п, используя тот факт, что для двух случайно выбранных целых чисел вероятность отсутствия общих множителей (то есть, вероятность того, что их наибольший общий делитель будет равен 1) составляет 6/п2.7 Чтобы получить приближенное значение п, мы производим большое количество тестов В каждом тесте мы случайным образом выбираем два числа и проверяем, не равен ли их НОД единице. Доля тестов, которые проходят, дает нам приближение к 6/п2, и отсюда мы получаем приближенное значение п.

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

(define (estimate-pi trials)

(sqrt (/ 6 (monte-carlo trials cesaro-test))))

(define (cesaro-test)

(= (gcd (rand) (rand)) i))

(define (monte-carlo trials experiment)

(define (iter trials-remaining trials-passed) (cond ((= trials-remaining 0)

(/ trials-passed trials)) ((experiment)

(iter (- trials-remaining i) (+ trials-passed i))) (else

(iter (- trials-remaining i) trials-passed)))) (iter trials 0))

Теперь попробуем осуществить то же вычисление, используя rand-update вместо rand, как нам пришлось бы поступить, если бы у нас не было присваивания для моделирования локального состояния:

(define (estimate-pi trials)

(sqrt (/ 6 (random-gcd-test trials random-init))))

7Эта теорема доказана Э. Чезаро. Обсуждение и доказательство можно найти в разделе 4.5.2 книги Knuth 1981.