Решение упражнения 2.79 из SICP

26 February, 2008 (21:49) | Решения упражнений | 1 comment

Первым делом, определим саму обобщенную операцию проверки эквивалентности equ?. Мы еще не определяли обобщенных операций, являющихся предикатами. Но никаких сложностей с этим не возникает, ведь предикат – это всего лишь частный случай обыкновенной процедуры, который возвращает булево значение (истина или ложь). Таким образом определяется обобщенный предикат так же, как любая обобщенная операция:
(define (equ? x y) (apply-generic 'equ? x y))

Однако, есть важный нюанс. Поскольку возвращаемое значение имеет не пользовательский тип, а логический, нам не нужно добавлять к нему тег типа при определении в пакетах обыкновенных, рациональных и комплексных чисел.

Для того, чтобы реализовать equ? для каждого типа чисел, добавим в install-scheme-number-package следующий код:
(put 'equ? '(scheme-number scheme-number) =)

В install-rational-package аналогично добавим (процедура equal-rat? взята один в один из раздела 2.1.1 без модификаций):

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))
(put 'equ? '(rational rational) equal-rat?)

В install-complex-package добавим такие строки:

(define (equal-complex? x y)
  (and (= (real-part x) (real-part y))
       (= (imag-part x) (imag-part y))))
(put 'equ? '(complex complex) equal-complex?)

Все. Теперь наша обобщенная операция equ? будет работать при сравнении пар обыкновенных, рациональных либо действительных чисел. Правда, сравнить обыкновенный 0 с рациональным 0/1 или комплексным 0+0i не получится. Пока что. Следующий раздел книги 2.5.2 как раз об этом…

Решение упражнения 2.78 из SICP

25 February, 2008 (20:58) | Решения упражнений | 6 comments

Итак, мы хотим, чтобы внутреннее представление обычных чисел в нашей обобщенной системе совпадало со внутренним представлением чисел в Scheme. С числами в таком представлении работать удобнее, так как они выглядят естественнее.

Если мы вспомним, что процедуры attach-tag, type-tag и contents соответственно помечают данные типом, определяют тип данных и получают непомеченные данные из помеченных, то сразу же поймем, что для обычных чисел эти операции тривиальны:

  • помечать числа, как и договорились, мы вообще не будем;
  • определять тип будем с помощью предиката number?, а типом чисел будем считать scheme-number;
  • непомеченные числа у нас совпадают с помеченными.

Таким образом получим следующие определения введенных ранее процедур для работы с помеченными типом данными, в которых числа являются особым случаем:
(define (attach-tag type-tag contents)
  (if (number? contents)
      contents
      (cons type-tag contents)))

