СИНТЕЗ ПРОГРАММНЫХ СИСТЕМ НА ОСНОВЕ ИЕРАРХИИ БЛОК-СХЕМ
(ИрГУПС, Иркутск)
Рассматривается технология низкоуровневого визуального программирования на основе редактирования блок-схем иерархически связанных модулей с автоматическим исполнением сконструированной логики программы встроенным интерпретатором, а также формированием внешнего исполняемого модуля с использованием консольных компиляторов и линковщиков. Разработанная демо-версия редактора показывает эффективность данного подхода, когда обычный текст программы является лишь промежуточным представлением, а основная логика кодируется на специальном языке описания блок-схем.
1. Введение. Для того, чтобы создать программу, необходимо, как правило, поэтапно выполнить следующие шаги: разработать алгоритм, написать исходный код, запустить компиляцию и компоновку.
При разработке алгоритма составляется определенная последовательность некоторой совокупности операций. Алгоритм может быть записан словами с помощью псевдокода и изображён схематически блок-схемами. Псевдокод [1] – искусственный и неформальный язык, который помогает программисту разрабатывать алгоритм. Псевдокод подобен разговорному языку. Его назначение – помочь разработчику обдумать программу прежде, чем попытаться написать её на выбранном языке программирования. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Редактирование исходного кода представляет собой изменение файла с помощью редактора программ. Разработчик набирает с помощью этого редактора код программы на языке программирования. Для многих языков существуют специальные среды разработки (Delphi, Visual Studio, Dev-C++ и др.), включающие собственные редакторы, средства обнаружения ошибок в тексте программ.
Если обращаться с текстом программы как с обычной линейной последовательностью символов, то по мере роста размеров текстов задача выявления и описания нужных изменений может стать просто непосильной для человека. Для поддержания в рабочем состоянии программ используют два подхода – декомпозицию и абстракцию [2]. Корректность конструирования программ решают отдельные технологии, например структурное программирование.
Исследования 60-х годов показали, что многократные нарушения последовательного выполнения операторов программ с использованием оператора goto вели к большим проблемам при групповой разработке программного обеспечения [3]. Развитие структурного программирования способствовало появлению дисциплинированного подхода к написанию программ, и, как следствие, привело к лёгкости их создания, редактирования и понимания. Идеей структурного программирования стало требование “не применять goto”.
Первые программы, как и первые приёмы их разработки, были созданы для ЭВМ последовательной архитектуры. Совокупность технологий программирования, структур данных, которые отвечали последовательной архитектуре ЭВМ, назвали моделью последовательного программирования. Появление векторной архитектуры привело к проблемам организации процесса распараллеливания обрабатываемых данных. Идеи, положенные в основу асинхронной модели, не могли быть в полной мере реализованы правилами структурного программирования. Поэтому впоследствии для векторной архитектуры были сформулированы свои парадигмы параллельного программирования и введены языки для параллельных вычислений (High Performance FORTRAN, C*, и др.).
Текстовое представление определяет синтаксис описания программы. Поэтому для различных языков, особенно разных парадигм, создаются специфические синтаксические и семантические конструкции, затрудняющие объединение и анализ таких программ. Переход к моделям программ позволяет исследовать одну и ту же логику через различные внешние формы представления и производить эффективное преобразование между ними [4]. В частности, модель структурного программирования с использованием оператора goto может оказаться пригодной для описания последовательных и параллельных программ.
2. Средства проектирования программ. Блок-схема - графическое представление программы или алгоритма с использованием стандартных графических элементов. Несмотря на то, что блок-схемы программ использовались вместе с первыми языками программирования, они до сих пор остаются лишь вспомогательным средством поддержки проектирования алгоритмов.
Современным инструментарием для разработки информационных систем являются CASE-средства[5]. Эти средства поддерживают многочисленные технологий проектирования программных систем: от простых средств анализа до полномасштабных средств автоматизации.
CASE-средства, как правило, направлены на поддержку верхнего уровня без рассмотрения формальных ограничений конкретного языка программирования. Одним из подходов к решению этой проблемы предлагается технология автоматического синтеза модулей программы на основе интерактивного построения блок-схем. Такой способ создания приложений, когда составление программных кодов осуществляется путём манипулирования графическими объектами, получил название визуальное программирование.
Общие принципы создания программ через блок-схемы представлены на рис. 1. Предлагаемая технология не затрагивает весь процесс конструирования программного обеспечения, рассматривается та часть деятельности, разработка которой не может обойтись без участия программиста: проектирование и кодирование.
 |  | ||
|
| ||
| |||
На основе предложенной технологии реализована система синтеза блок-схем отдельных модулей программы с автоматическим формированием текстов программ выбранного языка и исполняемого кода через запуск соответствующих консольных компиляторов и линковщиков.
3. Управляющие структуры. В соответствии с методологией структурного программирования любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:
· следование — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;
· ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;
· цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие.
Конструирование блок-схем модулей программы достигается путём выбора комбинаций конструкций, соответствующих ограниченному множеству управляющих структур.
Утверждение. Для построения любой формы управления, которая может потребоваться при построении блок-схемы программы, достаточно две базовые конструкции: следование и ветвление. Цикл является результатом их комбинирования (рис. 2).
 | |
 |  |
