Содержание к диссертации
Введение
Глава I. Обзор и анализ проблемы автоматизации процесса синтеза программ 8
1.1 Актуальность рассматриваемой проблемы 9
1.2 Обзор и анализ методов и систем автоматизации процесса разработки программ 13
1.3 Обсуждение рассматриваемой проблемы 27
Выводы по I главе 33
Глава II Постановка задачи. Описание информационной среды и процесса синтеза программ 34
2.1 Постановка задачи 35
2.2 Описание информационной среды диалогового монитора 43
2.3 Описание процесса синтеза программ
в диалоговом мониторе 50 Выводы по II главе 69
Глава III Формализованное описание процесса синтеза программ 70
3.1 Общее описание формализованной систе мы Описание формализованного языка 71
3.2 Описание исходных высказываний формали зованной системы 74
3.3 Формализованное описание процесса синтеза программ . . 82
3.4 Непротиворечивость и полнота формализованной системы^Х Вывод секвенций 94 Выводы по III главе 100
Глава ІV Реализация диалогового монитора по формализованному техническому заданию 101
4.1 Построение алгоритма диалогового монито ра по формализованному техническому зада нию 102
4.2 Описание блок-схемы диалогового монитора. Пример функционирования монитора в иници ативном диалоге 109
4.2.1 Описание блок-схемы диалогового монитора 109
4.2.2 Пример функционирования монитора в иници ативном диалоге 115
Выводы по ІУ главе 119
Глава V Оценка эффективности диалогового монитора 120
5.1 Общий подход к оценке: эффективности методов автоматизации программирования 121
5.2 Оценка качества программ 124
5.3 Оценка времени разработки программ 130
Выводы по У главе 134
Заключение 135
Литература
- Обсуждение рассматриваемой проблемы
- Описание информационной среды диалогового монитора
- Формализованное описание процесса синтеза программ .
- Описание блок-схемы диалогового монитора. Пример функционирования монитора в иници ативном диалоге
Введение к работе
Большое внимание партией и государством уделяется развитию вычислительной техники и созданию различных вычислительных комплексов. В соответствии с решениями ХХУ съезда КПСС выпуск средств вычислительной техники возрос в 1,8 раза. Постановления XX7I съезда партии предусматривают дальнейшее увеличение выпуска вычислительной техники в 1,8-2 раза. Намечено развивать производство универсальных и управляющих вычислительных комплексов, периферийного оборудования, приборов, устройств регистрации и передачи информации для автоматизированных систем управления технологическими процессами и оптимального управления в отраслях народного хозяйства.
Так в стране в 1976 г. функционировало около 800 различных автоматизированных систем управления и систем автоматизации процесса решения прикладных задач. В 1980 г. их число возросло до 1700.
Широкий фронт приложений, связанных с использованием электронно-вычислительных машин (ЭВМ), обусловил целый этап развития работ по автоматизации процесса программирования, в том числе и работ, связанных с созданием языков программирования, удобных для формализации задач и процессов их решений, и методов построения соответствующих языковых процессоров - систем, обеспечивающих выполнение на ЭВМ программ, составленных на этих языках. Была создана и реализована серия языков программирования, ориентированных на отдельные сферы приложений и получивших название процедурно-ориентированных языков. Общей особенностью этих языков является на _ 5 личие в них средств обработки, характерных для данной сферы приложений. Получили распространение и признание методы трансляции, основанные на синтаксическом управлении. Процесс перевода с одного языка на другой в синтаксически управляемом трансляторе распадается на две фазы: построение синтаксического разложения исходной записи программы и замена элементов разложения их семантическими эквивалентами в выходном языке. При этом возникает ряд новых проблем, связанных со способшли формализации синтаксиса и семантики входных и выходных языков в системах программирования. Указанные проблемы стимулировали создание метасистем, позволяющих по формальному заданию синтаксиса и семантики входного языка получить транслятор с этого языка.
Разработкой процедурно-ориентированных языков, предназначенных для обслуживания различных сфер приложений, и созданием соответствующих языковых процессоров в значительной степени упрощается программирование за счет включаемых в эти языки специальных средств описания процессов решения тех или иных классов задач. Однако за пользователем процедурного языка остается функция осмысливания алгоритма решаемой задачи во всех ее деталях и нюансах в терминах избранного им языка. Особые трудности вызывает задача отладки программ, которую следует отнести к задачам с неполной информацией. Аналогичные трудности возникают при решении класса задач, общий алгоритм решения которых еще не известен и для нахождения частичного решения требуется проведение самостоятельного исследования, а также при рассмотрении класса задач с неполной информацией, решаемых неизбежно эвристическими методами и относимых к классу задач искусственного интеллекта.
Уже первые попытки решения задач подобного класса привели к возникновению двух новых направлений в программировании - созданию проблемно-ориентированных языков (ПО-язы-ков), систем их реализации и диалоговых систем, знаменующих собой новый этап в развитии автоматизации программирования, характеризующийся в целом идеей представления пользователю средств общения с ЭВМ при минимальных непроизводительных затратах. Эта идея легла в основу создания операционных систем (ОС), реализующих как пакетный режим обработки программ, так и режим работы с разделением времени, особенно удобный для коллективного использования и дистанционной работы с ЭВМ.
Развитие диалоговых систем осуществлялось в двух направлениях: для диалога, когда инициатива исходит от пользователя, и для диалога, когда инициатива запроса отнесена к ЭВМ. В первом случае пользователь формирует запросы ЭВМ на входном директивном языке, во втором - ЭВМ запрашивает информацию от пользователя на языке запросов и получает ответ на входном языке системы. При этом язык запросов ЭВМ и язык ответов может быть сведен к усеченному естественному (русскому) языку. При инициативе ЭВМ возможна передача ей функций по общей организации процесса разработки программ. Например, возможна организация автоматизированной разработки программ на основе метода программирования с помощью стандартизированных структур, который получил название структурного или структурированного программирования (называемого также программированием без СО ТО ). Структурированное программирование позволяет локализовать и упорядочить связи между участками программ, упростить их взаимодействие. Эта возможность была реализована в данной работе.
Кроме того диалоговые системы с инициацией запроса информации от ЭВМ позволяют в относительно простой форме реализовать накопление информации в процессе функционирования системы таким образом, чтобы увеличить долю автоматического режима работы за счет использования этой накопленной информации в процессе поиска.
В данной работе рассматривается диалоговый монитор, который реализует диалог с пользователем на основе инициативного запроса необходимой информации таким образом, что в процессе диалога монитор организует разработку программы пользователя по методу структурированного программирования. По окончании разработки алгоритма возможна генерация фрагментов или всей программы по формулам, указанным пользователем на экране видеотона. Диалог осуществляется на усеченном русском языке. В процессе функционирования диалоговый монитор обобщает и накапливает информацию о решениях задач пользователя. Оценивается эффективность данного подхода, которая заключается в уменьшении времени разработки программ в 4 -6 раз по сравнению с ручным проектированием при качестве, равном 804-100 единиц.
Обсуждение рассматриваемой проблемы
В предыдущем параграфе по ходу обзора указывались некоторые трудности использования и ограничения рассматриваемых систем. В этом параграфе подробнее рассматриваются основные направления, обеспечивающие расширение возможностей диалоговых мониторов.
1. В системах директивного диалога, используемого в сущест вующих мониторах , трудно или невозможно работать с изменяющей ся, развивающейся информационной моделью среды. Как следствие этого, не предусматривается возможность работы с нулевой, на чальной базой данных. В этом случае целесобразно использование инициативного диалога, когда монитор инициирует последователь ность запросов пользователю при отсутствии в памяти конкретной информации. Запрашиваемая информация в виде правильных ответов используется для синтеза программы пользователя, а также может быть использована для накопления при выполнении определенных условий по обобщению, например, для накопления схем решений.
Реализация инициативы монитора по формированию алгоритма и программы пользователя относится к реализации внутренних функций монитора и используется, кроме прямого назначения, для структурирования и расширения предметной области монитора.
2. Автоматическое развитие модели, в общем случае, начи ная с нулевой, связано с принципом совершенствования такой мо дели в результате чего возникает прирост информации, приводя щий к ускорению и упрощению процесса решения задач. За счет обо бщения и структурирования информации о задаче при построении модели возникает эффект адаптации - выделение и использование информации с целью достижения определенного состояния или по ведения [22fe2)J Можно выделить некоторые виды адаптации.
а/ Адаптацией к задаче называется процесс обобщения, на копления и использования в решающей системе информации о процессе решения задачи с целью выбора более эффективного развития этого процесса. Под эффективностью может пониматься уменьшение времени разработки прграммы. В этом случае использование накопленной информации может обеспечить автоматический режим синтеза программы, до этого решаемых в диалоге,
в/ Под схемой решения задачи понимается последовательность операторов фрагментов , реализующих решение данной задачи. Адаптацией к задаче является обобщение, накопление и использование схем решений задач при решении задач из заданного класса. Накопление схем решений может осуществляться при нулевой начальной базы схем решений.
с/ Адаптация к классу задач называется процесс накопления и использования в решающей системе информации о классе задач, направленный на увеличение эффективности процесса решения задач. Конкретное увеличение эффективности решения задач при адаптации к классу задач сводится к сужению области поиска приемлемого решения задачи данного класса.
3. Целесобразно дальнейшее развитие и использование средств обеспечивающих простоту применения решающих систем. Сюда относится упрощение входного языка вплоть до применения фраз русского языка, то есть понятий предметной области и понятий описания задачи,
4. Недостаточно уделено внимание по обеспечению возможности оперативной разработки программы. Поз оперативной разработкой программ понимается возможность генерировать отдельные программы фрагментов при отсутствии их в памяти системы. В работе используется генерация программ при использовании формул в описании алгоритма.
5. Перспективным является использование метода формали-зованных технических заданий, как технологического подхода к проектированию программ. Данный метод позволяет от формального описания процесса преобразования информации перейти к описанию алгоритма.
Так как всякая программа реализует некоторое отображение исходных данных в результаты, то формализованная модель программы представляет собой математическое описание этого отображения. Формализованное описание может быть выполнено путем задания совокупности функций, которые вычисляются в процессе работы программы, либо путем задания преобразований информационной среды, которые выполняются программой, либо задания отношений, которые связывают исходные данные и результаты. Разработка функциональной модели включает в себя уточнение математической постановки задачи и определение содержательных структур данных. Выбор математической логики в качестве формального аппарата для построения формализма и использование отношений зри описании преобразований информации определяется тем, что описание отношений используется в математической логике и, по существу, тем, что при описании функционирования диалогового монитора необходимо учесть переход от одного состояния к другому, представленного в различных режимах, то естылереход между состояниями различной природы, например, переход от состояния автоматического синтеза к состоянию диалога. Формализация переходов должна описывать конкретные условия переходов в рамках используемых отношений. Кроме того, аппарат математической логики позволяет исследовать класс описанных моделей на основе построения и исследования формальных систем.
Описание информационной среды диалогового монитора
Под состоянием неопределенности понимается состояние прерывания автоматического процесса синтеза программы в случае отсутствия необходимой информации. Тогда Qsi &А 0о.і fi/Z4 чп. «Sf/ - операторы, обеспечивающие возврат к автоматическому синтезу. Выделение состояний автоматического синтеза и состояний неопределенностей, устранение которых осуществляется получением да необходимой информации, позволяет описать класс мониторов,по своему функционированию занимающих промежуточное положение между автоматическими мониторами и мониторами с директивным диалогом.
Информацию, которая определяет продолжение автоматического режима функционирования монитора, то есть разрешает возникшую неопределенность, будем называть разрешающей информацией, а процесс ее получения - разрешением неопределенности. Операторы (РА а следовательно и Q_a. , определяются конкретным построением монитора, поэтому разрешение неопределенностей может быть осуществлено встроенными средствами через использование алгоритмических средств, а также через диалог с пользователем, реализуемый с помощью операторов QjyrQb- При этом в ответ на конкретный запрос пользователь может ввести программные средства разрешения. Такие программные средства должны "узнавать" неопределенность и разрешать ее для данного класса задач.
Формирование программы задачи пользователя из программных фрагментов определяется процессом определения необходимых составляющих программы и процессом коррекции параметров (свойств) этих составляющих. Таким образом, процесс синтеза программы пользователя является процессом конструирования или процессом сборки программы задач из фрагментов с необходимой коррекцией параметров.
Процесс автоматического синтеза может прерываться при возникновении состояния неопределенности.
Процесс синтеза решения задачи осуществляется в условиях изменения информационной среды монитора, базы данных. Пользователю или пользователям трудно или невозможно учесть такие изменения. Целесообразно, как отмечалось выше, использовать в этом случае инициативный диалог, когда монитор инициирует последовательность запросов пользователю с целью получения информации, необходимой для реализации процесса синтеза решения задачи.
Под инициативным диалогом понимается диалог пользователя с ЭВМ, когда монитор формирует последовательность запросов к пользователю таким образом, чтобы последовательность ответов на запросы определила необходимую информацию для достижения заданного состояния процесса синтеза.
Инициативный диалог позволяет реализовать прогрессивную методологию формирования программы, включая методы разделения задачи на подзадачи и методы структурированного программирования 15] . Кроме того, инициативный диалог позволяет относительно просто реализовать в рамках структуры монитора принципы адаптации. Использование адаптации как метода достижения большой эффективности диалоговых мониторов в отношении времени решения задач позволяет осуществить построение класса диалоговых мониторов, занимающих по принципу функционирования промежуточное положение между мониторами автоматического синтеза программ и мониторами, принцип работы которых основан на директивном диалоге.
Использование адаптации позволяет получить: - накопление информации, которая определяет класс решаемых задач, то есть информацию, разбивающую множество задач на классы; - обобщение и накопление информации, описывающей схемы реше ний задач; - накопление компонент решения задач (фрагментов) в прог раммном исполнении. диалоговый монитор, обобщающий и накапливающий информацию в процессе функционирования, может осуществить выдачу накопленных решений или схем решений. Накапливая информацию, диалоговый монитор увеличивает относительную долю времени работы в автоматическом режиме и в пределе переходит в автоматический режим выдачи решений задач заданного класса.
Формальное описание семантики операторов преобразования информации О, диалогового монитора в соответствии с методом формализованных технических заданий необходимо строить с учетом: - формального описания класса диалоговых мониторов на основе выделения основных формальных положений или аксиом; - наличия трех принципиально отличающихся по смыслу подмножеств состояний $А , SJI , Sjb , и соответственно - процесса обобщения и накопления различной информации, а именно: о классе решаемых задач, об особенностях решаемых задач, описанных в схемах решений, и т.п.
Учитывая вышеизложенное, целесообразно формальное описание семантики операторов преобразования информации строить в высказы-вательной форме: "если где Jik($i) -высказывание, описывающее состояние $i ; Яе( ) -высказывание, описывающее состояние Sj .
Формализованное описание процесса синтеза программ .
Формальное описание процесса синтеза программ осуществляется на основе использования вышеописанного шагового процесса, в котором шаги представляют собой высказывания формальной системы X . Целесообразно высказывания шагов определять в виде вы-сказывательной схемы, параметры которой конкретизируются при реализации. Отметим некоторые особенности использования именных множеств объектов с приписанными свойствами.
1. Равенство ()(1 = Xz) для (b,Xz)GG понимается как эквивалентность объектов, которая имеет место при равенстве свойств. Во множестве свойств может быть свойство "иметь имя" со значением. Приравнивание объектов осуществляется на основе приравнивания значений свойств, в том числе и значений свойства "иметь имя".
2. В общем случае имя объекта отличается от имени, которое определяется через свойство, например имена именованного множества X&G могут быть порядковыми числами, а значение именного свойства может указывать на смысловое имя объекта.
3. В именованном множестве одному объекту может быть соотнесено несколько имен.
В дальнейшем используется следующая схема доказательства. Пусть теорема имеет вид К.(х)ІС(у) [А(х,у) = в(х,у)] , где 3 - квантор. Проведем подстановку конкретных значений предметных переменных и одно из полученных высказываний обозначим через Л , а другое - через & . Дальнейшее доказательство проводится в терминах исчисления высказываний как доказательство общезначимости формулы Л 3 . Для перехода от доказуемости формулы (Д в) к доказуемости формулы вида К(у)К(у)[А(х,у)= = & »у) 1 используются аксиомы исчисления предикатов, а также правила вывода для V - и 3 - введения. Если доказано (Я $ & ) для каких-либо конкретных значений Х= $t , У-$2 » то по правилу 3 - введения - М($и$і) Mfrffe) 3у 3у [Л(х,у) =з &(х,у)] , где h - знак выводимости. Чтобы применить правило V - введения, необходимо проверить, чтобы допущения во вспомогательных и результирующих выводах были одинаковыми относительно той переменной, для которой применяется \/ -Введение. В ЭТОМ Случае, ПОСТРОИВ ВЫВОД формулы (yfl-ї S) как конечный список Г {8,)1й, &п) формул, не содержащих свободно X , можно перейти от Л(х) =» &С ) к і/у [Л(х) ВС )]
Формальное представление шагов осуществляется в соответствии с шаговым процессом автоматического режима синтеза программ.
I. Поиск в классах задач описывается через поиск имени класса. Совпадение указанного пользователем имени класса в с имеющимся в памяти 3 М указывает на выбор множества имен задач данного класса. Теорема Т I.I: У і (t С ST) VUi4 (l/u і V) Зі fe kL) B\Jn (tnQV) {[Wm ft) A Vr W А Ш = \JnJ] (ітг)} (3,3,I) Для любого класса і с ST ти V существует класс itKL и \frti V такие, что, если іt % обладают свойствами "иметь имя" и значения этих свойств равны ( = irLZ) , то классы толерантны (it і),
Следующий шаг оперирует найденным классом 1-і.. . Имя класса предопределяет любое имя задачи этого класса. Теорема Т 1.2:
Множество СИ описывает схемы решений задач данного класса. Имя класса определяет множество схем задач данного класса. Выбор схемы решения осуществляется по совпадению имени задачи пользователя eST с именем схемы в памяти ОД (heCH), Теорема Т 2.1: W (шт) VifcOfc v) 3h(hecu) (irJhGV) (3e3#3)
Для любой задачи itST и VtiV существует схема АвСА/ и l/rh такие, что, если ifh обладают свойствами "иметь имя" и значения этих свойств равны, то объекты толерант-т ны ({ г А).
Результатом данного шага является найденная схема решения / -#, которая определяет множество реализующих операторов решения СИ К . Формально имеет место теорема Т 2.2: Уу(уинЮ{[УіІЇ)лШу)АЇШ$) ЇЇМ] її- у)} (3.3.4) Формальная запись для отношения предопределения реализуется простым указанием того, что имя схемы соответствует именам функций реализующих операторов. Это относится и к предопределению в (3.3.2). Список реализующих операторов схемы переписывается в список фрагментов функциональной схемы задачи.
Описание блок-схемы диалогового монитора. Пример функционирования монитора в иници ативном диалоге
Блок-схему ДМ можно разделить в соответствии с формализованным заданием на две части (см. рис. 4.2.1): - часть ДМ, работающая в автоматическом варианте выполнения заданных шагов (блоки 1-7); - часть ДМ, работающая при возникновении состояний неопределенности (блоки 8 - II).
Входная информация поступает на вход блока I, который осуществляет выбор режима функционирования и общее управление работой других блоков. Основным режимом ДМ является режим формирования программы пользователя. В этом режиме ДМ организует, если необходимо, инициативный диалог, результатом которого является сформированная программа. Выделяется режим формирования программы как с начала процесса решения задачи, так и при продолжении. Режим продолжения формирования программы реализуется в том случае, если пользователь уже имел сеанс работы и в памяти ДМ зафиксировано конечное прерванное состояние этого сеанса. Таким образом реализуются режимы: 1) режим синтеза программы при отсутствии предыдущих сеансов работы по данной задаче; 2) режим продолжения синтеза программы, который определяет синтез программы при имеющейся в ДМ информации о прерванном сеансе работы по данной задаче; 3) режим окончания работы по синтезу программы. Режим опре деляется ключевым словом: КОНЕЦ, которое пользователь может набрать при ответе на любой запрос; 4) режим окончания работы с последующим продолжением. Режим определяется ключевыми словами КОНЕЦ СЕАНСА, которые пользователь может набрать при ответе на любой запрос.
Общее управление блоком I определяется построением ДМ из процедур, вызов которых осуществляется по анализу текущей информации.
Далее рассматривается работа Д в режиме формирования программы задачи с нулевой исходной информацией в памяти. По исходной информации блок 2 осуществляет поиск класса, если указано имя или признаки класса, в противном случае формируется запрос соответствующих признаков у пользователя с сообщением ему структуры признаков. По получению таких признаков указанная задача заносится в класс и управление передается блоку
Блок 3 осуществляет поиск схемы решения для заданной задачи в указанном классе. Реализация функций поиска информации (блоки I, 2, 3) выполнена через использование процедуры PL , которая осуществляет поиск заданной информации в указанной структуре списка, например в ST , В2 , PS и т.п. Структурирование информации в используемых списках, а также запись необходимой информации осуществляется процедурой S .
В случае отсутствия такой схемы возникает состояние неопределенности. Разрешение неопределенности осуществляется блоком 8 (процедура DIAL ), который в диалоге организует построение схемы решения или функциональной схемы алгоритма задачи. Последовательность запросов этого блока и ответов пользователя реализует процесс формирования алгоритма задачи. Структура блока выполнена с учетом возможной настройки его на реализацию принципа структурированного программирования. В этом случае последовательность запросов и ответов на них определяет структуру алгоритма задачи в соответствии с методом структурированного программирования. Алгоритм блока 7 выполнен в соответствии с общими принципами инициативного диалога с использованием массива меток. При каждом ответе пользователя выполняется только необходимая часть алгоритма.
Диалог требует от пользователя только знаний специфики задачи. Пользователь видит результаты своей работы на различных этапах, кроме того, ему сообщается дополнительная информация, которая может быть использована при решении задачи, например сообщаются схемы некоторых имеющихся в памяти подзадач, операторы и т.п.
Дополнительная информация сообщается пользователю вместе с кратким описанием смысла использования, например для оператора кратко описывается его назначение: нахождение корней алгебраического уравнения, решение дифференциальных уравнений по методу рунге-К тта и т.п. Наряду со смысловым определением указывается и имя оператора с параметрами. Смысловое объяснение параметров операторов (процедур) осуществляется при согласовании формальных параметров с фактическими.
