18.2. Структурное проектирование и программирование
Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»).
В результате строится иерархическая схема, отражающая состав и взаимоподчиненность отдельных функций, которая носит название функциональная структура алгоритма (ФСА) приложения.
Последовательность действий по разработке функциональной структуры алгоритма приложения:
определяются цели автоматизации предметной области и их иерархия (цель-подцель);
устанавливается состав приложений (задач обработки), обеспечивающих реализацию поставленных целей;
уточняется характер взаимосвязи приложений и их основные характеристики (информация для решения задач, время и периодичность решения, условия выполнения и др.);
определяются необходимые для решения задач функции обработки данных;
выполняется декомпозиция функций обработки до необходимой структурной сложности, реализуемой предполагаемым инструментарием.
Подобная структура приложения (рис. 18.2) отражает наиболее важное – состав и взаимосвязь функций обработки информации для реализации приложений, хотя и не раскрывает логику выполнения каждой отдельной функции, условия или периодичность их вызовов.
Разложение должно носить строго функциональный характер, т.е. отдельный элемент ФСА описывает законченную содержательную функцию обработки информации, которая предполагает определенный способ реализации на программном уровне.
Функции ввода-вывода информации рекомендуется отделять от функций вычислительной или логической обработки данных.
По частоте использования функции делятся на:
Степень детализации функций может быть различной, но иерархическая схема должна давать представление о составе и структуре взаимосвязанных функций и общем алгоритме обработки данных. Широко используемые функции приобретают ранг стандартных (встроенных) функций при проектировании внутренней структуры программного продукта.
Пример 18.4. Некоторые функции, например Ф2, далее неразложимы на составляющие: они предполагают непосредственную программную реализацию. Другие функции, например Ф1, Фm, могут быть представлены в виде структурного объединения более простых функций, например Ф11, Ф12 и т.д. Для всех функций-компонентов осуществляется самостоятельная программная реализация; составные функции (типа Ф1, Фm) реализуются как программные модули, управляющие функциями-компонентами, например, в виде программ-меню.
Рис. 18.2. Функциональная структура приложения:
Ц – цель; пЦ – подцель; П – приложение; Ф – функция
МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ
Модульное программupовоние основано на понятии модуля – логически взаимосвязанной совокупности функциональных элементов, оформленных в виде отдельных программных модулей.
один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input – Process – Output) – вход-процесс-выход;
функциональная завершенность – модуль выполняет перечень регламентированных операций для реализации каждой отдельной функции в полном составе, достаточных для завершения начатой обработки;
логическая независимость – результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;
слабые информационные связи с другими программными модулями – обмен информацией между модулями должен быть по возможности минимизирован;
обозримый по размеру и сложности программный элемент.
Таким образом, модули содержат определение доступных для обработки данных, операции обработки данных, схемы взаимосвязи с другими модулями.
Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело – способ реализации процесса обработки.
Модульная структура программных продуктов
Принципы модульного программирования программных продуктов во многом сходны с принципами нисходящего проектирования. Сначала определяются состав и подчиненность функций, а затем – набор программных модулей, реализующих эти функции.
Однотипные функции реализуются одними и теми же модулями. Функция верхнего уровня обеспечивается главным модулем; он управляет выполнением нижестоящих функций, которым соответствуют подчиненные модули.
При определении набора модулей, реализующих функции конкретного алгоритма, необходимо учитывать следующее:
каждый модуль вызывается на выполнение вышестоящим модулем и, закончив работу, возвращает управление вызвавшему его модулю;
принятие основных решений в алгоритме выносится на максимально «высокий» по иерархии уровень;
для использования одной и той же функции в разных местах алгоритма создается один модуль, который вызывается на выполнение по мере необходимости.
В результате дальнейшей детализации алгоритма создается функционально-модульная схема (ФМС) алгоритма приложения, которая является основой для программирования (рис. 18.3).
Рис. 18.3. Функционально-модульная структура приложения
Пример 18.5. Некоторые функции могут выполняться с помощью одного и того же программного модуля (например, функции Ф1 и Ф2).
Функция Ф3 реализуется в виде последовательности выполнения программных модулей.
Функция Фm реализуется с помощью иерархии связанных модулей.
Модуль n управляет выбором на выполнение подчиненных модулей.
Функция Фх реализуется одним программным модулем.
Состав и вид программных модулей, их назначение и характер использования в программе в значительной степени определяются инструментальными средствами. Например, применительно к средствам СУБД отдельными модулями могут быть:
экранные формы ввода и/или редактирования информации базы данных;
отчеты генератора отчетов;
стандартные процедуры обработки информации;
меню, обеспечивающее выбор функции обработки и др.
Алгоритмы большой сложности обычно представляются с помощью схем двух видов:
обобщенной схемы алгоритма – раскрывает общий принцип функционирования алгоритма и основные логические связи между отдельными модулями на уровне обработки информации (ввод и редактирование данных, вычисления, печать результатов и т.п.);
детальной схемы алгоритма – представляет содержание каждого элемента обобщенной схемы с использованием управляющих структур в блок-схемах алгоритма, псевдокода либо алгоритмических языков высокого уровня.
Наиболее часто детально проработанные алгоритмы изображаются в виде блок-схем согласно требованиям структурного программирования; при их разработке используются условные обозначения согласно ГОСТ 19.003-80 ЕСПД (Единая система программной документации). Обозначения условные графические, ГОСТ 19.002-80 ЕСПД. Схемы алгоритмов и программ. Правила обозначения.
СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
Структурное программирование основано на модульной структуре программного продукта и типовых управляющих структурах алгоритмов обработки данных различных программных модулей (рис. 18.4).
Рис. 18.4. Блок-схема алгоритма поиска в базе данных
В любой типовой структуре блок, кроме условного, имеет только один вход и выход, безусловный переход на блок с нарушением иерархии запрещен (оператор типа GoTo в структурном программировании не используется). Виды основных управляющих структур алгоритма приведены в табл. 18.1.
Пример 18.6. Алгоритм поиска в базе данных сведений о максимальном окладе сотрудников (рис. 18.4).
Таблица 18.1. Управляющие структуры алгоритмов
Типовые задачи, решаемые методами функционального программирования
Любой математический аппарат предназначен для решения конкретных задач. Некоторые формализмы имеют более узкую специализацию, иные — предоставляют довольно широкие возможности. В любом случае, ни один из теоретических формализмов в их практическом применении не может быть рассматриваем в чистом виде, как «вещь в себе», созданная только ради самой себя.
В связи с этим и парадигма функционального программирования как одно из направлений дискретной математики первоначально разрабатывалась для решения специфического класса задач. Однако впоследствии такой класс расширился, были найдены новые применения теоретическому материалу, а в последнее время в связи в бурным развитием вычислительной техники функциональное программирование даже начинает применяться и для таких задач, которые больше свойственны программированию императивному (например, разработка приложений графического характера).
Однако традиции нарушать не стоит. Поэтому далее в этом разделе рассматриваются в качестве задач, именно традиционно изучающихся в рамках курсов по функциональному программированию, следующие.
- 1. Получение остаточной процедуры.
- 2. Построение математического описания функций.
- 3. Определение формальной семантики языка программирования.
- 4. Описание динамических структур данных.
- 5. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой.
- 6. Доказательство наличия некоторого свойства программы.
- 7. Эквивалентная трансформация программ.
Все эти задачи достаточно легко решаются средствами и механизмами, разработанными в рамках функционального программирования, но решаются гораздо сложнее в императивных языках (за исключением пары проблем, более или менее простое решение для которых было найдено опять-таки благодаря развитию технических средств, на которых выполняются программы). Далее кратко рассматриваются все перечисленные задачи с указанием глав и разделов книги, в которых их решение описывается самым подробным образом.
Кроме того, все больше и больше методов и инструментов, предлагаемых парадигмой функционального программирования для решения задач, находит свое применение в рамках искусственного интеллекта как науки о решении слабофор-мализованпых и неформализованных задач. Это связано с тем, что функциональное программирование как нельзя лучше подходит для описания проблем искусственного интеллекта, то есть постановки задачи компьютеру, если так можно выразиться, без точной формализации. Исследователь, нс задумываясь о способах представления данных, о методах решения, просто переводит свои математические формулы на функциональный язык, после чего предоставляет время на работу интерпретатору. Тем самым ученый избавляет себя от скрупулезной формализации того, что он формализовать не в силах зачастую даже для самого себя, не говоря уже о вычислительной технике.
Хотя такой способ решения для некоторых задач дает сбой из-за слишком долгого времени интерпретации (то есть, по сути, поиска решения), сам процесс может натолкнуть исследователя на новые возможности в поиске решения.
Некоторые задачи искусственного интеллекта и их разработка при помощи языка Haskell предлагаются для ознакомления в главе 7.