SICP по-русски

Итак, мы хотим, чтобы внутреннее представление обычных чисел в нашей обобщенной системе совпадало со внутренним представлением чисел в Scheme. С числами в таком представлении работать удобнее, так как они выглядят естественнее. Если мы вспомним, что процедуры attach-tag, type-tag и contents соответственно помечают данные типом, определяют тип данных и получают непомеченные данные из помеченных, то сразу […]

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

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

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

Это упражнение сформулировано довольно обобщенно и допускает достаточно широкий диапазон трактовок. Я предлагаю один из вариантов по мотивам предшествующего раздела книги, который демонстрирует основные идеи. Итак, пусть в компании 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) […]

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