автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Система порождения программ

Л. </О, /3?

м

"АКАДЕМИЯ НАУК СССР ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ

На правах рукописи

ИЛЬИН Владимир Дмитриевич

УДК 681.3.06

СИСТШЛ ПОгОЛДЕШЯ ПРОГР/ММ

Специальности: 05.13.17 - Теоретические основы информатики

0S.i3.il - Математическое и программное

обеспечение вычислительных малин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва - 1909

Работа выполнена в Институте проблем информатики АН СССР

Официальные оппоненты:

член-корреспондент АН СССР,

доктор физико-математических наук, профессор

ИВАННИКОВ В.П.;

доктор физико-математических наук КАЛИНИЧЕНКО Л.А.;

доктор технических наук, профессор КУЗИН К.С.

Ведущее предприятие:

на заседании Специализированного совета Д 003.56.01 при Институте проблем информатики*АН СССР по адресу: 117900, ГСП-1, г. Москва,. В-334, ул. Вавилова, 30/6.

С диссертацией, представленной в виде монографии "Система порождения программ" (М.: Наука, 1989, 264с.), можно 9знакомиться в библиотеке Института проблем информатики АН СССР. / ■ ' Ч

Автореферат разослан __^^__1990 т.

Институт кибернетики АН ЭССР

Защита состоится .

1990 г. а

.час__мин

о

Ученый секретарь Специализированного совета кандидат технических наук

С. Н. ГРИНЧЕНКО

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Если уровень информатизации определяет интеллектуальную продуктивность общества, то уровень автоматизации разработки программных средств - реализуемость и интенсивность самого процесса информатизации. В "Комплексной программе научно-технического прогресса стран-членов СЭВ до 2000 года" одно из ключевых мест занимает автоматизация разработки программного обеспечения.

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

Порождение целевых программных систем в пространствах за-' дачных конструктивных объектов (И-порождение) - это новое направление в автоматизации разработки программного обеспечения, основанное на конструктивном представлении знаний о мире программируемых задач.

Состояние ■ вопроса. Повышение продуктивности разработки программных систем не менее, чем.б (5-10) раз по сравнению с традиционными методами определяет все возрастающий интерес к генераторам программ. Именно поэтому проблема автоматизации ях разработки выдвинулась на передний план и стала предметом интенсивного исследования. Ведущие фирмы (IBM, AT&T Bell ;,n bora tor i'os) активна субсидируют исследования, целью которых толяется распространение технологии автоматизированной разработки приложений посредством'генераторов и на системное программное. обеспечение (например, семейство генераторов Stage -разработка AT&T Bell Laboratories; Cross System Product -разработка IBM).

В нашей стране успешно ведутся работы в области автомата-

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

Для успешного развития работ в области автоматизации конструирования программного обеспечения, к которой относится данная диссертационная работа, необходимо бь;ло решить пробле-• ' му конструктивного представления и обработки знаний о мире программируемых задач (вне зависимости от их природы). Первые результаты были получены при разработке семейства ИГЕН-гене-раторов. Эти результаты были развиты и апробированы при конструировании системы ГЕНПАК, к;, горая существует как программный продукт.

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

Для достижения поставленной целй^были решены следующие задачи :

-> - разработка представления знаний о мире программируемых задач и механизма вывода, рассчитанного на конструиррвание целевых программных сисГЬм;

- создание теории порождения целевых программных систем на основе знаний о м;фе программируемых задач;

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

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

Методы исследования. При выполнении работы использовался аппарат теорий множеств, графов и моделей.

Научная новизна и значимость. Работа представляет собой новое направление в автоматизации разработки программного обеспечения: порождение целевых программных систем в пространствах задачных конструктивных объектов. Созданная методология применяется для автоматизированного конструирования систем порождения генераторов программ.

При решении проблемы автоматизированного конструирования программных систем впервые предложены:

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

- теория порождения целевых программных систем в пространствах задачных конструктивных объектов;

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

- архитектура целевых программных систем, конструируемых в пространствах задачных конструктивных объектов;

- табс-ориентированное воплощение инфов в виде Т-инфов, рассчитанное на базовую структуру данных - табс (трехмерная таблица с типизированными клетками);

- принципы построения табс-ориентированныу языков специфицирования и программирования;

- реализация в виде программного продукта системы порождения (ГЕНПАК) , ориентированной на автоматизированное конструирование генераторов приложений для актуальных предметных об--ластей (учет и планирование).

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

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

Основные положения, которые выносятся на защиту:

представление знаний о мире программируемых задач в пространствах задачных конструктивных объектов и механизм вывода, ориентированный на построение задачных конструкций;

- теория порождения целевых программных систем в простран-стшх задачных конструктивных объектов;

- архитектура целевых программных систем и их представле-

- 4 -

ние в операционной среде в виде иифов;

- табс-реализация инфов как воплощение позиционного принципа работы со структурами данных и процедурами;

- принципы построения табс-ориентированных языков специфицирования и программирования;

- методология порождения целевых систем как основа для создания средств автоматизированного конструирования генераторов программ массового применения.

Реа.шзаиия и внедрение результатов работы. В процессе формирования (1972-ВОг.) предложенного подхода к конструированию программных систем были разработаны и переданы в промышленную эксплуатацию в объединенном диспетчерском управлении южными энергосистемами (ОДУ ЮГА, г.Киев): математическое и программное обеспечение для решения комплекса задач оперативного управления режимами энергосистем и их объединения (УО-75) и долгосрочного планирования мексистемных потоков электроэнергии (МО ПП1-Юг).

Искомый подход был в первом приближении сформирован (1982-ВЗг.) при разработке диалоговой программной системы для обработки результатов эксперимента (ДИЭКС), которая вошла в состав базового программного обеспечения информационно-вычислительного комплекса КВК-20 и управлявшего вычислительного ' комплекса СМП-1300.1701Р

Основным результатом выполнения НИР по теме ИГЕН (1984-В7г.) в соответствии с "Комплексной программой научно-технического прогресса стран-членов СЭВ до 2000 г." (п.1.1.9 и 1.1.4.) стало завершение формирования искомого подхода к конструированию программных систем: были созданы методология порождения целевых программных систем и образец системы порождения из семейства ИГЕН-генераторов, воплощающий осноьлые теоретические посылки. Образцы компонент ИГЕН-гене-раторов и версия системы ДНЭКС-2.0 были переданы ряду организаций и предприятий для опытной эксплуатации и анализа продуктивности: производственному объединению "Сода" Минхимпрома СССР, /¡ИМТУ, Московскому областному филиалу НИИ АСУ при Госплане РСФСР, Московскому институту повышения квалификации руководящих работников и спепиалистов Минхимпрома СССР, Институту геологии и разработки горячих ископаемых (Волгоградское

о

отделение). Анализ результатов подтвердил перспективность выбранного подхода.

В 19в0г. ОКР по теме ГЕНПАК ("Программные средства генерации пакетов программ с заданными функциональными характеристиками"), выполненная в соответствии с Постановлением ЦК КПСС И СМ СССР от 23.01.06., была завершена созданием системы ГЕНПАК, воплощающей методологию И-порождения. Система ГЕНПАК сдана в фонд алгоритмов и программ и передана МПТЦ СНПО Алгоритм.

Практическая ценность работы состоит в том, что на основании полученных теоретических результатов созданы:

- научно-обоснованная методология автоматизированного конструирования программных средств массового применения, обеспечивающая значительное повышение продуктивности разработки; ■

■ - табс-ориентированные языки спецификации и программирования;

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

- ряд программных комплексов и систем для решения задач из различных предметных областей: управление режимами энергосистем (УО-75 и МО ПП1-Юг), автоматизация научных исследований-(ДИЭКС), учет и планирование (ГЕНПАК).

Предложенный подход к решению проблемы автоматизированного сонструирования программных систем развивается и конкретизируется в кандидатских диссертациях, подготавливаемых под научным руководством автора в аспирантуре ИПИАН и МИРЗА.

Апробация работы. Основные результаты диссертационной ра-5оты докладывались и обсуждались на международных, всесоюзных,- межреспубликанских и региональных конференциях, совеща-1иях и семинарах: Международное совещание экспертов Комплекс -юго научного проекта N0 "Технология программного обеспечения ЭВМ новых поколений" (п.1.1.9. Комплексной программы науч-ю-технического прогресса стран СЗВ до 2000г.), 1986, 1987, ЭВйг.г.; Всесоюзная научно-техническая конференция "Проблемы разработки и внедрения математического, программного и инфор-кшионнОго обеспечения АСУ технологическими процессами". Моста, 19В2г.; Всесоюзный научно-технический семинар "Программ-

ные сродства СМ ЭВМ семейства СМ-4 и микро-ЭВМ СМ-1800", Москва, 1983г.; Шестая межреспубликанская школа-семинар "Интерактивные системы", Батуми, 1984г.; IV Всесоюзная конференция "Диалог ТЕЛОВЕК-ЭВМ",%иев, 1905г.; II Всесоюзная конференция по актуальным проблемам информатики и вычислительной техники, Ереван, 1987г.; научный семинар ИК АН ЭССР под руководством академика АН ЭССР Э.Х.Тыугу ,0Таллин. 198йг.; Всесоюзная кон-ферсн"ия "Актуальные проблемы развития и внедрения новой информационной технологии", Таллин, 1989г.

Публикации. По теме диссертации опубликовано 35 печатных работ. 20 ословн'*х работ включены в список, приведенный в конц- автореферата. Результаты диссертации отражены в монографии.. о

Структура и объем диссертации. Диссертация представлена з вице монографии: В.Д. Ильин "Система порождения программ". М.: Наука, 1989, 204с. Монография состоит из предисловия, раздела "Форма записи определений и обозначения", введенияо девяти глав, объединенных в три части, ю списка литературы из 45 нЁйменований. Объем монографии 264 страницы (16,5 п.л.), рисунки и таб^цы - 47 страниц, список литературы - 3 страницы.

'(РАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Часть 1 (г.?. 1-4) содержит результаты анализа современных подходов к решению проблемы автоматизации разработки программного обеспечения и обоснование предложенного подхода к решению проблемы. Часть 2 (гл.5-7) содержит изложение методологии И-порождения целевых программных систем как процесса их автоматизированного конструирования. Часть 3 (гл.0-9) посвящена описанию применения методологии И-порождения и проблемам ее рагтчтш. 0

Обозначения. 9ыбор обозначений сделан, исходе из следующих оообрсжт.Д:

1) ориентация на специалистов в области разработки программного Обеспечения;

