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

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

Часть III

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

555

556

Профессионализм программиста во многом определяется тем,какими ме-

тодами составления программ он владеет.Понятие «владеть методом»включа-

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

ции. Именно это отличает владение от пассивного знания, и является решаю-

щей характеристикой квалификации профессионала. Такой уровень овладе-

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

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

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

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

он может превратить новичка в профессионала).

• Широкий взгляд на всю сферу программирования, когда излюбленные

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

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

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

лучше Вас или просто их больше любит.

• Умение видеть взаимосвязи создаваемых Вами конструкций с фунда-

ментальными теоретическими и методологическими идеями. Даже на

весьма среднем уровне это превращает совокупность знаний в систе-

му и дает Вам реальную возможность подняться на уровень Метода и

Стратегии с уровня Комбинирования и Тактики. А уж если Вы овладе-

ли этим на достаточно высоком уровне... (но это требует широкого и

глубокого образования и высокого исходного уровня интеллекта).

• Как следствие из всего предыдущего, умение видеть суть задач, пере-

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

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

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

прямой и очевидный, но явно в некоторых отношениях не более чем

удовлетворительный, путь.

• Владение тонкостями алгоритмов и методов из Вашей профессиональ-

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

это позволит Вам хорошо реализовать Ваши хорошие идеи).

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

раз в пять-семь лет.

557

• И, наконец, опыт неудач! Рим был более велик,чем куча других антич-

ных государств, не потому, что он умел побеждать (это умели и другие),

но потому, что он умел переносить тяжелейшие поражения и неудачи,

и часто превращать победу противника в Пиррову или Ганнибаловы.

Пока Вы не потерпели серьезную неудачу и не встали на ноги после

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

класса.

В данном изложении мы, конечно, не ставим цели осветить все основ-

ные методы программирования — любые попытки такого рода пока что в

принципе ведут к энциклопедии и коллекции, а не к структуре знаний. На-

ша задача в том, чтобы помочь ориентироваться в применении методов (в

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

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

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

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

трудностями

Понятие метода программирования в известной мере соотносится с по-

нятием стиля: для каждого стиля характерны свои методы. Но соотношение

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

методах. Стиль программирования — это, прежде всего, образ мышления: «я

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

решения». Здесь нет явной привязки к какой-либо задаче. Метод же опреде-

ляет направление движения от задачи к решению. Он налагается на стиль,

т. е. формулируется в рамках системы первичных понятий стиля. Иногда та-

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

о естественности метода для данного стиля. Иногда метод не вписывается в

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

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

ствии метода стилю. Среди рассмотренных в главе 3 стилей есть такие, кото-

рые поощряют и даже пытаются предписывать использование определенных

методов или классов методов. Так, программирование от событий, постули-

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

За одного битого двух небитых дают

(Русская поговорка).

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

ского и глубокого курса. В системе отечественного университетского образования обычно

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

558

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

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

матов — см. § 10.1). Но разработчик остается свободным: стили, которым он

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

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

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

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

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

Наиболее естественная языковая поддержка метода достигается в язы-

ке соответствующего стиля. Но это не значит, что использование метода в

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

моделировать стиль: если непосредственное применение метода недостижи-

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

языке. Показать такие приемы программирования — еще одна задача, решае-

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

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

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

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

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

ные. Наша цель в связи с этим — выявить действительный и мнимый анта-

гонизм стилей, и тем самым дать практикующему программисту методи-

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

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