|
Фрагменты конструкций, представляющие собой логически целостные вычислительные блоки, выделяются в виде отдельных структур.
В отличие от структурного программирования, в котором выход одной структуры подключается непосредственно ко входу следующей структуры без возможности возврата, предлагается отказаться от запрета повторного вызова управляющих структур. Простейшей реализацией такой логики является использование оператора безусловного перехода goto, неприемлемого при структурном программировании, но эффективно используемого при подходе, когда текст программы является внутренним представлением, а внешним – блок-схема.
В качестве модели предлагается к рассмотрению модуль для разработки последовательной программы, имеющий наборы типизированных блоков или с одним выходом, или с несколькими альтернативными выходами (ветвление).
4. Описание редактора блок-схем. Графический интерфейс бета-версии редактора представлен на рис. 4.
Рис.4. Бета-версия редактора блок-схем
Для построения блок-схемы программы в распоряжении пользователей имеются две управляющие структуры: действие и выбор. Эти структуры соединяются стрелками - линиями связи. Линии связи показывают последовательность, в которой должны осуществляться операции обработки.
Структура действия обозначается символом узла обработки (рис. 3, а). Узел обработки обозначает действия: вычисления, операции ввода/вывода и т. д.
Структура выбора используется для выбора среди альтернативных путей обработки информации. Структура с единичным и двойным выбором изображается символом узла проверки условия (рис. 3, б). Символ имеет две выходящие из него линии связи. Одна показывает направление, которое выбирается, если выражение в символе истинно (знак “+”), другая – если выражение ложно (знак “–”). Структура множественного выбора изображается символом разветвителя (рис. 3, в).
Общим для отображения управляющих структур является расположение входов слева и выходов справа блока.
Для построения длинных цепочек управляющих структур, а так же для цепочек, которые можно выделить в отдельные функциональные блоки (функции), предусмотрено их вложение. При использовании вложений отображается текущий уровень вложения, на котором находится пользователь. Блок-схема, которая предоставляет полный алгоритм программы, имеет нулевой уровень вложения.
Любая блок-схема должна имеет символы начала и завершения (рис. 3, г).
 | |||||||
 |  | ||||||
 | |||||||
