Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

3.6. ПРОГРАММИРОВАНИЕ ОТ ПРИОРИТЕТОВ

145

тектурная схема разработки программного проекта. В рамках событийного

подхода готовятся фрагменты системы, которые отвечают за реакцию на ка-

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

ние этих обработчиков ведется в стиле программирования от приоритетов.

Как для событийного программирования, так и для программирования

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

действия тоже.

Рассмотрим написанный в двух вариантах на двух условных языках при-

мер программы с приоритетами.

Программа 3.6.1

3: Цикл пока не будет все сделано

{

5: Подготовка данных;

10: Обработка текущих изменений;

};

4: Демон {Если Поступили данные То

Прием рутинных данных};

8: Демон {Если Поступили экстренные данные То

Запоминание экстренных изменений};

12: Демон {Если Авария То Аварийные действия};

Программа 3.6.2

a: PRIO 3 {Prepare Data;SLEEP};

b: PRIO 10{Process Changes;SLEEP};

c: PRIO 8 DAEMON IF Extra Data

THEN Store Extra Data;

AWAKE b FI;

d: PRIO 12DAEMON IF Alert

THEN Emergency; FI;

e: PRIO 2 DAEMON IF Idle

THEN AWAKE a; FI;

Видно, что в данном примере все приоритеты задавались статически. Имен-

но к этому стремятся почти во всех случаях современной практики вычисле-

ний с приоритетами. Но полной статичности можно добиться лишь в про-

146

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

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

полнение,то естественно постепенно поднимать его приоритет.Но тогда при-

оритет такого «пользовательского» действия может превзойти приоритет си-

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

допустимый максимальный приоритет и мы вновь попадаем в ту же ловушку,

либо задавать разным классам процессов приоритеты просто несравнимые

по порядку, чтобы ни при каком нормальном исполнении приоритет пользо-

вательского процесса не дорос, скажем, до 10

, за которым начинаются при-

оритеты срочных системных демонов.

Заметим, что назначение приоритетов операционной системой, «сверху»,

принципиально ничего в данной картине не меняет. С точки зрения пользо-

вательских программ эти приоритеты все равно статические.

Рассмотрим теоретически, какие классы программ можно описать при

помощи статических и динамических приоритетов. Оказывается, при помо-

щи статических приоритетов, являющихся натуральными числами, невоз-

можно описать даже примитивно-рекурсивные композиции исходных дей-

ствий

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

описания приоритетов, но оказывается, что для них хватает ординалов (см.

курс математической логики). Поскольку ординалы до ε

имеют хорошую

вычислительную модель (см., напр. [63]), можно рассматривать целочислен-

ные приоритеты как конкретную реализацию абстрактного класса таких ор-

диналов.

А в случае реально распределенных или реально параллельных действий

проблема приоритетов еще важнее и еще сложнее. Часто управление по при-

оритетам — единственный шанс справиться со сложностью такой нелиней-

ной во времени системы. Тут уже и линейно упорядоченного множества при-

оритетов не хватает.

В целом программирование от приоритетов является мощным, но спе-

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

или распределенных процессов. Его элементы проникают и в традиционные

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

программах.Здесь, как и в событийном программировании с обособленными

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

зующей конструкции.Противоречивость этого средства со структурным про-

Правда, здесь мы отвлекаемся от реальных ограничений, и считаем 10

столь же легко

достижимым числом, как и 10.

3.7. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

147

граммированием только в том, что не всегда ясно, что делается далее, когда

обработка исключения завершается. В сравнении со структурными перехо-

дами такое расширение представляется более искусственным.

§ 3.7. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

При функциональном программировании основным понятием является

функция. Мы интересуемся определением и переопределением функции как

целого. Соответственно, тогда сами функции становятся значениями. По-

этому здесь необходим серьезный теоретический анализ. Нужно разобрать,

какие действия мы можем производить над функцией как над единым объ-

ектом, какие мы можем получить от этого преимущества и в каких случаях

целесообразно так работать, а в каких нет.

Функциональное программирование полностью

реализовано в ряде до-

статочно широко используемых систем, например, в языках

LISP

. На-

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

Но применяются они, в основном, в академической среде. Для понимания

того, что затрудняет использование функционального программирования в

производственной практике, также необходим теоретический анализ. Функ-

ции оказываются столь абстрактными и высокоуровневыми объектами, что

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

немедленно ведут в тупики.

Функциональное программирование базируется на λ-исчислении, на те-

ории рекурсивных схем и на денотационной семантике, дающей модели этих

понятий.

Элементарное изложение λ-исчисления, представление о котором дол-

жен иметь любой квалифицированный программист, можно найти, напри-

мер, в [63]. Для лучшего представления дадим его сверхкраткий набросок.

В λ-исчислении любой объект является функцией, которая может приме-

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

ражение f(f). По любому выражению t, содержащему переменную x, мож-

но определить функцию λx.t, принимающую в качестве аргумента значение

x и подставляющую его в выражение t. Если в выражении нет других сво-

бодных переменных, то после такого определения получается постоянный

И даже более, чем полностью; см. дальнейший текст этого параграфа.

148

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

объект. Основное правило преобразования очень естественно:

λx.t(a) → t[x | a].

Оно сводится к обычному вызову функции с заменой ее параметра на кон-

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

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

и внутри определений функций.

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

значения. Например, таково

λx.x(x)(λx.x(x)).

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

Если запретить самоприменимость, приписав всем переменным и кон-

стантам типы и разрешив применять функцию лишь к аргументам правиль-

ного типа (это обозначается следующим требованием: функция f должна

иметь тип (τ → ρ), ее аргумент t — тип τ, и тогда выражение f(t) имеет

тип ρ). В этом типизированном λ-исчислении зацикливание уже исключает-

ся, если его нет в исходных функциях.

В денотационной семантике области значений типов данных представля-

ются как сложные топологические и алгебраические структуры, а вычисли-

мые функционалы описываются как непрерывные операторы.

Основной метод определения новых функций, принятый в программиро-

вании — рекурсия.

Пример 3.7.1. Дж. Маккарти в 1960 г. сформулировал определение вычи-

слимости, в котором все функции строятся из исходных при помощи схем

типа

Mult(x, y) ⇐ if y = 0 then 0 else Add(Mult(x, Pd(y)), x) ﬁ

(рекурсивные схемы по Маккарти [57]). Здесь Pd — функция, находящая пре-

дыдущее натуральное число, Add — функция сложения. А что определяется

такой схемой, читатель может разобраться и сам.

Конец примера 3.7.1.

Соответственно, в функциональном програмировании рекурсия использует-

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

функциональности. Функции нужно уметь порождать динамически.

3.7. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

149

Полностью проявить свою силу функциональное программирование мо-

жет, если разрешается строить не только функции, но и функционалы произ-

вольных конечных типов,преобразующие функционалы более низких типов.

Дело в том, что логически

эти функционалы соответствуют абстрактным

математическим понятиям, а, как показано Оревковым (см. [63]), примене-

ние таких понятий может сократить рассуждение в башню экспонент раз.

Соответственно, и длина программы может быть сокращена во столько же

раз, а потери эффективности практически не будет.

Поэтому возникает вопрос о том, какие минимальные операции нужны