(define (type-tag datum)
  (cond ((number? datum) 'scheme-number)
        ((pair? datum) (car datum))
        (else (error "Некорректные помеченные данные -- TYPE-TAG" datum))))

(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Некорректные помеченные данные -- CONTENTS" datum))))

А вот, хорошо ли это – иметь особые случаи – вопрос для отдельного обсуждения.

Решение упражнения 2.77 из SICP

25 February, 2008 (20:14) | Решения упражнений | No comments

Объект z, с которым мы работаем в этом упражнении и для которого мы хотим вычислить модуль (magnitude), – это дважды помеченная пара, представляющая собой комплексное число в декартовой форме. Он состоит из метки complex, за которой следует метка rectangular, а уже затем идет представление числа.

Процедура magnitude задана в разделе 2.4.3 и выглядит следующим образом:

(define (magnitude z) (apply-generic 'magnitude z))

Когда мы вызываем (magnitude z), не определив никаких дополнительных элементов в таблице типов, у apply-generic есть выбор только из двух типов, для которых задана процедура magnitude: rectangular и polar. Эти типы были проинсталлированы в систему ранее и содержали вызовы put для операции magnitude.

Однако в нашем объекте z первой идет метка типа complex, а не rectangular! Поэтому процедура apply-generic выдает Хьюго сообщение об ошибке.

Совет Лизы относительно добавления в пакет для работы с комплексными числами еще нескольких операций put, пополняющих таблицу типов, абсолютно верный. При этом мы фактически разрешаем операции (real-part, imag-part, magnitude, angle) не только для типов rectangular и polar (то есть для объектов с метками типа ‘rectangular и ‘polar), но и для типа complex.

При вызове (magnitude z) по-прежнему вызовется apply-generic c параметрами ‘magnitude и ‘(complex). Однако на этот раз в ячейке таблицы типов, соответствующей операции magnitude и типу complex уже не будет пусто, а будет записана процедура. Причем в этой ячейке будет записана… сама процедура magnitude. Таким образом apply-generic вновь диспетчиризует к magnitude, с одним только важным изменением: она уже сняла внешнюю метку типа complex с объекта z. Теперь magnitude вычисляется для объекта с меткой типа rectangular. Для этого еще раз вызывается apply-generic, которая на этот раз диспетчеризует к процедуре, находящейся в таблице типов в ячейке, соответствующей операции magnitude и типу rectangular, то есть процедуре из пакета декартового представления комплексных чисел, возвращающей квадратный корень из суммы квадратов действительной и мнимой частей комплексного числа, представленного в декартовой форме.

То есть все работает отлично благодаря происходящей двойной диспетчеризации.

О комментариях

24 February, 2008 (13:33) | Разное | 4 comments

Этот пост не о SICP.

Я немного подправил работу с комментариями таким образом, чтобы сделать публикацию фрагментов кода в них более удобной. Если вы хотите включить в комментарий код, окружите его тегами <code> и </code>.  В этом случае будет сохранено его форматирование, и код будет лучше читаться.

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

Если вам нужны еще какие-то теги, сообщите пожалуйста, и я их активирую.

Решение упражнения 2.76 из SICP

22 February, 2008 (14:16) | Решения упражнений | 2 comments

Рассмотрим, что нам нужно сделать при добавлении нового типа или новой операции в систему с обобщенными операциями при разных стратегиях представления операций и типов.

1. Обобщенные операции с явной диспетчеризацией.При добавлении типа нам нужно будет:

  • добавить специфичные операции типа по числу операций в системе;
  • изменить все обобщенные операции, добавив в каждую условия проверки метки нового типа и вызова соответствующей операции нового типа.

При добавлении новой операции нам нужно будет:

  • добавить для каждого типа специфичную реализацию этой операции;
  • добавить обобщенную операцию в систему.

2. Стиль, управляемый данными.

При добавлении типа нам нужно будет:

  • добавить пакет со всеми операциями реализованными для этого типа;
  • добавить все реализации операций в таблицу типов с тегом этого типа.

Обобщенные операции при этом менять не нужно!

При добавлении новой операции нам нужно будет:

  • изменить все пакеты типов, добавив для каждого типа специфичную реализацию этой операции и добавить эту реализацию в таблицу типов;
  • добавить обобщенную операцию в систему.

3. Передача сообщений.

При добавлении типа нам нужно будет:

  • добавить тип в виде конструктора с процедурой диспетчеризации, содержащей условия для каждой операции в системе;

Обобщенные операции при этом менять не нужно!

При добавлении новой операции нам нужно будет:

  • изменить все конструкторы, добавив в каждый из них условие диспетчеризации для новой операции и ее реализацию для каждого типа;
  • добавить обобщенную операцию в систему.

Какая же стратегия лучше при частом добавлении новых типов, а какая – при частом добавлении новых операций? В случае добавление нового типа меньше всего телодвижений приходится делать при передаче сообщений. В случае же добавления новой операции все не так однозначно. По большому счету, ни один из подходов не имеет большого преимущества перед другими.

Я был бы рад обсудить это упражнение. Мне кажется, что я тут мог упустить нечто важное. Комментарии приветствуются.

Решение упражнения 2.75 из SICP

22 February, 2008 (13:01) | Решения упражнений | No comments

Это весьма интересное упражнение, поскольку оно подводит нас очень близко к такой популярной сейчас в разработке программ парадигме, как объектно-ориентированное программирование. Действительно, передача сообщений – это фундамент, на котором построено ООП.

Собственно решение упражнения приведено ниже:

(define (make-from-mag-ang r a)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          (else
           (error "Неизвестная оп. -- MAKE-FROM-MAG-ANG" op))))
  dispatch)

В результате вызова конструктора (тоже популярный в ООП термин) make-from-mag-ang мы получаем объект (термин из ООП; на самом деле мы получаем процедуру диспетчеризации, которая представляет собой объект). Затем при операциях над этим объектом можно сказать, что происходит вызов методов (которые задаются условиями внутри cond). Имени метода соответствует имя обобщенной операции, например ‘real-part).

Не правда ли, очень похоже на объектно-ориентированный подход? Думаю, в главе 3 нас ждет еще много интересного про ООП.

Решение упражнения 2.74 из SICP

22 February, 2008 (11:37) | Решения упражнений | 4 comments

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

Итак, пусть в компании Insatiable Enterprises, Inc. есть два отела: разработки (инженерный) и продаж.

В отделе разработки записи о сотрудниках содержат имена, должности и размеры окладов. Запись соединяет поля с помощью операций cons. Сами записи хранятся в списке. Для поиска записи в списке определена специальная процедура поиска.

(define (make-employee name position salary)
  (cons name (cons position salary)))
(define (get-name employee)
  (car employee))
(define (get-position employee)
  (cadr employee))
(define (get-salary employee)
  (cddr employee))
(define employees
  (list (make-employee 'Hugo 'junior 60000)
        (make-employee 'Alyssa 'senior 90000)
        (make-employee 'Eva 'lead 100000)
        (make-employee 'Ben 'senior 110000)))
(define (get-employee name)
  (define (find-employee employees)
    (cond ((null? employees) null)
          ((eq? name (get-name (car employees)))
           (car employees))
          (else (find-employee (cdr employees)))))
    (find-employee employees))

В отделе продаж работают люди опытные и творческие. Поэтому записи о сотрудниках содержат самое главное: имена, размеры окладов и стаж. Запись соединяет поля просто в список. Сами записи задаются в специальная процедуре, возвращающей соответствующую запись по ключу – имени сотрудника.

(define (make-record name salary experience)
  (list 'employee name salary experience))
(define (get-record-name record)
  (cadr employee))
(define (get-record-salary record)
  (caddr employee))
(define (get-record-experience record)
  (cadddr employee))
(define (get-salesman who)
  (cond ((eq? who 'Mike) (make-record 'Mike 200000 5))
        ((eq? who 'Jennifer) (make-record 'Jennifer 180000 3))
        ((eq? who 'Scott) (make-record 'Scott 250000 10))
        (else null)))

Как видим, структуры представления данных в записи и хранения самих записей отличаются друг от друга довольно сильно. Для того, чтобы работать с ними единообразно, мы завернем данные об отделах в пакеты и поместим операции над данными в таблицу типов. В этой таблице тип будет задаваться именем отдела, а операциями будут имена обобщенных операций, например get-record.

(define (install-engineering-department)
  (define (make-employee name position salary)
    (cons name (cons position salary)))
  (define (get-name employee)
    (car employee))
  (define (get-position employee)
    (cadr employee))
  (define (get-salary employee)
    (cddr employee))
  (define employees
    (list (make-employee 'Hugo 'junior 60000)
          (make-employee 'Alyssa 'senior 90000)
          (make-employee 'Eva 'lead 100000)
          (make-employee 'Ben 'senior 110000)))
  (define (get-employee name)
    (define (find-employee employees)
      (cond ((null? employees) null)
            ((eq? name (get-name (car employees)))
             (car employees))
            (else (find-employee (cdr employees)))))
    (find-employee employees))
  (put 'get-record 'engineering get-employee)
  (put 'get-salary 'engineering get-salary)
  'done)

(define (install-sales-department)
  (define (make-record name salary experience)
    (list 'employee name salary experience))
  (define (get-record-name record)
    (cadr employee))
  (define (get-record-salary record)
    (caddr employee))
  (define (get-record-experience record)
    (cadddr employee))
  (define (get-salesman who)
    (cond ((eq? who 'Mike) (make-record 'Mike 200000 5))
          ((eq? who 'Jennifer) (make-record 'Jennifer 180000 3))
          ((eq? who 'Scott) (make-record 'Scott 250000 10))
          (else null)))
  (put 'get-record 'sales get-salesman)
  (put 'get-salary 'sales get-record-salary)
  'done)

а. Теперь мы можем легко написать обобщенную процедуру получения записи сотрудника по его имени и отделу:

(define (get-record name department)
  ((get 'get-record department) name))

б. Для того, чтобы получить зарплату сотрудника, мы сначала добываем из таблицы операцию извлечения информации о зарплате из записи для данного отдела, а затем применяем ее к записи сотрудника, полученной обобщенной процедурой get-record:

(define (get-salary name department)
  ((get 'get-salary department)
   (get-record department name)))

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

(define (find-employee-record name departments)
  (if (null? departments)
      null
      (let ((record (get-record name (car departments))))
        (if (null? record)
            (find-employee-record name (cdr departments))
            record))))

Здесь при реализации можно было бы использовать библиотечную процедуру findf.

г. Для внесения в систему информации о новых подразделениях достаточно будет установить пакет для соответствующего подразделения, в который включить специфичное для него описание данных о сотрудниках и дополнительно задать новую строку операций в таблице типов, соответствующую этому подразделению, с помощью набора вызовов put:

(define (install-new-department)
  ;; ...
  (put 'get-record 'new get-record-new)
  (put 'get-salary 'new get-salary-new)
  'done)

При этом ничего менять ни в пакетах других подразделений, ни в обобщенных процедурах get-record, get-salary и т.д. не нужно! Именно в этом и заключается наш выигрыш.

Решение упражнения 2.73 из SICP

20 February, 2008 (21:22) | Решения упражнений | 2 comments

Выполнять это упражнение не очень удобно, так как операции put и get пока что для нас виртуальны, а значит опробовать код на практике не удастся. Тем не менее начнем.

а. В приведенном определении процедуры deriv после проверок выражения на числовое значение и переменную происходит диспетчеризация по типу операции. То есть код смотрит, какая операция находится на самом верхнем уровне выражения и применяет к ее операндам соответствующую этой операции процедуру дифференцирования выражения из таблицы.

Предикаты number? и variable? не содержат операцию, по которой собственно и происходит диспетчеризация. Таким образом включать их в общую схему выбора, управляемого данными, не имеет смысла.

б. Код для операций дифференцирования для сумм и произведений оформлен в виде пакета и представлен ниже:

(define (install-sum-product-package) 
  (define (make-sum a1 a2) 
    (list '+ a1 a2)) 
  (define (addend s) (car s)) 
  (define (augend s) (cadr s)) 
  (define (deriv-sum exp var) 
    (make-sum (deriv (addend exp) var) 
              (deriv (augend exp) var))) 
  (define (make-product m1 m2) 
    (list '* m1 m2)) 
  (define (multiplier p) (car p)) 
  (define (multiplicand p) (cadr p)) 
  (define (deriv-product exp var) 
    (make-sum 
      (make-product (multiplier exp) 
                    (deriv (multiplicand exp) var)) 
      (make-product (deriv (multiplier exp) var) 
                           (multiplicand exp)))) 
  (put 'deriv '+ deriv-sum) 
  (put 'deriv '* deriv-product) 
  'done)

Операции put просто задают значения элементов таблицы. В таблицу помещаются сами символы + и *, обозначающие тип операции, а не списки, поскольку этого достаточно для решения задачи.

в. Для того, чтобы добавить правило для взятия производной от возведения в степень, достаточно поместить приведенные ниже строки внутрь пакета из предыдущего пункта:

(define (make-exponentiation base exp) 
  (list '** base exp)) 
(define (base e) (car e)) 
(define (exponent e) (cadr e)) 
(define (deriv-exponentiation  exp var) 
  (make-product 
    (make-product 
      (exponent exp) 
      (make-exponentiation (base exp) 
                           (- (exponent exp) 1))) 
      (deriv (base exp) var))) 
(put 'deriv '** deriv-exponentiation)

Этот вариант добавления нового правила для вычисления производной имеет тот минус, что нам нужно изменять старый пакет. Вместо этого мы могли бы создать отдельный новый пакет, содержащий только определение производной для возведения в степень, и не затрагивающий пакет для производных сумм и произведений. Но тогда мы столкнемся с некоторыми трудностями, так как конструктор make-product, который используется при построении производной экспоненты, определен внутри другого пакета и недоступен. Можно вынести конструкторы и селекторы за пределы пакетов, что решит узкую проблему, но не является удачным выходом, поскольку теперь части определений не сгруппированы в пакеты и не скрывают имена.

Я думаю, что проблема более глобальна и заключается в том, что вычисление производных сложных функций использует операцию умножения, то есть не может быть отделена от ее определения.

г. Мы просто поменяли порядок аргументов в процедуре get. Для того, чтобы все работало по-прежнему, нам будет достаточно всего лишь поменять местами и соответствующие аргументы в процедуре put, ведь таблица операций и типов отделена от всего остального кода только этими двумя операциями. Никаких других изменений в системе дифференцирования делать не нужно.

Решение упражнения 2.72 из SICP

19 February, 2008 (20:57) | Решения упражнений | 2 comments

Количество шагов, необходимых для кодирования одного символа в общем случае может сильно розниться. Можно говорить о наилучшем, наихудшем и среднем случаях для разных символов и разных конфигураций дерева Хаффмана. Говорить же о порядке роста числа шагов, ничего не зная о символах и дереве, сложно.

В качестве иллюстрации рассмотрим случай, когда относительные частоты символов таковы, как в предыдущем упражнении. В этом случае для того, чтобы закодировать наиболее часто встречающийся символ, мы найдем его сразу же в множестве из одного элемента за константное число шагов, а затем сделаем один шаг по дереву вниз. То есть порядок роста числа шагов равен Θ(1).

Для кодирования наиболее редкого символа нам придется спуститься на всю глубину дерева, то есть произвести поиск в n-1 множестве. В этих множествах будет находиться последовательно n-1, n-2, …, 1 элементов. Поскольку множества представляются неупорядоченными списками, поиск элемента в множестве требует порядка Θ(k) шагов, где k – число элементов множества. Таким образом будет выполнено порядка n поисков, каждый из которых потребует порядка n шагов. А значит порядок роста числа шагов для кодирования самого редкого элемента будет Θ(n2).

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

Для того, чтобы закодировать самый частый символ нам нужно константное число шагов, для кодирования второго по частоте – число шагов порядка n, для третьего – порядка 2n, для четвертого – порядка 3n и т.д. При этом их частоты убывают от 2n-1 до 1. Тогда в среднем число шагов будет равно n*(1/2 + 2/4 + 3/8 + 4/16 + 5/32 + … ). Вообще говоря, ряд конечный, но его можно ограничить сверху соответствующим сходящимся бесконечным рядом с общим членом вида k/2k. Сумма этого сходящегося ряда равна 2. Таким образом мы можем сделать вывод, что в среднем для кодирования одного символа текста требуется Θ(n) шагов. В среднем в данном случае – это не просто какая-то оценка. Это означает, что для кодирования всего сообщения потребуется порядка Θ(L*n) шагов, где L -длина сообщения в символах.

Решение упражнения 2.71 из SICP

18 February, 2008 (21:50) | Решения упражнений | No comments

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

1+2 = 3 = 4 – 1,

3+4 = 7 = 8 – 1,

2n-1 + 2n = 2n+1-1.

Таким образом дерево Хаффмана для n=5 будет выглядеть следующим образом (слева частоты обозначены простыми числами, а справа через степени двойки для наглядности):

2711.png

Для n=10 дерево будет таким (вновь слева частоты обозначены простыми числами, а справа через степени двойки):

2712.png

Самый часто встречающийся символ имеет частоту 2n-1 и находится сразу налево от корня, то есть кодируется одним битом 0.

Самый редко встречающийся символ имеет частоту 1=20 и находится на самом длинном пути в дереве, состоящем из n-1 единицы, то есть имеет код 11…1 (число битов в коде равно n-1).