Мы стремимся показать не просто сегодняшнее (не дошедшее до уровня

зрелости практически ни в одной из областей программирования и инфор-

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

бы увидеть побудительные причины развития (либо не развития)языковых

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

ствительно появляются, в других — они пока что остаются на уровне кон-

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

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

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

мисту очень важно уметь различать такие случаи, а также понимать, почему

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

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

Мы почти совсем не рассматриваем стиль объектно-ориентированного

программирования. Этот стиль и связанные с ним методы программирова-

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

559

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

ной языковой инструмент конструирования значительной части современно-

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

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

информационной поддержке бизнеса.

Глава 10

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

состояний

Есть много программистских задач, которые удобно решать с помощью

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

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

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

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

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

Мура.

Теоретически эквивалентные альтернативные варианты этих методов —

когда действия ассоциируются с переходами (по аналогии с автоматами Ми-

ли). Какой из вариантов выбирать, зависит от задачи. Из общих соображений

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

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

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

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

рованного описания действий.

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

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

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

программирования и показываем различные реализации программирования

от состояний.

Очень часто диаграммы переходов порождают структуру конечного авто-

мата (см. определение A.4.1). В этих случаях программирование от состоя-

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

560

10.1. ОСНОВНЫЕ СТРУКТУРЫ

561

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

числительной модели. Словом, если сохраняется инвариант “Действия гло-

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

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

Есть много вариаций методов программирования от состояний. Более то-

го, ‘уместно’ не всегда означает ‘лучше всего’. Поэтому программирование

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

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

задач. Небольшое изменение в ресурсных ограничениях — и, хотя старые

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

§ 10.1. ОСНОВНЫЕ СТРУКТУРЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯ-

НИЙ

Информационное пространство всех блоков и процедур при программи-

ровании от состояний в первом приближении одно и то же: состояния систе-

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

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

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

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

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

общаться прямо, в обход иерархически вышестоящей системы (см.рис.10.1).

Таким образом, структура информационного пространства при программи-

ровании от состояний в общих чертах соответствует той, которая навязыва-

ется современными системами с развитой модульностью.

§ 10.2. ЗАДАЧА ПОДСЧЕТА ДЛИН СЛОВ ТЕКСТА И ЗАДАНИЕ КОНЕЧ-

НОГО АВТОМАТА

10.2.1. Постановка задачи и первичный анализ

Пусть требуется решить следующую задачу. Словом называется любая

непустая последовательность букв латинского алфавита (для простоты —

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

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

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

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

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

правило, записан именно в стиле программирования от состояний.

562

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

Система

S1 S2

SS1

SS2

SS3

Пояснения к картинке.

Светло-серые области — традиционный общий контекст системы и подсистемы.

Темно-серые иллюстрируют, что доступность может быть односторонней, и не

только по иерерхии. Одна из систем может влиять на часть информационного

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

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

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

обход иерархии.

Рис. 10.1. Информационное пространство систем

10.2. ПОДСЧЕТ ДЛИН СЛОВ

563

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

волов все слова в следующем виде:

<слово> - <длина слова><конец строки печати>

Эту довольно простую задачу можно решать по-разному. Ближайшая цель —

построить решение, исходя из представления вычислительного процесса на-

бором состояний с переходами.

Для решения задачи входную последовательность символов естественно

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

ка. При чтении букв, небукв и конца строки действия, которые необходимо

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

для последующих букв слова.

Здесь уже сделаны неявные предположения об алгоритме:

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

поток;

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

ющей генерацию первого элемента потока-слова.

Можно считать, что эти предположения выяснены в результате анализа за-

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

этих предположений следует, что в данном случае задача чисто автоматная,

и поэтому построение диаграммы переходов и конечного автомата — одно и

то же.

10.2.2. Построение графа состояний

Решение,которое исходит из применения метода конечного автомата,тре-

бует, чтобы был определен набор состояний. Различные состояния выделя-

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

Вот полный перечень вариантов таких действий:

1. Символ буква: инициализировать обработку слова

(счетчику длины слова присвоить единицу).

2. Символ буква: продолжить обработку слова

(счетчик длины слова увеличить на единицу).

3. Символ не буква: закончить обработку слова

(напечатать длину прочитанного слова).

4. Символ не буква: пропустить символ.

5. Символ конец строки: закончить обработку слова и

564

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

завершить процесс.

6. Символ конец строки: завершить процесс.

Есть еще одно действие, не отраженное в этом списке, но подразумевае-

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

ход срабатывает (соответстующее сдвигу входной ленты конечного автома-

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

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

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

возможны и другие ситуации:

• используется ‘отрицательное’ условие перехода, которое отсылает к

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

контекста передаваемого символа с последующими переходами (с чте-

нием символов) к другим состояниям;

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

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

чтением из потока.

Внимание!

Наличие нестандартных (не требующих чтения) переходов, вообще говоря,

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

являются потенциальными источниками бесконечного зацикливания без про-

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

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

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

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

принципиальному

упрощению схем.

Теоретически первая ситуация означает переход по пустому (несуществу-

ющему) символу. Оно исключается довольно просто: строятся сквозные пе-

реходы, минующее промежуточное состояние.Это,возможно,потребует кор-

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

стать менее наглядным.

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

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

рабатываемых данных или на самом деле модель вычислений не автомати-

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

стандартные переходы использованы для вполне стандартизованных целей,