ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ КАФЕДРА СИСТЕМ ИНФОРМАТИКИ ПАРАДИГМА ПРОГРАММИРОВАНИЯ КУРС ЛЕКЦИЙ НОВОСИБИРСК 2015 УДК 004.43 (042.4) ББК 32.973-018 Г Рецензент канд. физ.-мат. наук, Ф.А.Мурзин Издание подготовлено в рамках реализации Программы развития государственного образовательного учреждения высшего профессионального образования «Новосибирский государственный университет» на 2009–2018 годы. Городняя, Л. В. Г Парадигма программирования : курс лекций / Л. В. Городняя ; Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 2015. – 206 с. ISBN ___________ Курс лекций посвящен проблеме анализа, сравнения и определения парадигм программирования. Содержание представляет интерес для специалистов по программированию и информационным технологиям. УДК 004.43 (042.4) ББК 32.973-018 © Новосибирский государственный университет, 2015 ISBN________ © Л. В. Городняя, 2015 3 СОДЕРЖАНИЕ Содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Лекция 1. Проявление парадигм программирования . . . . . . . . 12 1.1. Многоликое программирование . . . . . . . . . . . . . . . . . . . . 12 1.2. Технологии программирования . . . . . . . . . . . . . . . . . . . . 15 1.3. Жизненный цикл программ . . . . . . . . . . . . . . . . . . . . . . . 19 1.4. Развитие парадигм программирования . . . . . . . . . . . . . . 23 1.5. Эксплуатационная прагматика . . . . . . . . . . . . . . . . . . . . 25 Лекция 2. Поддержка парадигм программирования . . . . . . . . . 27 2.1. Семантика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2. Абстрактная машина . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3. Структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4. Реализационная прагматика . . . . . . . . . . . . . . . . . . . . . 49 2.5. Определитель парадигм . . . . . . . . . . . . . . . . . . . . . . . . 53 Лекция 3. Языки низкого уровня . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.1. Императивное программирование на ассемблере . . . . 59 3.2. Стековая машина Forth . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.3. Продукционная макротехника . . . . . . . . . . . . . . . . . . . . 71 3.4. Языки управления процессами . . . . . . . . . . . . . . . . . . . 79 Языки высокого уровня Лекция 4. Императивно-процедурное программирование . . . . . . 91 4.1. Особенности представления программ на Си . . . . . . . . . . 91 4.2 Структурное программирование . . . . . . . . . . . . . . . . . . . . . . 93 4.3.Функциональная модель ИП . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4. Спецификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Лекция 5. Функциональное программирование . . . . . . . . . . . . . . . 101 5.1. Основы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.2. Функциональные ЯП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3. Отображения и функционалы . . . . . . . . . . . . . . . . . . . . . . . 114 5.4. Отложенные действия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.5. Свойства атомов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.6. Гибкий интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.7. Функциональная модель взаимодействия монад . . . . . . . 123 5.8. Спецификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4 Лекция 6. Логическое программирование . . . . . . . . . . . . . . . . . . . . 128 6.1. Операционная семантика . . . . . . . . . . . . . . . . . . . .. . . . . . . 129 6.2. Основы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.3. Язык декларативного программирования Prolog . . . . . . . . 132 6.4. Функциональная модель ЛП . . . . . . . . . . . . . . . . . . . . . . . . 135 6.5. Модели недетерминизма . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.6. Спецификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Лекция 7. Объектно-ориентированное программирование . . . . . . 141 7.1. Общее представление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.2. Абстрактная машина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.3. С++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 7.4. Функциональные модели ООП . . . . . . . . . . . . . . . . . . . . . . 153 7.5. Спецификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7.6. Мультипарадигмальные языки программирования . . . . . 158 Лекция 8. Параллельное программирование . . . . . . . . . . . . . . . . . . 164 8.1. Пространство решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.2. Параллельные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . 166 8.3. Практичные системы программирования . . . . . . . . . . . . . 169 8.4. Модели параллелизма в языках программирования . . . . . 175 8.5. Языки сверхвысокого уровня . . . . . . . . . . . . . . . . . . . . . . . 185 8.6. Высокопроизводительное программирование . . . . . . . . . 187 8.7. Трансформационная семантика . . . . . . . . . . . . . . . . . . . . . 191 8.8. Абстрактный комплекс . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 8.9. Память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5 ВВЕДЕНИЕ Курс лекций знакомит с разнообразием проявлений парадигм программирования (ПП) и подходов к их поддержке в языках и системах программирования (ЯСП). В центре внимания находятся исторически значимые и концептуальные языки программирования, в которых видны ключевые идеи и практические следствия их реализации. Стили и языки программирования, характерные для рассматриваемых парадигм, отражают эволюцию технологий программирования (ТП), используемых при решении задач системной и прикладной информатики от средств машинного программирования на стыке с аппаратурой до языков сверхвысокого уровня и систем высокопроизводительного программирования, включая средства поддержки жизненного цикла программ (ЖЦП). Альтернативные подходы к обработке информации, сложившиеся при создании и применении языков и систем программирования, принято называть парадигмами программирования. Изучение и чѐткая классификация уже сложившихся и новых ПП призваны помочь как обоснованному выбору, так и созданию компьютерных языков при формировании программных проектов и совершенствовании информационных технологий (ИТ). Парадигмами программирования в форме языков и систем программирования представлено знание о потенциале ИТ. В момент создания язык программирования (ЯП) отражает некий прогноз относительно области приложения ИТ. Практика разработки и применения систем программирования (СП) конкретизирует и уточняет такое знание в форме отлаженных программ с комплектами данных для них и прецедентами успешного их применения. Успех применения ЯП можно рассматривать как результат удачного выбора ПП, задающей концептуальную схему постановки проблем и методов их решения с удобным инструментом «грамотного» описания фактов, событий, явлений и процессов, выделения частных и общих понятий. Развитие ПП отражает практичность языковых понятий и реализационных структур, используемых при создании сложных программных систем. Интересно отметить, что рейтинг популярности языков программирования отличается от рейтинга ЯП, использованных в успешно завершенных проектах. Именно парадигмам программирования Роберт Флойд посвятил свою Тьюринговскую лекцию, в которой обратил внимание на значимость этого понятия в контексте проблемы обучения программистов. Авторитетный ученый, заложивший основы теорий анализа и верификации программ, автор ряда эффективных методов обработки данных счѐл необходимым 6 подчеркнуть влияние ПП на успех программистских проектов, на особенности изучения разных ПП и на то, как они должны быть поддержаны в языках программирования. Рассматривая пример структурного программирования в качестве доминирующей методологии программирования, Р. Флойд отметил, во-первых, нацеленность этой парадигмы на нисходящее проектирование, пошаговое улучшение и сведение задачи к более простым подзадачам; во-вторых, переход от конкретных объектов и функций машинного уровня к более абстрактным объектам и функциям, позволяющим продумывать модули, выделяемые при нисходящем проектировании. На своем программистском опыте Р. Флойд сделал интересное наблюдение: искусство программирования включает в себя расширение репертуара используемых парадигм. Его внимание привлекла задача подготовки рекурсивных сопрограмм, удобно формулируемых в терминах недетерминизма, неэффективность которого практично преодолевается макротехникой. Р. Флойд высоко оценил созданные в MIT многочисленные примеры потенциала программирования на универсальном языке Lisp, показывающие путь от простейших списков до универсальных структур данных (СД), способствующих манипулированию программами как данными. Р. Флойд выразил уверенность, что можно наладить ясное обучение ряду таких семантических методов для всех уровней программного проекта, чтобы у обученных студентов хватало головы на решение полного спектра проблем от упрощѐнной учебной постановки задачи до непрерывно расширяющегося класса практических задач. Следует отметить, что за тридцать лет, прошедших со времени Тьюринговой лекции Р. Флойда, число различных языков и систем программирования возросло с нескольких сотен до десятков тысяч. При этом число парадигм не столь велико. В разных источниках называют от двадцати до сорока парадигм, нередко включая в их перечень отдельные техники и методы. Изучение и чѐткая систематизация уже сложившихся ПП призваны помочь обоснованному выбору подходов к обеспечению производительности, надежности и эффективности сложных ИС, конструируемых с использованием разносортных ИТ и сервисов, применяемых в разных условиях. Средства низкоуровневого программирования могут быть охарактеризованы возможностью реализации эффективных решений ценой использования общего доступа к слабо защищенным СД. Языкам высокого уровня свойственно использование расширяемой иерархии СД, компоненты 7 которой защищены от бесконтрольного взаимодействия независимо создаваемых фрагментов программы. Механизмы сверхвысокого уровня (языки спецификаций, языки параллельного программирования, системы представления знаний и т. д.) нацелены на полноту пространства реализационных решений, факторизуемого по отдельным направлениям проблем, связанных с разработкой и применением долгоживущих программ. Благодаря языкам высокого уровня (ЯВУ) программирование стало массовой профессией. Программирование на ЯВУ приспособлено к представлению расширяемой иерархии понятий, отражающей природу понимания человеком решаемых задач и организации процессов их решения. Переход к ЯВУ дал возможность систематически укрупнять конструкции при подготовке текстов программ. Для этого понадобились сложные структуры данных, стереотипы техники программирования, локализуемые области видимости имен объектов и процедур их обработки, подчиненные структурно-логической модели управления, допускающей сходимость пошагового процесса отладки программ. Результативны графические интерфейсы и компонентные технологии, поддерживающие перенос отлаженных результатов в разные системы. В центре внимания – интеграция с библиотеками процедур, эффективная компиляция программ, контроль типов данных, соответствие стандартам области применения программ и технологиям быстрой разработки удобно сопровождаемых программ. Ряд проблем эффективности решается включением в ЯВУ низкоуровневых средств. Практически исчезает необходимость в блок- схемах, а методика самодокументирования и реализации справочных подсистем смягчает роль документирования. Программе на ЯВУ обычно соответствует семейство допустимых процессов, определение которого представлено формальной семантикой языка. Система программирования (СП), поддерживающая ЯВУ, как правило, порождает один из процессов этого семейства. Такое сужение диктуется не только реализационной прагматикой ЯВУ, но и необходимостью воспроизведения процессов при отладке программ. Текст программы на ЯВУ обычно обретает бипланарность – императивное представление процесса обработки данных в нем совмещено с декларативным описанием типов обрабатываемых данных, спецификаций, прагм и пр. Возникает нечто вроде пространственной аппроксимации процесса вычислений, используемой при проверке корректности программ, статический или динамический контроль типов данных. Проработка понятий ЯВУ характеризуется пропорциями между чѐткой аппликативностью и недетерминизмом, пространствами константных и 8 переменных значений, элементарных и составных данных, открытыми и замкнутыми процедурами, средствами обработки строк и файлов, возможностями активного и «ленивого» вычисления, использованием последовательных и параллельных схем управления вычислениями. Все ЯВУ используют стек при реализации укрупненных конструкций и защите локализуемых данных. Стилистика ЯВУ тесно связана с конструированием структур данных, кодированием алгоритмов, методами синтаксического анализа и компиляции программ с опорой на критерии теории программирования. Обычно высокий уровень языка обеспечивается программными средствами, но с появлением программаторов и микропрограммирования разница между программой и аппаратурой стала условной. Lisp, Pascal, Prolog, Smalltalk, Algol и другие ЯВУ были реализованы как входные языки на правах машинного кода. Ассемблер Эльбрус – яркий пример отечественной реализации ЯВУ аппаратными средствами. При анализе парадигм ЯВУ необходимо учитывать следующие их особенности: – практикуются неявные формы представления отдельных понятий ради лаконизма записи программ; – выражения чаще всего рассчитаны на схему предвычисления над скалярами конкретной длины или сложными значениями (сначала вычисляются операнды, затем вычисляется результат операций); – различны виды ветвлений и циклов, категории функций и процедур; – типы данных конструируются по фиксированным в ЯП правилам и реализуются по принятым в СП шаблонам; – схемы управления вычислениями нередко фиксированы в языке и конкретно реализованы в системе программирования; – взаимодействие и соответствие средств и методов, относящихся к разным семантическим системам, при их реализации в системе программирования определено по традиции и прецедентам, причем в коде оно скрыто или рассредоточено, а не структурировано; – эффективность программирования базируется на знании методов реализации значений и обработчиков структур данных в памяти; – результат программы, как правило, рассредоточен по разным переменным, но во многих ЯВУ есть выражения и функции, формирующие один результат. 9 Таб л иц а 0 Названия некоторых ЯВУ, относящихся к разным парадигмам программирования ИП ФП ЛП ООП УЯ Fortran Algol Альфа C Modula Эльбрус Occam BLISS ЯРМО YACC Lex Lisp Рефал ML Cmucl Erlang Interlisp MuLisp Sсheme Hope Clean Dylan Miranda Python Haskell Rubi F# Planner Snobol Prolog Conniver QLisp Mercury Oz Simula-67 Smalltalk-80 C++ Eiffel Clos Java C# Scala Pascal Basic Grow Logo Oberon Робик Рапира Oz (ИП – императивное (стандартное/системное) программирование, ФП – функциональное/аппликативное программирование, ЛП – логическое/декларативное программирование, ООП – объектно- ориентированное программирование, УЯ – учебные языки программирования 1 ). В сравнении с языками низкого уровня семантика ЯВУ содержит арифметику, разделенную на ряд вспомогательных систем обработки целых и вещественных чисел в разных диапазонах, обычно зависящих от разрядности адресов и машинных слов. Имеются дополнительные системы работы с указателями, символами и строками и средства конструирования типов данных. Поддерживается набор стандартных операторов управления вычислениями: ветвления, циклы и вызовы процедур/функций. Кроме работы с глобальными объектами, используются разные схемы локализации хранимых в памяти объектов, что обеспечено организацией структур данных по принципу иерархии описаний или динамики исполнения. 1 УЯ не образуют самостоятельной парадигмы. Обладая своей эксплуатационной прагматикой, они используют операционную семантику изучаемых парадигм. 10 Инструментальное ядро ЯВУ можно ограничить одной арифметической системой. Элементарные уровни опорных ЯВУ разных парадигм можно описать как расширения или конкретизации такого ядра. При анализе парадигм ЯВУ следует отметить вехи совершенствования системной программотехники: – первый ЯВУ Fortran ввѐл в практику раздельную компиляцию, снизившую трудозатраты на отладку программ благодаря выделению техники сборки модулей; – универсальный язык Lisp дал жизнь машинно-независимому стилю символьной обработки данных, что привело к парадигме функционального программирования; – популярность языка C связана с решением проблем машинно- зависимого переноса программ, что одновременно поддержало перенос на множество архитектур; – логическое программирование на языке Prolog позволило работать с недоопределѐнными постановками задач, повышая степень их изученности; – появление С++ и ООП расширило сферы приложения информационных систем, при конструировании которых необходимо повторное программирование. Теоретически различие ПП достаточно ясно выражается на уровне операционной семантики, представляющей детали структур памяти и механизмы выполнения укрупнѐнных действий. Для выработки практических рекомендаций требуется более подробная формулировка различий на всех уровнях определения ЯП, включая реализационную прагматику, задающую границы вычислимости и эффективности программируемых решений, набор синтаксически различимых понятий, показывающий удобство отображения терминологии области приложения в программные конструкции, и эксплуатационную прагматику, определяющую трудоѐмкость программирования и живучесть разрабатываемых программ. Представление специфических деталей парадигм при сравнении ЯВУ можно выразить в форме нормализованной предикатной формы интерпретатора, различающего сквозные понятия сравниваемых языков на уровне абстрактного синтаксиса (АС) и абстрактной машины (АМ), дополненной описанием реализационной прагматики и онтологической спецификации опорных ЯП, поддерживающих парадигмы программирования. 11 При сравнительном описании парадигм СП, ФП, ЛП и ООП в качестве опорных языков используются C, Lisp 1.5, Clisp, Prolog, C++, Clos 2 на базе Венской методики определения ЯП и подходов к динамической оптимизации программ. Курс лекций начинается с общего представления о разнообразии задач программирования и решений, принимаемых при программировании. Затем следует краткий экскурс в методы определения языков программирования, включая вопросы построения систем программирования как основных средств поддержки ПП. Рассматриваются вопросы прагматической классификации ПП на основе анализа особенностей их операционной семантики, представленной в форме семантических систем, реализационной прагматики, дающей примеры типовых механизмов, и эксплуатационной прагматики, показывающей практику их применения. Далее описаны конкретные средства и методы поддержки языков низкого уровня, основных парадигм языков высокого уровня, параллельного программирования и базовых парадигм учебных языков и систем программирования, имеющих образовательное значение. В заключении предпринята попытка резюмировать особенности развития парадигм программирования, описать динамику их кристаллизации и наметить технику парадигматической характеристики языков и систем программирования. Приведена сводка терминов, толкование которых может вызывать разночтения. 2 CLOS – Объектно-ориентированная библиотека функций для Common Lisp. 12 ЛЕКЦИЯ 1. ПРОЯВЛЕНИЕ ПАРАДИГМ ПРОГРАММИРОВАНИЯ В середине прошлого (XX) века термин «программирование» не подразумевал связи с компьютером. Например, можно было увидеть название книги «Программирование для ЭВМ». Теперь по умолчанию термин «программирование» означает организацию процессов на компьютерах и компьютерных сетях. Программирование как наука существенно отличается от математики и физики с точки зрения оценки результатов исследования. Уровень результатов, полученных физиками и математиками, обычно оценивают специалисты близкой или более высокой квалификации. В оценке результатов программирования большую роль играет оценка пользователя, не претендующего на программистские познания. Поэтому специалисты в области программирования частично выполняют функцию переводчика своих профессиональных терминов в понятия пользователя. Программирование имеет свой специфичный метод установления достоверности результатов – это компьютерный эксперимент. Если в математике достоверность сводится к доказательным построениям, понятным лишь специалистам, а в физике – к воспроизводимому лабораторному эксперименту, требующему специального оснащения, то компьютерный эксперимент доступен широкой публике. 1.1. Многоликое программирование Другая особенность программирования обусловлена его зависимостью от быстро развивающейся элементной и инструментальной базы. Для быстрого обновления знаний и навыков нужен классический фундамент. Программистские знания – это сочетание классики и моды. Критерии качества программ весьма разнообразны. Их выбор и упорядочение, по существу, зависит от класса задач и условий применения программ: – результативность; – надежность; – устойчивость; – автоматизируемость; – эффективное использование ресурсов (время, память, устройства, информация, люди); – удобство разработки и применения; – наглядность текста программы; – наблюдаемость процесса работы программы; – диагностика происходящего. 13 Порядок критериев нередко претерпевает изменения по мере развития области применения программы, роста квалификации пользователей, модернизации оборудования, информационных технологий и программотехники. Вытекающее из этого непрерывное развитие пространства, в котором решается задача, вводит дополнительные требования к стилю программирования информационных систем: – гибкость; – модифицируемость; – верифицируемость; – безопасность; – мобильность/переносимость; – адаптируемость; – конструктивность; – измеримость характеристик и качества; – улучшаемость. Программирование как наука, искусство и технология исследует и творчески развивает процессы создания и применения программ, определяет средства и методы конструирования программ, разнообразие которых складывается в практике и экспериментах и фиксируется в форме ЯП. Сложности классификации быстро расширяющегося множества ЯП приводят к выделению понятия «парадигмы программирования», число которых меняется не столь стремительно. Это ставит задачу определения принадлежности ЯП конкретной ПП или поддержки ПП определѐнным ЯП. Для решения этой задачи ПП характеризуется взаимодействием основных семантических систем, таких как вычисление, обработка структур данных, хранение данных и управление обработкой данных. ЯП, поддерживающий некоторую ПП, в значительной мере наследует характеристику ПП при его реализации в СП на уровне абстрагирования операционной семантики от возможностей доступной аппаратуры. При таком подходе выделяются три общие категории парадигм: – низкоуровневое программирование; – программирование на языках высокого уровня; – подготовка программ на базе языков сверхвысокого уровня. Низкоуровневое программирование связано со структурами данных, обусловленными архитектурой и оборудованием. При хранении данных и программ используется глобальная память и автоматная модель управления обработкой данных. 14 Программирование на языках высокого уровня приспособлено к заданию структур данных, отражающих природу решаемых задач. Используется расширяемая иерархия областей видимости структур данных и процедур их обработки, подчиненная структурно-логической модели управления, допускающей сходимость процесса отладки программ. Подготовка программ на базе языков сверхвысокого уровня нацелена на представление регулярных, эффективно реализуемых структур данных, при обработке которых возможны преобразования представления данных и программ, использование подобий и доказательных построений, гарантирующих высокую производительность вычислений и надежность процесса разработки программ, включая подготовку программ для многопроцессорных конфигураций. Дальнейшая детализация зависит от специфики реализационных решений, типичных для СП, поддерживающих конкретные ПП. Есть основания полагать, что отмеченная Р. Флойдом потребность в расширении репертуара парадигм при программировании связана с динамикой представления знаний, сводимой к чередованию фаз восходящего и нисходящего проектирования решений развивающихся постановок задач. Динамика представления знаний сводится к переходу от одного представления к другому. Чередование стадий индуктивного и дедуктивного развития знания можно рассматривать как обоснование выбора метода программирования в зависимости от зрелости, степени изученности решаемой задаче. В методике программирования конкретизация соответствует нисходящим методам «сверху вниз». (Вопреки лингвистической ассоциации нет причин считать нисходящие методы обратными восходящим. Обобщение психологически не симметрично конкретизации. Top_Down – Bottom_Up.) По степени изученности существенно различаются следующие категории постановок задач, влияющие на стиль мышления и выбор методов решения задач: – новые; – исследовательские; – практичные; – эффективные. Для новых постановок задач характерно отсутствие доступного прецедента решения задачи, новизна используемых средств или недостаток опыта исполнителей. Исследовательские постановки задач обычно усложнены требованиями уникальности и универсальности. Практичные 15 постановки задач нацелены на актуальность и удобство применения. Эффективные постановки задач включают в себя исследование возможностей используемых средств, связанных с мерой организованности созданной программы и рангом работоспособности реализованных решений. Макетный образец решения новой задачи работоспособен при предъявлении автором небольшого набора подходящих данных. Для экспериментального полигона отладки решений исследовательских задач требуется приспособленность к обработке почти любых данных, которые могут быть заданы в качестве входных. Практичная версия может быть ограничена обработкой данных, реально встречающихся в сфере еѐ приложения. Для эффективной реализации нужны специально подобранные данные, показывающие еѐ превосходство над менее искусно выполненными решениями задачи. По специфике программирования весьма существенно различаются следующие категории задач: – многоуровневое абстрагирование для особо важных и сложных задач со специальными методами решения; – бизнес-приложения, зависящие от динамики производственной деятельности человека; – сбор фактов и накопление знаний для не вполне определенных задач; – исследование и разработка новых алгоритмов и структур данных, включая создание новых языков; – реализация хорошо изученных алгоритмов для корректных задач. Независимо от области приложения, парадигмы программирования могут отличаться уровнем абстрагирования от возможностей аппаратуры, степенью изученности постановок задач, мерой организованности и рангом работоспособности программ решения задач. Дальнейшая классификация ПП проявляется в технологиях программирования, схемах жизненного цикла программ и лексиконе программирования. 1.2. Технологии программирования Понятие «технология» подразумевает существование целевого производственного процесса, в рамках которого за определенное время на ограниченных ресурсах при известной квалификации персонала по конкретным техническим процедурам гарантированно может быть получен запланированный результат. 16 Основные вехи чисто программистской линии технологического повышения производительности труда в программировании связаны с кристаллизацией определѐнных ПП, обусловленных созданием конкретных ЯП, изобретением новых принципов реализации СП, появлением новых ТП: – создание языка Fortran сопровождалось появлением технологии раздельной компиляции; – язык Lisp дал жизнь технологии символьных вычислений и функционального программирования; – разработка языка C как средства реализации операционных систем привела к технологии машинно-зависимого переноса программ; – практика применения учебного языка Pascal позволила сформулировать принципы структурного программирования, выполняющего роль доминирующей методологии учебного программирования; – язык Prolog связан с парадигмой логического программирования и реализацией средств логического вывода на базе частичного определения решений, достаточных для практики; – идея организации процессов в языке Simula 67 и реализация работы с объектами в языке SmallTalk 80 дали импульс ООП с технологией декомпозиции программ по иерархии классов, допускающей расширение, не искажающее ранее отлаженные определения; – разработка средств авторского форматирования текстов для публикаций TeX/LaTeX породила попытку технологии грамотного программирования (успешную, но не принятую программистами) и публикационно-ориентированную ветвь функционального программирования на языке Haskell. За исключением языка Lisp, в большинстве этих подходов программа рассматривается как статический объект, тогда как в реальности она развивается и может частично видоизменяться в процессе разработки и исполнения. Ждут своего часа резервы верификации, обретающие практичность на современной технике. В конце 1990-х годов стали набирать признание две перспективные технологии, представляющие собой разумный компромисс для разработки программ, обладающих новизной или исследовательским компонентом – экстремальное программирование (XP) и функционально-ориентированное проектирование (FDD). Технология экстремального программирования сложилась в сфере производства игровых программ. В целом, экстремальное программирование показывает обнадѐживающие результаты на постановках 17 задач с частыми обновлениями и соответствует восходящей методике программирования. Технология функционально-ориентированного проектирования соответствует нисходящей методике программирования и учитывает ряд человеческих факторов, что позволяет процессу разработки достичь устойчивости. Такая технология пригодна для решения сложных задач с заметным исследовательским компонентом. Следует отметить, что многие авторы современных технологий программирования выражают претензии к авторитетным рекомендациям по стилю и технике программирования, якобы сделавшим практику программирования беспомощной. Здесь желательно помнить о высоком темпе развития информационных технологий, осознание возможностей которых не успевает созревать. Следует особо отметить трудоѐмкость параллельного программирования, необходимость разработки методов верифицирующей компиляции и оптимизации программных компонентов, средств масштабируемой макрогенерации кода и автоматизируемых трансформаций программ с удостоверением сохранения свойств при их комплексации из ранее отлаженных компонентов. Программа, не устаревая физически, подвержена сложным эффектам, связанным с обнаружением и исправлением ошибок и моральным устареванием не только реализованных решений, но и исходной постановки задачи. Любое производство включает процессы поиска и устранения недочѐтов. В программировании это отладка и тестирование. Независимо от ПП и ТП в процессе разработки программ примерно 45% трудозатрат падает на долю автономного и комплексного тестирования и отладки программ. Столь высокая нагрузка на тестирование в практическом программировании требует ясности в понимании его целей, заметно отличающихся от естественно лингвистических представлений. Тестирование – это организация такого применения программы, в котором обнаруживается наличие дефекта: ошибки или несоответствия ожиданиям конкретных групп пользователей. Это означает, что для определения множества недостаточно задать его элементы, надо ещѐ определить и всѐ, что множеству принадлежать не может. Обычно подготовка тестовых данных подчинена ряду принципов и гипотез, нацеленных на экономию труда и надѐжность результатов тестирования: – для выбираемых входных данных сразу подбираются ожидаемые выходные данные; 18 – тест, не обнаруживающий ошибку, не имеет смысла как тест, но может быть полезен как демонстрационный материал; – тестирование – это творческий процесс, т.к. возможности допустить ошибку в программе разнообразнее, чем еѐ правильные построения; – удачный тест выявляет новую, незамеченную ранее ошибку; При автоматизации тестирования решают следующие проблемы: – создание и накопление хорошего набора тестов; – оценка набора на полноту по ряду критериев; – исполнение программ на тестах, оценка результатов и их хранение; – символьное исполнение программ; – исполнение программ в альтернативных условиях, отличных от условий разработки. Тонкости выбора тестового материала детально описаны в книге С. К. Черноножкина. Различается отношение к источникам ошибок и мерам их профилактики в разных ПП. Если императивно-процедурное программирование (ИП) апеллирует к спецификации типов данных (ТД), обеспечивающих возможность статического контроля при компиляции программ, то функциональное программирование (ФП) предпочитает полный динамический контроль любых условий, гарантирующих корректность вычислений. С математической точки зрения процесс тестирования можно представить как обнаружение точек графика реализуемой функции, через которые эта функция не должна бы проходить. Локализация ошибки – это установление отклоняющейся точки. Исправление ошибки – это преобразование определения функции к виду, дающему еѐ уточнѐнный график. Может быть использовано сравнительное исполнение программы и еѐ прототипа. В целом, процесс разработки программ можно представить как последовательность шагов по уточнению постановки задачи, методов еѐ решения, текста программы решения и набора данных, представляющих тесты и «нетесты». Если последовательность достигает состояния, в котором уточняемые сущности соответствуют друг другу, то утверждается, что завершена отладка программы. Подходы к отладке не менее требовательны к творчеству, чем методы тестирования, но объѐм необходимых затрат на отладку может быть сокращѐн выбором стиля конструирования программ из проверенных шаблонов, рамками надѐжных стандартов, использованием удобно 19 реализуемых моделей. Здесь многое даѐт парадигма функционального программирования. Сложность процесса отладки программы можно оценивать по мощности множества данных, на которых необходимо выполнить прогон программы. Так, например, множество данных для отладочного прогона программы, содержащей цикл, должно содержать не менее трѐх наборов: – без захода в тело цикла; – с однократным заходом в тело цикла; – с многократным прохождением тела цикла. Таким образом, существует ряд ПП, появление которых обусловлено развитием ТП, представленных в форме языков и систем программирования, поддерживающих решение задач определѐнной степени изученности, меры организованности, уровня абстрагирования и ранга работоспособности программ при слабом учѐте проблем тестирования и отладки, а также поддержки процесса разработки (полного жизненного цикла) программ. 1.3. Жизненный цикл программ (ЖЦП) Важнейшая задача технологии программирования – обеспечение сходимости процесса отладки программы, т.е. достижение взаимного соответствия постановки задачи, методов еѐ решения, текста программы решения и набора данных, представляющих тесты и «нетесты». Итоговая постановка задачи, решение которой реализовано в программе, может оказаться как обобщением, так и сужением исходной задачи, что можно назвать более общим термином – «уточнение». Обнаружение закономерностей в процессе разработки программ привело к понятию «жизненный цикл программы». Изменение репертуара ПП в процессе создания программ связано со структурой расширяемого пространства, в котором принимаются решения при практическом программировании. При решении самой простой задачи можно выделить такие этапы, как подготовка к решению, собственно реализация решений и оценка полученных результатов. В прикладном программировании, использующем результаты докомпьютерного программирования, изначально выделяли этапы разработки и эксплуатации программы. Подразумевалось, что этапы строго упорядочены по времени и приводят к получению окончательного результата в виде программы решения поставленной задачи. Класс заранее 20 достаточно изученных для программирования задач быстро исчерпался, и потребовался неоднократный пересмотр принципов организации труда в программировании. Реальность заставила мириться с итеративностью фаз, любая из которых могла потребовать повторного прохождения, что получило название «принцип водопада». Кроме того, со временем обратили внимание на этап подготовки постановки задачи, опережающий этап разработки программ для решения новых задач. Много позднее возник этап «идентификации потребностей» – принятия решения о том, нужно ли вообще разрабатывать программу. В производственном программировании сложилось понятие ЖЦП, структура которого требует не только четкого ответа на вопросы «Что? Как? Кто?», но и уяснения приоритетов между ними. |