Структурный подход в программировании. Структурное программирование

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

Опыт применения методов структурного программирования при разработке, например, ряда сложных операционных систем показывает, что правильность логической структуры системы в этом случае легко поддается доказательству, а сама система допускает достаточно полное тестирование. Уменьшение трудностей отладки и тестирования программ приводит к увеличению производительности труда программистов, поскольку на тестирование программы тратится от трети до половины времени ее разработки. Производительность труда программиста обычно измеряется числом отлаженных операторов, которые он может написать за день. Приближенные оценки показывают, что применение методов структурного программирования позволяет увеличить это число в 5-6 раз. Также нужно сказать, что структурное программирование предполагает определенную организацию самого процесса программирования и определенную технологию проектирования программ, что также положительно влияет на производительность труда программистов.

Основы структурного программирования. Теоретическим фундаментом структурного программирования является теорема о структурировании , из которой следует, что алгоритм (программа) решения любой практически вычислимой задачи может быть представлен с использованием трех элементарных базисных управляющих структур: структуры следования (последовательности); структуры ветвления, структуры цикла, изображенных на рис. 6.5-6.7 соответственно, где Р - условие, S - оператор.

Структура следования представляет собой естественный ход выполнения алгоритма - любую последовательность операторов, выполняющихся друг за другом (см. рис. 6.5). В языке программирования это соответствует последовательности операторов ввода, вывода и операторов присваивания.

Представляет фактор принятия решения, включает проверку некоторого логического условия Р и, в зависимости от результатов этой проверки, выполнение оператора S1 либо оператора S2. В языках программирования (например, Pascal) реализуется оператором if Р then SI else S2 (см. рис. 6.6).

Структура цикла (цикла с предусловием) представляет фактор повторяемости вычислений, обеспечивает многократное повторение выполнения оператора S, пока выполняется (истинно) логическое

Рис. 6.5. Структура следования

Рис. 6.6.

условие Р. В языках программирования (например, Pascal) реализуется оператором while Р do S (см. рис. 6.7).

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

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

Каждая из структур может рассматриваться как один функциональный блок с одним входом и одним выходом. Блоки S, SI, S2, входящие в состав базисных управляющих структур, сами могут быть одной из них, поэтому возможны вложенные конструкции. Однако, какова бы ни была степень и глубина «вложенности», важно, что любая конструкция в конечном итоге имеет один вход и один выход. Следовательно, любую сложную структуру можно рассматривать как «черный ящик» с одним входом и одним выходом. Таким образом, можно ввести преобразование любой структуры в функциональный блок. Тогда всякий алгоритм, составленный из стандартных структур, поддается последовательному преобразованию к единственному функциональному блоку, и эта последовательность преобразований может быть использована как средство понимания алгоритма и доказательства его правильности. Обратная последовательность преобразований может быть использована в процессе проектирования алгоритма с постепенным раскрытием единственного функционального блока в сложную структуру основных элементов.

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

Методика разработки программ. Распространены две методики (стратегии) разработки программ, относящиеся к структурному программированию: программирование «сверху вниз»; программирование «снизу вверх».

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

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

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

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

• программирование должно осуществляться «сверху вниз»;
• весь проект должен быть разбит на модули/подпрограммы с одним входом и одним выходом;
• любая подпрограмма должна допускать только три основные структуры: последовательное выполнение операторов, ветвление и цикл;
• недопустим оператор безусловной передачи управления goto;
• документация должна создаваться одновременно с программированием, частично в виде комментариев к программе. Применение принципов и методов структурного программирования позволяет повысить надежность программ (благодаря хорошему структурированию при проектировании программа легко поддается тестированию и отладке) и их эффективность (структурирование программы позволяет легко находить и корректировать ошибки, а отдельные подпрограммы можно переделывать/модифицировать независимо от других), уменьшить время и стоимость программной разработки, улучшить читабельность программ.

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

Характерными принципами структурного программирования являются:

· нисходящее программирование – способ разработки программ, при котором программи­рование ведется методом «сверху-вниз», от общего к деталям;

· модульное программирование , при котором относительно независимые подзадачи про­граммируются в виде отдельных программных модулей;

· использование при программировании трех структур управления (следование, выбор, повторение). Структура следование предполагает естественную последовательность выполнения операторов. Структура выбор задается схемой «если – то – иначе» (условный оператор if). Структуре повторения сопоставлен оператор цикла;

