(Эта процедура устроена немного хитро, но она не такая уж сложная. Если Вы видите, что строите сложную процедуру, значит, почти наверняка Вы делаете что-то не то. Можно извлечь немалое преимущество из того, что мы используем упорядоченное представление для множеств.)

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

Нижеприведенный алфавит из восьми символов с соответствующими им относительными частотами был разработан, чтобы эффективно кодировать слова рок-песен 1950х годов. (Обратите внимание, что «символы» «алфавита» не обязаны быть отдельными буквами.)

A2NA16

BOOM1SHA3

GET2YIP9

JOB2WAH1

При помощи generate-huffman-tree (упр. 2.69) породите соответствующее дерево Хаффмана, и с помощью encode закодируйте следующее сообщение:

Get a job

Sha na na na na na na na na Get a job

Sha na na na na na na na na

Wah yip yip yip yip yip yip yip yip yip

Sha boom

Сколько битов потребовалось для кодирования? Каково наименьшее число битов, которое потребовалось бы для кодирования этой песни, если использовать код с фиксированной длиной для алфавита из восьми символов?

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

Допустим, у нас есть дерево Хаффмана для алфавита из n символов, и относительные частоты символов равны 1, 2, 4,..., 2n-1. Изобразите дерево для n = 5; для n = 10. Сколько битов в таком дереве (для произвольного n) требуется, чтобы закодировать самый частый символ? Самый редкий символ?

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

Рассмотрим процедуру кодирования, которую Вы разработали в упражнении 2.68. Каков порядок роста в терминах количества шагов, необходимых для кодирования символа? Не забудьте включить число шагов, требуемых для поиска символа в каждой следующей вершине. Ответить на этот вопрос в общем случае сложно. Рассмотрите особый случай, когда относительные частоты символов таковы, как описано в упражнении 2.71, и найдите порядок роста (как функцию от n) числа шагов, необходимых, чтобы закодировать самый частый и самый редкий символ алфавита.

2.4 Множественные представления для абстрактных данных

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

пользуется рациональными числами, от задачи реализации рациональных чисел через элементарные механизмы построения составных данных в компьютерном языке. Главная идея состояла в возведении барьера абстракции, - в данном случае, селекторов и конструкторов для рациональных чисел (make-rat, numer, denom), - который отделяет то, как рациональные числа используются, от их внутреннего представления через списковые структуры. Подобный же барьер абстракции отделяет детали процедур, реализующих рациональную арифметику (add-rat, sub-rat, mul-rat и div-rat), от «высокоуровневых» процедур, которые используют рациональные числа. Получившаяся программа имеет структуру, показанную на рис. 2.1.

Такие барьеры абстракции - мощное средство управления сложностью проекта. Изолируя внутренние представления объектов данных, нам удается разделить задачу построения большой программы на меньшие задачи, которые можно решать независимо друг от друга. Однако такой тип абстракции данных еще недостаточно мощен, поскольку не всегда имеет смысл говорить о «внутреннем представлении» объекта данных.

Например, может оказаться более одного удобного представления для объекта данных, и мы можем захотеть проектировать системы, которые способны работать с множественными представлениями. В качестве простого примера, комплексные числа можно представить двумя почти эквивалентными способами: в декартовой форме (действительная и мнимая часть) и в полярной форме (модуль и аргумент). Иногда лучше подходит декартова форма, а иногда полярная. В сущности, вполне возможно представить себе систему, в которой комплексные числа представляются обоими способами, а процедуры-операции над комплексным числами способны работать с любым представлением.

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

В этом разделе мы научимся работать с данными, которые могут быть представлены в разных частях программы различными способами. Это требует построения обобщенных процедур (generic procedures) - процедур, работающих с данными, которые могут быть представлены более чем одним способом. Наш основной метод построения обобщенных процедур будет состоять в том, чтобы работать в терминах объектов, обладающих метками типа (type tags), то есть объектов, явно включающих информацию о том, как их надо обрабатывать. Кроме того, мы обсудим программирование, управляемое данными (data-directed programming) - мощную и удобную стратегию реализации, предназначенную для аддитивной сборки систем с обобщенными операциями.

Мы начнем с простого примера комплексных чисел. Мы увидим, как метки типа и стиль, управляемый данными, позволяют нам создать отдельные де-

Пакет комплексной арифметики

Списковая структура

Рис. 2.19: Барьеры абстракции данных в системе работы с комплексными числами.

картово и полярное представления комплексных чисел, и при этом поддерживать понятие абстрактного объекта «комплексное число» . Мы добьемся этого, определив арифметические процедуры для комплексных чисел (add-complex, sub-complex, mul-complex и div-complex) в терминах обобщенных селекторов, которые получают части комплексного числа независимо от того, как оно представлено. Получающаяся система работы с комплексными числами, как показано на рис.2.19, содержит два типа барьеров абстракции. «Горизонтальные» барьеры играют ту же роль, что и на рис.2.1. Они отделяют «высокоуровневые» операции от «низкоуровневых» представлений. В дополнение к этому, существует еще «вертикальный» барьер, который дает нам возможность отдельно разрабатывать и добавлять альтернативные представления.

В разделе 2.5 мы покажем, как с помощью меток типа и стиля программирования, управляемого данными, создать арифметический пакет общего назначения. Такой пакет дает пользователю процедуры (add, mul и т.д.), с помощью которых можно манипулировать всеми типами «чисел», и если нужно, его можно легко расширить, когда потребуется новый тип чисел. В разделе 2.5.3 мы покажем, как использовать обобщенную арифметику в системе, работающей с символьной алгеброй.

2.4.1 Представления комплексных чисел

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

Подобно рациональным числам, комплексные числа естественно представлять в виде упорядоченных пар. Множество комплексных чисел можно представлять себе как двумерное пространство с двумя перпендикулярными осями:

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

Программы, использующие комплексные числа add-complex sub-complex mul-complex div-complex