Программная инженерия. Часть 5.

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

Наиболее перспективными в этом отношении представляются идеи абстрактных типов данных (АТД), основные варианты которых были предложены во второй половине 70-х годов (Хоар, Лисков, Лондон, Парнас, Шо и др.). К сожалению, когда в программной инженерии (примерно 10 лет назад) период теоретических находок сменился периодом широкого внедрения найденных и апробированных решений, концепция АТД не была к этому готова — требовались дополнительные исследования экспериментальных языков с перспективой разработки базирующегося на АТД промышленного языка программирования, ориентированного на создание больших систем ПО, что противоречило предъявляемым языком АДА претензиям на монополию в этой области. Дальнейшего развития идей АТД следует ожидать после создания качественных трансляторов языка АДА, развеивания связанных с ним иллюзий и исчерпания его достоинств. Однако владеть проблематикой АТД необходимо уже сейчас. Это будет содействовать повышению качества разрабатываемого ПО даже при отсутствии средств поддержки АТД в используемых языках программирования. Важно видеть цель, многое можно сделать и без идеальных инструментов.

Концепции АТД удобно пояснить, рассмотрев принадлежащее Хоару более раннее определение типа данных:

  1. Тип определяет класс значений, которые могут принимать переменная или выражение.
  2. Каждое значение принадлежит одному и только одному типу.
  3. Тип значения константы, переменной или выражения можно вывести либо из контекста, либо из самого операнда, не обращаясь к значениям, вычисляемым во время работы программы.
  4. Каждой операции соответствуют некоторый фиксированный тип ее операндов и некоторый фиксированный тип результата.
  5. Для каждого типа свойства значений и элементарных операций над значениями задаются с помощью аксиом.
  6. При работе с языком высокого уровня знание типа позволяет обнаруживать в программе бессмысленные конструкции и решать вопрос о методе представления данных и преобразования их в вычислительной машине.
  7. Интересующие нас типы — это типы, хорошо знакомые математикам: прямые произведения, размеченные объединения, множества, функции, последовательности и рекурсивные структуры.

Такая интерпретация типов данных была реализована Виртом в языке ПАСКАЛЬ. Она обеспечила абстрагирование от специфики конкретных ЭВМ, предоставила богатый выбор готовых типов данных и стандартных конструкторов типов данных (массивы, записи и т.д.), полезных для решения задач. Предусмотренная определением возможность контроля использования данных облегчает обнаружение ошибок до начала выполнения программ.

Можно указать следующие недостатки этой интерпретации:

  • выбранные для решения задачи типы данных могут иметь не только полезные, но и вредные свойства, причем их наличие обычно связано не с принципиальными трудностями, а с невозможностью при создании языка заранее предусмотреть все проблемы проектирования ПО;
  • ориентация на выбор из множества готовых типов ограничивает возможности построения проблемно-ориентированных расширений, так как нельзя создавать и накапливать типы данных, в точности соответствующие специфике решаемых задач;
  • способ представления данных и реализации операций может быть не оптимален. Например, компактное представление разреженных массивов зависит от специфики расположения ненулевых элементов, учесть которую может только сам программист;
  • близкие с точки зрения проблемной области типы данных могут оказаться далекими в языке, что затрудняет выполнение модификаций программ, связанных с изменением организации данных.
    Например, переход от обработки строк фиксированной длины к строкам переменной длины легко выполняется в языке ПЛ/1, но требует глобальной переработки программы в языках ПАСКАЛЬ или АДА.