· отказ от безусловных передач управления и ограниченное использование глобальных переменных.

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

Следование– это линейная последовательность действий (рис. 2.6):

Рис. 2.6. Следование

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

Ветвление – алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение (рис. 2.7):

Рис. 2.7. Ветвление

Цикл – повторение некоторой группы действий по условию. Различаются два типа цикла. Первый – цикл с предусловием (рис. 2.8):

Рис. 2.8. Цикл с предусловием

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры – цикл с постусловием (рис. 2.9):

Рис. 2.9. Цикл с постусловием

Здесь тело цикла предшествует условию цикла. Тело цикла повторяет свое выполнение, если условие ложно. Повторение кончается, когда условие станет истинным.

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

Иногда в литературе структурное программирование называют программированием без goto. Действительно, при таком подходе нет места безусловному переходу. Неоправданное использование в программах оператора goto лишает ее структурности, а значит, всех связанных с этим положи­тельных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, придерживаясь структурного подхода, его употребления следует избегать.

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

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

Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма.

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

Конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);

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

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

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

«сверху вниз»: сначала строится основной алгоритм, затем вспомогательные алгоритмы;

«снизу вверх»: сначала составляются вспомогательные алгоритмы, затем основной.

Первый подход еще называют методом последовательной детализации, второй – сборочным методом.

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

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

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

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

Лекция 1. Объектно-ориентированное программирование.

Объектно-ориентированное программирование (ООП) явля­ется доминирующим стилем при создании больших программ. Основные этапы эволюции структурного подхода в программировании помогают лучше понять взаимосвязь структурного подхода , модульного программирова­ния и ООП .

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

Другими факторами, влияющими на эволюцию методов проектиро­вания и создания ПП, являются:

Изменение архитектур вычислительных средств (ВС) в интересах повышения
производительности, надежности;

Упрощение взаимодействия пользователей с ВС и интеллектуализация ВС.
Действие двух последних факторов сопряжено с ростом сложности программного обеспечения ВС. Сложность представляет неотъемлемое свойство про­граммирования и программ, которое проявляется во времени и стоимости создания программ, в объеме или длине текста программы, характеристиках ее логической струк­туры, задаваемой операторами передачи управления (ветвления, циклы, вызовы подпрограмм).

Выделяют 5-ть источников сложности программирования:

Решаемая задача;

Язык программирования;

Среда выполнения программы;

Технологический процесс коллективной разработки и создания ПП;

Стремление к универсальности и эффективности алгоритмов и типов данных.

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

В программировании широко используется фундаментальный принцип управле­ния сложными системами, который известен человеку с глубокой древности - devide et impera (разделяй и властвуй, лат.) и применяется при разработке и про­ектировании любых сложных технических систем. Согласно первой части этого прин­ципа, при проектировании сложной программной системы проводится алгоритми­ческая декомпозиция решаемой задачи.

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

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

Теоретическое оформление структурный подход получил в нача­ле 70-х годов в работах теоретиков и практиков программирования(А.П.Ершова, Э. Йодана, Н.Вирта). Следует отметить появле­ние структурного программирования, в котором нашла определенное отражение идея упорядочивания структуры программы. Структурное программирование ориентирует на составление программ, структура которых близка к «дереву» опе­раторов или блоков. Использование структуры типа «дерево» в качестве своеоб­разного эталона объясняется тем, что это простая для анализа и реализации структура.

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

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

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

Развитие языков в направлении повышения эффективности составления приклад­ных программ привело к разделению языков по следующим уровням:

Низкий уровень (машинно-ориентированные языки - языки ассемблера),

