Лекция 2:

к оглавлению
оглавление

Методология программирования

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

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

[к началу]

Декомпозиция и абстракция

Итак,

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

На этапе декомпозиции задачи на подзадачи следует придерживаться трех правил:

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

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

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

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

Пример. Группа авторов создает пьесу, причем каждый из них пишет текст для одного персонажа. Очевидно, что хотя каждый из авторов и справится со своей задачей, о смысле готового произведения говорить не приходится.

Поэтому стадии декомпозиции должен предшествовать этап абстракции.

Абстракция подразумевает собой процесс изменения уровня детализации программы. Когда мы абстрагируемся от проблемы, мы предполагаем игнорирование ряда подробностей с тем, чтобы свести задачу к более простой.

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

Пример. Группа авторов предварительно оговаривает сюжет пьесы, смысл отдельных диалогов и т.п.

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

Как уже упоминалось, процесс абстракции может быть выражен как некоторое обобщение. Оно позволяет рассматривать различные предметы, так как если бы они были эквивалентны за счет выделения существенных атрибутов от несущественных. Одним из первых шагов на пути понятия процесса абстракции мы все проделали еще в первых классах школы, когда от конкретной задачи "3 яблока + 2 груши = ? фруктов" перешли к осознанию более абстрактного выражения "3+2 = ?", а затем и вовсе "X+Y = ?".

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

Сравним, например, два фрагмента кода

int i,a[100];

int iaMax = 0;
int aMax = a[0];
for (i=1; i<100; i++)
{
if (a[i]>aMax)
{
aMax = a[i];
iaMax = i;
}
}
int i,a[100];

int iaMax = 99;
int aMax = a[99];
for (i=98; i>=0; i--)
{
if (a[i]>aMax)
{
aMax = a[i];
iaMax = i;
}
}

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

Было бы гораздо удобнее обладать некоторым мощным набором примитивов для манипуляции со структурами данных. Так, если бы существовали примитивы GetMaxValue и GetMaxIndex, тогда рассматриваемая задача легко реализуется

aMax = GetMaxValue (a);

iMax = GetMaxIndex (a);

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

[к началу]

Абстракция через параметризацию

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

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

int aMax, a[100];
int zMax, z[100];

aMax = GetMaxValue (a);

zMaz = GetMaxValue (z);

Следовательно, мы используем абстракцию через параметризацию, обобщая этим процедуру и делая ее более универсальной.

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

[к началу]

Абстракция через спецификацию

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

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

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

При анализе спецификации для уяснения смысла обращения к процедуре нужно придерживаться двух правил:

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

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

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

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

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

Например, абстракцию SQRT (извлечение квадратного корня) можно сравнить с операцией: она абстрагирует отдельное событие или задачу. Мы будем ссылаться к абстракциям такого рода как к процедурным абстракциям. Отметим, что абстракция SQRT включает в себя как абстракцию через параметризацию, так и абстракцию через спецификацию. Процедурная абстракция – мощное средство. Она позволяет расширить заданную некоторым языком программирования виртуальную машину новой операцией. Такое расширение полезно, когда мы работаем с задачами, которые можно представить в виде набора независимых функциональных единиц. Однако часто удобно к такой новой виртуальной машине добавить несколько объектов данных с новыми типами.

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

Например, при работе с целыми числами используются обычные арифметические операции, но при работе со стеком нужны другие операции, такие как POP (изъять из стека), PUSH (положить в стек).

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

[к началу]

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

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

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

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

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

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

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

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

Абстракция через спецификацию наделяет структуру программы двумя отличительными особенностями.
1. Локальность
2. Модифицируемость

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

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

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

[к началу]

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

То, какие новые типы данных необходимы, зависит от области применения программы. При реализации интерпретатора полезны стеки, а при определении пакета численных функций – матрицы, в банковской системе естественной абстракцией являются счета. В каждом конкретном случае абстракция данных состоит из набора объектов (стеков, полиномов, матриц и т.д.) и набора операций над ними. Например, матричные операции включают в себя сложение, умножение...

Новые типы данных должны включать в себя абстракции как через параметризацию, так и через спецификацию. Абстракция через параметризацию может быть осуществлена также как и для процедур, – использованием параметров там, где это имеет смысл. Абстракция через спецификацию достигается за счет того, что мы представляем операции как часть типа. Чтобы понять зачем, почему необходимы операции, посмотрим, что получится, если рассматривать тип просто как набор объектов. В этом случае, все, что необходимо сделать для реализации типа – это выбрать представление памяти для объектов. Тогда все программы могут быть реализованы в терминах этого представления. Однако, если представление изменяется, все программы, которые используют этот тип, должны быть изменены.

С другой стороны, предположим, что операции включены в определение типа следующим образом:

абстракция данных = <объекты, операции>

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

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

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

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

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

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

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

[к началу]

Классы операций

Операции абстракции данных распадаются на четыре класса.

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

2. Конструкторы. Эти операции используют в качестве аргументов объекты соответствующего им типа и создают другие объекты такого же типа. Например, операция сложения матриц создает новую матрицу.

3. Модификаторы. Эти операции модифицируют объекты соответствующего им типа. Например, операция push для стека.

4. Наблюдатели. Эти операции используют в качестве аргумента объекты соответствующего им типа и возвращают элемент другого типа, они используются для получения информации об объекте. Сюда относятся, например, операции типа size. Обычно примитивные конструкторы создают не все, а только некоторые объекты. Другие объекты создаются конструкторами и модификаторами. Иногда наблюдатели комбинируются с конструкторами и модификаторами (pop).

Теперь скажем несколько слов о полноте новых типов данных.

[к началу]

Полнота.

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

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

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

[к началу]
назад КОНЕЦ ВТОРОЙ СЕРИИ вперед