2) ^рцинаковос :ь в языках спецификаиии системп порождения л в тюяе;.лющем методологию порождения тексте;

3) кл левые слова - в англоязычном изображении, как приня-

о

то в языках специфицирования и программирования;

Л) все символы в обозначениях должны быть рассчитаны на распространенные типы клавиатур и печатающих устройств.

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

а: с1ет(Л) - означает "а является элементом множества А";

Л: s с: t (а) - "Л является множеством, содержащим элемент а";

Л < sct(B) (или Л < В, когда ясно, что Л и В рассматриваются как множества) - "Л является подмножеством В";

D = sct(B) (или короче: 1) = В, когда по контексту ясно,

что В и D рассматриваются как множества) - "множества I) и В

совпадают"; п

w о

С <= set(B) (или С <= В) - "С является подмножеством В или

совпадает с ним";

В > sel(A) (В > Л) содержит Л";

Л >= set(K) (Л >= Е) - "Л содержит Е "ли совпадает с Е";

Л - В - пересечение множеств А и В (здесь несколько отличается от традиционного только симвсл, обозначающий пересечение^) ;

А \ В - разность множеств Д и В (небольшое Отличие также только в изображении символа разности);

Л * В - декартово произведение множеств Л и В (изменен только^снмвол умножения);

R <= set(A*U) - бинарное отйЬыение, заданное н"\ множествах А и В; 0

О - обозначает пустое множество или нуль (в контексте разница обнаруживается без труда);

§ - обозначает "не равно";

Строчная запись индексов и помечающих символов. Все индусы (в -^м числе индексированные) и помечающие символы ^звездочка, нолик и др.) записываются в строчку внутри квадратных скобок, следующих сразу за индексируемой (или/и помеченной) переменной. Индексы, 01у)еделяющие элемент массива, отделяются запятыми, индексированные индексы - косой чертой "/". Верхний индекс от нижнего отделяется точкой с запятой ";". Если в описании индекса точка с запятой не встречается, го индекс считается нижним.

- о -

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

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

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

Делается вывод, что при реиении проблемы построения языковой среды для решения задач автоматизированной разработки программного обеспечения необходимо стремиться к создании многоязыковой среды. Вводятся понятия ЧТО- и КАК-языков: первые для описания постановок задач, вторые - для описания способов их решения. Определяется зависимость уровня языка от его свойств. Приведены характеристика языков, ориентированных на задачи автоматизации разработки программного обеспечения.

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

Глава < посвящена проблеме повторного использования программ в системах автоматизации разработки программного обеспечения. Анализируются подходы, реализующие идеи фугкцио:.ально-iO программирования и генерации частичных систем.

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

