РЕКУРСИВНЫЕ ВЫЧИСЛЕНИЯ В РАЗЛИЧНЫХ ПАРАДИГМАХ ПРОГРАММИРОВАНИЯ.

Г.В. Ваныкина, А.В. Якушин

Тульский Государственный педагогический университет им. Л. Н. Толстого

[email protected]

1. Парадигмы современного программирования.

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

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

В сходном смысле как модель или пример, и в целом как организующий подход это слово использовано в лекции «Парадигмы программирования» Роберта Флойда, лауреата премии Тьюринга 1979 года.

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

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

В зависимости от способа декомпозиции можно выделить следующие основные парадигмы программирования, представленные в таблице 1.

Таблица 1. Основные парадигмы программирования

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

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

Проблема становления алгоритмической культуры школьников как основополагающего компонента информационной культуры решается с точки зрения различных парадигм программирования в зависимости от ряда факторов: учебной программы для преподавания курса информатики, технического и программного обеспечения, а также личностных и профессиональных качеств преподавателя. Раздел «Программирование» в рамках общеобразовательного уровня подготовки школьников предполагает изучение основ императивной (Basic , Pascal , C , школьный алгоритмический язык) либо объектно-ориентированной (Delphi , C ++, Java ) парадигм. Профильная подготовка старшеклассников по естественно научному направлению реализуется, как правило, также в рамках вышеперечисленных парадигм. Следует, однако, отметить, что обучение программированию на конкретном языке не является основной задачей в реализации алгоритмической подготовки школьников. Гораздо более приоритетным направлением выступает обучение алгоритмическому подходу в решении задач, умению оценивать эффективность разработанного алгоритма с точки зрения решаемой задачи, выбору технологии для его реализации – то есть, речь идет о знакомстве с методами разработки алгоритмических моделей, реализация которых возможна в рамках любой парадигмы.

Развитие различных парадигм программирования проходило параллельно друг другу. Долгое время императивный подход был главенствующим, в 70-е, 80-е годы акцент сместился в сторону исследования неклассических парадигм, 90-е годы ознаменованы бурным развитием объектно-ориентированной парадигмы и внедрения ее элементов в другие. Развитие языков программирования с точки зрения различных парадигм представлено на рис.1

Рис1. Развитие языков и парадигм программирования

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

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

2. Императивная парадигма.

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

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

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

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

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

4. Объектно-ориентированная парадигма.

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

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

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

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

5. Программирование в ограничениях.

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

Программирование в ограничениях тесно связано с традиционным логическим программированием. Большинство систем программирования в ограничениях представляют собой интерпретатор языка Prolog со встроенным механизмом для решения определенного класса задач удовлетворения ограничениям. Программирование в таких системах называют логическим программированием в ограничениях (Constraint Logic Programming или CLP), а большинство языков или библиотек называются CLP(X), где X указывает на класс решаемых задач.

Например, CLP(B) означает возможность решать уравнения с булевыми переменными. CLP(Q) – уравнения в рациональных числах, а CLP(R) – в вещественных. Наиболее популярны решатели задач на конечных множествах целых чисел CLP(FD).

Постановка задачи – это конечный набор переменных X = { x 1 , ..., x n }, соответствующих им конечных (перечислимых) множеств значений D X = { dx 1 , ..., dx n }, и набор ограничений C = { c 1 ,..., c m }. Система ограничений может включать в себя уравнения, неравенства, логические функции, а также любые допустимые формальные конструкции, связывающие переменные из набора X . Решение задачи состоит в построении набора переменных, удовлетворяющего всем ограничениям c i ,где i = 1,.., m .

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

6. Сценарная парадигма.

Сценарные языки . Сценарные языки, или языки скриптов (scripting languages), за последние годы сделали огромный шаг вперед. Еще лет десять назад им отводилась роль вспомогательных средств, сейчас же скепсис по отношению к ним сменился интересом и признанием.

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

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

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

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

Сценарные языки для web -разработки в основном созданы в 90-е годы XX века и включают в себя элементы различных парадигм программирования от императивной до объектно-ориентированной. Среди наиболее мощных и популярных скриптовых систем можно отметить следующие: Perl , Pyton , PHP , ASP . Синтаксис и семантика различных сценарных языков весьма похожи. Это обусловлено значительным влиянием языков С и С++ на сообщество программистов. Поддержка рекурсии в сценарных языках реализована аналогично императивной и объектно-ориентированной парадигмам.

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

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

Определение парадигмы звучит обычно таким образом:

парадигмы это совокупность принципов идей и понятий которые определяют стиль написания компьютерной программы.

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

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

Виды парадигм программирования

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

Перечислим самые популярные из них:

• Императивное программирование
• Структурное программирование
• Декларативное программирование
• Объектно-ориентированное программирование

На самом деле, есть ещё множество других парадигм, которые мы не перечислили в списке, мы охватываем лишь самые известные из них.

