Современные технологии программирования |
Конспект лекций |
Лекция 2. Декомпозиция и абстракция
Содержание
ЖЦ
- является моделью создания и использования программного обеспечения (ПО), отражающей его различные состояния, начиная с момента возникновения необходимости в данном программном изделии и заканчивая моментом его полного выхода из употребления у всех пользователей.Анализ требований - первая фаза разработки ПО, на которой требования заказчика уточняются, формализуются и документируются. На этом этапе даётся ответ на вопрос: “Что должна делать будущая система?”.
Проектирование - вторая фаза разработки ПО, которая даёт ответ на вопрос: “Каким образом система будет удовлетворять предъявленным к ней требованиям?”.
Тестирование - третья фаза разработки ПО, на которой осуществляется тестирование и отладка ПО.
Эксплуатация - четвёртая фаза разработки ПО, на которой осуществляется сопровождение и модификация ПО.
Технология программирования - система методов принципов и средств автоматизации, обеспечивающих в заданных условиях получение программной продукции с заданными свойствами.
Декомпозиция - процесс разделения сложной задачи на множество меньших независимых задач, лёгких для понимания и решения.
Детализация - привлечение в рассмотрение существенной для решаемой задачи информации.
Абстракция (абстрактное понятие) - понятие, в котором мыслится свойство предмета или отношения между предметами.
Иерархия - порядок подчинения низших чинов высшим чинам.
Цель процесса декомпозиции - на основе детализации расчленить исходную задачу на части, которые представляют собой выбранные абстракции, и построить схему иерархии полученных абстракций.
Набор абстракций определяет выбранная технология программирования. Так технология на основе абстрактных типов данных предлагает описывать задачу в терминах, для описания которых, в свою очередь, используются абстракции через параметризацию, абстракции через спецификацию, абстракции итерации и процедурные абстракции.
При декомпозиции задачи мы разбиваем её на ряд подзадач так, чтобы
Декомпозиция задачи требует вовлечения в рассмотрение деталей, особенностей процесса обработки данных, исполняемого при решении задачи.
Правильно выбранный уровень детализации позволяет сформировать абстракции следующего уровня, абстрагированием от введённых деталей.
На начальном этапе решения задачи уровень абстрагирования - наивысший, уровень детализации - низший.
Конечный этап решения задачи характеризуется низшим уровнем абстрагирования и наивысшим уровнем детализации.
Абстракция представляет собой эффективный способ декомпозиции, осуществляемый посредством изменения списка детализации. Когда мы абстрагируемся от проблемы мы предполагаем игнорирование ряда подробностей с тем, чтобы свести задачу к более простой.
Последовательное выполнение декомпозиции посредством детализации и последующего абстрагирования выполняется при проектировании до тех пор, пока исходная проблема не будет сведена к набору подзадач, решение которых известно.
Понятие - форма мышления, отражающая предметы в их существенных признаках.
Содержание понятия - совокупность существенных признаков предмета, которая мыслится в данном понятии.
Объём понятия - совокупность предметов, которая мыслится в понятии.
Термин - это слово или словосочетание, обозначающее строго определённое понятие в пределах данной науки или группы родственных наук.
Конкретное понятие - понятие, в котором мыслится предмет или совокупность предметов как нечто самостоятельно существующее.
Абстрактное понятие - понятие, в котором мыслится свойство предмета или отношение между предметами.
Определение понятия - логическая операция, раскрывающая содержание понятия.
Процесс обработки данных - процесс последовательного изменения состояния данных в результате выполнения над ними заданных операций, цель которого - получение результирующего состояния данных из исходного.
Абстракция - абстрактное понятие о процессе обработки данных.
Абстрагирование - мысленное выделение отдельных признаков предмета и отвлечение от других признаков называется абстрагированием.
Спецификация - форма (шаблон) в соответствии с которой, раскрывается содержание абстракции.
Реализации - процессы обработки данных, которые мыслятся в абстракции.
Наша цель — составление программ высокого качества, являющихся несложными, легко модифицируемыми и простыми в обращении.
Очень небольшая программа, содержащая всего несколько сотен строк, может быть представлена одной “неделимой” единицей. Однако по мере возрастания размера программы такая монолитная структура становится неудобной, поскольку ее текст уже труден для понимания. Поэтому программа должна быть разбита на ряд независимых небольших программ, называемых модулями, которые сообща выполняют требуемую функцию. Мы остановимся на этом процессе декомпозиции более подробно, какие типы модулей наиболее подходящие при таком процессе, и какие способы увеличивают вероятность того, что объединение этих модулей даст возможность решить поставленную задачу.
Корректность процесса декомпозиции становится все более и более важной по мере того, как размер программы возрастает. Это обусловливается следующими причинами. Во-первых, в процесс составления программы вовлекается все большее число людей. Если над программой работает несколько человек, то естественно предположить их регулярные контакты. Такой контакт снижает вероятность различных разногласий, касающихся того, кто и что должен делать, и уменьшает серьезность последствий, возникающих в подобных ситуациях. Если над задачей работает много людей, то регулярные взаимодействия между ними становятся невозможными, поскольку они отнимают слишком много времени. По этой причине программа может быть разбита на части, причем каждая из них может создаваться отдельными участниками независимо от остальных, вследствие чего контакты между людьми становятся минимальными.
Полезное время жизни программы (ее “рабочая” стадия) начинается с того момента, когда она передается потребителю. Однако на этом работа над программой не заканчивается. В тексте программы могут быть требующие исправления ошибки, а для обеспечения удобства работы с программой сообразно с требованиями пользователя может возникнуть необходимость в ее дальнейшей модификации. Работа по модификации и сопровождению программы может потребовать больше времени, чем все время, потраченное на ее разработку.
При модификации и сопровождении программы редко оказывается разумным начинать работу с ее полной переделки. Вместо этого предпочтительней внести изменения в уже существующую структуру и, следовательно, весьма важно, чтобы структура допускала возможность подобной модификации. В частности, необходимо, чтобы части программы были независимы друг от друга с тем, чтобы изменение в одной части могло быть сделано без изменения других ее частей.
И, наконец, время жизни большинства программ достаточно велико, поэтому работа с ними продолжается еще долгое время. Кроме этого, необходимо учитывать постоянные изменения в составе рабочей группы, что приводит к тому, что модификация программ обычно выполняется уже не разработчиками задачи. Все эти факторы предполагают структурирование программ таким образом, чтобы они были легко понимаемыми.
В методологии, описанной далее, программы составляются путем декомпозиции задачи. Эта декомпозиция основана на опознавании абстракций. Декомпозиция и абстракция, являясь двумя ключевыми концепциями, и составят предмет нашего последующего обсуждения.
1.1. Декомпозиция и абстракция
Базовая парадигма в подходе к любой большой задаче ясна: мы должны “разделять и властвовать”. К сожалению, буквальное следование этому макиавеллевскому принципу по-прежнему предполагает долгий путь к решению задачи. Самым важным является то, каким образом мы осуществляем это разделение.
Нашей целью при декомпозиции программы является создание модулей, которые в свою очередь представляют собой небольшие программы, взаимодействующие друг с другом по хорошо определенным и простым правилам. Если мы достигнем этой цели, то разработка отдельных модулей может осуществляться различными людьми независимо друг от друга, без необходимости общения друг с другом, при этом все эти объединенные вместе программы будут функционировать правильно. Помимо этого в процессе модификации программы появится возможность корректировать отдельные модули без необходимости исправления других.
При декомпозиции задачи мы разбиваем ее на ряд подзадач так, что
Изящным примером декомпозиции является сортировка с использованием метода “сортировка слиянием”. В этом случае сортируемый список произвольного размера разбивается на две более простые задачи, каждая из которых сортирует половину списка, после чего производится слияние двух отсортированных списков произвольной величины.
Декомпозиция является весьма полезным и экономящим время способом решения задач в самых различных областях. Со времен Беббиджа люди осознали выгоду от использования программистами таких средств декомпозиции, как макроопределения и подпрограммы. Важно понимать, что декомпозиция не является некой панацеей и при неграмотном использовании может принести массу неприятностей. Отметим далее, что большие или плохо понимаемые задачи поддаются декомпозиции с большим трудом. К числу наиболее распространенных проблем относится ситуация, при которой создание отдельных компонент, способных решить соответствующие подзадачи, не приводит к тому, что объединение этих компонент позволяет решить исходную задачу. Это является одной из причин, по которой интеграция системы часто оказывается затруднительной.
Предположим, например, что группа авторов создает пьесу. Каждому автору дается список персонажей и общий план. Каждый из них должен при этом написать текст для одного из персонажей. Можно предположить, что любой из авторов без труда справится с поставленной перед ним задачей, однако маловероятно, что пьеса в целом окажется удачной. Она может быть достаточно художественна, но в ней, скорее всего, будет отсутствовать какой-либо смысл. Приемлемые в отдельности решения не могут быть объединены подходящим образом, если исходная задача была разделена на части непродуманно.
Абстракция представляет собой эффективный способ декомпозиции, осуществляемый посредством изменения списка детализации. Когда мы абстрагируемся от проблемы мы предполагаем игнорирование ряда подробностей с тем, чтобы свести задачу к более простой. Например, в задаче по созданию пьесы мы можем свести ее к задаче решения того, сколько актов она должна содержать, каков должен быть общий замысел или даже смысл (но не сам текст) отдельных диалогов. После выполнения этого исходная задача по-прежнему будет оставаться нерешенной, однако она значительно упростится — возможно, даже до такой степени, что может быть решена другим человеком или даже группой таких людей. (Подобным образом писал свои романы Дюма-отец.)
Задачи абстрагирования и последующей декомпозиции типична для процесса создания программы: декомпозиция используется для разбиения программы на компоненты, которые могут быть, затем объединены, позволив решить основную задачу; абстрагирование же предполагает продуманный выбор компонент. Мы последовательно выполняем то один, то другой из этих процессов до тех пер, пока не сведем исходную задачу к набору подзадач, решение которых известно.
Процесс абстракции может быть рассмотрен как некоторое обобщение. Он позволяет нам забыть об информации и, следовательно, рассматривать различные предметы так, как если бы они были эквивалентны. Мы выполняем это в надежде упростить наш анализ, отделяя существенные атрибуты от несущественных. Однако при этом важно знать, что критерий такого отделения во многом зависит от контекста. В контексте школьного курса мы учимся абстрагировать от (8/3)*3 и 5 + 3 к понятию, представленному числом 8. В дальнейшем мы узнаем, что при работе на большинстве вычислительных машин такая абстракция приводит к неприятностям.
Например, рассмотрим структуру, приведенную на рис. 1.1. Понятием здесь является “млекопитающие”. Все млекопитающие обладают определенными общими характеристиками. Например, все женские особи этого класса вырабатывают молоко. На таком уровне абстракции мы фокусируемся именно на этих общих характеристиках и игнорируем различия между существующими видами млекопитающих.
На нижнем уровне абстракции мы сосредоточиваем свое внимание на конкретных представителях семейства млекопитающих. В этом случае мы можем абстрагироваться, рассматривая не отдельных представителей или даже особей, а группы родственных особей, например, приматов или грызунов. Здесь опять мы рассматриваем общие характеристики, например тот факт, что все приматы носят своих детенышей, а не отличия между, скажем, человеком и шимпанзе. Эти отличия остаются существенными и на более низких уровнях абстракции.
Рис. 1.1. Иерархия абстракций.
Иерархия абстракций, показанная на рис. 1.1, относится к вполне определенной области зоологии, однако она приложима также и к другим областям этой науки. Более машинно-ориентированным примером, весьма полезным при составлении большей части программ, является концепция “файла”. Файлы абстрагированы от конкретного носителя, реализуя долговременное и постоянно доступное хранилище поименованных единиц. Операционные системы отличаются по способам работы с файлами. Например, структура имен файлов может меняться от системы к системе. Изменяется также и способ их размещения на устройствах внешней памяти.
Далее мы рассмотрим различные виды абстракций и общие принципы применения их в программах. Наиболее существенным достижением в этой области является на сегодняшний день развитие языков высокого уровня. Имея дело непосредственно с конструкциями языка высокого уровня, а не с различными наборами машинных инструкций, в которые данные конструкции могут быть транслированы, программист существенно упрощает свой труд.
В последние годы программистов перестал удовлетворять уровень абстракции, достигаемый в программах, написанных даже на языке высокого уровня. Рассмотрим, например, фрагмент программы на рис. 1.2.
Рис. 1.2. Два фрагмента программы.
На уровне абстракции, определенном использованным языком высокого уровня, очевидно, что приведенные фрагменты отличаются друг от друга: если е присутствует в а, то первый фрагмент отыскивает индекс его первого вхождения, а второй — индекс последнего вхождения. Первая программа устанавливает i в high(а) + 1, а вторая — в low(1) — 1. Обе программы, однако, были написаны для выполнения одной и той же функции: установить в found значение false, если е отсутствует в а, а в противном случае установить в found true и в z — индекс вхождения е в а. Если нам необходимо выполнение именно этого требования, то становится очевидным, что приведенные фрагменты программ не находятся на требуемом уровне абстракции.
Одним из подходов к решению такой проблемы является создание языков “очень высокого уровня”, реализованных на базе некоторого фиксированного набора относительно обобщенных универсальных структур данных и мощном наборе примитивов, используемых для манипуляции с ними. Например, рассмотрим язык, в котором имеются примитивы is_in и index_of, позволяющие осуществлять соответствующие операции над массивами. Тогда рассматриваемая задача легко реализуется следующим образом:
found:= is_in (a, e); if found then z:= index_of (a, e);
Недостатком такого подхода является предположение о том, что разработчик языка включит в него большинство абстракций, которые могут понадобиться пользователю. Предвидеть все возможные ситуации довольно затруднительно. Однако, даже если это и удалось бы сделать, получившийся язык содержал бы столь много встроенных абстракций, что работа с ним стала бы невозможной.
Альтернативой может быть создание таких языковых механизмов, которые позволяют программисту создавать свои собственные абстракции по мере необходимости. Наиболее распространенным механизмом такого рода является использование процедур. Разделяя в программе тело процедуры и обращения к ней, язык высокого уровня реализует тем самым два важных метода абстракции: абстракция через параметризацию и абстракция через спецификацию.
1.2.1. Абстракция через параметризацию
Абстракция через параметризацию позволяет нам, используя параметры, представить фактически неограниченный набор различных вычислений одной программой, которая есть абстракция всех этих наборов. В абстракциях через параметризацию мы абстрагируемся от конкретных используемых данных. Эта абстракция определяется в терминах формальных параметров. Фактические данные связываются с этими параметрами в момент использования такой абстракции. Значения конкретных используемых данных являются несущественными; важно лишь их количество и типы. Параметризация позволяет обобщить процесс обработки данных, делая его полезным в большом числе ситуаций. Преимущество таких обобщений заключается в том, что они уменьшают объём программы и, следовательно, объём модификаций.
Пример. Пусть имеются следующие реализации процессов обработки данных:
2*2+6*6
5*5-8*8
4*4+9*9
5*5+7*7
3*3-5*5
7*7-9*9
Используя абстракцию через параметризацию все их можно обобщить, например, так:
function R(a,b:Integer):Integer;
int R(int a, int b);
Используя заголовки функций Паскаля или C++, а они, по существу, и являются спецификациями абстракции через параметризацию, мы акцентировали наше внимание на таких существенных признаках этих реализаций, как входные параметры, результат и их типах.
Программисты часто используют абстракцию через параметризацию, даже не замечая этого. Например, предположим, что нам необходима процедура, которая сортирует массив целых чисел а. В дальнейшем, вероятно, понадобится отсортировать некоторый другой массив, возможно, в другом месте этой же программы. Однако маловероятно, что каждый такой массив будет иметь имя а. Мы, следовательно, используем абстракцию через параметризацию, обобщая этим процедуру и делая ее более универсальной.
Абстракция через параметризацию является важным средством повышения универсальности программ. Программа sort, сортирующая произвольный массив чисел, полезнее той, которая может работать только с конкретным массивом целых чисел. Дальнейшее абстрагирование позволяет еще больше обобщить программу. Например, мы можем определить абстракцию sort, которая работает над массивами как целых, так и действительных чисел или даже вообще над различными массивоподобными структурами.
Абстракция через параметризацию — весьма полезное средство. Она не только позволяет относительно просто описывать большое (даже бесконечное) число вычислений, но и является легко и эффективно реализуемой на языках программирования. Однако этот способ не позволяет полностью реализовать тот уровень обобщения, который можно достичь при работе с процедурами.
1.2.2. Абстракция через спецификацию
Абстракция через спецификацию позволяет нам абстрагироваться от процесса вычислений, описанных в теле процедуры, до уровня знания лишь того, что данная процедура должна в итоге реализовать. Это достигается путем задания для каждой процедуры спецификации, описывающей эффект ее работы, после чего смысл обращения к данной процедуре становится ясным через анализ этой спецификации, а не самого тела процедуры.
Мы пользуемся абстракцией через спецификацию всякий раз, когда связываем с процедурой некий комментарий, достаточно информативный для того, чтобы иметь возможность работы с ней без анализа тела процедуры. Одним из удобных способов составления подобных комментариев является использование пар утверждений. Утверждение “Предусловие” (или начальное условие) задает на входе процедуры истинность или ложность некоторого условия. Обычно на практике правильное выполнение процедуры задается некоторым набором таких условий. (Это часто просто означает, что некоторое логическое утверждение истинно.) Утверждение “Процесс” (или конечное условие) задает некоторое условие, которое предполагается истинным по завершению данной процедуры в предположении, что для этой процедуры было удовлетворено начальное условие.
Рассмотрим, например, процедуру sqrt на рис. 1.3. Поскольку в процедуре имеется спецификация, мы можем игнорировать тело процедуры. Обращение вида call у:= sqrt(x) будет иметь следующий смысл: “Если при вызове процедуры х больше 0, то после выполнения процедуры у есть приближение квадратного корня из х”. Отметим, что начальные и конечные условия позволяют нам не упоминать о значении у для случая, когда х не больше 0.
При анализе спецификации для уяснения смысла обращения к процедуре мы придерживаемся двух четких правил:
Эти два правила демонстрируют два преимущества, предоставляемых абстракцией через спецификацию. Первое из них состоит в том, что использующие данную процедуру программисты не обязаны знакомиться с ее телом. Следовательно, они освобождены от необходимости уяснения подробностей выполнения описанных в теле вычислений, устанавливая, что процедура действительно извлекает квадратный корень из аргумента. Это является большим преимуществом при работе со сложными процедурами и даже с простыми, но использующими незнакомые алгоритмы,
double sqrt(double coef)
{
double ans = coef/2.0;
int i = 0;
while(i < 7)
{
ans = ans - ((ans * ans - coef)/(2.0 * ans));
i++;
}
return ans;
}
Рис. 1.З. Процедура sqrt.
Второе правило уточняет, что мы на самом деле абстрагировались от тела процедуры, позволив себе не обращать внимания на несущественную информацию. Именно это “забывание информации” и отличает абстракцию от декомпозиции. Анализируя тело процедуры sqrt, пользователи данной процедуры могут извлечь для себя большое количество информации, не следующее из конечного условия, например, что sqrt (4) возвратит результат +2. Однако в спецификации мы говорим, что подобная информация о возвращаемом результате игнорируется. Этим мы утверждаем, что процедура sqrt есть абстракция, представляющая собой набор всех вычислений, при котором вычисляется “приближение квадратного корня из х”.
Пример. Пусть имеются следующие реализации процессов обработки данных:
1) 2*2+2*2*6+6*6
2) 5*5-2*5*8+8*8
3) 4*4+2*4*9+9*9
4) 5*5+2*5*7+7*7
5) 3*3-2*3*5+5*5
6) 7*7-2*7*9+9*9
Используя абстракцию через спецификацию можно обобщить представленные реализации например, так:
1, 3, 4 реализации – квадрат суммы a и b,
2, 5, 6 реализации - квадрат разности a и b.
Здесь мы акцентировали наше внимание на таких существенных признаках этих реализаций, как связь входных параметров с результатом.
Абстракции через параметризацию и через спецификацию являются мощными средствами создания программ. Они позволяют нам определить три различных вида абстракций: процедурную абстракцию, абстракцию данных и абстракцию через итерацию. В общем случае каждая процедурная абстракция, абстракция через данные и абстракция через итерацию используют оба способа.
Например, абстракцию sqrt можно сравнить с операцией: она абстрагирует отдельное событие или задачу. Мы будем ссылаться к абстракциям такого рода как к процедурным абстракциям. Отметим, что абстракция sqrt включает в себя как абстракцию через параметризацию, так и абстракцию через спецификацию.
Процедурная абстракция является мощным средством. Она позволяет нам расширить заданную некоторым языком программирования виртуальную машину новой операцией. Такой вид расширения наиболее полезен в том случае, когда мы работаем с задачами, которые легко представить в виде набора независимых функциональных единиц. Однако часто оказывается более удобным добавить к виртуальной машине несколько объектов данных с новыми типами.
Поведение объектов данных наиболее естественно представлять в терминах набора операций, применимых к данным объектам. Такой набор включает в себя операции по созданию объектов, получению информации от них и, возможно, их модификации. Например, операции push и pop принадлежат к классу операций, имеющих смысл при работе со стеками, в то время как для работы с целыми числами используются обычные арифметические операции. Таким образом, абстракция данных (или тип данных) состоит из набора объектов и набора операций, характеризующих поведение этих объектов.
В качестве примера рассмотрим мультинаборы (multisets). Мультинаборы сходны с обычными наборами, за исключением того, что элемент может входить в мультинабор несколько раз. Операции для работы с подобными мультинаборами включают в себя операции empty, insert, delete, number_of и size. Эти операции создают пустой мультинабор, удаляют и добавляют в него элементы, вычисляют, сколько раз данный элемент входит в мультинабор и сколько всего элементов содержится в мультинаборе. Данные операции могут быть реализованы в языке программирования через соответствующие процедуры. Программисты, работающие с мультинаборами, не должны беспокоиться о том, каким образом эти процедуры реализованы. Для них операции empty, insert, delete, number_of и size являются абстракциями, определяемыми операторами типа
The size of the multi_set insert (s, e) is equal to size (s) + 1
(Размер мультинабора insert (s, e) равен размеру size(s) - 1)
For all e, the number_of times e occurs in the multi_set empty() is 0.
(Для всех е число вхождений е в пустой мультинабор empty () равно 0.)
Важно отметить, что каждый из этих операторов работает сразу с несколькими операциями. Мы не приводим независимые определения каждой операции, но скорее определяем их через взаимосвязи. Этот акцент на взаимосвязях между операциями и делает абстракцию данных существенно отличной от набора процедур. Важность этого отличия обсуждается на протяжении всего дальнейшего повествования.
В дополнение к процедурным абстракциям и абстракциям данных мы рассмотрим также абстракцию через итерацию. Абстракция через итерацию дает возможность не рассматривать информацию, не имеющую прямого отношения к управляющему потоку или циклу. Типичная абстракция итерации позволяет нам обрабатывать все элементы мультинабора без накладывания каких-либо ограничений на последовательность обработки.
Далее мы покажем, как осуществлять декомпозицию программы на базе абстракции через итерацию. Акцент будет делаться на абстракции данных. Мы считаем, что, хотя процедурные абстракции и абстракции через итерацию и играют существенную роль, организация процесса программирования начинается, как правило, с абстракции данных.