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

В статье "Фантазия или программирование?" ("Мир ПК", # 10/97, с. 116) начат разговор о "скелете" и "мышцах" программных систем, о числе измерений в программировании. Многие просят меня пояснить или уточнить эти понятия. Очевидно, это нужно сделать потому, что "активистов", которым нравится процесс анализа и решения проблем, меньше, чем "реалистов", которые с проблемами сталкиваются, но в силу определенных причин их решением не занимаются. Статья "Фантазия..." была рассчитана на "программистов-активистов". Теперь необходимо позаботиться о других, предложив для них готовое решение.

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

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

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

Алгоритмы + структуры данных = программы.

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

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

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

Старые песни на новый лад

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

Что означает "спеть" RS-триггер по-старому? Нужно построить блок-схему, определяющую алгоритм работы отдельного элемента И-НЕ, и написать программу, реализующую этот алгоритм. (Оба этапа будут подробно рассмотрены ниже.) Последний шаг - погружение двух (по числу элементов в триггере) экземпляров программы в любую параллельную среду, например Windows 95, которую сейчас можно найти чуть ли не на каждом столе.

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

Чем привлекает третье измерение? Прежде всего тем, что программа в нем работает правильно, а еще тем, что оно без ограничений позволяет распространить схему решения задачи об RS-триггере на другие задачи. А чем привлекает данная схема? Непроцедурностью. Это свойство характерно для интеллектуальных систем, способных взять на себя часть решения задачи. В случае с триггером достаточно определить алгоритм работы отдельного элемента и необходимые связи между компонентами системы. Алгоритм работы всей системы описывать не нужно: система построит его сама, руководствуясь полученными указаниями.

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

Когда-то программисты применяли подход, предусматривающий точное и полное знание алгоритма работы всей системы, но сейчас так почти никто не работает - слишком сложно. Действительно, предположим, что ценой титанических усилий вы создали такой алгоритм, предположим, что он даже правилен. Вы его запрограммировали и уже любуетесь результатами полученного решения. Но что вы "запоете", когда вам скажут о необходимости учета задержек в работе элементов!? Повторите весь процесс заново? Учтите, что на этот раз все будет гораздо сложнее, особенно на уровне системы.

Разбиение монолитных систем на части - веление времени. Это, пожалуй, то единственно верное решение, которое позволяет справиться с возрастающей структурной и алгоритмической сложностью программных систем. Подтверждение тому - объектное и параллельное программирование, параллельные системы, решения на базе модели COM. Лично мне такой курс по душе, но смущает, что на уровне отдельных частей таких систем как были блок-схемы, так блок-схемы и остались. Вроде и песни новые, а мотивчик старый! Я убежден, что именно КА и системы с третьим измерением позволят дать новым песням новое звучание. Поделитесь, если кому-то известны другие подходы.

Теперь об обещанном. Программисты ЗАО "Аргуссофт Компани", которым я благодарен за проявленный интерес к моей работе, продемонстрировали мне свое решение задачи моделирования RS-триггера. Для этого ими была использована система G2 (фирма Gensym, США) - инструментальная программная оболочка для экспертных систем. Это современная объектно-ориентированная программная среда со средствами визуального проектирования, но речь не о ней. На поверку оказалось, что триггер работает неправильно. Совместными усилиями мы все-таки заставили его работать правильно и достаточно устойчиво: оказалось, для этого необходимо задать модельное время равным почти секунде. Что мешает триггеру работать правильно всегда, а не только в этом режиме, мы так и не поняли. Вероятно, при всей своей мощи и интеллекте эксперта система G2 всего лишь имитирует - временами даже удачно - третье измерение. И пока я не выясню, почему происходят сбои в работе триггера и как их устранить, мне сложно доверять советам такого "эксперта".

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

Старые песни

Итак, о старом, но по-прежнему главном. Блок-схемы для программистов - святое. Кажется, время перед ними бессильно: они были и остаются основной программной моделью. Именно БС - "скелет" современных программных решений. В некоторых случаях его, безусловно, видоизменяют, добавляя новые или убирая лишние "косточки", но в своей основе модель остается той же.

Рассматривая свойства модели БС, сложно обойтись без соответствующего примера. На рис. 1 представлена блок-схема алгоритма вычисления логической функции И-НЕ. Это обычная блок-схема, которой нельзя удивить современных программистов (да и несовременных тоже). На ней есть дополнительные пометки, необходимые для того, чтобы нагляднее представить "скелетные" отличия между БС и КА.

Исходный текст функции с именем N_AND на языке Си++ представлен листингом 1. Сопоставив программу с блок-схемой, можно легко определить "начинку" для каждого элемента БС. Точный смысл комментариев, связанных с пометками St, S1, : 00 на блок-схеме, будет ясен чуть позже. Но уже сейчас понятно, что эти пометки соответствуют некоторым промежуточным состояниям программы.

bool N_AND (bool bX1, bool bX2)
{
	bool bY;
//		состояние "St"
	bY = false;
//	Y1
//		состояние "S1"
	if (!bX1) bY = true;
//	Y2
	else {
		if (!bX2) bY = true;
//	Y2
		else bY = false;
//	Y1
		}
//		состояние "00"
	return bY;
}

Проведем анализ решения на структурном уровне. На верхнем уровне абстракции, так называемом уровне "черного ящика", логической функции И-НЕ соответствует "ящик", имеющий два входа и один выход. Входам соответствует набор входных переменных, которые имеют имена X1 и Х2, а выходу - выходная переменная c именем Y и/или значение, возвращаемое функцией. Очевидно, что "черные ящики", представляющие различные алгоритмы, будут отличаться друг от друга количеством и функциональным назначением своих входных и выходных каналов.

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

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

У БС на рис.1 может быть два предиката и два действия. Предикаты X1 и X2 возвращают значения, исходя из анализа переменных bX1 и bX2, действие Y1 присваивает выходной переменной значение, равное false, а действие Y2 - true. В тексте программы предикатов и действий нет. Ничто, конечно, не мешает их создать. Практически любой язык программирования имеет все необходимое для того, чтобы такую структурную реорганизацию провести. Но в данном случае это не столь необходимо. В случае же с КА такая "перестройка" будет нужна.

От блок-схем к автоматам

Теперь о новом и таком же главном, как БС. Модель конечного автомата - такая же алгоритмическая модель, как и блок-схема. Формально они эквивалентны, и потому особого смысла в замене БС на КА, кроме создания дополнительных хлопот, связанных с освоением новой модели, казалось бы, нет. Но реально это не так. Автомат обладает качествами, которых нет у БС. И они проявляются уже во втором измерении, не говоря уж об остальных.

1. Автомат, особенно структурный, изначально имеет множество входных и выходных каналов и потому полностью соответствует структурной модели "черного ящика".
2. У автомата есть состояния, которых нет у блок-схем, что часто очень удобно использовать (см. следующий пункт).
3. То, что для блок-схем приходится придумывать (метод программирования с переменной состояния, таблицы решений, в конце концов, сами автоматы и т. д. и т. п.), для автомата часто является естественным и "родным".
4. Параллелизм автоматов несравненно выше, чем у блок-схем. Это еще не третье, но уже и не "чисто" второе измерение, как у БС. Ничто не мешает организовать параллельную работу входных и выходных каналов и выполнять параллельный анализ дуг текущего состояния для перехода в следующее состояние. В этом и еще кое в чем скрыты большие аппаратные резервы этой модели.
5. Автоматы непроцедурны по своей природе, поскольку "самостоятельно" решают, какую дугу перехода выбрать и каким будет следующее состояние автомата. Программист выполняет только интеллектуальную работу по заданию условий таких переходов, множеству следующих состояний и определяет перечень действий, которые нужно выполнить, когда возникла ситуация перехода. Математическая теория автоматов более разнообразна и обширна, чем теория блок-схем. Например, автоматы можно делить, умножать и т. п. А как выполнить такие операции непосредственно над блок-схемами?
6. КА несложно интерпретировать с помощью виртуальной машины, обеспечив таким образом более простой и естественный способ работы, чем при процедурной реализации. Виртуальная машина послужит также "мостом" к последующим измерениям, которые отсутствуют у БС.

Посмотрим, как выглядит автомат, эквивалентный БС на рис. 1. Граф такого автомата изображен на рис. 2. С ним становится понятен смысл пометок на БС - они соответствуют состояниям автомата. А предикаты и действия отождествляются соответственно с его входами и выходами.

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

bool bY, bX1, bX2;
//	предикаты
bool X1() { return bX1; }
bool X2() { return bX2; }
//	действия
void Y1() { bY = false; }
void Y2() { bY = true; }
//	таблица переходов автомата
ARC N_AND[ ] = {
	"St, S1, --, Y1",
	"S1, 00, X1X2, Y1",
	"S1, 00, ^X1, Y2",
	"S1, 00, ^X2, Y2"
	};

Конечный автомат - не только "скелет" программы. Это ее управление, о котором обычно упоминается в теории программ. Там на формальном уровне программа рассматривается как тройка: множество операторов, множество данных и управление. И если "скелет" - образ, то управление - строгое математическое понятие. Перейдя от БС к КА, мы с формальной точки зрения изменили только управление программы.

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

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

Каждому измерению - виртуальную машину

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

Модель БС эффективна благодаря тому, что воспроизводит современную архитектуру процессоров. Заменяя блок-схемы автоматами, мы создаем свою виртуальную машину, но и она достаточно эффективна с точки зрения быстродействия; потери времени на интерпретацию автоматов в большинстве случаев почти незаметны на фоне других вычислительных затрат. Качественная оценка такой эффективности произведена мною в статье "Компиляторы С++: кто сильнее?" ("СофтМаркет", # 13/97).

И хотя модель КА решает в основном проблемы второго измерения, без создания автоматной виртуальной машины невозможно было бы реализовать другие программные измерения. Любая операционная среда - тоже виртуальная машина. И если уж выдавать всем сестрам по серьгам, то каждому измерению следует выделить свою операционную среду. А если серьезно, то автоматная среда - это вынужденная мера. Разумеется, можно заниматься объектным программированием на чистом Си или писать для Windows, не используя готовых библиотек объектов, но в большинстве случаев гораздо эффективнее применять Си++, а также MFC или OWL.

Трепещите, программисты

Как вам уже, наверное, стало ясно, мы поставили перед собой задачу найти замену для блок-схем на все или по крайней мере почти на все "случаи жизни". И это вполне осуществимо, правда, только в режиме интерпретации. Мы только что рассмотрели модель КА, при помощи которой это можно сделать. Уже сейчас о ней можно с уверенностью сказать, что пусть в режиме интерпретации, но "поет" она вполне сносно.

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

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

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

Со времени первых программ, написанных леди Лавлейс, утекло много воды. "Песен" программистами за это время "спето" более чем достаточно. Придуманные за последнее время сонмы Builder'ов, обновленные Visual'ы и совсем свежие Office, COM, OLE и ActiveX, HTML и VRML во всех своих ипостасях - лишь небольшая их часть. Хочется надеяться, что и только что "спетое" найдет своего благодарного слушателя.