Современные технологии программирования |
Конспект лекций |
Лекция 3. Процедурная абстракция
Содержание
Абстракция
Абстракция через параметризацию
Абстракция через спецификацию
Локальность
Модифицируемость
Спецификация, формальная и неформальная, язык спецификаций
Спецификация процедурной абстракции
Реализация
Параметризация процедурной абстракции через тип
Недоопределенность, обобщаемость, простота, частичные и общие процедуры.
Наиболее известный в программировании тип абстракции — процедурная абстракция, или процедура. Всякий, кто применял для выполнения функции подпрограмму, которая может быть использована в других программах, реализовывал тем самым процедурную абстракцию. Процедуры объединяют в себе методы абстракции через параметризацию и через спецификацию, позволяя абстрагировать отдельную операцию или событие, например нахождение наибольшего делителя двух целых чисел или сортировку массива.
Процедура выполняет преобразование входных аргументов в выходные. Более точно, это есть отображение набора значений входных аргументов в выходной набор результатов с возможной модификацией входных значений. Набор входных или выходных значений или оба этих набора могут быть пусты. Например, процедура gcd (наибольший общий делитель) имеет два входных аргумента и один выходной, модифицируя при этом входные данные. В противоположность этому программа remove_dupls (удалить дубликаты) имеет один входной аргумент и не имеет выходного, модифицируя при этом входной.
Начнем с рассмотрения преимуществ, предоставляемых подобного рода абстракциями и, в частности, абстракцией через спецификацию. Затем обсудим спецификации и необходимость их использования. Далее рассмотрим способы задания и составления процедур и завершим рассмотрение общими замечаниями, в которых коснёмся их проектирования.
Абстракция представляет собой некоторый способ отображения. При этом мы “абстрагируемся” от “несущественных” подробностей, описывая лишь те, которые имеют непосредственное отношение к решаемой задаче. Реализации абстракции должны быть согласованы по всем таким “существенным” подробностям, а в остальном могут отличаться. Разумеется, различие между существенным и несущественным зависит от решаемой проблемы.
В абстракции через параметризацию мы абстрагируемся от конкретных значений используемых данных. Эта абстракция определяется в терминах формальных параметров. Фактические данные связываются с этими параметрами в момент использования такой абстракции. Значения конкретных используемых данных являются несущественными; важно лишь их количество и типы. Параметризация позволяет обобщить модули, делая их полезными в большем числе ситуаций. Преимущество таких обобщений заключается в том, что они уменьшают объем программы и, следовательно, объем модификаций.
В абстракции через спецификацию мы фокусируем внимание на особенностях, от которых зависит пользователь, и абстрагируемся от подробностей реализации этих особенностей. Существенным является “поведение” — “то, что делается”, а несущественным — то, “как” это делается. Например, в процедуре sort существенным является факт сортировки массива, а не сам алгоритм сортировки.
Главное преимущество абстракции через спецификацию заключается в несущественности способа реализации, что позволяет нам переходить к другой реализации без внесения изменений в программу, использующую данную реализацию (рис. 3.1). Например, мы можем переписать процедуру sort, использовав метод пирамидальной сортировки, при этом программы, использующие процедуру sort, будут продолжать выполняться правильно и с этой новой реализацией (хотя будет заметно некоторое увеличение производительности). Реализации могут быть даже выполнены на различных языках программирования при том условии, что типы данных аргументов в этих языках трактуются одинаково.
Абстракция через спецификацию наделяет структуру программы двумя отличительными особенностями.
Первая из этих особенностей заключается в локальности, которая означает, что реализация одной абстракции может быть создана или рассмотрена без необходимости анализа реализации какой-либо другой абстракции. Для написания программы, использующей абстракции, программисту достаточно понимать только ее поведение, а не подробности ее реализации.
Рис. 3.1. Общая структура абстракции через спецификацию.
Как само составление программы, так и анализ уже созданной абстракции облегчает так называемый принцип локальности. Этот принцип также позволяет составлять программу из абстракций, создаваемых людьми, работающими независимо друг от друга. Один человек может создать абстракцию, которая использует абстракцию, созданную кем-то другим. После достижения договоренности об общих задачах, выполняемых программой, группа людей может работать над отдельными абстракциями независимо друг от друга, получая при этом корректно выполняющиеся программы. Кроме того, для понимания работы программы достаточно понимания функций только одной абстракции. Для понимания программы, реализующей одну из абстракций, необходимо знать, что реализуют собой сами используемые абстракции, а не конкретные операторы их тела. В большой программе объем “несущественной” информации может быть весьма велик, и мы можем игнорировать не только внутренний текст используемых в ней абстракций, но и коды абстракций, которые они сами используют, и так далее.
Второй особенностью является модифицируемость. Абстракция через спецификацию позволяет упростить модификацию программы. Если реализация абстракции изменяется, но ее спецификация при этом остается прежней, то эти изменения не повлияют на оставшуюся часть программы. Разумеется, если число подлежащих исправлению абстракций достаточно велико, то на это по-прежнему тратится много времени. Как мы увидим, объем работ может быть значительно сокращен путем выделения потенциальных модификаций уже на начальном этапе разработки программы и последующей попыткой ограничения их небольшим числом абстракций. Например, эффект машинной зависимости может быть ограничен несколькими модулями, что обеспечивает простоту в переносимости программ на другую вычислительную машину.
Модифицируемость существенно повышает эффективность программы. Программисты обычно плохо прогнозируют фактическое время, необходимое на разработку сложной системы, вероятно, по той причине, что предугадать все возможные трудности заранее невозможно. По причине неразумности изобретения структур, избегающих несуществующих трудностей, рекомендуется начать с простого набора абстракций, апробировать систему, выясняя все узкие, места, а затем модифицировать соответствующие абстракции.
Очень важно дать абстракциям четкие определения. В противном случае не могут быть достигнуты преимущества абстракции через спецификацию. Например, мы можем заменить одну реализацию абстракции на другую только в том случае, если все то, что поддерживала старая реализация, поддерживает и новая. Элементом, создающим данную зависимость, является абстракция. Следовательно, мы должны знать, что она собой представляет.
Мы будем определять абстракции посредством спецификаций, которые создаются на языке спецификаций, причем последний может быть как формальным, так и неформальным. Преимущество формальных спецификаций заключается в том, что они имеют точно определенное значение. Неформальные спецификации легче читать и понимать, однако точное их содержание установить затруднительно, поскольку язык неформальных спецификаций точным не является. Несмотря на это, неформальные спецификации могут быть весьма информативны, и составлены таким образом, что читатели без труда поймут их смысловое содержание. Здесь мы будем использовать неформальные спецификации.
Спецификация отлична от любой определяемой ею реализации абстракции. Все реализации сходны между собой, поскольку они реализуют одну и ту же абстракцию. Отличие их заключается в том, что это делается разными способами. Спецификация определяет их схожесть.
3. Спецификации процедурных абстракций
Спецификация процедуры состоит из заголовка и описания функции, выполняемого процедурой. Заголовок содержит имя процедуры. Информация о параметрах содержится в разделах “Вход”, “Выход”. Кроме этого, выходные параметры могут, а входные должны быть поименованы.
Информация в разделах “Вход” и “Выход” чисто синтаксическая она описывает “форму” процедуры.
Смысл действий, выполняемых процедурой или функцией, приводится в семантической части спецификации, в которой смысл выполняемых процедурой действий описывается на естественном (разговорном) языке, возможно расширенном привычными математическими обозначениями. В этом описании используются имена входных и выходных параметров.
На рис. 3.2 приводится шаблон спецификации для процедуры. Семантическая часть спецификации состоит из трех разделов — “Предусловия” (требует), “Постусловия” (модифицирует) и “Процесс” (эффекты). Эти предложения должны появляться в указанном ниже порядке, однако предложения “Предусловия” и “Постусловия” обязательными не являются.
Имя процедуры: |
|
Вход: |
Описывается набор входных значений |
Предусловия: |
Задаются необходимые требования |
Процесс: |
Описываются выполняемые функции |
Выход: |
Описывается набор выходных значений |
Постусловия: |
Идентифицируются все модифицируемые входные данные |
Рис. 3.2. Шаблон спецификации для процедурных абстракций.
Раздел “Предусловия” задает ограничения, накладываемые на абстракцию. Раздел “Предусловия” необходим в том случае, если процедура является частичной, т. е. если ее поведение для некоторых входных значений недетерминировано. Если же процедура глобальна, т. е. ее поведение определено для всех входных значений, то раздел “Предусловия” может быть опущен. В этом случае единственными требованиями, предъявляемыми при обращении к процедуре, являются требования, указанные в разделах “Вход” и “Выход”, т. е. число и типы аргументов. В разделе “Постусловия” задается список имен входных параметров, модифицируемых процедурой. Если входные параметры не указаны, то это предложение может быть опущено. Наконец, раздел “Процесс” описывает работу процедуры со значениями, охваченными разделом “Предусловия”. Оно определяет выходные значения и модификации, производимые над входными параметрами, перечисленными в списке раздела “Постусловия”. Раздел “Процесс” составляется исходя из предположения, что требования предложения раздела “Предусловия” удовлетворены. Однако в том случае, когда требования раздела “Предусловия” не удовлетворены, о поведении процедуры ничего не сообщается.
НОД: |
|
Вход: |
a,b – целые значения |
Предусловия: |
(a > 0) И (b > 0) |
Процесс: |
Вычисляет и возвращает наибольший общий делитель для a и b. |
Выход: |
Целое число. |
Постусловия: |
Нет. |
Удалить_дубликаты: |
|
Вход: |
a – массив целых чисел. |
Предусловия: |
Нет. |
Процесс: |
Удаляет из массива а все повторяющиеся элементы. Нижняя граница а остается без изменений, однако порядок следования оставшихся элементов может измениться. Если, например, перед вызовом а = [1:3, 13, 3, 6], то по возвращению массив а имеет нижнюю границу, равную 1, и содержит три элемента 3, 13 и 6, расположенных в некоторой неопределенной последовательности. |
Выход: |
Нет. |
Постусловия: |
Модифицируется а. |
Искать_значение: |
|
Вход: |
a – массив целых чисел, x – целое значение. |
Предусловия: |
Массив a упорядочен по возрастанию. |
Процесс: |
Если элемент х принадлежит массиву а, то возвращается значение i такое, что a [i ] = х; в противном случае значение i на единицу меньше, чем значение нижней границы массива а. |
Выход: |
Целое значение. |
Постусловия: |
Нет. |
Рис. 3.3. Спецификация процедурной абстракции.
На рис. 3.3 приведено несколько спецификаций. Процедура НОД не модифицирует входные переменные, а процедура Удалить_дубликаты изменяет входной массив, что отмечено в разделе “Постусловия”. Отметим, что в спецификации процедуры Удалить_дубликаты дается пример. Наличие примеров облегчает понимание спецификации, и их рекомендуется использовать во всех подходящих случаях.
Процедура Удалить_дубликаты является общей процедурой, поскольку её спецификация не содержат раздела “Предусловия”. Процедуры НОД и
Искать_значение являются частичными. НОД вычисляет своё значение, если входные значения больше нуля. А Искать_значение выполняет свою функцию только в том случае, если входной массив отсортирован. Отметим, что раздел “Процесс” ничего не говорит о результате работы процедуры в том случае, когда входной массив не отсортирован. В этом случае составитель процедуры может выбрать любой подходящий для него вариант; например, процедура Искать_значение может в этом случае возвращать индекс, выходящий за границы массива, или индекс, лежащий в пределах границ, но не содержащий х, или даже зацикливаться.Спецификации составляются на языке спецификаций, а не на языке программирования. Кроме этого, спецификации обычно принципиально отличаются от программ, поскольку они фокусируют свое внимание на описании самой абстракции, а не ее реализации.
Реализация процедуры должна выполнять действия, определенные в спецификации. В частности, она должна модифицировать только те входные параметры, которые указаны в разделе “Постусловия”, а условия в разделе “Предусловия” должны выполняться для всех входных значений. Выходные значения должны соответствовать требованиям, указанным в разделе “Поцесс”.
Каждый язык программирования имеет свой механизм реализации процедурных абстракций. В языке C++ эти абстракции реализуются при помощи функций.
На рис. 3.4 показаны две процедуры, написанные на языке C++ и реализующие функцию search. Одна из них использует линейный поиск, а вторая — бинарный. Эти две реализации во многом отличаются друг от друга. Например, для всех небольших массивов бинарный поиск быстрее линейного. Кроме этого, если элемент х встречается в массиве а более одного раза, то две процедуры могут возвратить в качестве результата различные значения индексов. Наконец, если х содержится в массиве а, но сам массив при этом не отсортирован, то процедура, использующая алгоритм бинарного поиска, может возвратить high (a) + 1, а другая процедура может отыскать требуемый элемент х (рассмотрим, например, массив а = [1:1, 7, 6, 4, 9] и х = 7). Тем не менее обе процедуры являются корректными реализациями абстракции search, поскольку обе они выполняются согласно указанной для них спецификации.
//-----------------------------------------------------
const n = 4;
typedef int vector[n];
//-----------------------------------------------------
int linesearch(vector a, int x)//линейный поиск
{
int i = 0;
while (i < n)
{
if (a[i] == x) {return i; }
else i++;
}
return -1;
}
//-----------------------------------------------------
int binarysearch(vector a, int x)//бинарный поиск
{
int l = 0,h = n - 1, mid = (l + h)/2;
while (l != h)
{
if (a[mid] == x) {return mid; }
else if (a[mid] > x) {h = mid; mid = (l + h )/2;}
else {l = mid ; mid = (l + h)/2 + 1;}
}
return -1;
}
Рис. З.4. Две реализации процедуры search.
Рассмотренная ранее процедура sort работает с произвольным массивом целых чисел. Она оказалась бы более полезной, если бы смогла работать с различными массивами данных — символьными, строковыми или массивами действительных чисел. Мы можем достичь подобного обобщения, расширяя абстракцию через параметризацию и используя типы данных в качестве параметров.
Польза от применения типов в качестве параметров очевидна. Это следует из того факта, что многие встроенные типы данных, например массивы, записи и процедуры, параметризованы через типы.
При использовании типов в качестве параметров некоторые значения параметров могут не иметь смысла. Например, массивы могут быть отсортированы только в том случае, если элементы, принадлежащие к типу, упорядочены. Ограничения на параметры типа предполагают набор некоторых заданных операций над ними. Спецификация абстракции должна содержать эти ограничения в разделе “Предусловия”.
Обменять_значениями: |
|
Вход: |
a,b – переменные типа T. |
Предусловия: |
Нет. |
Процесс: |
Обменивает значениями переменные a,b. |
Выход: |
Нет. |
Постусловия: |
Модифицируется а, b. |
Рис. 3.7. Спецификации параметризованных процедур.
Параметризованная абстракция в действительности представляет собой класс взаимосвязанных абстракций, определенных в одной спецификации. Например, параметризованная абстракция sort представляет собой не одну параметризованную процедуру, а целый класс процедур, одна из которых принимает в качестве параметра массив целых чисел, другая — строковый массив и т. д. Мы будем поименовывать такие процедуры сочетанием имени класса с именем типа, например sort [целочисленная ] и sort [строковая]. Аналогично мы получим search [целочисленная] и search [действительная].
//---------------------------------------------------------------------------
template <class T>
void swap(T& x, T& y)
{
T t;
t = x;
x = y;
y = t;
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
int a = 2, b = 3;
float c = 8, d = 9;
swap(a,b);
cout << "a = "<< a << " b = "<< b << endl;
swap(c,d);
cout << "c = "<< c << " d = "<< d << endl;
getch();
return 0;
}
//---------------------------------------------------------------------------
Рис. Реализация параметризованной процедурной абстракции swap.
6. Создание процедурных абстракций
В данном разделе, мы рассмотрим ряд проблем, возникающих при создании процедурных абстракций. Процедуры, как и другие виды абстракций, которые мы рассмотрим позднее, в процессе своего создания необходимо минимизировать. В них должны быть реализованы только необходимые функции. Это предоставляет разработчику большую свободу, позволяя ему создать более эффективную версию. Например, если приведенная на рис. 3.5 процедура sort позволяет модифицировать аргумент, заданный массивом, то это уменьшает занимаемый ею объем памяти. Однако список значимых для пользователя подробностей такого рода должен быть ограничен.
К одному из таких пунктов, который обычно остается неопределенным, относится сам метод, используемый в конкретной реализации. Обычно пользователям предоставляется свобода в его выборе. (Впрочем, имеются исключения; например, процедура, работающая с числами, может быть ограничена хорошо известным числовым методом с тем, чтобы при округлении ее работа приводила к известным, четко определяемым погрешностям.) Также могут быть оставлены неопределенными некоторые выполняемые процедурой функции. В такой ситуации процедура становится недоопределенной. Это означает, что для определенных значений входных параметров на выходе вместо единственного правильного результата имеется набор допустимых результатов. Реализация может ограничивать этот набор только одним значением, однако он может быть любым из числа допустимых.
Процедура search является недоопределенной, поскольку мы не указываем точно, какой индекс должен быть возвращен в том случае, если значение х встречается в массиве несколько раз. Как уже говорилось, две приведенные на рис. 3.4 реализации процедуры search отличаются именно в этом пункте. Однако каждая из них является корректной.
Процедура remove_dupls (рис. 3.3) также является недоопределенной, поскольку она не всегда сохраняет исходный порядок следования элементов в выходном массиве. Отсутствие такого требования может явиться причиной ошибки, поскольку пользователи могут быть заинтересованы в сохранении исходного порядка. Например, если входной массив отсортирован, то желательно сохранять исходный порядок. Важно отметить, что подобные ограничения зависят от нужд пользователей. Каждая существенная для пользователей подробность должна быть оговорена в спецификации, а остальные оставлены неопределенными.
Недоопределенная абстракция может иметь детерминированную реализацию, т. е. такую, которая, будучи вызванной два раза с идентичными входными данными, выполняется одинаково. Обе реализации процедуры search, приведенные на рис. 3.4, являются детерминированными. (Недетерминированные реализации требуют использования своих собственных переменных. Здесь они не рассматриваются.)
Помимо требований к минимизации другим важным свойством процедур является обобщаемость, которая достигается путем использования параметров вместо переменных. Например, процедура, работающая с массивами произвольного размера, является более обобщенной, чем та, которая работает с массивами фиксированного размера. Аналогично процедура, работающая с массивами элементов произвольного типа, является более обобщенной, чем процедура, требующая, чтобы все элементы массива были целыми числами. Однако обобщение процедуры полезно только в том случае, если эффективность ее применения повышается. Это почти всегда так, когда речь идет о независимости от размеров, поскольку при этом небольшие изменения контекста применения процедуры (например, удваивание размера массива) требуют небольших модификаций в программе.
Другой важной характеристикой процедур является простота. Процедура должна обладать хорошо определенным и легко объяснимым назначением, независимым от контекста ее использования. Хорошим правилом может служить присваивание процедуре имени, описывающем ее назначение. Отсутствие такого дополнительного пояснения может породить сложности.
Наконец, процедура должна действительно выполнять некоторые функции. Процедуры создаются в процессе написания программы и служат цели упрощения и облегчения работы с ней, а также создания более ясной структуры программы. При этом программа становится более легко понимаемой. Однако существует опасность введения слишком большого числа процедур. Например, приведенная на рис. 3.6 процедура merge полезна потому, что ее назначение четко выражено, а также потому, что она позволяет нам отделить друг от друга задачи сортировки и слияния. Это делает процедуру merge_sort более ясной и понятной. По всей видимости, дальнейшая декомпозиция является избыточной. Например, тело цикла в процедуре merge может быть выделено в процедуру, однако в этом случае ее назначение трудно определить.
Некоторые описанные ранее процедуры являются частичными, другие — общими. Подобная дихотомия поднимает вопрос о том, в каких случаях выгоднее определять частичную абстракцию. Частичные процедуры не так безопасны, как общие, поскольку они требуют от пользователя выполнения требований, заданных в разделе “Предусловия”. Если эти требования не удовлетворены, то поведение процедуры становится неопределенным, что может привести к неверной работе программы. Например, при задании для процедуры search неупорядоченного массива она может возвратить неверный индекс. Эта ошибка может оставаться необнаруженной долгое время после возврата из процедуры search. Вследствие этого причина ошибки будет неясна, а объекты данных могут быть разрушены.
С другой стороны, частичные процедуры могут оказаться более эффективными в реализации, чем общие. Например, если процедура search должна работать даже в том случае, если массив не был упорядочен, то ни одна из реализаций, приведенных на рис. 3.4, не будет правильной. В этом случае можно будет использовать только менее эффективный вариант, при котором анализируются все элементы массива.
При выборе между частичной и общей процедурами мы должны придерживаться определенных соглашений. С одной стороны, критерием должна, являться эффективность. С другой — корректное выполнение с меньшим числом потенциальных ошибок. Каким образом осуществить такой выбор? Одним из важных факторов является ожидаемая область применения. Если процедура создается для общего пользования (например, доступна как часть библиотеки программ), то соображения безопасности играют существенную роль. В такой ситуации невозможно осуществить статистический анализ всех обращений к процедуре, позволяющий удостовериться в том, что необходимые требования удовлетворены. Следовательно, в этом случае полагаться на такой анализ неразумно.
Другой случай предполагает использование некоторых процедур в ограниченном контексте. Такой была ситуация, когда процедуры merge и merge_sort вызывались только программой sort, использующей метод сортировки слиянием. В ограниченном контексте легко обеспечить выполнение необходимых требований. Например, два массива, передаваемые процедуре merge, только что были отсортированы. Следовательно, мы имеем безопасное поведение, не жертвуя при этом эффективностью.
Наконец, необходимо наличие четкой и понятной спецификации.
В этой главе мы имели дело главным образом с процедурами: что они из себя представляют, как описывается их поведение и как осуществляется их реализация. Мы также рассмотрели два важных преимущества абстракции и необходимость в спецификации.
Абстракция дает два основных преимущества, заключающихся в локальности и модифицируемости. Оба этих преимущества базируются на различии между абстракцией и ее реализациями. Локальность предполагает, что каждая реализация может быть рассмотрена независимо от остальных. Абстракция может быть использована без уяснения для себя способа ее реализации и реализована без понимания того, как она будет использована. Модифицируемость означает, что одна реализация может быть заменена другой без изменения других программ.
Для достижения этих преимуществ мы должны иметь описание абстракции, которое отлично от любой ее реализации. До сих пор мы рассматривали спецификацию, которая описывает поведение абстракции на специальном языке спецификаций. Этот язык может быть формальным или неформальным. Пользователи должны опираться на описываемое в спецификации поведение данной процедуры, а создатели процедуры должны обеспечить это поведение. Следовательно, спецификация является соглашением между пользователями процедуры и ее составителями.
Процедуру можно рассматривать как некоторое отображение входных значений в выходные с возможной модификацией некоторых входных значений. Поведение процедуры, подобно другим видам абстракций, описывается в ее спецификации, и здесь мы даем форму неформальных спецификаций процедур.
Поскольку мы заинтересованы в разработке и реализации хороших абстракций, то заканчиваем тему рассмотрением того, как должны выглядеть процедуры. Желательно наличие таких свойств, как минимальность, простота и обобщенность. Требование минимальности часто ведет к недоопределенным абстракциям. Мы продолжим обсуждение этих свойств в последующих темах по мере рассмотрения других видов абстракций.