Стандартизация. Структуры данных

Как я писал, я называю «структурами данных» универсальные структуры, которые используются в программах независимо от языков программирования. Примеры структур данных: списки, очереди, стеки, деревья, ассоциативные массивы и т.д. В большинстве языков программирования такие структуры напрямую не поддерживаются.

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

Вопрос: Как помещать структуры данных в open semi-binary репозиторий? До сих пор мы помещали туда только отдельные функции.

Рассмотрим, что нужно для реализации структуры данных.

Очевидно:

  • Описание раскладки в оперативной памяти
  • Набор функций, реализующих операции над структурой данных

Возьмем в качестве примера «очередь»:

  • Раскладка – это массив (элементов) или список (элементов)
  • Основные операции: create, push, pull

Раз у нас есть несколько вариантов раскладки, то есть и несколько вариантов реализации, по разному использующие ресурсы (процессор, память):

  • Реализация через массив (статически ограниченный или расширяемый)
  • Реализация через односвязанный список
  • Реализация через двусвязанный список

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

Для структуры данных «очередь» в репозитории должно храниться:

Единица хранения «Очередь»:

  1. Список реализаций
    • Реализация 1
      • Описание особенностей реализации (преимущества, недостатки). Сравнение с другими реализациями
      • Раскладка в оперативной памяти (описание структуры)
      • Реализации функций (semi-binary code)
      • Дополнительные тесты (особенности реализации)
      • Дополнительная информация для верификации
      • Возможно доп. интерфейс/реализация для функций, имеющих смысл только для этой реализации
    • Реализация 2
    • Реализация 3
  2. Интерфейс (список функций)
  3. Набор тестов независимых от реализации
  4. Информация для верификации (пред/пост условия, …)
  5. Документация, примеры использования

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

Упоминание сериализации (впрочем, и визуализации) сразу же вызывает дополнительный вопрос: Как? Короткий ответ: мета описание.

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

Перейду к принципиальному вопросу – как соотносится то, что я предлагаю с такими общеупотребительными вещами, как объекты (классы) и templates.

Objects/Classes

У меня сложное отношение к объектно-ориентированности. С одной стороны, ООП философски вырастает из понятия категории. И если рассматривать класс, как программное отражение описания и способов управления некоторой обобщенной сущностью (например, геометрической фигурой или человеком), то ООП – это естественный способ программирования. С другой стороны, то, как реализовано ООП в большинстве языков – это полный [censored].

Но это (мое отношение к реализации ООП) не имеет отношения к нынешней заметке.

На мой взгляд, структура данных не является классом и не должна быть представлена классом. Мы можем использовать синтаксис вызова методов, то есть писать queue.pull – это удобно, но это не имеет отношения к ООП (это синтаксический сахар).

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

Каждая функция структуры данных – это отдельная сущность (так же как sin), которая может быть исправлена/улучшена независимо от остальных функций (стека, очереди или дерева).

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

  • Для человека – имя (как-то) указывает на смысл «объекта»
  • Для компилятора – определяет «объект», соответствующий имени в области действия

Лексика языков программирования обычно сделана в угоду компилятору, программисту приходится использовать плохо читаемые названия, дикие сочетания больших букв, подчерков и т.д.

В репозитории надо разделить «Имя для человека» и «Уникальный идентификатор для компиляторов». Для функции в разных языках программирования могут использоваться разные имена, в соответствии с лексикой языка программирования и используемого естественного языка (русский, английский, …).

Вернусь к ООП. Обычно в число сущностных принципов ООП включается инкапсуляция и наследование.

Под инкапсуляцией обычно понимается объединение данных и функций, причем, упор делается на данные. Хочу обратить внимание, что для в структурах данных данные не имеют значения(!). Уточню – есть «внешние» данные, те, которые укладываются в очереди, стеки или деревья, в них есть смысл, так как ради них программист использует структуры данных. А вот «внутренние» (служебные) данные структуры не имеют значения. Именно благодаря этому мы можем заменить реализацию – изменятся ресурсные показатели (память/скорость), но не поведение программы (не учитываю здесь нехватку ресурсов).

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

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

Итак, для структур данных:

  • Отсутствие объединяющей структуры (класса), есть скорее namespace для каждой структуры данных
  • Возможность добавления функций
  • Возможность использования только тех функций, которые нужны. Нет упаковки всех функций в один кусок кода.
  • Инкапсуляция есть, но она не такая, как в ООП
  • Наследование – не имеет смысла

Итого, это не ООП или, точнее, это другое ООП.

Заметка получилась длинная, и далеко не все, я смог в ней вместить, о templates – продолжение следует.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *