Использование абстракций и спецификаций при разработке программ

3.1. Общие положения

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

1) каждая подзадача имеет один и тот же уровень рассмотрения;

2) каждая подзадача может быть решена независимо;

3) полученные решения могут быть объединены вместе.

Эффективным способом декомпозиции является абстракция – игнорирование ряда подробностей для сведения задачи к более простой.

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

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

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

1) процедурная абстракция (ПА) позволяет расширить заданную некоторым языком виртуальную машину новой операцией;

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

3.2. Процедурная абстракция

3.2.1. Понятие и преимущества процедурной абстракции

Процедура выполняет преобразование входных параметров в выходные.

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

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

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

Локальность – возможность реализации абстракции без необходимости анализа реализации какой-либо другой абстракции. Принцип локальности позволяет создавать программу из абстракций, созданных различными программистами, работающими независимо друг от друга.

Модифицируемость – изменения в реализации абстракции не влияют на программу в целом, если спецификации абстракций остаются прежними.

3.2.2. Спецификация процедурной абстракции

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

Спецификация процедуры состоит из заголовка и описания функции. Заголовок содержит имя процедуры, количество, порядок и типы входных и выходных параметров. Информация в заголовке чисто синтаксическая. В семантической части описывается смысл выполняемых процедурой действий на естественном языке, возможно расширенном привычными математическими обозначениями. Семантическая часть спецификации состоит из трех предложений: requires (требует), modifies (модифицирует), effects (выполняет). Предложения requires и modifies могут быть опущены. Шаблон спецификации процедурной абстракции:

Pname=proc(входные параметры) returns(выходные параметры)

requires список ограничений

modifies список модифицируемых входных параметров

effects описание работы процедуры

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

Предложение modifies задает список имен входных параметров, модифицируемых процедурой. Если входные параметры не указаны, то это предложение может быть опущено.

Предложение effects описывает работу процедуры, определяет выходные значения и модификации над входными параметрами. Предложение effects составляется исходя из предположения, что требования предложения requires удовлетворены. В том случае, когда требования requires не удовлетворены, о поведении процедуры ничего не сообщается.

Примеры спецификаций процедурных абстракций:

Concat=proc(a,b: String) returns(ab: String)

effects По возврату ab есть новая строка, содержащая символы из a (в порядке их расположения в a), за которыми следуют символы из b (в порядке их расположения в b).

RemoveDupls=proc(a:array[real])

modifies a

effects Удаляет из массива a все повторяющиеся элементы, порядок следования оставшихся элементов может измениться.

Search=proc(a:array[real],x:real) returns(i:int)

requires Массив a упорядочен по возрастанию.

effects Если элемент x принадлежит массиву a, то возвращается значение i такое, что a[i]=x; в противном случае возвращается значение i на единицу большее, чем значение верхней границы массива a.

3.2.3. Реализация процедурных абстракций

Реализация ПА должна выполнять все действия, определенные в спецификации. Каждый язык программирования имеет свой механизм и особенности реализации ПА. Например, в Паскале в процедурах существует возможность чтения и модификации глобальных переменных; она не должна использоваться при реализации любых абстракций – значение абстракции при этом зависит от контекста, в котором она находится, т.е. снижается уровень абстракции.

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

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

Замечания по реализации процедурных абстракций.

1. При реализации ПА могут быть оставлены неопределенными некоторые выполняемые процедурой функции. Такая процедура называется недоопределенной – для некоторых значений входных параметров на выходе вместо единственного правильного результата имеется набор допустимых результатов. Реализация может ограничивать этот набор одним значением, однако он может быть любым из числа допустимых. Например, процедура Search будет недоопределенной, если не будет указано точно, какой индекс должен быть возвращен, если искомое значение встречается в массиве несколько раз.

В спецификации должны быть оговорены все существенные для пользователя подробности, все остальные могут оставаться неопределенными.

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

3. Частичная или общая абстракция? Общие процедуры (не имеют ограничений на входные параметры) являются более безопасными, чем частичные, так как неудовлетворение входных требований в частичной процедуре может привести к неверной работе программы. В свою очередь, частичные процедуры чаще более эффективны в реализации, чем общие. Критерии выбора между частичной и общей абстракцией: 1) эффективность; 2) корректное выполнение с меньшим числом потенциальных ошибок.

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

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

3.2.4. Более обобщенные (параметризованные) процедуры

Процедура Search работает с произвольным массивом вещественных чисел. Она была бы более полезной, если бы смогла работать с массивами данных различного типа. Такого обобщения можно достичь, расширяя абстракцию через параметризацию и используя типы данных в качестве параметров. При этом некоторые значения параметров могут не иметь смысла, например, массив может быть отсортирован только в том случае, если элементы, принадлежащие к типу, упорядочены. Ограничения на параметры типа предполагают набор некоторых заданных операций над ними. Спецификация абстракции должна содержать эти ограничения в наборе requires.

Спецификация параметризованной процедуры в заголовке содержит указание на параметр-тип. Предложение requires помимо прочих ограничений содержит ограничения, накладываемые на параметры-типы.

Например, абстракция Search требует, чтобы ее параметр t имел операции equal (равно) и less (меньше), упорядочивающие t.

Search=proc[t:type](a: array[t],x:t) returns(i: int)

requires t имеет операции: equal, less: proctype(t,t) returns(boolean);
t упорядочивается через less, и массив a упорядочен по возрастанию через less.

effects Если элемент x принадлежит массиву a, то возвращается значение i такое, что a[i]=x; в противном случае – значение i на единицу больше, чем значение верхней границы массива a.

Параметризованная абстракция представляет собой класс взаимосвязанных абстракций, определенных в одной спецификации. Спецификация процедуры получается из спецификации класса путем замены имени параметра-типа его значением и удалением из предложения requires ограничений на тип параметров. Если язык программирования имеет в наличии средства реализации параметризованных абстракций, то класс процедур реализуется в виде одной программы. Если язык реализации не имеет средств для создания параметризованных абстракций, то класс абстракций реализуется в виде нескольких непараметризованных процедур для всех допустимых типов параметров.

3.3. Абстракция данных

3.3.1. Понятие абстракции данных

Процедурные абстракции дают нам возможность добавлять в базовый язык новые операции. Необходимость добавления в базовый язык новых типов данных удовлетворяется абстракцией данных.

Область применения программы определяет набор новых типов данных. Например, при создании компилятора или интерпретатора полезны стеки и символьные таблицы, в аналитических вычислениях – полиномы, в матричной алгебре – векторы и матрицы. Новые типы данных должны включать в себя абстракцию через параметризацию и абстракцию через спецификацию. Смысл АП – использование параметров, АС – включение операций над типом в сам тип: абстракция данных = данные + операции.

3.3.2. Спецификация абстракции данных

Состоит из заголовка, определяющего имя типа и имена его операций, и двух секций – описания и операций:

Dname=data type is список операций

Описание – описание абстракции данных

Операции – спецификации всех операций над типом

end Dname

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

Пример. Спецификация очереди целых чисел.

TQueue=data type is Create, Empty, Insert, Remove, Destroy