Кратко рассмотрим каждую из них

Императивное программирование

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

от английского imperative - приказ

отличительные черты императивного программирования:

в исходном коде записываются «приказы» команды, а не классы, как в отличии например от объектно-ориентированного программирования.

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

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

Языки представители парадигмы: машинные (бинарные) коды, Ассамблер, fortran, algol, cobol

Структурное программирование

предложил этот метод нидерландский ученый

Эдсгер Дейкстра 1930 — 2002г

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

• последовательность
• ветвление

Структурное программирование имеет также 7 принципов, описанный Дейкстрой:

1. полный отказ использования оператора goto; *
2. любая программа строиться на трех управляющих структурах последовальность, цикл и ветвление;
3. базовые управляющие структуры могут быть вложены в друг друга, как угодно;
4. Повторяющие компоненты, оформлять как подпрограммы;
5. каждая логическая структура следует оформлять как блок;
6. все структуры должны имеет один вход и один выход, и не более;
7. разработка программы должна идти пошагово «лестницей» (методом сверху вниз)

* —
goto — оператор безусловного перехода, который широко использовался в 1970-х

Декларативное программирование

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

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

Объектно-ориентированное программирование (ООП)

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

Основные понятия ООП

Абстракция данных — выделение значимой информации и отделение её от незначимой.

Инкапсуляция — это такое свойство которое позволяет объединить данные, методы в классе

Наследование — свойство которое позволяет создать новый класс на основе старого (унаследовать все его свойства)

Полиморфизм — а это свойство позволяет использовать объекты с одинаковым интерфейсом

Парадигма программирования - это совокупность идей и понятий, определяющая стиль написания программ.

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

Первыми императивными языками были машинные коды - родной язык программирования для компьютера. В этих языках инструкции были крайне просты, что снижало нагрузку на компьютеры, однако затрудняло написание крупных программ. В 1954 появился первый «человеческий» язык программирования - FORTRAN, затем ALGOL, COBOL, BASIC, Pascal, C.

Одна из характерных черт императивного программирования - наличие переменных с операцией "разрушающего присвоения". То есть, была переменная А, было у нее значение Х. Алгоритм предписывает на очередном шаге присвоить переменной А значение Y. То значение, которое было у А, будет "навсегда забыто".

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

Выбор рамок императивной парадигмы для обучения основам программирования, по-видимому, ни у кого не вызывает сомнения. Этому есть несколько причин:

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

· программирование в рамках императивной парадигмы эффективно для широкого класса задач, многие из которых попадают в зону ближайшего развития учащихся в старших классах базовой школы;

· императивная парадигма наиболее близка природе компьютера, основным принципам его функционирования, так как, не смотря на всю сложность современного компьютера, на уровне аппаратной части его можно по-прежнему рассматривать как некоторый автомат (процессор+память+…) с конечным множеством состояний (содержимого памяти);

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

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

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

Недостаток: в чистом виде позволяет решать только очень простые задачи.

Событийно-управляемое программирование - программирование, при котором задаются реакции программы на различные события (действия пользователя). СУП можно рассматривать как «потомок» императивной парадигмы. СУП имеет 2 подкласса:

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

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

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

Важно выделить следующие основные свойства объектов:

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

2.) Так как объекты взаимодействуют исключительно за счет обмена сообщениями, объекты-собеседники могут ничего не знать о реализации обработчиков сообщений у своего визави. Взаимодействие происходит исключительно в терминах сообщений/событий, которые достаточно легко привязать к предметной области. Это свойство (описание взаимодействия исключительно в терминах предметной области) называют абстракцией.

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

Многие современные языки поддерживают ООП, хотя и в разной степени: - чисто объектно-ориентированные языки, например, Smalltalk и Ruby, разработаны для того, чтобы поддерживать и даже навязывать объектно-ориентированный стиль разработки, и не поддерживают другие стили программирования; - преимущественно объектно-ориентированные языки, например, Java, C++ и Python, разработаны в основном для поддержки ООП, но позволяют использовать элементы процедурного программирования; - исторически процедурные языки, например, Perl и Fortran 2002, были доработаны и в них была добавлена поддержка некоторых элементов ООП.

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

Декларативное программирование является противоположностью императивного программирования; первое описывает, что необходимо сделать, а второе - как именно это сделать.

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

1.Функциональное программирование представляет собой одну из альтернатив императивному подходу. Оно основано на лямбда-исчислении Черча. В императивном программировании алгоритмы - это описания последовательно исполняемых операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени.

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

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

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

Логическое программирование

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

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

Логическое программирование допускает естественную параллельную реализацию.

Лекция № Парадигмы программирования. Императивное программирование.

Понятие парадигмы программирования.

Класификация парадигм программирования.

Императивное программирование.

1. Понятие парадигмы программирования.

Парадигма программирования - это совокупность подходов, методов, стратегий, идей и понятий, определяющая стиль написания программ.

Парадигма программирования в современной индустрии программирования очень часто определяется набором инструментов программиста (язык программирования и операционная система).

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

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

История термина

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

Термин «парадигма программирования» впервые применил Роберт Флойд в своей лекции лауреата премии Тьюринга.

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

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

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

2.Классификация парадигм программирования.

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

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

Прикладное программирование подчинено проблемной направленности, отражающей компьютеризацию информационных и вычислительных процессов численной обработки, исследованных задолго до появления ЭВМ. Именно здесь быстро проявился явный практический результат. Естественно, в таких областях программирование мало отличается от кодирования, для него, как правило, достаточно операторного стиля представления действий. В практике прикладного программирования принято доверять проверенным шаблонам и библиотекам процедур, избегать рискованных экспериментов. Ценится точность и устойчивость научных расчетов. Язык Фортран - ветеран прикладного программирования. Лишь в последнее десятилетие он стал несколько уступать в этой области Паскалю-Си, а на суперкомпьютерах - языкам параллельного программирования, таким как Sisal. [, , , ]

Теоретическое программирование придерживается публикационной направленности, нацеленной на сопоставимость результатов научных экспериментов в области программирования и информатики. Программирование пытается выразить свои формальные модели, показать их значимость и фундаментальность. Эти модели унаследовали основные черты родственных математических понятий и утвердились как алгоритмический подход в информатике. Стремление к доказательности построений и оценка их эффективности, правдоподобия, правильности, корректности и других формализуемых отношений на схемах и текстах программ послужили основой структурного программирования [, ] и других методик достижения надежности процесса разработки программ, например, грамотное программирование . Стандартные подмножества Алгола и Паскаля, послужившие рабочим материалом для теории программирования, сменились более удобными для экспериментирования аппликативными языками, такими как ML, Miranda, Scheme и другие диалекты Лиспа. Теперь к ним присоединяются подмножества C и Java.

Функциональное программирование сформировалось как дань математической направленности при исследовании и развитии искусственного интеллекта и освоении новых горизонтов в информатике. Абстрактный подход к представлению информации, лаконичный, универсальный стиль построения функций, ясность обстановки исполнения для разных категорий функций, свобода рекурсивных построений, доверие интуиции математика и исследователя, уклонение от бремени преждевременного решения непринципиальных проблем распределения памяти, отказ от необоснованных ограничений на область действия определений - все это увязано Джоном Мак-Карти в идее языка Лисп . Продуманность и методическая обоснованность первых реализаций Лиспа позволила быстро накопить опыт решения новых задач, подготовить их для прикладного и теоретического программирования. В настоящее время существуют сотни функциональных языков программирования, ориентированных на разные классы задач и виды технических средств. [,,,,,,]

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

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

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

Высокопроизводительное программирование нацелено на достижение предельно возможных характеристик при решении особо важных задач. Естественный резерв производительности компьютеров - параллельные процессы. Их организация требует детального учета временных отношений и неимперативного стиля управления действиями. Суперкомпьютеры, поддерживающие высокопроизводительные вычисления, потребовали особой техники системного программирования. Графово-сетевой подход к представлению систем и процессов для параллельных архитектур получил выражение в специализированных языках параллельного программирования и суперкомпиляторах, приспособленных для отображения абстрактной иерархии процессов уровня задач на конкретную пространственную структуру процессоров реального оборудования [,,].

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

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

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

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

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

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

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

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

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

Многие важные для практики программирования понятия, такие как события, исключения и ошибки, потенциал, иерархия и ортогональность построений, экстраполяция и точки роста программ, измерение качества и т.д. не достигли достаточного уровня абстрагирования и формализации. Это позволяет прогнозировать развитие парадигм программирования и выбирать учебный материал на перспективу компонентного программирования (COM/DCOM, Corba, UML и др.). Если традиционные средства и методы выделения многократно используемых компонентов подчинялись критерию модульности, понимаемой как оптимальный выбор минимального сопряжения при максимальной функциональности, то современная элементная база допускает оперирование многоконтактными узлами, выполняющими простые операции. [,,,,,]

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

В середине прошлого (20-го) века термин "программирование" не подразумевал связи с компьютером. Можно было увидеть название книги "Программирование для ЭВМ". Теперь по умолчанию этот термин означает организацию процессов на компьютерах и компьютерных сетях.

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

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

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

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

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

результативность

надежность

устойчивость

автоматизируемость

эффективное использование ресурсов (время, память, устройства, информация, люди)

удобство разработки и применения

наглядность текста программы

наблюдаемость процесса работы программы

диагностика происходящего

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

гибкость

модифицируемость

улучшаемость

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

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

низкоуровневое программирование;

программирование на языках высокого уровня;

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

Низкоуровневое программирование связано со структурами данных, обусловленными архитектурой и оборудованием. При хранении данных и программ используется глобальная память и автоматная модель управления обработкой данных. [,,,,,,,,]

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