для работы с функциями? Конечно же, это композиция функций (эту опера-

цию не позволяет в общем виде естественно запрограммировать ни

C++

, ни

Pascal

, ни

Ada

, ни

Алгол-68

В 60-х гг. была выделена еще одна естественная и в принципе исключи-

тельно просто реализуемая операция над функциями. Это частичная пара-

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

тов процедуры и получаем процедуру,выдающую результат после получения

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

цело является функция (в обозначениях

)

third

(i) = i%3.

Доказано, что композиции и частичной параметризации достаточно для мо-

делирования всего типизированного λ-исчисления. Соответственно, эти опе-

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

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

большие сложности, и для понимания их теории нужно хорошо знать логику,

современную алгебру и топологию. Специалистов, владеющих и этой теори-

ей, и практикой программирования, практически нет. Поэтому, хотя экспери-

ментальных систем для работы с понятиями высших типов довольно много,

все они наследуют первородный грех языка

LISP

: их создатели просто не

могут удержаться и добавляют какую-либо возможность (концептуально не-

совместимую), которая разрушает эффективность системы. Соответственно,

это препятствует применению систем на практике.

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

освоение позволяет намного эффективнее решать аналитические проблемы и сознательно

выбирать соответствующие средства. А это — высшие уровни профессионального мастер-

ства.

150

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

Функциональное программирование дает возможность проиллюстриро-

вать тезис о вредности концептуально несогласованных пополнений систе-

мы понятий на примерах, которые проработаны и на практике, и в теории.

Рассмотрим один такой пример.

Динамическое порождение функций можно понимать следующим обра-

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

(поскольку исторически действия над списками определялись рекурсивно,

именно таковы базовые данные практически всех нынешних функциональ-

ных языков). Тогда можно список, произвольным способом порожденный

в нашей программе, просто прочитать как программный текст и объявить

определением динамически вычисленной процедуры. Именно так подошли

к функциональному программированию в языке

LISP

, созданном Дж. Мак-

карти. Этот язык уже 40 лет живет в академической среде, на нем написано

множество исследовательских и экспериментальных систем, и богатый опыт

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

Порождение функций с помощью динамической генерации их определе-

ний оказалось крайне опасным средством. Даже при его правильном при-

менении оно почти всегда приводит к потрясающей неэффективности про-

грамм. Впрочем, это можно было бы оценить и чисто теоретически. Такой

стиль программирования практически эквивалентен λ-исчислению, в кото-

ром универсальная функция пишется легче всего. А универсальная вычи-

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

даже не может быть продолжена до всюду определенной.

Любое расширение указанного нами минимального множества операций

над функциями с большой вероятностью ведет в ту же пропасть неэффектив-

ности.

Рассмотрим пример. Показано, что функций, получающихся путем вы-

числения с помощью циклов типа пересчета типизированных λ-выражений,

базирующихся на элементарных вычислимых функциях, достаточно для до-

казательства непротиворечивости арифметики. Таким образом, внешне безо-

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

дать потрясающе ресурсоемкую функцию.

Это теоретическое рассмотрение в совокупности с другими, подобными

ему, приводит к выводу:

функциональное программирование и циклы кон-

цептуально противоречат друг другу

Функциональное и сентенциальное программирование поддержано в на-

стоящий момент глубокими теоретическими рассмотрениями, которые вы-

годно отличают его от операционных моделей. Есть и опыт, и практические

3.8. ОБЪЕКТНО-ОРИЕНТИРОВАННЫЙ ПОДХОД

151

результаты, связанные с его применением. Базируясь на серьезной матема-

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

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

циональный и сентенциальный стили программирования часто демонстри-

руют очень высокую выразительность, быть может, именно в связи с тем, что

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

Наиболее богатый опыт и развитые традиции функционального програм-

мирования имеет язык

LISP

.Методы составления

LISP

-программ вполне сло-

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

LISP

’е не удалось погубить даже внедрением совершенно чуждого функци-

ональности присваивания. В то же время, этот стиль оказался гибок по от-

ношению к освоению новых концепций, когда они не противоречат базовым

средствам языка: и абстрактные типы данных, и объектная ориентирован-

ность вполне успешно прививаются на стройное дерево списочной структу-

ры

LISP

’а.

Как показывает опыт

LISP

’а, взаимопроникновение стилей возможно, и

особенно успешно в случае концептуально хорошо проработанной базы. Но

далеко не всегда оно приводит к ожидаемому росту выразительности. Мно-

гочисленные примеры демонстрируют обратное. И всегда неудачи заимство-

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

того, что логически и теоретически предопределено для данного стиля. Вот

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

сущность, а не поверхностные сходства и различия.

Опыт показал, что владение функциональным стилем программирования

является элементом фундаментального образования программиста и мощ-

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

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

же овладевает современными высокоуровневыми методами объектно-ориен-

тированного проектирования и дизайна и гораздо эффективнее их применяет.

Таким образом, мы естественно переходим к следующему стилю.

§ 3.8. ОБЪЕКТНО-ОРИЕНТИРОВАННЫЙ ПОДХОД

В современном программировании объектно-ориентированный подход

(ООП) является одним из популярнейших. Он превратился в стандарт во

многих фирмах и во многих сообществах программистов. Средства для под-

держки ООП вошли практически во все профессиональные системы про-

152

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

граммирования.

Этот стиль вместе с соответствующими организационны-

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

работы программистов.

Конечно же, при этом ООП рекламируется как универсальное средство.

Но читатель уже должен понимать,что любое хорошее средство должно иметь

и ‘хорошие’ недостатки. Бесспорно только бесполезное. Поскольку профес-

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

объектно-ориентированного программирования, здесь данный подход будет

описан эскизно, тем более, что, как станет ясно ниже, он и не предназначен

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

ООП базируется на интенсивном использовании сложных структур дан-

ных: объектов. Объекты соединяют внутри себя данные и методы. Чаще

всего объекты организуются таким образом, что к данным прямого доступа

извне нет, мы можем обращаться к ним лишь через методы. Это позволя-

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

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

Пример 3.8.1. Имея тип объектов

TPoint

, выражающий точки двумерного

пространства, мы можем даже и не знать, в какой системе координат пред-

ставлены эти точки. Важно, что у нас должен быть метод вычисления декар-

товых координат точки и метод задания точки ее декартовыми координатами.

А внутри пусть они будут хоть барицентрические, если так удобно состави-

телю программы.

Конец примера 3.8.1.

Более того, для замены внутреннего представления данных в объектно-

ориентированном программировании имеется механизм наследования. Мож-

но описать новый тип объектов, базирующийся на уже имеющемся, и пе-

реопределяющий его методы. Как следствие, при присваивании переменной-

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

щие их функции.

Присваивание функций вместо присваивания данных выводит лишь на

второй уровень функциональной абстракции, но каждый из этих уровней да-

ет экспоненциальный выигрыш в выразительных средствах. Правда,этот вы-

игрыш в полной мере проявляется лишь для достаточно больших и сложных

Поэтому мы не приводим примеров. В частности, системы

Delphi

Visual C++

просто на-

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

наверняка уже видели на собственном опыте.

3.8. ОБЪЕКТНО-ОРИЕНТИРОВАННЫЙ ПОДХОД

153

систем и при хорошо продуманной системе понятий, их описывающих. Та-

ким образом, объектно-ориентированный подход позволил облегчить и про-

блему работы со сложными программными системами.

Одним из выводов теории систем и системного анализа является то, что,

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

трудности и новые эффекты, которые были практически неразличимы для

малых систем. Лучше всего заметны появляющиеся неприятности, но для

людей, владеющих достаточно высокоуровневой системой понятий, откры-

ваются и новые возможности.Объектно-ориентированный подход смог под-

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

и открыв новые возможности, характерные именно для больших систем и

для их целостного анализа.

Объектный подход является прежде всего структурой достаточно высо-

коуровневых понятий, которые надстраиваются над базисом программных

конструкций какого-то стиля первого уровня. В частности, объектная про-

грамма может с равным успехом базироваться и на структурном программи-

ровании, и на программировании от состояний, и на программировании от

приоритетов.

Отметим, что нынешняя литература по объектно-ориентированному про-

граммированию грешит тем, что то, что представляется как теория данно-

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

этого стоит разобрать, поскольку в курсах, специально посвященных ООП,

производится систематическая подмена понятий и даже истории вопроса.

Необходимо заметить, что в ООП нет никаких ограничений на измене-

ние наследником смысла операций предка. Конечно, благими пожеланиями

кишат все руководства, но, поскольку ограничений нет, на практике един-

Как ни парадоксально, именно эти принципиальные преимущества ООП труднее всего

показать в практике формального обучения в вузе.

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

бы проделать системный анализ и построить обозримую открытую модель. Это еще возмож-

но (например, в качестве таковой можно рассматривать игру в ‘очко’ с учетом различных

стратегий игроков и их психологии.) Но на таких задачах удается показать лишь некоторые

преимущества и некоторые стороны объектной модели, которые почти уравновешиваются

недостатками, связанными с резким увеличением объема сопровождающей моделирующую

программу информации.

Можно привести содержательную аналогию. Если построен мощный танк, то даже для

того, чтобы его разместить, требуется значительное пространство, а уж чтобы ему развер-

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

комнате директора или в аудитории, рассчитанной на 10 человек.

154

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

ственное, что с гарантией сохраняется — имена понятий. Когда говорят о

конкретизации объекта, фактически речь идет о смене ролей.

Система программирования,основанная на объектах и их ролях, была ре-

ализована в языках

SMALLTALK

PLASMA

. В последнем из них объекты так

и назывались актерами. Эта система и была воспринята ООП. Поскольку си-

стема ролей очень хорошо подходит для описания взаимодействия человека

и программной системы и для описания поведения программной системы

в человеческой среде, ООП оказалось успешным методом проектирования

систем по заказу, для нужд непрофессионалов, и позволило повысить произ-

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

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

быстро перестраивать достаточно сложные программные системы при изме-

нении требований заказчика. Уже эти два преимущества показывают прак-

тическую ценность ООП.

А в качестве теории (это показывает еще раз, что часто к теоретику обра-

щаются как к научному аналогу священника, который должен освятить ре-

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

имеет)ООП восприняло то,что развивается под именем абстрактных типов

данных (АТД). АТД сохраняет не только имена методов, но и их смысл. Цель

теории — дать способ автоматизированной конкретизации понятий, когда в

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

сложной, непосредственного практического выхода получить не удалось, и,

как часто бывает, теория вышла из моды, так и не дойдя до точки зрелости.

Конечно же, сама проблема осталась и лишь обострилась. Вернуться и раз-

вивать теорию дальше все равно придется, но произнесенные слова о конкре-

тизации понятий и связанной с ней заменой представлений и методов были

перенесены туда, где нет ни конкретизации, ни сохранения смысла при заме-

не.

Внимание!

В ООП конкретизацией понятий называется переход от класса к

его наследнику, который содержит все функции и значения, опре-

В данном случае роль — это не профессиональный термин из актерской деятельности

или из программирования, а психологическое понятие. Например, придя в аудиторию, Вы

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

выступающий в разных ролях, на одни и те же раздражители реагирует по-разному. Если

же человек играет не ту роль, которую ожидают от него окружающие, то он ведет себя (с

точки зрения окружающих) неадекватно, что зачастую рассматривается как один из видов

асоциального поведения.