Высокий уровень (процедурно-ориентированные языки: FORTRAN, ALGOL,

Уровень решаемой задачи (проблемно-ориентированные языки - SQL).

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

Результатом обобщения понятия «тип данных» являются классы объектов (C++), которые могут содержать в качестве эле­ментов не только данные определенного типа, но и методы их обработки (функ­ции).

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

Человек мыслит образами или объектами, он знает их свойства и манипулирует ими, сообразуясь с определенными событиями. Древним грекам принадлежала мысль о том, что мир можно рассматривать в виде объектов и событий. Люди обычно имеют объектно-ориентированный взгляд на мир. Так, подумав о телефонном аппарате, человек может представить не только его форму и цвет, но и возможность позвонить, характер звучания звонка и ряд других свойств (в зави­симости от его технических знаний, фантазии).

Язык программирования позволяет описать свойства моделируемых объектов и порядок манипуляции с объектами или порядок их взаимодействия, сообразуясь с условиями решаемой задачи. Первые языки программирования ориентировались на математические объекты, на определенную модель вычислителя. Поэтому они содержали такие конструкции как переменная, константа, функция, формальные и факти­ческие параметры. Программисты представляли свои программы в виде взаимодей­ствующих функций и модулей. Характер програм­мирования был процедурно-ориентированным, поскольку первостепенное внимание уделялось последовательностям действий с данными. Соответственно такие языки программирования, как FORTRAN, PL-1, С называют процедурно-ориентированными.

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

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

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

Объектный подход начал развиваться в программировании с 70-х годов (Smalltalk, CLOS, Ada). Эти языки называются объектными . Иерархическая классификация объектов инаследование свойств являются отправными идеями появившегося в 80-х годах объектно-ориентированного подхода. Одной из причин сравнительно медленного становления объектно-ориентированного стиля программирования яв­ляется его существенное отличие от процедурно-ориентирован­ного стиля.

функциональном подходе к программированию.

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

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

Что касается первой реализации, то она появилась в 50-х годах XX столетия в форме языка LISP , о котором речь пойдет далее.

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

Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP . Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в частности, в SML , а также ряд других языков. Из них, пожалуй, самым "молодым" является созданный уже совсем недавно, в 90-х годах, язык Haskell.

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

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

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

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

Естественно, языки функционального программирования не лишены и некоторых недостатков.

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

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

Заметим, что под термином " функция " в математической формализации и программной реализации имеются в виду различные понятия.

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

таких, что если

b 1 = b 2 .

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

Для формализации понятия "

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

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

• указание последовательности выполнения технологических операций;
• перечисление условий, при которых выполняется та или иная операция;
• описания самих операций, где для каждой операции определены исходные данные, результаты, а также инструкции, нормативы, стандарты, критерии и методы оценки и т. п.

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

Объектно-ориентированное программирование (ООП) определяется как технология создания сложного программного обеспечения, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного типа (класса), а классы образуют иерархию с наследованием свойств. Взаимодействие программных объектов в такой системе осуществляется путем передачи сообщений.

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

Бурное развитие технологий программирования, основанных на объектном подходе, позволило решить многие проблемы. Так были созданы среды, поддерживающие визуальное программирование, например, Delphi, C++ Builder, Visual C++ и т. д. При использовании визуальной среды у программиста появляется возможность проектировать некоторую часть, например, интерфейсы будущего продукта, с применением визуальных средств добавления и настройки специальных библиотечных компонентов. Результатом визуального проектирования является заготовка будущей программы, в которую уже внесены соответствующие коды.

Можно дать обобщающее определение: объект ООП - это совокупность переменных состояния и связанных с ними методов (операций). Упомянутые методы определяют, как объект взаимодействует с окружающим миром.

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

Структурное программирование (СП) возникло как вариант решения проблемы уменьшения СЛОЖНОСТИ разработки программного обеспечения.

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

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

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

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

Подход базируется на двух основных принципах:

· Последовательная декомпозиция алгоритма решения задачи сверху вниз.

· Использование структурного кодирования.

Напомним, что данная методология является важнейшим развитием императивной методологии.

Происхождение, история и эволюция. Создателем структурного подхода считается Эдсгер Дейкстра. Ему также принадлежит попытка (к сожалению, совершенно неприменимая для массового программирования) соединить структурное программирование с методами доказательства правильности создаваемых программ. В его разработке участвовали такие известные ученые как Х. Милс, Д.Э. Кнут, С. Хоор.

Методы и концепции, лежащие в основе структурного программирования. Их три

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

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

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

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

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

Теорема о структурировании (Бёма-Джакопини (Boem-Jacopini)): Всякую правильную программу (т.е. программу с одним входом и одним выходом без зацикливаний и недостижимых веток) можно записать с использованием следующих логических структур - последовательность, выбора и повторение цикла

Следствие 1: Всякую программу можно привести к форме без оператора goto.

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

Следствие 3: Сложность структурированных программ ограничена, даже в случае их неограниченного размера.

Структурное программирование- это не самоцель. Его основное назначение- это получение хорошей ("правильной") программы, однако даже в самой хорошей программе операторы перехода goto иногда нужны: например - выход из множества вложенных циклов.

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

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