Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Высокоуровневые методы информатики и программирования (ВМИП) - файл 1.doc


Лекции - Высокоуровневые методы информатики и программирования (ВМИП)
скачать (2205.5 kb.)

Доступные файлы (1):

1.doc2206kb.04.12.2011 09:12скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10   11
Реклама MarketGid:
Загрузка...
^

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


Парадигмы программирования – это лишь различные инструменты, которые можно использовать при программировании. Каждый из этих инструментов по-своему хорош. Но это не значит, что они "эффективно универсальны". То есть, на самом деле, различные методики программирования дают разный выигрыш для решения задач разных классов. Этот выигрыш можно мерить по двум параметрам:

  • эффективность программного обеспечения на современных ЭВМ

  • общие затраты на разработку программного обеспечения

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

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

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

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

A B - последовательно А, за тем В.
A | B - альтернатива. Читается: "A или B".
A* - произвольное количество повторений (в том числе - 0 раз) А. Читается: "последовательность А".
A # B - эквивалентно A ( B A )*. Читается: "последовательность А через В".

Терминальные символы выделяются подчеркиванием.
^

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


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

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

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

Оператор ::= Простой оператор | Структурный оператор
Простой оператор ::= Оператор присваивания | Оператор вызова | Оператор возврата
Структурный оператор ::= Оператор последовательного исполнения | Оператор ветвления | Оператор цикла
Оператор присванивания ::= Переменная := Выражение ;
Оператор вызова ::= Имя подпрограммы ( Список параметров ) ;
Оператор возврата ::= return [ Выражение ] ;
Оператор последовательного исполнения ::= begin Оператор* end
Оператор ветвления ::= if Выражение then Оператор* (elseif Выражение then Оператор*)* [ else Оператор* ] end
Оператор цикла ::= while Выражение do Оператор* end

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

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

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

5. Параллельное и событийно-управляемое программирование


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

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

Процесс ::= Простой процесс | Структурный процесс
Простой процесс ::= Послать значение | Принять значение | Процесс вычислительной модели
Структурный процесс ::= Последовательный процесс | Параллельный процесс
Послать значение ::= Канал связи << Выражение ;
Принять значение ::= Канал связи >> Выражение ;
Процесс вычислительной модели ::= нечто, определяемое конкретным вычислителем
Последовательный процесс ::= seq Процесс* end
Параллельный поцесс ::= par Процесс* end

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

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

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

Параллелизм является не только надстройкой над другими вычислительными моделями; некоторые методологии программирования имеют естественную реализацию на платформах, поддерживающих параллелизм. Об этом будет упомянуто отдельно в каждом таком случае.
1   2   3   4   5   6   7   8   9   10   11



Скачать файл (2205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru