Диалоговый монитор для автоматизации процесса синтеза программ ЭВМ тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

Введение

Глава I. Обзор и анализ проблемы автоматизации процесса синтеза программ

§ I.I Актуальность рассматриваемой проблемы

§ 1.2 Обзор и анализ методов и систем автоматизации процесса разработки программ

§ 1.3 Обсуждение рассматриваемой проблемы . . 27 Выводы по I главе

Глава II Постановка задачи. Описание информационной среды и процесса синтеза программ

§ 2.1 Постановка задачи

§ 2.2 Описание информационной среды диалогового монитора

§ 2.3 Описание процесса синтеза программ в диалоговом мониторе

Выводы по II главе

Глава III Формализованное описание процесса синтеза программ

§ 3.1 Общее описание формализованной системы Л! . Описание формализованного языка

§ 3.2 Описание исходных высказываний формализованной системы.

§ 3.3 Формализованное описание процесса синтеза программ

§ 3.4 Непротиворечивость и полнота формализованной системы

X . Вывод секвенций . 94 Выводы по III главе

Глава 1У Реализация диалогового монитора по формализованному техническому заданию

§ 4.1 Построение алгоритма диалогового монитора по формализованному техническому заданию

§ 4.2 Описание блок-схемы диалогового монитора.

Пример функционирования монитора в инициативном диалоге.

§ 4.2.1 Описание блок-схемы диалогового монитора

§ 4.2.2 Пример функционирования монитора в инициативном диалоге.

Выводы по 1У главе

Глава У Оценка эффективности диалогового монитора

§ 5.1 Общий подход к оценке: эффективности методов автоматизации программирования

§ 5.2 Оценка качества программ

§ 5.3 Оценка времени разработки программ . 130 Выводы по У главе . . 134 Заключение . . . 135 Литература . . 142 Приложение I. Листинг отдельных процедур диалогового монитора . . 148 Приложение 2. Протокол разработки программы расчета точностных характеристик реактивного снаряда

Большое внимание партией и государством уделяется развитию вычислительной техники и созданию различных вычислительных комплексов. В соответствии с решениями ХХУ съезда КПСС выпуск средств вычислительной техники возрос в 1,8 раза. Постановления ХХУ1 съезда партии предусматривают дальнейшее увеличение выпуска вычислительной техники в 1,8-2 раза. Намечено развивать производство универсальных и управляющих вычислительных комплексов, периферийного оборудования, приборов, устройств регистрации и передачи информации для автоматизированных систем управления технологическими процессами и оптимального управления в отраслях народного хозяйства.

Так в стране в 1976 г. функционировало около 800 различных автоматизированных систем управления и систем автоматизации процесса решения прикладных задач. В 1980 г. их число возросло до 1700.

Широкий фронт приложений, связанных с использованием электронно-вычислительных машин (ЭВМ), обусловил целый этап развития работ по автоматизации процесса программирования, в том числе и работ, связанных с созданием языков программирования, удобных для формализации задач и процессов их решений, и методов построения соответствующих языковых процессоров - систем, обеспечивающих выполнение на ЭВМ программ, составленных на этих языках. Была создана и реализована серия языков программирования, ориентированных на отдельные сферы приложений и получивших название процедурно-ориентированных языков. Общей особенностью этих языков является наличие в них средств обработки, характерных для данной сферы приложений. Получили распространение и признание методы трансляции, основанные на синтаксическом управлении. Процесс перевода с одного языка на другой в синтаксически управляемом трансляторе распадается на две фазы: построение синтаксического разложения исходной записи программы и замена элементов разложения их семантическими эквивалентами в выходном языке. При этом возникает ряд новых проблем, связанных со способами формализации синтаксиса и семантики входных и выходных языков в системах программирования. Указанные проблемы стимулщювали создание метасистем, позволяющих по формальному заданию синтаксиса и семантики входного языка получить транслятор с этого языка.

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

Уже первые попытки решения задач подобного класса привели к возникновению двух новых направлений в программировании - созданию проблемно-ориентированных языков (ПО-язы-ков), систем их реализации и диалоговых систем, знаменующих собой новый этап в развитии автоматизации программирования, характеризующийся в целом идеей представления пользователю средств общения с ЭВМ при минимальных непроизводительных затратах. Эта идея легла в основу создания операционных систем (ОС), реализующих как пакетный режим обработки программ, так и режим работы с разделением времени, особенно удобный для коллективного использования и дистанционной работы с ЭВМ.

Развитие диалоговых систем осуществлялось в двух направлениях: для диалога, когда инициатива исходит от пользователя, и для диалога, когда инициатива запроса отнесена к ЭВМ. В первом случае пользователь формирует запросы ЭВМ на входном директивном языке, во втором - ЭВМ запрашивает информацию от пользователя на языке запросов и получает ответ на входном языке системы. При этом язык запросов ЭВМ и язык ответов может быть сведен к усеченному естественному (русскому) языку. При инициативе ЭВМ возможна передача ей функций по общей организации процесса разработки программ. Например, возможна организация автоматизированной разработки программ на основе метода программирования с помощью стандартизированных структур, который получил название структурного или структурированного программирования (называемого также программированием без £0 ТО ). Структурированное программирование позволяет локализовать и упорядочить связи между участками программ, упростить их взаимодействие. Эта возможность

- 7 была реализована в данной работе.

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

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

Выводы по У главе.

1. Описывается общий подход к оценке эффективности процесса синтеза программ в отношении времени разработки и качества программ. Для оценки качества программ рассматриваются следующие показатели качества: а/ корректность Cjf , для описания соответствия характеристик программы заданным требованиям; б/ расширяемость » поддерживаемость $$ , для отражения возможностей изменения программы при добавлении новых функции и частичного изменения имеющейся структуры; в/ размер и время выполнения программы ^ » 9$ соответственно, для оценки затрачиваемых ресурсов ЭВМ.

Диапазон изменений показателей качества определяется неравенствами: 9$д< , 94 gz <Ю , д% </о , S^ifo

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

2. Оценка времени разработки программы определяется как сумма времени, затраченного на изучение и подготовку необходимых данных, и времени, затраченного на написание непосредственно самой программы. Отношение времени разработки программы при ручном исполнении и времени разработки при использовании системы автоматизации является коэффициентом убыстрения создания программы Хм . Для монитора рассматриваемого класса учет времени подготовки данных является существенным, так как монитор данного класса работает с накоплением информации и, использование которощуменьшает время изучения и подготовки данных. Построены кривые для коэффициентов ^нг при различных параметрах. Реальный диапазон коэффициентов убыстрения процесса разработки программы составляет 2 т 5 раз и выше.

Заключение

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

Во втором случае путь решения задачи в памяти монитора отсутствует и не определен пользователем в виде исходной информации. Путь решения задачи в этом случае формируется в инициативном диалоге в форме алгоритма задачи. Реализация этого процесса осуществляется блоком J>IAL монитора. Блок DIAL формирует последовательность запросов, ответы на которые определяют построение алгоритма задачи.

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

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

Процесс накопления и дальнейшего использования информации связан с принципом обобщения частных решений. В работе чаетное решение считается новым обобщающим решением, если его схема содержит не менее чем заданное количество операторов, не испольэрваншх ранее и отсутствующих в памяти монитора. Таким образом, текущее решение проверяется^проверяется?на наличие новых, ранее не использованнх операторов, а обобщенным решением является сама схема текущего решения. Дальнейшее развитие обобщающего принципа связано с применением ключевых операторов, которые определяют сущность решения, например, в задаче расчета точностных характеристик реактивного снаряда ключевыми операторами можно считать операторы расчета аэродинамических характеристик / АВк /, определения координат /3>2fF/ и расчета статистических параметров / ТСН /. Выделение ключевых операторов осуществляется в диалоге с пользователем. Накопление и дальнейшее использование текущей информации определяет процесс адаптации. В работе формально описввается и реализуется адаптация к классам задач, к схемам решений и к реализующим операторам.

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

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

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

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

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

- автоматический режим определяется последовательностью подцелей ., S^ . . с соответствующим описанием шагов прохождения этих подцелей 7*; ., , Tj . . . ) ;

- разрешающие последовательности шагов неопре-деленностиЛ^-О обеспечивают достижение ближайшей подцели ;

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

- расширение моделей М и тем самым подмножества состо-ний осуществляется редукцией подцелей с одной стороны, а также через введение разрешающих и оценочных состояний с другой; такое расширение определяет частичный порядок на S .

Формальное описание шагов в виде Т(Х) строится как формализованное техническое задание на разработку программы диало~~ гового монитора.

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

6. Программная реализация показала, что:

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

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

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

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

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

- Монитор реализует оперативное планирование в процессе синтеза программ через введение пользователем в систему дополнительной информации.

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

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

- При использовании*процедуры генерации программ по формульным зависимостям синтактическая отладка синтезируемых программ исключается. За пользователем остается семантическая отладка, так как она определяется смысловым построением задачи.

1. Глушков В.М., Вельбицкий И.В. Технология программирования и проблемы ее автоматизации. - Управляющие системы и машины, 1976, $6, с.

2. Тамм Б.Г., Тыугу Э.Х. О создании проблемно-ориентированного программного обеспечения. Кибернетика,1974,М,с.76-85.

3. Ющенко Е.Л., Перевозчикова О.Л. Развитие языков программирования и диалоговых систем в СССР. Кибернетика, 1976, №6, с. 16-33.

4. Берестовая С.Н., Перевозчиков^" О.Л., Романов В.М., Ющенко Е.Л. Конструирование систем программирования обработки данных. М.: Статистика, 1979, 270с.

5. Липаев В.В., Филиппович В.В. Принципы и правила модульного построения сложных комплексов программ АСУ. Управляющие системы и машины, 1975, М, с. 53-57.

6. Браун П. Макропроцессоры и мобильность программного обеспечения. М.: Мир, 1977, 253с.

7. Глушков В.М.,Капитонова Ю.В., Летичевский А.А. 0 применении метода формализованных технических заданий к проектированию программ обработки структур данных. Программирование, IS78, 16, с. 31-43.

8. Непейвода Н.Н. Об одном методе построения правильной программы из правильных подпрограмм. Программирование, 1979, М,с. 15-25.

9. Королев Л.Н. Структура ЭШ и их математическое обеспечение. М.: Наука, 1978, 352с.

10. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971, 360с.

11. Тыугу Э.Х. На пути к практическому синтезу программ.- Кибернетика, 1976, №6, с.37 -39.

12. Тыугу Э.Х. Решение задач на вычислительных моделях.- Журнал вычислительной математики и .математической физики, 1970, т.10, №3, с.23 29.

13. Брановицкий В.И., Довгялло A.M., Никитин А.И., Стог-ний А.А. Диалог человека и ЭВМ: основные понятия и определения.- Управляющие системы и машины, 1978, М, с. 41 44.

14. Довгялло A.M. Диалог пользователя и ЭВМ и место средстх искусственного интеллекта в его реализации. Кибернетика, 1979, №2, с.102 - 108.

15. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975, 247с.

16. N. Wilth, Ргодго/п development 6у stepwise tenement . Communications ±he ЛСМ, t97i,

17. Ершов А.П. Система БЕТА сравнение постановки задачи с пробной реализацией. - Тр. Всесоюз. симпозиума по методам' реализации новых алгоритмических языков. - Новосибирск, ВЦ СО АН СССР, 1975, чЛ, 73с.

18. Криштопа И.В., Непомнящий Б.Д., Перевозчикова О.Л., Ющенко Е.Л. ДИСУППП диалоговая система управления специализированными пакетами прикладных программ. - Кибернетика, 198бу №2, с.70 - 76.

19. Словарь по кибернетике. Под ред. Глушкова В.М. -Киев.: УСЭ, 1979, 623с.

20. Вельбицкий И.В., Ходаковский В.Н., Шолмов Л.И. Технологический комплекс программиста БЭСМ-6. Управляющие системы и машины, 1976, М, с.32 - 39.

21. Погребный В.К. Построение и исследование графовых моделей алгоритмов управления в АСУ. Сб. Автоматизация проект» рования систем управления, под ред. Трапезникова В.А. - М.: Статистика, 1978, с.68 - 99.

