SICP по-русски

суббота, 8 января 2011 г.

Exercise-3.9-3.11

В этих упражнениях надо рисовать диаграммки. Их можна посмотреть у Эли. Перед просмотром, разумеется, следует прорешать самостоятельно)

Когда в разделе 1.1.3 мы определяли модель вычислений, мы сказали, что первым шагом при вычислении выражения является вычисление его подвыражений. Однако мы нигде не указали порядок, в котором проходит вычисление подвыражений (слева направо или справа налево). Когда мы вводим присваивание, порядок, в котором вычисляются аргументы процедуры, может повлиять на результат. Определите простую процедуру f, так, чтобы вычисление (+ (f 0) (f 1)) возвращало 0, если аргументы + вычисляются слева направо, и 1, если они вычисляются справа налево.

Вопрос может показаться не существенным, но в таком языке как С++ порядок вызова для такого случая не определен и программа (теоретически) может вести себе по разному от выполнения к выполнении. После этого упражнения мы должны сделать вывод что писать программы зависящие от описываемого порядко не хорошо) Приступим к выполнению

Определим функцию, которая при нечетных вызовах (первый, третий и тд раз) возвращает параметр, а при четных (второй, четвертый и тд) возвращает 0. Это можно сделать множеством способов. Вот один из них

(define f

(let ((trigger false))

(λ (a)

(set! trigger (not trigger))

(if trigger a 0))))

Проводим эксперимент

(+ (f 0) (f 1)) ;0

Как видим, аргументы вычисляются слева направо.

Можно обобщить это наблюдение для большего количества аргументов

(define f

(let ((counter 0))

(λ (a)

(set! counter (+ counter 1))

counter)))

(define (foo first . rest)

(cons first rest))

(foo (f 100) (f 100) (f 100) (f 100) (f 100) (f 100) (f 100) (f 100))

где возвращает какой раз ее вызывают

Exercise-3-07

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

Рассмотрим объекты-банковские счета, создаваемые процедурой make-account, и снабженные паролями, как это описано в упражнении 3.3. Предположим, что наша банковская система требует от нас умения порождать совместные счета. Напишите процедуру make-joint, которая это делает. Make-joint должна принимать три аргумента. Первый из них — защищенный паролем счет. Второй обязан совпадать с паролем, с которым этот счет был создан, иначе make-joint откажется работать. Третий аргумент — новый пароль. Например, если банковский счет peter-account был создан с паролем open-sesame, то

(define paul-acc (make-joint peter-acc ’open-sesame ’rosebud))

позволит нам проводить операции с peter-account, используя имя paul-acc и пароль rosebud. Вам может потребоваться переработать решение упражнения 3.3, чтобы добавить эту новую возможность.

Может понадобится результат упражнения 3.3, но мы воспользуемся результатами 3.4, так как оно написано почище. В этом случае нам совершенно не надо его перерабатывать, пишем решение в лоб

(define (make-joint orig orig-pass joined-pass)

(λ (pass . args)

(if (eq? pass joined-pass)

(apply orig (cons orig-pass args))

wrong-pass)))

Предварительна вынеся функцию сообщения неправильного пароля

(define (wrong-pass arg . other) "Неверный пароль")

Тестируем