В глазе б изложены теоретические основы И-порождения циле вых программных.систем. Введены и формально определены понятия: •■■ заданный конструктивный объект, простая задача, составная задача, заданная сеть, разрешающая структура н§ заданной сёти, пространство р-объектов. Сформулированы теоремы сущест вования разрешающих гт'?1"тур на .заданных сетях и даны конструктивные . доказательс?. Приведено формальное описание И-по-рочдення как процесса индуктивного построения множества заданных конструктивных -объектов.

^Заданный 'кошпдашшшй объект Задача - это

пара (глет, rcL), где теш-'- множество понятий, не котором задано разбиение: mem = inp U out; inp - ci Л = &; reí - отношение. на mcm (rcl< inp'oul). Будем также называть множество mem паОятыо задачи: inp входом (значения которого предполагается задавать) и out выходом задачи (значения которого предполагается искать).

Определены следующие представления задачи р:

- í-представление p[f] - это пара (теп, íormul), где íormul - отношение на mem.(íormul < inp*out), называемое формулировкой (условием) задачи, являющейся описанием отношения без указания способа его реализации; _

- ПГ представление p[m] - (mem, set(íormul|теth)) ГДР set(íormul Imetli) - непустое множество методов решения зада1*;! р; при этом для каждого melh: clcm(set( íormul |mcth)') выполняется íormul = mcíh (чт<9 означает семантическую эквивалентность отношений íormul и moth; то есть, каждый метод из множества определяет то же подмнолестпо экземпляров горы (inp, out),, что и формулирс пса); с

\

о

- ¡o -

- t - продет;, аление pfl] - (menri, set(rneth I tempi)) , где mem -память задачи, set(mcth|tempi) - непустое множество заготовок tempi программ; каждой заготовке программы, представляющей собой образец, поставлено в соответствие некоторое непустое множество программ (программа сЙ1теэируется в результате подстановки в переменную часть заготовки данных об условиях применения); мнозество заготовок°поставлено в соответствие некоторому методу из set( ioriTiu 1 |mcth); заготовка tempi рассчитана ' на фиксированные язык и операционную Среду (при этом lorir.ul = meth = temí справедливо для любой заготовки из объединения множеств заготовок);

- р-преставление p|pl - (теш, set (tempi |progr.))t где теш -память задачи, set(tempi iprogr) - непустое множество программ Oprogr; каждое множество программ поставлено в соответствие Никоторой заготовке программы из sct(meth|tempi) (при этом formul = meth - temp] = ргодг справедливо для любой программы из объединения мнокеств программ). °

С фочки зрения разработчика способа решения интерпретация задачи заключается в отыскании представления reí, соответствующего заданном требованиям. С ?í?j;ai зрения пользователя - в соотнесении экземпляру i»p экземпляра out посредством rol с известным-представлением.о

Заданный конструктивный объшег (р-объект) является представлением задачи в процессе И-порождения. Р-объект наделен структурой в виде конечного дерева, корнем которого является вервйна, помеченная формулировкой, а листьями - вершины, помеченные программами. Промежуточные (на пути от формулировки к программе) КАК-представления задачи (методы и заготбЪси программ) соответствуют логике разработки. 1 Переход (формулировка -> метод - • заготовка программы -> программа) представляет собой процесс р-конкретизации. Кроме того, р-объект 0наделен характеристиками, определяющими его связь с другими р-объектами. Он может быть прообразом некоторого непустого мноЕества р-объектов (и.-и образом некоторого прообразу или быть одновременно и образом какого-то одного Р-Объекта. и прообразом некоторого множества других р-объектов) .° Существует способ образования родовой связи между p-объек-лми: р-специализаг>'я как перех д к задаче, частной по относ:ен!!% к 1'г^од' эй. Ммпю получать р-объекты путем замени

понятийной оболочки. Этот процесс называется р-замегой. Наконец, связь р-объекта с другими р-объектами при ¡..образовании конструкций реализуется посредством связи по nav itii в лроцес-се р-конструировапия.

Слазь да памяти рлМыдшш^ заданная айлаель и заданные знания. Задачи Л и В связаны мезду собой, если пересечение по памяти непусто, т.е. (Л|шсш) ~ (B|mcm) // О.о

«Задачная область G - это пара, включающая множество S задач и семейство R отношений вязи по памяти, заданных на S. Память S|mem заданной области - это объединение памяти всех задач, входящих в S.o

Задачные знания - ото пара (L, С) . Здесь I, - язык, интерпретируемый на задачной области G.o

Точкой зрения называется влстор view = (who, purp, stage), где who - корреспондент, purp - 1&ль, stage - стадга.о

Переход qi JLi к рлршшзашенив. Именно этот процесс расс-' матривается здесь как процесс разработки программы. Р-объект как участник процесса (3-порождения рассматривается с четырем точек зрения (в зависимости от стадии):

1) при реализации процесса р-конкретизации. где р-объект предстает в четырех ипостасях: f-представление (сформулированная задача), m-представление (множество методов решения задачи), t-представление (множество зрт-отопок программ для. каждого метода решения) и р-представление (множество программ, фоторые могут быть получены из каждой заготовки);

2) в процессе р-специализации, где р-объект проявляет себя либо как прообраз некоторого непустого 'множества других р-объсктов, либо как образ некоторого р^бъекта, либо и как прообраз, и как образ (одновременно);

3) при р-замене;

<1) при реализации р-конструирования.

Определены правила получения новых объектов путем р-специ-ализащЙ, р-замены, p-конструиропания и р-конкретизациЙ.,

Каждый из р-объектов наделен характеристиками, присущими конструктивном^ объекту. Поскольку И-порокденье реализуется с отнесением р-объектово к различным пространствам (по родовой принадлежности: к пространству р-объектов некоторого поколения; по применению в И-порождении: к абстрактным, прикладным и пользовательским пространствам), в описании указывается

о .

- 12 -

принадлежность к пространству по родовой принадлежности и к пространству по применению.

Описание р-объекта.0Описание р-объекта,. обладая необходимой общностью отражает специфику пространства. Па каждом; пространстве задано разбиение ®: классы. Поэтому признак принадлежности к классу присутствует в описании р-объекта. Структурная сложность р-объектов различна, что учитывается при работе с ними. Поэтому в описании р-объекта указана его структурная сложность. Описание каждого р-объекта включает описание точки зрения (кто, с какой целью, на какой стадии процесса порождения работает с р-объектом).

Представление р объекта определяется формой из двух составляющих одна ориентирована на человека (в соответствии с°

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

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

Будем также говорить об атомарном р-объекте как о простой задаче. Простая задача (с точки зрения построителя заданных конструкций в фиксированном пространстве) не имеет внутренней структуры (т.е. не под-ежит декомпозиции).;

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

1 вые объекты вместе с атомарными могут быть применены при р-конструировании.

функции свяаи^гш памятки Отношения связи по памяти между р-объектами (далее: задачами) определяются тремЯ типами функций, каждая из которых является функцией двух аргументов и позволит паре р-сбъектов поставить в соответствие некоторый * |ий р-^бъект, образованный из этой пары.

За®1ча и связана с задачей Ь по памяти, если хотя бы один элемент», принадлежащий - памяти задачи и, одновременно принад-> ложи, и 1цмьт;1 ч*Нг{а>-ч. Ь:

- 13 . -

(a|mem) ~ (b|mcm) = inter; inter # O.K>

Тип связи по памяти зависит от содержимого inter: составлена ли связь из элементов выхода одной и входа другой задачи; или из элементов входов задач; или же связь получена путем комбинации предыдущих списобов.

Пусть S и П - множества р-объентоп. Пусть дал^е D <= S*S, то с есть в S*S выделено подмножество. Если каждой паре (sjif, sf j]) элементов из I) ставится в colгвстстш.е определенный элемент из Н, то будем говорить, что задана функция связи по памяти:

h = conn(s[i ], iff j]).

При этом I) будем называть областью определения, фукнкции conn и Обозначать Dfeonn). Множество R - {h: elem(H); h = conn(s[i], sfj]); s[ i ] : e!cm(Df conn J) , s[j]; el em(D[ conn j) } будем называть областью значений функции conn, о

Функцией conn [ х | (s [ i ], s[j 1) свяьл по памяти типа "выход-вход" называется функция, область D[conn[x]] определения которой состоит из пар (s|i], s|j]).

Для них выполняется условие:

0 interfx] = (s[i ] |out) - (sfjjlinp) ,f О.

При"этом каждый элемент из области Rfxf = {hfx]: nlem(H[x]; hf х ] = connfx](s[i |, s [ j ]) ; sfi] e Lcm(„[ conn'f x ]) , sfj]: clern(i)[connf x ])} значений функции имеет память:

Pif х ] | mem) = ((sf i J [tnem) U (s|j]|mcm)) \ interfx]. Вход hfxJIinp полученного р-ос5ъекта представляет собой разность объединения входоь объектов i f H0.sf j | и пересечения interfx], а выход hfх 11out - разность объединения выходов и interfx].<>

Функцией connf у](sf i], sfjf) связи по памяти типа "вход-вход" называется функция связи по памяти, область Df connf] определения которой состоит из пар (sfi]. Для этих пар выполняется условие: •

intcrfy] = (sfiffinp) - (sfi'flin?) // 0. 0

При этом каждый элемент из области R[y] = {hfy]:elem(H[y]); hfy] .= connfyl(sf i ], sf9 I); s[i]- elcm(D| connf у ])', i:[j]: elcm(l)[ connf у |)} значений функции имеет память-.

4h[y]imem) = (s|.i]|mcri) U (s[j]|mem). При этом вход hfyj|inp является объединением входоп, а выход - объединением выходов объектов sfi] и sfjj.o

- ' с

- и -

Функцией coi',n[ |(н[ i ], кf] ]) связи по памяти типа "выход-вход и вход-вход" называется функция связи по памяти, область D( conn| ] ] определения которой состоит из пар (s[L], s[j]). Для них одновременно выполнятся условия: (s[i?|out) - ы j]|inp) # О и (slillinp) - (glillir.p) # 0 (intci'[7.] является объединением этих непустых пересечений). П. л этом каждый элемент из о^'асти К| ■/. ] - {h[z ]: clcm(II| •/. j; h[z] = сошд|/, |(s[ i], s| j ]); i ) : e I cm(D[ conn| /.)) , ■•.s[j]: elcm(D[conn[и])} значений функции имеет память:

(h[z]|mcm) = ((s|i]|mem) U (s'l j ) |гпсш)) \

((sii ]|ouL) - (s[jJlinp)). Вход h[z]plnp полученного р-объекта представляет собой раз-О ■ ность объединения входо. объектов s[ij и s[ j] и пересечения (s [ j ] | он L) - (s|j]|inp) , а выход h| •/.) | ou I - разность объединения выходов и того же пересечения.о

Заданная конструкция. Элементарной, заданной конструкцй, является задачная пара. Из заданных паромояно построить более слож^ю задачную конструкцию, если рассматривать их как элементы, подобное задачам (для .елей конструирования). Любая конструкция, в свою очередь, мояет быть использована как составляющая еще более сложной конструкции. °

Заданная Млас^ъ и составная задана*. Прежде чем ввести определение составной задачи, являющейся структурой, заданной на множестве других задач (простых и/или составных), рассмотрим подробнее введенное понятие задачная область.

Задачная Ооласть G задана, если определена п"ра (S, К), где S < 1> - непустое подмножество задач. • заданное на i';cji = {г: elcm(li); г <= S*S} - семейство отношений связи по памяти. При этом в S (где не менее двух элементов) не существует ни одного элемента, юторый но был бы спялан по памяти хотя бы с одгмм элементом из S.o 0

Памятью С|тД заданной области С будем называть объединение памяти все* элементов множества S:

G|msTi = Us | теш

(ф'.есь I £> ■ объединение по к). На пг Чяти заданной области за; то разбиение:

С>|(псп = >; i" и сопри t I1 (м ) ;

О

giv, сотриt и ог попарно не пересекаются. Здесь <5?- - объединение всех пересечений типа "Би1ход-:,ход", giv - разгость объединения входов всех элементов из 3 и ог:

Glgiv = (Us|inp) \ (G|or). сотриl - разность объединения выходов всех элементов из S и ог :

G|сотриI = (Uslqut) \ (G|or).<> В отличие от памяти задачи, состоящей из входа и выхода, память заданной области содержит подмножеств^ ог элементов памяти, каждый из которых может быть или задан (как входной), или вычислен (как внходной). Будем называть такие элементы памяти обратимыми, а ог,- подмножеством обратимых элементов. Подмножество giv будем называть подмножеством задаваемых, а подмножество сотриt - подмножеством вычисляемых элементов.

Заданная область G является моделью, на которой интерпретируются предложения.Интерпретация заключается в постановке в соответчике. некоторому подмножеству (или парс подмножеств) памяти G|mcm некоторой подобласти. Процесс интерпретации I, на G будем называть 'ллкже поиском представимых за^дч.

Составная задана comp - это подобласть заданной области G (comp <= С), которая содержит не менее двух элементов из S и . на oníf íftí- complmem которой задано разбиение:

y . compl(mcm = inp U out; inp ~ out = 0),

определяющее вход comp|inp и вйод comp|out составной задачи.о о

Чтобы создавать конструкции из р- объектов, нужно определить связь между объектами, типы связей, типы ксструкций.

В И-порождении рассматривается три типа р-объектов: рос-тая задача, составная задана i заданная сеть. Два последних явл: лтцу конструкциями из р-объектов. О

Составной задаче поставлен в соответствие ориентированный граф, вершинами которого являются отношения i .1 и элементы t памяти mcm задан. Кажд^т вершина помечена: вершины reí - именами задан, остальные - именами элементов памяти. Множество ребер состоит из двух подмножеств, ребра одногс подмножества соединяют вершины, помеченные именами задач, с вершит,ами элементами памяти этих задач; ребра другого подмножества соединяют ьлеменгы памяти разных задач Между собой.

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

Заданные Lb^-С^'и N-сет'и и 'лцелатазлеииа'1 заданных amimlL. Заданная сеть являете^ представлением заданной области, рассчитанным на реализацию процесса р-конструирования..

Дано определение заданных се^ей трех типов: U-сети, где все узлы - атомарные р-объекты (простые задачи); С-оети, где хотя бы один узе' является составной задачей и нет узлов, •представляющих собой заданную область, и, наконец, N-сети, где не менее одного узла представлено заданной областью (остальные могут быть простыми и составными задачами).

Граф, в-котором вершина.reI (reí|ver)• :с именем паспорта задачи, соответствующая отношению reí, заданному i i ее памяти mem, соединена ребрами 'с .mem-вершинами (mem| ver.) ...каждая из' э которых соответствует элементу памяти, будем называть задач-, ним узле i (p-узлом) и обозначать p-nodc.<>

Pecípo (р|еОд) задачного узла ;- это пара вершин (mem|ver, rel|ver) ИЛИ (reí [ver, mem(ver). . О

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

Интерпретация задачного узла заключается в соотнесении экземплярам входа экземпляров вых^уа в соотЁетствии с заданным отношением re].

Объединение заданных узлов, попарные пересечения которых по памяти пусты, называется зада;ным базисом и обозначается p-bagis. О

Пара ист-вершин.'относящихся к разним заданным узлам, называете i дугой межзадачной связи и обозначается р-агс.о О Множес.вп всех дуг межзадачной связи, поставленное в со, ответствие паре узлов из задачного базиса, называется межзадачной связью.<>

"'ежзадачпая связь существует, если множество дю1 межзадачной связи непуст^, в противном случае - она отсутствует.

Связг.мй граф. содержащий задачн>'й базис p-basis, все элементы которого яв-чются простыми задачами, и непустое множеству set[pCferc] дуг межзадачной связи, называется U-сетью и огэзнэдается U-n^tw:

l)-netw - (р-Ьа is, sct[p-arc ,).<>

Объединение памяти задачуых узлов, составляю:;;!« базис, называется памятью и-сете и обозначается и-пе1м/|те!Р.<>

На U-nctw|шeш задано разбиение. Подмножеством задаваемых элементов памяти называется подмножество входных пет-вер-шин,• пересечение которого с объединением госго-верио, являющихся первыми элементами пар, определяющих дуги ие :задачной связи, пусто. Подмножеством Сотри! вычисляемых элементов памяти называется подмножество выходных шсш-гершин, пересечение которого с объединением шет-вершин (вторых элементов пар, определяющих дуги межзадачной связи) ,:усто. Подмножеством Ог обратимых элементов памяти называется разность (и-пс1л\'|тет) \ (С1у и Сотри!.). Элементы Ог - это шет-веришны, относящиеся к входам задач. Они стоят на втором месте в парах, определяющих дуги межзадачной связи, где на первом месте - теш-вертины, относящиеся к выхецам. °

Интерпретация и-сети заключается: либо в постановке в соответствие подмножеству (или паре подмножеств) ее памяти такой и-подсети, память которой находилась бы в поданном отношении к введенному подмножеству (или их паре); либо в постановке в соответствие заданным значениям тггп-вершин некоторого подмножества памяти (пересечение которого с Сотри!, пусто) значений тст-вершин другого подмножества памяти (пересечение которого с С1у пусто). При этом второй вариант интерпретации о- это расширение первого: сначала ищется и-подсеть, а затем (если талая подсеть существует) - на ее оснсче ищутся з:<аче- ^ ния интересующих нас тет-вершин.

Для некоторой пары задачных узлов задано условие связи (по памяти), если определено непустое множество дуг межзадачной связи. Проверка условия - надстройка этих дуг.о

Семейство условий связи по памяти фиксирует на э-дачном базисе и-сеть.

Граф, содержащий заданный базис (где хотя Ом один узел является составной задачей и нет узлов, представля; дих собой задачную область) и непустое множество дуг межзадачне1 связи, называется С-сетьп и обозначается С-г.ег«.<>

Граф, содержащий заданный базис (г^е хотя бы один уз л является, задачкой ^¿астыо) и непустое множество дуг' межзадачной связи, называется Ы-сетью и обозначается М-пс1^.<>

Память С сети С-.1е1»|те,.1 и память Ы-сет». опре-'

- 1В -

деляю~ся а илогично памяти и-сети (как объединение памяти задачных узлов, составляющих базис). О Интерпретация С- и Ы-сати аналогична интерпретации и-сети. А'-сети в представлении заданных знаний. Существование в заданной сети одного или нескольких yзлog, являющихся заданными областями, имеет принципиальное значение для представления заданных знаний. Конкретным воплощением заданной области может быть сеть любого типа (и-. С- или М-сеть).

Тот факт, что Ы-сеть может замещать задачный узел, открывает логически неограничен!, ле возможности для усложнения заданной области. Она может быть представлена, в частности, посредством Ы-сети, базис которой содержит только узлы, представленный? 14-сетями.

Колсхрулр.ашние Ш заданной сети. Рассматривается механизм конструирования на заданной сети'. Искомая конструкция задается путем описания ее памяти (и иногда ограничений на ч1"ло заданных узлов). Затем описание памяти интерпретируется на заданной сети, которая служит представлением заданной области. Средства интерпретации запросов - это механизм конструирования на заданной сети.

Задача I разрешима на задачной сети ис1-ч тогда и только тогд,а. когда вход 1Цпр задачи содержится в подмножестве (псIV*|СлV и Ог), а выход 1|ои1 - в подмножестве (пс^уу ICompi.it и Ог) памяти задачной сети.о

Разрешающей структурой t-so.lv на сети по поставленной в соответствие некоторой задаче I, называется подсеть с минимальным числом задачных узлов, на которой задача I разрешима.

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

° Теорема существования раарашюиеЯ структуры хина Т- я о1 у|х]. Для заданного на памяти Ч-поЫ|тст задачной сети подмножества х тот-элементов тогда найдется разрешающая структура

1-301у[х | |¡пр <= х|о1и = Мах

о

(вход которой определен подмножеством х, а выход является непустым подмножеством Мах пьВияти сети, включающим максимальное число теш-элементов, которые могут быть определены при заданном х), Йогда х - СотриI = О (СотриI < 1-пиы|тст) и найдется хотя бы один заданный узел с разрешимой задачей.

Хедреш существо хшшя разрешающей структуры хила Ч'-но1у| у ]. Для заданного подмножества у теш-элементов памя.и заданной сети тогда найдется разрешающая структура

!. - ко 1V ( у ] | 1пр = М;п <= С|у{ои1 => у с минимальным числом заданных узлов, выход которой содержит у, а вход - это тот-элементы из С1У, когда у - =0.

Теорема сушйстншзаиия разрешающей схруктуры хида Т-^-о I у| •/. |. Для заданных подмножеств хиу(х~у=0) памяти заданной сети тогда Существует разрешающая структура

1-30 I ) | I Гф <= х|снН. '=> у О

с минимальным числом заданных узлов, вход которой определен посредством х, а выход - посредством у, когда найдется подсеть С, множество узлов которой включает хотя бы один заданный узел с разрешимой задачей, а объединение выходов заданных /злов подсети С содержит подмножество у (или совпадает с ним) О

Мир программируемых задач* Объединение множеств В базовых объектов и Т порожденных объектов обозначается чнрез Г' и называется множеством р-объектов. Совокупность пространств, построенных на подмножествах множества Р называется миром р-объектов (или миром задач).

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

Пространство содержит объекты о; ного поколения и называется пространством ¡-го поколения (5-1,2, ...). Деление объектов по принад -еж"ости к поколению выполнено с .очки зрени;; разраббтчиков мира задач, инте; ;сующихся ро;;ошмм "нязями между объектами.

Существует также неформальное деление задачного мира на пространства с -очки зрения тех, кто пользуется этим мирс^ для порождения программных систем. С этой точки зрения все задачные объекты рассматриваются как принадлежащие пространствам -грех типов: абстрактным, прикладным и пользовательским. Абстрактные пространства содержат объекте», -близкие по методам, прикладные - но областям применения и пользовательские -по принадлежности конкретному пользователю, работающему с этими объектами. Пространства каждого типа 'могу- содержать объект" разных поколений.

Илщкшшнщг как индуктивное пехацюашш толвства кшатл руипшиьк DílieiCLLi^ И-порождение I-gen, понимаемое как построение некоторого множества 'Г конструктивных объектов (t-ойъ-ектов, обозначаемых через t) на основе множества В базовых конструктивных объектов (Ь-объектов, обозначаемых через Ь) по правилам R пг строения ct-объектов из Ъ-объектов и ранее построенных t-объектов, - это четверка, включающая язык L описания объектов и конструкций из объектов, непустое множество В базовых объектов, порождаемое множество 'Г (В ~ 'Г = 0; до начала провеса порождения Т = 0) и.множество R правил построения объектов:

I-gen: (L, В, Т. R).

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

символы eonn[x], corin[y], corm[z] обозначают функции трех типов, применение которых позволяет построить t-объект из пары уже существующих объектов или конструкций из объектов. ■

Символ pre - обозначение прообраза некоторого непустого множества объектов.:Этот символ используется в объявлениях и в функциях. Символ dm - обозначение образа некоторого объекта (рассматриваемого как прообраз). Этот символ употребляется (так же как и символ pre) в объявлениях и функциях.. Символ hull обозначает понятийную оболочку и используется как функциональный символ.

Множество В состоит из базовых объектов (Ь-объектов), являющихся объектами первого поколения. То есть, любой Ь-объек^

о - 21 -

не имеет прообраза, Н£> может иметь образы.

Любому Ь-объекту может быть постагчено в соответствие некоторое непустое множество объектов-образов ' ве1.(1:[1т;р(Ь)]) = :т(Ь) (здесь символ 1т является верхней пометой, а р(Ь) - нижней, обозначающей указатель на объект-прообраз Ь). Каждый объект-образ Ь[1т;р(Ь)] имеет единственный объект-прообраз.

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

Множество Т строится на базисе В по правилам И. В Т °могут существовать конструкции, построенные из объектов, принадлежащих В, конструкции из Ь-объектов и ранее построенных ^объектов, а также конструкции изЧ-обьектов. Некоторые I-объекты могут быть объектами-прообразами, ^для которых определены некоторые непустые множества объектов-образов.

Определено множество I? правил построения ^объектов, в соответствии с которыми работает механизм И-порождения при создании конструкций из Ь-объектов, Ъ- и г-объектов, а. также из

<П-объектов. _

О

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

Це*-^ и нелепая система. Цель - это множество зада-!, разрешимых на задачн^й сети, представляющей задачную область.о.

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

Определить ц^ль - значит задать задачную область.о

Оп,:зделить интерпретацию цели - значит задать язык и механизм интерпр тации.ч^

В зависимости от способности порождать программы все целе-

вые системы делятся на типы.

Начальной (первичной, порождающей системой (Г-системой) называется система, предназначенная для продуцирования с ее помощью других целевых систем и разработанная без использования механизма И-порождения. :>

Вторичной порождающей системой (Б-системой) называется целевая система, предназначенная для порй 'КИЯ с ее помощью других целевых систем и полученная с использованием механизма И-порождения.о

Конечной порожденной системой (Е-системой) называется целевая система, не рассчитанная на порождение других систем и полученная с помощью порождающих систем (или их объединения) . >

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

База Т-Ьаые заданных знаний как воплощение задачных знаний в системе порождения представляет собой с формальной точки зрения пару

Т-Ьаэс = (I. С), где Ь - язык, интерпретируемый на заданной ооласти С.

Ладанная область й задается множеством Б задачных конструктивных объектов и семсйством и отношений на Б:

С -- <3. К> И = (г: г < (3*Э)); г - отношение, задаваемое функциями сопп[*] связи по памяти между задачами.

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

Развитие, понимаемое и как расширение множества Э задачных конструктивных объектов, и как изменение семейства К отношений для каждой базы, осуществляется инженерами заданного знания и системными аналитиками. Добавление новых баз, новых отношений взаимодействуя на множестве задачных баз - этот процесс не ограничен сверху и отражает совершенствование интел-

о - 23 -

лентуальной платформысристемы порождения.

Понятие инфа как модели целевой сшехслы. Будем называть инфом модель целевой системы. рассматриваемой как машина для решения задач.

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

Характеристика поведения гчфа определяется следующими требованиями, предъявляемыми к нему:

- принимать и отправлять сообщения, взаимодействуя с другими инфами и элементами окружения (пользователями: людьми и/или автоматами);

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

- выполнять работу, запрошенную в сообщении, допуская диалог, паузы н отмену;

- оформлять результат выполненной работы для отправки корреспонденту;© о

- образовывать объединения инфов, предназначенные для решения комплексов задач.

!'нф как средство ■ обработки сообщений состоит иЪ следующих о компонент, составляющих конвейер (которые могут работать асинхронно, есля операционная система и аппаратные средства J рассчитаны на поддержку такой работы):

BEFORE.- инициализация, запуск, обучение;

START - прием, буферизация, интерпретация сообщений ;

STEP - шаг в процессе выполнения работы, запрошенной в сообщении;

END - завершение работы с текущим сообщением;

AFTER - завершение работы инфа.

Одновременно с тем, как компонента BEFORE занята, например, обучением пользователя, компонента START может интерпретировать очередное сообщение, a STH11 - выполнять раооту, запрошенную в предыдущем сообщении.

'¡fei /Чя инф-компонента moi зт находиться в одном из состояний, принадлежащих следующему множеству:

State = {st: head. tail, dial, intr, paus, canc, resl, fail, null}, где

- 24 -

head - состояние ГОТОВНОСТИ; tail - работа закончена; . dial - диалог (взаимодействие с ЭЛОКами); intr - взаимодействие с . другими икфами; . • paus - пауза; сапе - отмена;

rcsl - результат получен; Ol

f4.il, - неудача: результат получить не удалось;

null - состояние, требующее вмешательства корреспондента.

Инф как целевая система состоит из:

- анализатора сообщений, -

- построителя разрешающих структур,

- системы управления базами данных,

- интерфейсной компоненты,

- формо-ориентированного процессор? ввода-вывода,

- средств расширения множества разрешимых задач,

- монитора, о

- Функциональной компоненты.

В зависимости от назначения, инфы системы порождения делятся на два класса: инф-конструкторы и инф-конструируемые.

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

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

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

- 25 -

Еопать выполнению как р-специализации, так и р-замены.

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

Составная задача (р-объект) как участник процесса р-конст-руирования является моделью

р: paspfcns] (sct[ens|р], conn) >

При специфицировании р-объекта требуется заполнить его паспорт paspfens].' зафиксировать множество set[cns|p] р- объектов, каждый из которых участвует в образовании специфицируемого объекта, и, наконец, задать отношения conn связи по памяти .

Специфицируемая составная задача будет содержать не менее двух элементов из множества aet[cns|p] и на ее памяти comp|mem будет задано разбиение на inp и out. Ранее порожденные простые и состазные задачи o6jpa3ym- множество set[cns|p] р-объектов.

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

Как отмечалось, существуют три типа задачных сетей: U-, Си N-сети. Для того, чтобы специфицировать U-сеть, требуется описать граф, содержащий заданный базис p-basis, все элементы которого являются простыми задачами, и непустое множество set[p-arc] дуг межзадачной связи. На памяти U-сети задается разбиение, т.е. три' непересекающихся подмножества -£omput и Or, где Giv - подмножество входных mem-верш:^. Co>put - подмножество выходных mem- вершин, a Or - содержит обратимые элементы памяти.

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

Для rel-вершин фиксируется множество допустимых значений

атрибутов паспорта, т.е. задаются условия их активности.

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

Затем фиксируются условия активности заданных узлов как множества состояний. Каждое условие определяется бинарным отношением, представляющим собой подмножество декартова произведения множества состояний гс1-узла на множество состояний памяти этого заданного узла.

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

Специфицирование Ы-сети заключается в задании графа, заданный б£Ъис которого включает хотя бы один узел, являющийся заданной областью, и непустое множество дуг межзадачной связи. На памяти М-сети .задается такое же разбисн;:е, как на па-мят.. и-сети.

Глава 7 содержит изложение подхода к воплощению И-порожде-нп целевых систем, в основу которого положено табс-представление целевых систем. Введено понятие табса, дано табс-представление р-объектов и целевых систем. Введено понятие Т-инфа как инфа с табс-памятью. Определено табс-представление целевых знании при реализации обработки заданных знаний. Правила поведения системы И-порождения при конструировании целевых систем определены как правила табс-навигации.

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

Табс-структура - это некоторое множество табсов и семейство отношений, заданных на нем. Отношения реализуются посредством указателей на табс и вложенных табсов.

Чтобы сделать удобным для человека и доступным для выполнения ^автоматом (в условиях их партнерства) поэтапный процесс т-, 1-й р-представления задачи, в системе И-порожден1£я •¿пользуется табс-структура как форма для размещения поэтапного представления р-объекта.

Итак, воплощением позиционного принципа в представлении заданных знаний при порождении является табс-структура как

©

форма для размещения и ней'описания задачи или задачной сети.

Табс-пр-дставлекие0- это формальное описание объекта с использованием табс-структур, обеспечивающее работу с ним как с конструктивным объектом.

шазых систем. Целевые системы как конкретизированные ип^ы имеют в качестве основной структуры данных табс-структуру. Каждый из трех типов (Г-, Б-, Е-) целевых систем имеет присущую ему табс-архитектуру.

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

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

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

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

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

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

Пошаговый процесс приводит в ит ге к построение заданной сети, базис которой состоит из пользовательских задач и для которой определе-'Ы "е то-ъко условия межзадачных связей, ко ; условия выполнения этих связей щ .1 функционирлван'л., порожденной системы. Функционально' наполнение системы определяется созданной задачной сетью, а системное - механизмами обработки

- 2В -

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

Признаки сис1£ш порождения. Систему порождения отличает от других систем автоматизированной разработки программного обеспечения следующий набор признаков:

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

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

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

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

- множество базовых задач может быть расширено без каких бы то ли было ограничений;

0 - существующая программная система может быть использована в системе порождения на разных условиях: бег какого бы то ни было изменения (только при условии, что она работает под управлением ОС, входящей в число ОС, поддерживаемых системой порождения); с коррекцией описания ввода-вывода, если пользователь имеет намерение привязать имплантируемую систему к системе управления базами данных и интерфейсной компоненте;1 с коррекцией всех фрагментов описания, имеющих отношение к поэтапной спецификации (в этом случае имплантируемая система, сопровожденная полным описанием решаемых с ее помощью задач, входит в систему порождения как реализация некоторой новой базовой задачи); ■ о

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

Итак, система порождения - это средство продуцирования

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

ОШиаа харахссярлстша хайс^ржлтираЕшашк язшон^ Табс-ориентированные языки (Т-яэыки) относятся к интерактивным формо - ориентированным языкам.

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

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

В главе О основное внимание сосредоточено ка функциональ-!ых характеристиках и потребительских свойствах системы ГЕН-[ЛК порождения целевых программных систем, которая существует •як программный продукт и воплощает в себе основные черты истем И-порождения. Важная особенность генератора ГЕНГАК, тлпчоьщая его от других систем автоматизации разработки пассов, в том, что порождаемые с его помощью пакеты могут сос-авить прикладное программное обеспечение раз тичных конфигу-аций целевых машин, принадлежащих к разным семействам оВМ. ЕНПАК-пакеты могут быть реализованы на различных языках (из Манного множества языков) и могут работать под управление» аиболее целесообразной с эксплуатационной точки зрения опе-здионнсп системы (из заданного множества ОС).

В главе 9. где речь идет о развитии методологий пороядения'

• - 30 -

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

Приведено сравнение порождения целевых программных систем как подхода к их автоматизированному конструированию с традиционным программированием, а затем определены основные направления дальнейших исследований в области создания.среды порождения (названной И-средой).

И-среда предполагает для своего создания изучение задачно-го мышления в человеко-автоматной среде. Вместе с тем она может стать эффективным инструментом исследования такого мышления..

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Исследована проблема автоматизации конструирования программных систем и предложено ее решение на основе методологии порождения целевых программных систем в пространствах заданных конструктивных объектов.

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

3. Создана теория порождения целевых программных систем в пространствах задачных конструктивных объектов.

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

5. Разработано табс-ориентированное воплощение инфов в виде Т-инфов, которое рассчитано на базовую структуру данных -табс (трехмерная таблица с типизированными клетками).

6. Разработаны принципы построения табс-ориентированных языков специфицирования и программирования;.

7. Разработана архитектура целевых систем^ продуцируемых в пространствах задачных конструктивных объектов.

0. Методология И-порождения реализована при создании системы ГЕНИАК для автоматизированного конструирования генераторов приложений.

Из 35 печатных работ, опубликованных по теме диссертации, основными являются следующие:

1. Ильин В.Д. Система порождения программ. И.: Наука, 1Э0Э, 264 С.

а. Ильин В.Д. Система программирования для разработки диалоговых пакетов программ // Тез. докл. IV Всесоюэ. конф. "Диалог ЧЕЛОВЕК-ЭВМ". 4.1. Киев: ИК АН УССР. t9«5. С.52-53.

3. лльин В.Д. Система ИГЕН, Концепция, архитектура, технология программирования // Современные средства информатики. М.: Наука, 19S6. С.117-125.

4. Ильин В.Д. Генератор прикладных задач в системе ИГЕН // ЭЕ'Л кассового применения. М.: Наука, 1907. С.26-37.

5. Ильин В.Д. Построение среды порождения программ массового применения // Тез. докл. П Всесоюз. конф. по актуальн. проблемам информатики и вычисл. техн. Ереван: АН АрмССР, 1987. С.136-137.

G. Ильин В.Д. представление знаний о задачах в системе порождения программ // Препринт Ий-та проблем информатики АН СССР. М.: ИЛИАН, 1989, 50 С. ■

7. Ильин В.Д. Порождение пакетов программ // Системы и средства информатики. М.: Паука. 1909. С.39-66.

0. Ильин В.Д., Куров Б.И. Сравнение алгоритмов распределения нагрузок с учетом изменения состояния энергосистемы при реализации решений // Электричество, 1972. N9. С.7-ю.

9. Ильин В.Д., Салыга В.И. Виртуальный синтез алгоритмов оперативного управления режимами энергосистем на основе динамической модели объекта // Изв. вузов СССР - Электромеханика, 1973. N6. С.014-617. О

10. Ильин В.Д., Куров Б.Н. Математическая модель для опе~а-Т'дзного определения потоков мощности по ВЛ в автоматизированной системе диспетчерского управления // Электричество, 1973. N11. С.23-27.

11. Ильин В.Д., Салыга З.И. Об одном методе синтеза алгоритмов оптимального управления сложными системами // Приборы и системы автоматики, вып.28. Харьков: ХГУ. 1973, С.32-36.

12. Ильин В.Д., Куров Б.Н. Метод повышения точности информации об изменении активной мощности в задачах управления ре-'

-зажимами энергосистем // Электричество, 1974, N7. С.6-9.

13. Ильин В.Д., Куров Б.Н. Идентификация установившихся режимов электрической сети при управлении в условиях неполной , информации // Электричество, 1976. N1. С.18-22. ' .

14. Ильин В.Д., Куров Б.Н. Комплекс программ для идентификации и оперативных расчетов потоков мощности по межсистемным сечениям эпергообъединений//Электричество, 1980. N8, С.53-54.

15. Ильин В.Д., Куров Б.Н., Хрущев С.Н. Математическое обеспечение одного класса систем автоматизации научных исследований // УСИМ, 1900. N4. С.99-102.

16. Барышников В.Н., Ильин В.Д., Куров Б.Н., Семик В.П. Обработка результатов эксперимента в системе ДИЭКС // УСиМ, 1984. N1. С.62-С5.

17. Барышников В.Н., Ильин В.Д., Куров Б.И., Мартьянов A.B. Генератор программного обеспечения процессов создания, обработки и представления табличных структур // Современные средства информатики. М.: Наука, 1986. С.125-129.

10,. Ильин В.Д., Куров Б.Н., Толстохдебов С.В. Массовые вычисления в ИГЕН-пакетах программ // ЭВМ массового применения. М.: Наука, 1987. С.45-54.

019. Барышников В,Н., Борисов В.А., Ильин В.Д., Куров Б.Н., Лютов A.A.. Мартьянов A.B., Толстохлебов С.Е. ГЕНПАК - система порождения пакетов программ // Препринт Ин-та проблем информатики АН СССР. М.: ИПИАН. 1908, 60 с.

20. Ильин В.Д.. Мартьянов A.B. Взаимодействие с пользователем в ИГЕН-среде порождения программных сиотем // Программирование. 1980. N3. С.48-56. »

Заказ 115 Формат ' ; ;Ох /1 6 Т - 13534

Тираж 125 Объем 2.0 печ.л. от 17.10.89

(с)" ИГ.ИАН. yh.Вавилова." 30/6