книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

Глава VI ВЫБОР Я З Ы К А

П Р О Г Р А М М И Р О В А Н И Я

§ 6. 1. МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА

ПРОБЛЕМЫ ВЫБОРА

В настоящее время вычислительные машины стали необходимой частью любой системы обработки информации и тем более любой автоматизированной системы управления. Расшире­ ние сферы вычислительных машин ставит новые проблемы как в теории программирования, так и в теории алгоритмических язы­ ков. Одной из таких проблем является разработка алгоритмов оценки и выбора языков для оптимального программирования за­ дач из заданного класса проблем. Математическая формулировка этой проблемы приведена в работе Т. Я- Данелян [21].

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

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

141

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

лесообразнее отыскивать сравнительно узкий класс, содержащий интересующие нас языки, и применять их для описания проблем. В этих целях нужно уметь выделять характерные элементы, па­ раметры, составляющие языки программирования, которые дали бы возможность провести соответствие между элементами проблем и языка. Необходимо выработать определенные меры качества языков, с тем чтобы можно было оценить, в каких случаях и для каких задач нужен тот или иной язык (более универсальный, но менее выгодный или, наоборот, более узкий, но выгодный). Уметь квалифицировать язык — значит уметь оценить, какие и насколь­ ко сложные проблемы может описывать язык. В то же время ко­ нечный результат выбора языка программирования зависит от

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

Исходя из сказанного, общий подход к решению конкретной проблемы с использованием вычислительной машины можно пред­ ставить в виде трех этапов:

1.Спецификация проблемы.

2.Выбор и уточнение метода решения.

3.Реализация метода решения.

Первые два этапа известны как анализ и проектирование про­ блемы a.i, которыми занимается аналист. Третий этап носит назва­ ние программирования метода решения, которое реализуется про­ граммистом. Разница между этими двумя концепциями в том,что аналист изучает проблему и специфицирует ее решение в языке, доступном для понимания человеку, в то время как программист преобразует данную спецификацию в вид, удобный для передачи метода вычислительной машине. Собственно этап спецификации проблемы расчленяется на шесть самостоятельно поставленных перед аналистом задач:

1. Анализ представительности и типов данных из предметного {/-множества ^-объектов и уточнение множества f'-операций и процедур, определяющих проблему а;.

142

2.Установление всех ограничений на множестве данных V и операций F.

3.Установление всех функциональных связей на предметном множестве U всех тех ^-объектов, которые составляют данную проблему.

4.Определение возможно полного класса А всех проблем, спе­ цифицированных множествами U и F проблемы щ.

5.Решение вопроса о выборе языковых средств и средств ре­ ализации проблемы, т. е. какие требования необходимо предъяв­

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

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

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

ка — DL.

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

этого необходим тщательный анализ и изучение достаточно пред­ ставительного класса /.„-языков программирования. Безусловен тот факт, что внимательное изучение языков программирования с их характеристиками поможет пользователю избежать неправиль­ ного выбора конкретно требуемого L-языка.

2. Необходимо знать все типы алгоритмов выбранного для изу­ чения класса А проблем, их конструктивные особенности, а также типы и категории объектов, с которыми работает исследуемое мно­ жество алгоритмов из класса А. Необходимо в результате изуче­ ния строения L-языков уметь подвести базу под те принципы, ко-

143

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

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

кам. Классификация должна быть строгой в смысле формальности подхода к выбору характеристик, специфицирующих L-языки и алгоритмы из класса А . Кроме того, классификация должна быть унифицированной в смысле соответствия характеристик L-языка и алгоритмов проблем из класса А . Этот принцип своей базой име­ ет тот факт, что выбор L-языка должен производиться из подклас­

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

5. Необходимо иметь единую формальную систему, в рамках которой однозначно определяются L-языки и содержательные ал­ гебры проблем А как алгоритмические системы, т. е. формальная система в таком аспекте интерпретируется как единый способ за­ дания языков программирования и класса изучаемых проблем. Выбранная формальная система должна быть полной в смысле содержательного отображения всех компонент алгоритмических языков и проблемных систем. Кроме того, формальная система должна служить основанием для построения содержательной тео-

144

рии, определяющей разрешимость оценочного алгоритма выбора языков программирования для конкретного применения. Этот ме­ тодологический принцип строится на том основании, что оценочные критерии хорошего языка и требования, предъявляемые к языку, подходящему для данного класса проблем, можно получить лишь при том условии, что анализ языкового и проблемного множеств проводится в строгом соответствии с основными характеристика­ ми, заданными в единой системе измерения. Таким образом, за­ дача построения разрешающего оценочного алгоритма выбора языков программирования для конкретного применения является комплексной.

Научный аспект проблемы связан с выявлением факторов и критериев, определяющих сущность алгоритма выбора, и с непо­ средственным конструированием схемы алгоритма. Как первое, так и второе должно базироваться на научном обобщении резуль­ татов анализа и классификации языкового L n и проблемного А классов. Кроме того, построение системы оценочных функций сво­ им основанием имеет оценочные характеристики, получаемые пре­ образованием оценочных параметров в числовые эквиваленты. С помощью этих функций с достаточной степенью вероятности и однозначности можно определить меру качества выбираемого из

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

ми базовой структуры и конкретной формой представления сооб­ щения.

Параметр U языковой системы программирования может иметь различные конкретные значения для заданной параметрами l2, h абстрактной схемы языка. В зависимости от фактического значе­ ния /4 одна и та же схема абстрактного языка может принимать различные интерпретации. Но в любой из них конкретно представ­ ляемые L-языки должны быть эквивалентны, если они определены одними и теми же 12, / 3 . Термин «базовая форма» содержательно эквивалентен основному конструктивному представлению выраже­ ний операторов, объявлений, программы в целом для конкретного языка программирования.

Параметр /4 зависит от фактического преемника, т. е. вычис­

включаются при написании сообщений согласно схеме, заданной базовой структурой L-языка. По аналогии параметр h можно от­ нести к совокупности возможных промежуточных и конечных зна­ чений, которые получаются в процессе вычисления строк по задан­

и смысл функций алгоритма информационной системы / или строе­

форму, или синтаксис, вторая — смысл, или семантику.

Покажем, каким образом параметризуется алгоритмическая система проблем. В этом случае информационная система есть совокупность проблем или класс А взаимосвязанных проблем. Пусть мы имеем некоторую абстрактную проблему щ из класса А, определенную на предметном множестве UA. Тогда проблемный класс А однородных проблем а* в системе параметров предста­ вится следующим образом:

дур, перерабатывающих информацию, в частности, все выраже­

146

Параметр ой — совокупность всех возможных представлений алгоритмов, решающих проблему аг- или проблемы из класса Л.

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

примитивными процедурами. В свою очередь параметр 13 синтези­

ким аспектом, должен полностью соответствовать параметру аз. Компонента параметра / 3 определяет направленность сравнитель­ ного анализа между языковыми системами в целях выбора наи­ более удобных ;танструктивных представлений базовых форм и оп­ ределяет L-язык как хороший в аспекте его общности и практи­ ческой реализации для данной проблемы. Компонента U должна соответствовать компоненте 0С4 в смысле способов изобразитель­ ного представления алгоритма Л,-, который является наиболее удобным для решаемой проблемы. В заключение можно отметить, что конкретная оценка применимости L-языка для выбранной проблемы в рамках параметризированной системы Р может быть сведена к сравнительному сопоставлению параметризированных схем языковых и проблемных алгоритмических систем и опреде­ лению степени совместимости характеристических множеств каж­ дого из параметров схемы.

§ 6. 2. АЛГОРИТМ ВЫБОРА ЯЗЫКА ПРОГРАММИРОВАНИЯ ДЛЯ КОНКРЕТНОГО ПРИМЕНЕНИЯ

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

В общем виде задача выбора формулируется следующим об­ разом.

Заданы:

1) класс решаемых задач А и основные характеристики в виде набора параметров Р (At) по каждой задаче из этого класса Л,-:

2) множество языков программирования L n с указанием для каждого языка из этого класса L } основных характеристик, так­ же в виде набора параметров Р (а,):

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

Требуется разработать алгоритм выбора из множества языков программирования L n такого языка L h основные характеристики которого в максимальной степени удовлетворяли бы требованиям задач из заданного класса Л.

Исходными данными для выбора языка служат:

1)картотека языков программирования — L ;

2)картотека языковых систем — TL;

3)стандартная форма пользователя — СФ.

языка для описания конкретной проблемы, характеристики кото­ рой заданы в СФ;

II — этап апробации языка и отбор языков по оценочным ха­ рактеристикам;

I I I —этап выбора языковой системы.

Первый этап алгоритма выбора имеет целью путем сопоставле­ ния основных характеристик проблемы Ai и языков программиро­ вания выявить подмножество языков, пригодных для описания проблемы А^ Для этого по признакам «общности» и «области применения» из картотеки L n отыскивается подмножество тех языков, у которых значения признаков по таблице соответствия совпадают с указанными в СФ. Далее происходит сужение под­ множества выбранных языков путем исключения тех, которые ли-

148

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

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

1. Представительная проблема Л,- из семейства проблем А опи­ сывается средствами всех сравниваемых языков из подмножества,

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

Второе направление — выполнение этапа выбора языковой си­ стемы. Этот этап выбора связан с квалификационной оценкой внедрения языка программирования, т. е. качеством и организа­

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

Q — количество аннотаций (языков или языковых систем), ос­ тавшихся после очередного выбора;

р-—логический переключатель, где / = 1 , 2, 3, 4, имеющий сле­ дующие значения:

Р\ — имеет ли место дополнительная информация, т. е. запол­ нена ли вторая часть СФ;

Р2 — будет ли активизироваться этап апробации, а если он уже активизировался, то нужен безусловный переход;

149