22. Гладун В.П., Ващенко Н.Д. Адаптация в решающих системах. Кибернетика, 1979, Ш, с.83 - 88.

23. Виноградский Э.В., Еремина И.А. Принципы моделировав ния информационных и информационно-биологических систем. -Материалы I Всесоюз. конф. "Математическая теория биологических процессов", АН СССР, Калининград, 1976, е.218-219.

24. Бенерджи Р.В. Теория решения задач. М.: Мир, 1972,224с.

25. Виноградский Э.В., Райков Л.Г. Метод конструктивного синтеза управляющих программ ЦВМ. М.: МРС "ТТЭ", серия "ЭР", вып. 3, 1979.

26. Виноградский Э.В. Диалоговая система для оперативной разработки программ САПР. Сб. Организация управления процессами в САПР,МАЙ, 1982, с.47 - 54.

27. Ахо А., Ульман Дж. Теория синтаксического анализаперевода и компиляции. М.: Мир, 1978, 612с.

28. Расева Е., Сикорский Р. Математика метаматематики. М.: Мир, 1972, 592с.

29. Новиков П.С. Элементы математической логики. М.: Наука, 1973, 399с.

30. Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977, 288с.

31. Калиниченко Л.А. Метод построения коммутативных отображений моделей данных при интеграции неоднородных баз данных. Программирование, 1978, Л6, с.60 - 71.

32. Райков Л.Г., Виноградский Э.В. Исследование принятия решений конструктором при машинной организации процесса проектирования. Материалы II Всесоюз. конф. " Биологическая и медицинская кибернетика", ч.1, Ленинград, 1974, с.35-36.

33. Кейслер Г., Чён Ч. Теория моделей. М.: Мир,1977,614с.

34. Орлов Б.Н., Пономарев А.С. Система генерации модульных программ. Кибернетика, 1980, №2, с.82 - 84.

35. Турский В.М. Методология программирования. М.:Мир, 1981, 265с.

36. Чёрч А. Введение в математическую логику. М.: ИЛ, т. II, 1961, 480с.

37. Райков Л.Г., Виноградский Э.В., Еремина И.А. Построение многоуровневых моделей в биологии. Материалы I Всесоюз. конф. "Математическая теория биологических процессов", АН СССР, Калининград, 1976, с.62 - 64.

38. JMicAie д.} £oss Expe'iiments, w-ich -i/>e Adaptive Giaph Ttavezsez,- Mch. Mete., /ЩМ>.5

39. Яновская С.A. О так называемых определениях через абстракцию. Сб. Методологические проблемы науки. - М.:Мысль, 1972, с.5 - 36.

40. Драгалин А.Г. Математический интуиционизм. Введение в теорию доказательств. М.: Наука, 1979, 256с.

41. Шрейдер Ю.А. Пространства толерантности. Кибернетика, 1970, №2, с.22 - 26.

42. Бруевич Н.Г., Челищев Б.Е., Боброва И.В. Математические основы автоматизации проектирования процессов механической обработки деталей. Техническая кибернетика, 1978, М, с.134 - 145.

43. Floyd W, £ssigni<f meanings to рюдгот$.- (hoc. Sympos, JJppi. /УМ. Мег.ЛШ. Soc,t

44. Вирт H. Систематическое программирование. М.: Мир, 1977, 183с.

45. Фендриков Н.М., Яковлев В.И.,.Методы расчета боевой эффективности вооружения. М.: Воениздат, 1971, 224с.50'* Генделев Г.М. О подходах к оценке качества программ.- Управляющие системы и машины, 1977, №3, с.37 40.

46. Генделев Г.М., Куклин В.И., Шилай Л.К. Организация и методы разработки специального математического обеспечения АСУ. М.: Статистика,J974,,120с.

47. Велеско Е.И., Затуринский А.Г., Илюкович А.А. Нормирование труда при разработке математического обеспечения АСУ. Минск: БНИИНТИ, 1975, 57с.

48. Шеметов А.Н. Исследование и разработка методов повышения эффективности математического обеспечения систем электронной обработки данных. Канд. диссерт. М.: 1973.

49. Азгальдов Г.Г., Азгальдова А.А. Качественная оценка качества. М.: Изд. стандартов, 1971, 65с.