Exercise-3-21

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

Определите

процедуру print-queue, которая берет на входе очередь и выводит на печать последовательность

ее элементов.

Она могла бы выглядеть как-то так

(define (print-queue queue)
  (define (helper q)
    (if (not (null? q))
        (begin
          (display " " )
          (display (car q))
          (helper (cdr q)))))
    (display "(")
    (helper (front-ptr q))
    (display ")")
    (newline))

Exercise-3.18,3.19

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

Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, то есть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь по полям cdr, в бесконечный цикл.

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

Переделайте упражнение 3.18, используя фиксированное количество памяти.

Вот эти решения, Первый вариант логическая модификация предыдущего упражнения, а второй реализация классического алгоритма.

Этот алгоритм заключается в том, что мы пускаем вперед быстрого бегуна и, если он настигнет медленного, то значит он пробежал по замкнутой траектории. Отдельно стоит заметить что данные решения работают только для структур где car любого элемента не является парой.

(define (circles? x)

  (define (contains? what where)

    (cond

      ((null? where) #f)

      ((eq? what (car where)) #t)

      (else (contains? what (cdr where)))))

  (let ((found '()))

    (define (helper x)

      (cond ((contains? x found) #t)

            ((not (pair? x)) #f)

            (else (begin

                    (set! found (cons x found))

                    (or (helper  (car x)) (helper  (cdr x)))))))

    (helper x)))

(define (cycle? x)

  (define (helper one-stepper two-stepper)

    (cond ((null? one-stepper) #f)

          ((null? two-stepper) #f)

          ((eq? one-stepper two-stepper) #t)

          (else (helper (cdr one-stepper) (cddr two-stepper)))))

  (if (or (null? x) (null? (cdr x)) (null? (cddr x))) #f (helper (cdr x) (cddr x))))

Exercise-3-17

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

Напишите правильную версию процедуры count-pairs из упражнения 3.16, которая возвращает

число различных пар в любой структуре.

Решение

(define (count-pairs x)

  (define (contains? what where)

    (cond

      ((null? where) #f)

      ((eq? what (car where)) #t)

      (else (contains? what (cdr where)))))

  (let ((found '()))

    (define (helper x)

      (if (and (pair? x) (not (contains? x found)))

          (begin

            (set! found (cons x found))

            (+ 1 (helper  (car x)) (helper  (cdr x))))

          0))

    (helper x)))

Интересный прием заключен в конструкции

(set! found (cons x found))

В целом, весьма понятно что она делает, поэтому предлагается рассмотреть ее читателю самостоятельно.

Тест конструкции 

(define a (cons 1 2))

(define b (cons 3 a))

(define c (cons b a))

(set-cdr! a c)

(count-pairs c) ;3

Работает)

PS 2 упражнения с диаграммками пропущены.

Exercise-3.14

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

Следующая процедура, хотя и сложна для понимания, вполне может оказаться полезной:

(define (mystery x)

  (define (loop x y)

    (if (null? x)

        y

        (let ((temp (cdr x)))

          (set-cdr! x y)

          (loop temp x))))

Loop пользуется «временной» переменной temp, чтобы сохранить старое значение cdr пары x,

поскольку set-cdr! на следующей строке его разрушает. Объясните, что за задачу выполняет

mystery. Предположим, что переменная v определена выражением

(define v (list ’a ’b’c ’d).

 Нарисуйте диаграмму, которая изображает список, являющийся значением v. Допустим, что теперь мы выполняем (define w (mystery v)). Нарисуйте стрелочные диаграммы, которые показывают структуры v и w после вычисления этого выражения. Что будет напечатано в качестве значений v и w?

Упражнение оказалось глубже чем кажется на первый взгляд. При беглом ознакомление кажется что mystery всего лишь странная реализация reverse, но при дальнейшем рассмотрении оказывается что она обладает побочным эффектом оставляя лишь первый элемент в передаваемом ей списке. Все это должно подвигнуть нас на глубокие размышления о побочных эффектах функций.

Exercise-3.13

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

Рассмотрим следующую процедуру make-cycle, которая пользуется last-pair из упражне-

ния 3.12:

(define (make-cycle x) (set-cdr! (last-pair x) x) x)

Нарисуйте стрелочную диаграмму, которая изображает структуру z, созданную таким кодом:

(define z (make-cycle (list ’a ’b ’c)))

Что случится, если мы попробуем вычислить (last-pair z)?

На моей машинке получился бесконечный цикл, надо будет потестить с операционкой которая умеет выполнять подобные циклы за 5 сек.

Exercise-3-12

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

В разделе 2.2.1 была введена следующая процедура для добавления одного списка к другому:

(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))

Append порождает новый список, по очереди наращивая элементы x в начало y. Процедура append! подобна append, но только она является не конструктором, а мутатором. Она склеивает списки вместе, изменяя последнюю пару x так, что ее cdr становится равным y. (Вызов append! с пустым x является ошибкой.)

(define (append! x y) (set-cdr! (last-pair x) y) x)

Здесь last-pair — процедура, которая возвращает последнюю пару своего аргумента:

(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))

Рассмотрим последовательность действий

(define x (list ’a ’b))

(define y (list ’c ’d))

(define z (append x y))

z ;(a b c d)

(cdr x);b

(define w (append! x y));(a b c d)

w ;(a b c d)

(cdr x);(b c d)

В переменные z и w записываются “одинаковые” списки,но во втором случаем изначальный список также изменяется, чти и видно по выводу.

Interpriter

До этого момента я делал все упражнения, используя DrScheme и стандартный диалект racket, но работа с изменяемыми структурами тут отличается от предлагаемого синтаксиса в SICP, я нашел 2 выхода либо перейти на MIT Scheme либо выбрать язык R5RS. Второй вариант не интуитивен, но вроде рабочий, MIT Scheme оставим для любителей Emacs-a.

Exercise-3.9-3.11

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

Exercise-3-08

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

Когда в разделе 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)

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 (который остается таким же как и до введение политики безопасности)

(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)

  (define (dispatch m)

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

          ((eq? m 'deposit) deposit)

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

  (password-checker-wrapper dispatch password 7))

Exercise-3-03

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

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

(define acc (make-account 100 ’secret-password))

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

((acc ’secret-password ’withdraw) 40)

60

((acc ’some-other-password ’deposit) 50)

"Неверный пароль"

Опять не сложное упражнение, но при его реализации можно столкнуться со следующей проблемой - make-account возвращала функцию от одного аргумента надо бы эту логику и оставить вместо возвращения сообщения об ошибке, для этого в случае ошибки будем возвращать функцию которая будет возвращать сообщение об ошибки при любых праметрах

(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)

  (define (dispatch pass m)

    (if (eq? pass password)

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

              ((eq? m 'deposit) deposit)

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

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

  dispatch)

Exercise-3-02

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

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

(define s (make-monitored sqrt))

(s 100)

10

(s ’how-many-calls?)

1

Вполне прямолинейное решение

(define (make-monitored f)

  (let ((counter 0))

    (λ (arg) 

      (cond ((eq? arg 'how-many-calls?) counter)

            ((eq? arg 'reset-count?) (begin (set! counter 0) counter))

            (else (begin (set! counter (+ counter 1)) (f arg)))))))

Exercise-3-01

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

(define A (make-accumulator 5))
(A 10)
15
(A 10)
25

создадим такую функцию

(define (make-accumulator balance)
  (λ (amount)
    (begin
      (set! balance (+ balance amount))
      balance)))

make-accumulator создает функцию с счетчиком равным balance и возвращает ее.
Функция от одного аргумента amount добавляет аргумент к результату и возвращает результат.

first

Привет!

Этот блог создан как логическое продолжение sicp.sergeykhenkin.com как логическое продолжение решенных там задач. Отсталость решить упражнения для 3, 4 и 5 главы. Не будем терять время.