(define peter-acc (make-account 100 'open-sesame))

(define paul-acc (make-joint peter-acc 'open-sesame 'rosebud))

((peter-acc 'open-sesame 'deposit) 10) ; 110

((peter-acc 'open-sesame 'deposit) 20) ;130

((paul-acc 'rosebud 'withdraw) 5) ;125

((peter-acc 'open-sesame 'deposit) 20) ;145

Как видим, Полу удалось опустошить кошелек Питера на 5 у.е.

Exercise-3-06

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

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

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

Ух и довелось мне помучаться с этим, казалось бы, не сложным упражнением. Сложность его в том, что до этого в книги мы создавали некоторую функцию-фабрику и инкапсулировали в ней состояние. Тут такой прием не прокатывает. Интересно, что на том блоге где я сверял решение эта задача пропущена. Итак решение с новым способом объявления функций. Тут мы превратили rand в “фабрику” и функцию использующую состояние одновременно. random-val возвращает следующее случайное число.

(define rand

(let ((previous 0))

(λ (dispatcher)

(cond ((eq? dispatcher 'generate)

(set! previous (random-val previous))

previous)

((eq? dispatcher 'reset)

(λ(new-val)(set! previous new-val) ))

(else (error "Illegal message"))))))

Exercise-3-05

Упражнение 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, которая возвращает неотрицательное число меньше своего аргумента.

(define (random-in-range low high)

(let ((range (- high low)))

(+ low (random range))))

две функции. Интегрирование

(define (estimate-integral predicate x-low y-low x-high y-high trials)

(define (some-circle x y)

(<= (+ (square (- x 5)) (square (- y 7))) 9))

(let ((rectangle-area (* (- x-high x-low) (- y-high y-low))))

(* rectangle-area (monte-carlo trials

(λ () (predicate

(random-in-range x-low x-high)

(random-in-range y-low y-high)))))))

(estimate-integral some-circle 2 4 8 10 1000000)

И нахождение ПИ

(define (calc-pi trials)

(define (unit-circle-predivate x y)

(<= (+ (square x) (square y)) 1))

(let ((unit-area 4.0))

(* unit-area (monte-carlo trials

(λ () (unit-circle-predivate

(random-in-range -1 1)

(random-in-range -1 1)))))))

(calc-pi 10000000)

пятница, 7 января 2011 г.

How I can get an exact integer from floating point number?

Первые разочарование в столь прекрасном языке. Дабы округлить нормально число надо воротить вот такие конструкции

(random (inexact->exact (round 10.0))))

P.S. У меня DrRacket, в других диалектах может есть что-то попроще.

Exercise-3-04

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

Модифицируйте процедуру make-account из упражнения 3.3, добавив еще одну локальную пе-

ременную, так, чтобы, если происходит более семи попыток доступа подряд с неверным паролем,

вызывалась процедура call-the-cops (вызвать полицию).

Решение в лоб

(define max-tryes 7)

(define (call-the-cops arg1 . args) (error "За вами уже выехали"))

(define (make-account balance password)

(define (withdraw amount)

(if (>= balance amount)

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

"Недостаточно денег на счете"))

(define (deposit amount) (set! balance (+ balance amount)) balance)

(let ((wrong-tryes 0))

(define (dispatch pass m)

(if (eq? pass password)

(begin

(set! wrong-tryes 0)

(cond ((eq? m 'withdraw) withdraw)

((eq? m 'deposit) deposit)

(else (error "Неизвестный вызов -- MAKE-ACCOUNT" m))))

(begin (set! wrong-tryes (+ wrong-tryes 1))

(if (> wrong-tryes max-tryes) call-the-cops (λ(arg . other)"Неверный пароль")))))

dispatch))

Но, на самом деле, не для таких решений мы эту книгу читали. Задачи диспетчеризации и ограничения доступа совсем разные и никак не могут укладываться в одной функции написанной программистом в здравом уме.

Вынесем логику по проверке пароля в отдельную функцию

(define (password-checker-wrapper func password max-tryes)

(define (call-the-cops arg1 . args) (error "За вами уже выехали"))

(let ((wrong-tryes 0))

(λ (pass . args)

(cond ((eq? pass password) (begin (set! wrong-tryes 0)(apply func args)))

((= wrong-tryes max-tryes) call-the-cops)

(else (begin (set! wrong-tryes(+ wrong-tryes 1))

(λ(arg . other)"Неверный пароль")))))))

После этого мы можем вернуть make-accountпочти в первозданное состояние лишь завернув dispatch (который остается таким же как и до введение политики безопасности)