SICP по-русски

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

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

Это весьма интересное упражнение, поскольку оно подводит нас очень близко к такой популярной сейчас в разработке программ парадигме, как объектно-ориентированное программирование. Действительно, передача сообщений - это фундамент, на котором построено ООП.
Собственно решение упражнения приведено ниже:
(define (make-from-mag-ang r a)
(define (dispatch op)
(cond ((eq? op ‘real-part) (* r (cos a)))
[…]

Это упражнение сформулировано довольно обобщенно и допускает достаточно широкий диапазон трактовок. Я предлагаю один из вариантов по мотивам предшествующего раздела книги, который демонстрирует основные идеи.
Итак, пусть в компании Insatiable Enterprises, Inc. есть два отела: разработки (инженерный) и продаж.
В отделе разработки записи о сотрудниках содержат имена, должности и размеры окладов. Запись соединяет поля с помощью операций […]

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

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

Заметим, что для заданных частот символов справедливо утверждение о том, что сумма двух наименьших частот меньше любой из оставшихся частот. Следовательно, дерево будет вырождено. Также отметим, что:
1+2 = 3 = 4 - 1,
3+4 = 7 = 8 - 1,
…
2n-1 + 2n = 2n+1-1.
Таким образом дерево Хаффмана для n=5 будет выглядеть следующим образом (слева частоты обозначены простыми […]

Используя процедуру generate-huffman-tree, построим следующее дерево для заданного “рок-алфавита”:
> (generate-huffman-tree ‘((A 2) (BOOM 1) (GET 2) (JOB 2)
                           (NA 16) (SHA 3) (YIP 9) (WAH 1)))
((leaf NA 16)
 ((leaf YIP 9)
  (((leaf A 2)
    ((leaf WAH 1)
     (leaf BOOM 1)
     (WAH BOOM)
     2)
    (A WAH BOOM)
    4)
   ((leaf SHA 3)
    ((leaf JOB 2)
     (leaf GET 2)
     […]

На самом деле построить процедуру successive-merge совсем не сложно. Алгоритм наших действий прост. Мы будем хранить все деревья и листья в упорядоченном по возрастанию веса списке. Раз так, два самых легких элемента всегда будут находиться на двух первых позициях в списке. Стало быть, нам достаточно на каждом этапе алгоритма последовательного слияния брать два первых элемента […]

Я предлагаю реализацию encode-symbol, приведенную ниже. Она заключается в том, что для символа мы начиная от корня просматриваем вершины дерева кодирования и ищем символ в левом и правом поддеревьях каждой вершины. Если символ найден в левом поддереве, мы дописываем в его код 0, если в правом - 1. Остальная часть кода возвращается вызовом той же […]

Дерево кодирования из примера изображено на рисунке ниже:

При декодировании последовательности
0 1 1 0 0 1 0 1 0 1 1 1 0
будем двигаться в соответствии с описанными в параграфе, предшествующем упражнению, правилами от корня к листам в зависимости от значений входных битов и, достигнув листа, выводить символ в нем.
Сначала, пройдем по левой ветке (0) и попадем […]