|
|
|
|
Рис. 3. Элементы блок-схемы:
а) символ узла обработки, б) символ узла проверки условия,
в) символ разветвителя, г) символы начала-завершения
Если часть кода программы была составлена в текстовом редакторе или среде программирования и находится на внешнем запоминающем устройстве, тогда файл кода импортируется в редактор и обозначается в виде элемента “чёрный ящик”. Исходный текст программы формируется с учётом импортированного элемента.
Экспорт блок-схемы осуществляется в виде псевдокода, либо растрового или векторного изображения.
Все графические элементы блок-схемы хранятся в текстовых файлах, поэтому они могут быть изменены любым текстовым редактором.
Редактор обладает способностью автоматического размещения управляющих структур. Доступны несколько алгоритмов автоматической генерации блок-схем с проверкой на пересечение линий связи.
5. Представления кода программы. Рассмотрим различные представления кода программы на примере.
Пример. Произвести сортировку элементов массива array по возрастанию методом простого обмена (метод “пузырька”). Элементы массива – целые числа.
Запишем функцию SortUp на языке С, имеющую параметры: int array[] - массив целых чисел, int col – длина массива. Представление_1 – исходный код, выполненный по правилам структурного программирования.
Представление_1:
void SortUp (int array[], int col)
{
int temp,i,j;
for (i=1; i<col; i++)
{
for (j=0; j<col-i; j++)
{
if (array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
Построим блок-схему, используя предложенный модуль для разработки последовательной программы (рис. 5). Для операторов с одним выходом будем использовать имена блоков, начинающиеся с буквы P (Process), для операторов с двумя альтернативными выходами - имена блоков, начинающиеся с буквы L (Logic). Модель блок-схемы назовём представлением_2.
Рис. 5. Блок-схема функции SortUp
В каждый из блоков включены соответствующие функциональные операторы. Из блок-схемы может быть сгенерирован код программы на основе оператора goto.
Представление_3:
void SortUp (int array[], int col)
{
int temp,i,j;
P1: i=1; goto L1;
L1: if (i<col) goto P2; else goto P6;
P2: j=0; goto L2;
L2: if (j<col-i) goto L3; else goto P5;
L3: if (array[j]>array[j+1]) goto P3; else goto P4;
P3: temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; goto P4;
P4: j++; goto L2;
P5: i++; goto L1;
P6: return;
}
Многочисленные переходы затрудняют чтение представления_3 программного кода. Однако этот текст рассматривается в качестве внутреннего представления программы. После генерации код передаётся соответствующему компилятору или выполняется с помощью внутреннего модуля-интерпретатора.
6. Логика модуля-интерпретатора. Рассмотрим представление_3 программы в виде следующих блоков: управляющего устройства и функционального процессора [4]. Для этого запишем полученный код, используя структуру множественного выбора:
void Control (int select)
{
static array[col];
static int temp,i,j;
case (select)
{
P1: i=1; break;
L1: if (i<col) V1=1; else V1=0; break;
P2: j=0; break;
L2: if (j<col-i) V2=1; else V2=0; break;
L3: if (array[j]>array[j+1]) V3=1; else V3=0; break;
P3: temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; break;
P4: j++; break;
P5: i++; break;
}
}
Функциональный процессор включает набор функциональных команд (P1-P5) и статических объектов (переменные temp, i, j, массив array), соответствующие регистрам стандартного центрального процессорного устройства (ЦПУ). Набор логических команд (L1-L3) соответствует блоку арифметико-логического устройства (АЛУ).
В управляющем модуле осуществлён доступ к набору логических команд, для которых введены логические переменные (V1-V3):
void Logic ()
{
P1: Control(P1); goto L1;
L1: Control(L1); if (V1>0) goto P2; else goto P6;
P2: Control(P2); goto L2;
L2: Control(L2); if (V2>0) goto L3; else goto P5;
L3: Control(L3); if (V3>0) goto P3; else goto P4;
P3: Control(P3); goto P4;
P4: Control(P4); goto L2;
P5: Control(P5); goto L1;
P6: return;
}
Управляющий модуль формируется таблицей:
Таблица1: управляющий модуль
метка | функциональный оператор | переход1 | переход2 |
P1 L1 … P6 | Control(P1) Control(L1) … return | L1 P2 … | P6 … |
где метка – имя блока; функциональный оператор - имя команды функционального процессора; переход1 – переход к метке, осуществляемый для простых блоков и в случае true логического блока; переход2 – переход в случае false логического блока.
Схема интерпретации произвольного модуля [6] описывается в виде цикла выполнения функциональных блоков и совершения переходов до тех пор, пока цикла не завершится соответствующим функциональным оператором (рис.6).
Начиная с первой строки управляющего модуля, происходит выполнение функционального блока текущей строки (i). Если функциональный оператор завершает цикл, то интерпретатор останавливает свою работу, иначе проверяется возвращаемая функциональным оператором логическая переменная (Vi). В случае Vi > 0 осуществляется переход на строку, метка которой указана в переходе1 текущей строки, иначе – на строку с меткой перехода2.
Рис. 6. Схема интерпретации модуля
Технология представленной модели схожа с технологией работы машины Тьюринга. Модель представляет собой простейшую вычислительную машину с линейной памятью, которая преобразует входные данные с помощью последовательности элементарных действий по заданным правилам.
В состав Машины Тьюринга входит бесконечная лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Управляющее устройство работает согласно правилам перехода. В нашей модели в роли ленты выступает блок-схема, разделённая управляющими структурами. Управляющее устройство находится на начальном блоке и движется пошагово согласно линиям связи. Правила преобразования входных данных описаны узлами обработки.
Для реализации механизма взаимодействия асинхронных вычислений можно воспользоваться аппаратом Joiner-сетей [7] (обобщение сетей Петри), задающего логическое управление пусковых и флаговых функций. По мере накопления событий, сигнализирующих об окончании параллельных процессов, пусковые и флаговые функций позволяют запускать новые процессы, обеспечивая асинхронность отдельных функциональных блоков.
Разработанный прототип интерактивного построения блок-схем позволяет путём манипулирования графическими объектами редактировать логику программ, автоматически формировать программные коды в текстовом виде с последующей их передачей компиляторам, а также содержит собственный модуль интерпретации. Предлагается рассматривать исходный текст как внутреннее представление программы, а блок-схему как внешнее представление. В настоящее время ведутся работы по созданию технологии синтеза параллельных и распределенных программных систем на основе развития данного подхода.
ЛИТЕРАТУРА
1. Дейтел П. Как программировать на C++. М.: Бином, 200с.
2. Гатэг Дж. Использование абстракций и спецификаций при разработке программ. М.: Мир, 198с.
3. Структурное программирование. М.: Мир, 197с.
4. , От языков программирования – к моделям программ // Труды XII Байкальской Всероссийской конф. «Информационные и математические технологии в науке и управлении». Часть III. – Иркутск: ИСЭМ СО РАН, 2007. С. 140-147.
5. CASE-технологии. Современные методы и средства проектирования информационных систем. – М.: Финансы и статистика, 1998. – 176 с.
6. Основы универсальной среды программирования ЗИРУС // Вестник ИрГТУ. -2006. -№2(26).-С.62-68.
7. , Joiner-сеть для моделирования взаимодействующих параллельных процессов // Моделирование процессов управления: Сб. научных трудов / Моск. физ.-тех.. ин-т. - М., 2004. - С. 81-97.
