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

- п О

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ КНСТСТУТ АВТОМАТИКИ И ПРОЦЕССОВ УПРАВЛЕНИЯ

На празэл рукописи

1&твеева Тшгзра Олеговна

РАЗРАБОТКА И-ИССЛЕДОВАНИЕ ИЕТ0Д03 И СРЕДСТВ 121ЕРЕШШ РЕЛЯЦИОННЫХ ПРОГРАШ

05.1а 11 -. Нзте1ОТПчзскоэ я програюсгсс обесопечение выщжхигельяых .'ггая, гсоьтяексов, систеы н сетеЛ

Азтореферат диссертации на соилкзтге ученой степени •кандидата технических наук

Владивосток 1992

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения Российской Академии Наук.

Научный оуководитель: кандидат технических наук.

старший научный сотрудник, доцент Е И. Коган

Официальные оппоненты: доктор технических наук

А. Л. Синявскйй,

кандидат технических наук М. А. Князева

еедущре предприятие: Институт проблем управления

РАН (Шсква)

Защита состоится т? юдг года в 10 часов на

«заседании специализированного совета К 003.30.01 в Институте автоматики и процессов управления Дальневосточного отделения РАН по адресу:

690032, г. Владивосток,-ул. Радио, 5.

С диссертацией можно ознакомиться'в библиотеке Института автоматики и процессов управления ДВО РАН.

Автореферат разослан 1992 г

Ученый секретарь специализированного совета ои1-" - л б. И. Коган

российская

:уд л г.;-.

библиотека 3

ОЗЗАЯ ХЛРАК^ ЕРНСТИКД РАБОТЫ

Актуальность пробдо!/ы. Разработка экспертиз систем (8С) является одной из наиболее пэрспйгстизкых новых шгфориацпсншгх технологий. Стремхенко довести уровень ко'отетепткости SC до урезкя вздуг^х гкс-пертов требует создания баз званий (КЗ), содер,ткзяс icionra тисячи правил (или других элементов згапг-гй). Это, в своя очзрздь, пздгг к технологкчзским проблемам создания болы^::: п'Зс::о:''лчэс?еп!;!;ьк ЕЗ. Приг-ладно:"; програужст. создагту-й ксполпяе'.ую SEi <£ор>.у представления знаний эксперта, долтзп' полуодть прагпдьяую, к&кегяуэ, зо>-фэгстнв.чую ло'раздпгяг/м критерия;,« и лзпсо ccnposor^sstjyo 13 Sü.

Чаще всего в качестве основного средства роал::пгл;;-:п 13

прпчегстгсч продукцЕошшэ систем, з тем '-г::сдз, с рэящпогаакя язы-icci 1:рогра!Мфовачи_1. Слздует отг'зпггь, "то облеты в программах на t.-jüíx языках и • onepoisni пал этг:п сбхзн.тага спк-л-зззггя, гаг. прззило, в терминах, из поззолякза прикладному прогрдлгкту кепосг родственно оценивать указанию гарз-чтергет:::« .чачзствз полученных БЗ. йг/ пеойюджа сяецгзль"-^ срэдетза га кз^репгп.

Разработка кэтодоз и средств юмерэигя преград, каг.лсанних из адгрротиотеских йвкЬх прогрсягярзгап-ч, пуполнпзгся уяз более 20-ти л?т, Такте средс^ЕЗ дурно сг-п- сСзсатсльЕКЧ иямпокентои развитых 'технологий разрегеггз срогра-утзго с-Ъспечгтп SE:í. Подобтн ¡•'отоди и средства для статен- рзгяцкйзисго ярограу-'ггрозания с непро-цэдурнк."! я2!ля»21 типа Ралйп з .стгратурз по утс'^гжся. Тем не гагее использованиз подобных:средств язя создгпяя больких БЗ требует тзорзтичэсгаЯ прор?;Сот:а: Ьтпроооз ?гз:::-п?к::я копфлас-нтикх сиг-тем декларативное продукта, реглпзуасгг рз^кданиим программам! (РП). и праютчзс.'иЛ провеса! прэдгогзплз: к-зтодоз. "зло.тппннэ сбе-тоятсльстзз опредздяпг сктуальпссть jTocsprersonnoa работы.

Цель и задачи нсслзгова:;'Г:1 Цзльо дгзезрггздгеккой работ:; являет • ся разработка '.гэтодез л средств га^рзнгл РП п реизнпе задач ссгда-к;гя BLKcraiíavecTBei::?!« БЗ SC с гголуче.чнык кегодов и

срздстз.

Для достклзниз езл! д;:ссертац::о:п:оЗ работы прздполагакосъ реизпь еле дукера паучно-техплчйскте задач".:

-. сформулировать ос~;л ездход к определению обгектов из.\:ероняя г. языках програт/жрокшлд;

- разработать t/зтодц реадизацх! ерздетв измерения РП;

- исследовать возможность использования результатоп ícci.ícpcühíi .'Л для их оптимизация;

- разработать i&íjb срашкмяи мекау собой языков ru-

■шя ко их пришш&азсти для решения определенных классов задач;

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

исследовать с помощью разработанных средств реальные БЗ ЭС с цздью выявления недостатков самих БЗ и средств их создания.

&тоды исследований. Для репйния указанных задач использовались блзшнты теории формальных языков >: грамматик, элементы теории множеств, элементы теории графов, метода системного программирования.

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

1. Предложен универсальный подход к определению объектов измерения программ на произвольных языках программирования. Этот подход обеспечивает базис для конструирования.средств измерения программ.

2. Предложены новые методы реализации средств измерения программ. Специфицированы функции и'-данные таких средств, базирующиеся на концепции абстрактного типа данных.

3. Поставлена задача оптимизации РП, основанной на намерении потоков данных. Предлодевы решения этой вадачи, выполняемые как на этапе трансляции, так и при выполнении РП,

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

Практическая ценность/ Практическая ценность диссертационкой работ заключается в с до дующем.

1. Предложенные методы реализации развитых средств измерения программ доведены до инженерной практики и могут исрольвоваться при создании измерительных языковых процессоров'

2. Исследован процесс раевития обычного языкового процессора, в измерительный. Оценены трудозатраты на это развитие. Определены затраты ресурсов ЭВМ на намерения РП.

3. РпараСотанаые при выполнении работы средства измерения РП, написанных на языкз Реляп, испольаованы для исследования реальных ЕЯ оО. Эти средства продемонстирсвали высокую эффективность: исследований пегьслило выя^-ть значительное число дефектов БЗ.

4. Выполнено сравнение использования реляционного язы^а програм-■ мированил Ре ляп и обобщенного универсального алгоритмического языка для реализации № ЭС, подтвердившее явно выряженную целесообраз иооть ис-пользовашш первого кз «их д.ля этих целей.

Я Посла пованы ремьние КЗ Ььивлени деф.-кти этих IX? и

средств in разработал.

Реадшация и внедрение регудьтзтоз работ». Представленный з ;а-боте цикл исследований по ызтодаи и средствам игиэрения РП Сьи ь.:-яолнен в разках научно-нссла дова?эльс:ск тем института автомате!«! и процессов упраггек','я ДЭЗ РЛй

- "Исследование щмгадапоэ конструирования, применения к реализации проблеггю-српзнтнроЕГлниг. iratran представления знаний" К гос. регистрации Sí055371;

- "Исследование технологически принципов создам«, сбученгл и сопроводдеиия экспертных систем как составной части ¡»тематического обеспечения перспективна ЗБ5Г, Н гос. регистрации 01680107744.

В указанных НИР -втор принимал участие в качество ксполиитэля и отпетствеяного исполнителя.

Система измерения средств реляционного программирования сисреп внедрена в отделе экспертных систем Института атоматкки и процессов управлепия ДЕО РАН как составная часть техгюлогк» создания БЗ БС. 1-зтер:;ап1 работы используются в учебтют; процессе Дальневосточного государственного университета в сяецкурсаз, а тсжз при зцпсляеитп курсовых и дкпдлжа: робот.

Апробащгя работа Результаты работы Сьии прэдетавдёяы ¡;з:

- Шждупаро&юй корфзрзящс! "¡bpendcbility cf Artificial Int9lllgonc3 Systerra (DAiSYJ»!)" в ICSI г. (г. Bisa);

- Ececoronoft KoníepenuKi "Мгтсдо трзяеяацки я конструирования ярегрзма" в 1984 т. (г. 1Ьзоа:С::рс.";;

- Всесоюзной гколз-совесаЭД! А1&о0леш. проектировали:! зкепертних систем" в 1888 г. (г.Фсква);

- Всесоюзной паучно-технической гвотяз Tösi» кгтфагмтаряшныэ технологии в системотехнике" в 1283 г. (г. Одесса);

- Всесоюзной конференции "йгтоды трансляции и ганструироЕЗЯия программ" в 1088 г. (г. НэвостзЗггрЛ:);

- ВсессЕонсй пколе-сеютгарз tío проблемам ркжрявЕгя средств программирования и кетода« оценки трансляторов в 198Ö г. (г. Фрую»«):

- Всесоюзной научно-практической конференции "Гибриднш интеллектуальные системы" в 1У91 г. (п. Терскол);'•

- III Всесссзном сеюшаре "Качество прогржьпюго ооеспе^кяия" в 1991 г. (п.Дагомыс);

- региональном cescnrape "Мзтоды погьегения качества программного обеспечения" в 1990 г. (г.Вшдивосток);

- конференции кгалодих ученых Института автоматики я nfou-.'otíoi' Управления ЛЮ РАН в 1985 г.;

- научных сешкэрах отдела' экспертных систем Института автокати-Kiï у. процессоз управления ДБО РАИ б' 198-1-1032 гг.

Публикации по работе. Do теме диссертации опубликовано 12 печатных работ.

Структура и объем диссертация. Диссертационная работа включает введение, сзсть глав, заключение, список литературы 83 наименований и пять приложений. Основная часть работы иоложзна на 143 страницах машинописного текста. Работа содержит 10 рисунков и 22 таблицы.

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

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

Ь первой главе диссертационной работы рассматривается технологический цикл разработки программного средства (ПС) вообще л ЗС и их БЗ в частности; анализируются цели, задачи и средства измерения различных типов программ (П) в их жизненном цикле, особенности видения задач измерений программ различными специалистами, принимающая участие б разработке КЗ и их ЕЭ. Это рассмотрение позволило сформулировать задачи диссертационной работы.

Во второй главе диссертационной раббты рассматриваются методи-чесга:.-; вопросы выделения объектов измерений, а также методы реализации средств измерений этих объектов в PIL

Понятие "программа" 'предполагает наличие языка,- на- котором она написана, языкового процессора (ЯП) и порождаемого П вычкелчтельно-го процесса на определенном наборе данных.

Измерение П обеспечивается ее "погружением" в измерительную среду U1C). Процесс измерения'включает в себя три компонента: (а) выделение объектов измерения; (б) получение (измерение) атрибутов cGz-<ж:сз и (в) получение собственно меры объектов в зависимости от лоотаьлениой задачи измерений.

Объекта!.« измерения П на языке L в грамматике G могут быть: (а) элементы множества терминалов Т (в работе в качестве терминалов рассматриваются лексемы); (б) детерминированные последовательности терминалов, определяющие контекстные условия, и произвольные последовательности последовательностей терминалов - контексты; (в) ис-ползокенкь» при анализе элементы множества нетерминалов N; (г)

последовательности терминалов и нетерминалов з прг'.йжугочных цзпоч-' itax внЕока, вознккшх при анасгае П - коятзкстц з сзнтвнциапьиьас формах; (д) кспохьгоЕангагз при анализе злэшгшд »эоязсгва правил Р; (е) ограничена! реализации язьпса R. Fco сотал&г-шз о5т-з:сгы 4зр?г;ру-втся из вкгэукаеаяшп. В частности, *рд»кцксаяэ для злекзйтов Л. (объектов П) ставят и резая? 8агачи, свяеаа®» с вазлпзсу потоков.' ОЗкчпо для такого аяаяоа вводят пояатка двух типоз графзз,' сп;:сы-гагт'лх лез типа связей медцу тг:«та: уярзвлязггй граф я

кяфруационный. граф (1£Г) nporpsriai.

КаядкЯ ведзлзтай cStiirr П взатлсо&огхзяпо «шел с ео текстом, т.о. имеет "aqpec"-B тексте. С,т:ссгг aspecos рсспогагяпяй оба-с:гта гз тексте псогол.ст пзряхь ггст сбs;«:? бгз рзгеиэтрбния самого тезсста. is; фсргифует гагагз сс^ггсг. Пзс-з прзсгшрз П гек есшсуп-посхи т<чэтов ее изгулгй ГГЗ гслуетс:« глагг-'сето рзаультахсз из.»«ре-пяз прг-гзр-здегзгкглг. игзсевз я {рп7с:хггсз, ссатсяглэ га злзкоптоо трох тотоз (£яз:мес;а прггсгсзгтгг^х гсЗзй srAsnoi а cs::cir:):

CZZ5CH ГУКСЗУ S ГСГ.ЗТ-? ."ОЛУ'5 a) eerier (BüWi;::':?) '-"...

сгггок a~ccs.-> S тсглте олуля <гсгя-2>

^Icrz'sz:: . сяязох -¿r-cccr, s югсго г-олуля <:-а:п-3>

2) Клзсс jr~33J)

- ... - ■ (йг/ггетэ-ii

[c^ccr:: ciE-Kcrt злъ-зссз з i-гсдуяя <п.:л-1>

(ЗгхЛ'гякз-! p;|{rob:t лгрзсез с тскпто ко.т/ля <:и:л-5ч-icrrreor: - ...

ст~-5у?оз1)- сяггго«'е?1кссз я тзкстз шдугя <icäi-6>

3) 1'сзее - ...

с.'гз::,с:: cirr.ro?; огтксоз з тзгх-тг ;к>ду.гя <ir,/.i-7>

fc~:cc;: - ...

CTpt:i5TC3l> сскгсг: p^psccs з reis?« модуля <ir.;i-£> йзг^ргкг; сря^гза пссзятсшгл И даг ЕС - ото посл-здоигтс..' ькое

рггс:зггггз;э вес* гепогплегг?; плэгагьтгз П кгет* с их зпач?;п'.я>.«. Гс'ссгптрзт-;г.:э "трпезу" V.O. tea полиозтьн ошхыт»?-

ег процесс пелолйекхя П при хасгски у эгееггитоз П атрибутов, сгя-саяних с :кпользсз2якем ресурсов SIT.'.

Пр'5 та-ссн подход-о процзсс кзиерзяхп гшышяемой П cccxo.iT из двух racjnonoKros: ссохрсекгет тр?.?еи и rawpemra трасса йгмгрснип трасс:; iiomccTJ^ гз.гипям иггореипя т&кста iL 3 сб::;зи ре-

зультаты изнзрзш;.'! трассы - ото нно/лстсо датнк знда:

Объект - список (аврссов объекта б трассе irpa.je'i

(список .значений исполнения и значения:

статических атрибутов) линзлстчосю« атрибутов)

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

л успешного ресзния задач измерения РП ИО должны в лучшем, "йодном" случае : 1 ) строить списки использования элементов языка в РП; 2) строить трасоу исполнения РП; 3) строить статические и динамические графа потоков РП. Эта кэ средства долины по спискам и трассам строить профили статического и динамического использования средств языка б РП, а- такзе выделять описанные контексты использования определенных'средств пзика.

Поскольку РП не описывает последовательность выполнения ^а фрагментов, понятие "iправляндай граф" для нее отсутствует. В работе определяются дгя нида ИГ, соответствующих логическим связям мекду дяуыя видами основных объектов РП - предикатами и правилами.

С ra vine ским ИР РП с вершинами-правилами называется орграф с по-¡лаче;шыми взвешенными дугами G' = (У, F), где Y - множество вершин, в котором каадой вершине yi € У- соответствует одно и только одно праш-'о St Fil, F = Ci't) - множество дуг ?t, в котором каждой Еэрши-нк 1/ч с Y соответствует свсо множество дуг Fl = где

'•'l'i >i/j.'-r'i> ~ дата, соответствующая информационной связи ыезду цра-гд'ль'л! S к и Sj PU » и - ь-.етка дуги, зависящая от типа связи, k - вое дуги (кратность), рлмшй числу однотипных связей ко жду. St и SJt оплешшых. в PII. iiosœy г.£.ждои парой вершин yt и ¡jj возможны информационные связи (дуги) двух танов, зазиоядж от типа вхождений атом-тх Формул (ЛФ) с совпадающий предикатными символами в условие правила Sj и ь следствие правила Ь'{.

Аналогичным образом определяется, статический ИГ РП -с вер^ша;,^!-продикатамп: Множество вершин (Х{) ИГ соответствует.,множеству предикатов PII iPt), дуга мзду каздой парой вершш xt, Xj t X определяются типа® и числом вхождений АФ с предикатными символами и F, в условия и следствия правил РП. Возможны информационные связи секи типов.

Определены два вида динамических. ИГ РП. которые являются подграфами статических 1Я1, РП, имеюдаы то х:о множество вершш и множество дуг, соответствующее информационным связям, раалкэсвавшмся в про-Ut-ccrj вшолюния РП (т.е.. тем, по которым были "переданы" АФ). Еес коадой дуги равен суммарному числу АФ, "переданных" по ссятветству-щзй информационной связи во всех правилах РП.

Рассмотрены методы реализации КС ИЯП, обеспечивающей получение ;v\iwco3 кспх Т, Л, Р, контекстных условий, Н. Для обеспечения изме-^лп'Л объектов языка лексический и семантический анализаторы должны

фор?лиропать три типа дзаных для Иснэрэшй: адрзс последкзй Еилелен-' ной лвкеега; eres с алрэсаде пгрзих "?;:сзм сяптакснчэских конструк-сиЗ яви«; стек п елресг?п перзкс гекггм гснтвкзгсв.. 3 ctótsu с.т/чг* ИЗГЗТ ?LTÎ* С!5эрм»'ДфСВ2!Ю С-73ДУГГ.23 ТОПСТРУ1ЯИ5Я39 утсаеГч"ЗНГЭ для опязздятора любого ЯЛ.

Уггерггт<?!"гэ ÇJ.1 Лг;1 того, птоби- K?r.-?p!irs тсксг пройИ?;/р:13."':.:оЛ апааазтором П,гос-гото»шо рзсс:ф:ггь ого глзокая водагограи» (п/п) ПС, (1) передзггда пй жСоргяцкз о г-игг.тоггпк П и (2) r.i-

аолплсза струг-г/ри x:vízuz а пачаэс^я кс::гхрукц:гл.

При зтон ижжр^гая к« тробука* r;yciO,~i:::o.zb\:ovo прсс^хрз П (яро-го^з енаггаггсрз). Сор^дяшч г. л/п гг*зг rv*

с.) <;гп п/ц> (<115с;ггк'йпатср С, ^s^yniM);

б) <nvi я/я> с<г,г;-::с с<5ье;гга в тз,£;.~>).

В рзЗэтэ ииструкгогаз it ;:х7л prnris-

гсгзть- срзлзгсз гз."эрзк::л пг-гигсс-г Г?! с 1-зг,зл.го::т:;:;ем

кэтсхз -^TOTiiLS coisrzwn. Чюгсгнц - л/л-.-упк-

1ПЛ, jjcrsarsetsn в ГП î7?:î етом ' ^ г: с с : ^ ^ :: : ГЦ ca-rjîVCT-

ся соглтаЁжгеглгз гаргзгл (Л),. н/п, rr'swreu-

вк-э o7i:o~:c-:r/.i, cCpsüzTSuins ' сît :: г- -rvsres-

r;i:3 альтсрггзгсги усл)гхх

xrrroir"; PO, c-îrîl"5!:^т-----;р:г:'лк ГП.

-г::г:гП2згазг;«тг s * »f.-'p.TL'f схс-м ср-

Г2г*??л.~гл г;г;:"сс:'ого г"-с~з'г;а ГП - по г гз r,-T.":<;:nT¡«.

Спт!г.г.яац:з гзпргялгпз sa rr^r^rcrcw »гола с::.ичщг.З, сЗсолзчзязпв-пс-тлг'пкз рззултзтоз Егг-ггсгг:?;: ï i¡3 FE

Рггсизхрвш £г«горн, втакг^э c::ct«. Зала-

'з .опхпихакз! ГП fcpvy.r;ip7<$?e3 zX~'--' '■> г^ггегизасетл

г'потглз ?П за с:з? с£~2огс» .'"гглзго прешла

(предазтз) яр;: чгзгл tó^rx'^r."":? г»?:: кзягсл оо-

ррботке прг.зилз (продгашта).

Йэл обработкой прззжгэ понгасзтея: (1) с:Язр в качеств

сбрабзткпаеггго; (Я) псстроэжз йзогдвгла ксЗлрзз корхежзй (КК;. г.<У1сижа:ъпо озяа«сж?5к:<х FtÄpaaaiff? пра^кз, гдз sa^irt Ш ссдэрга:' хотя ей од;;;! К, пз ссп0сга5лявп::йся с ЕиЗрая::!."М пгавихом; (3) со-поставл'зшк ncez ШС с btóp-'ia::.'*! правда-)«, 1лл;:слскке означ::ваииЯ правила и (.4) сшзя!8йкв irpasííü с кс^ярауи зиаченкй !te-

ром'зшшх ;;з вычяс^еягая csnâ'KiSixmî.

Пол обра^огкоя пгсдгзстга k>jbî!ns«tc£: il) ti&op предиката з ivi'k-стсо обрзбатгпадскаго; i2) постройки--: кгкивства правил, лотеши^льно оэиачивз<?«я К г.и^рз?!ясг» про^гкз^а- 'S) сопоотзсление всех :u.c{*.c-.i-

ботанных ранее К выбранного предиката с ираси.5ами из построенного шюлг?стБа правил, вычисление означивачиЯ правил к (4) выполнение их следствий с кабоами глачений-переменных ¡э вычисленных означиваний.

Выполнение РП рассматривается как обход всех Есрага ИГ РП, для которых в текущем состоянии базы данных (Вд) ушеотся необработанные ПК. Дуги статических ИГ РП, соответствуйте потенциально возможным для рассматриваемой РП потокам данных рассматриваются как возможные управллвц«'-,' связи при организации выполнения РП.

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

Вводится понятие обобщенной йеркикы (ОВ). соответствующей подграфу ИГ РП, и операция обобщения вершин ИГ РЕ Предложена стратегия построения графа с ОВ, ориентированная на решение еадачи формирования процедуры оптимального обхода исходного ИГ РП.

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

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

В главе рассматриваются также дополнительные возможности использования КГ РП для оптимизации РП. В частности - использование графа с ОВ для организации оверлейной 8агруаки частей РЕ

Четвертая глава посвящена разработке и практической проверке метода количественного сравнения меаду собой языков общения с ЭВМ по сложности (содержательности) написанных на этих языках текстов (программ) с учетом • реальной практики использования сравниваемых

языков. Метод применен для сравнения языка Реляп и обобщенного алгоритмического языка программирования (ЛЯП).

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

Сравнение осуществляется следующим образом.

1. В качестве объектов при сравнении двух языков Но-лодержатель-ности их средств выбирается сжси (группы) предложений на этих языках, полученные при статистических измерениях реального использования средств языков в. рассматриваемой ПО. Число предложянй в смесях должно быть одинаковым (сравнивается одинаковое число "законченных мыслей"). Оно выбирается 'таган/, чтобы профили использованных в каждой смеси средств языка были как мояпо йлиэтэ к профилям всей иссле-довашюй выборки П.на этом языке. В принципе, в_ пределе смеси могут содержать всего по елному "ср^дкбму" прэллжяя» языка, если ско

зсстатс"г:о хорошо. отражает рассматриваемые свойства выборки пли нет других данных об одной или обеих исследованных выборках Л (текстов).

2. Смеси сравниваются по метрикам грамматической сложности (ГС). Сопоставляются сами смеси и смеси с их семантическими аналогами.

ГС смеси предложений n(L) языка L - ГС( П( L)); определяется г.о метрикам ГС.

Относительная ГО-.языков L1 и L2 - (rC(Ll/L2); определяется по ГС смесей предложений яоыков L1 и L2 ГС(ЩЫ)) и ГС(П(Ь2)).

Поскольку £С(П(У) отражает "насыщенность" смеси предложения на языке L конструциями язьза,- которая определяет и сложность восприятия всей совокупности предложений программистом, и "трудоемкость" ее обработки анализаторами трансляторов, то относительная сложность ГС(L1/L2) для П(1Л) и Пi\JL) «?сть

ГС( L1/L2) - ГС(П(И)) / г'С( П( 12) ).

Относительная сложность (относительная содержательность, мемен-■лв) языков L1 и L2 - С( L1/L2). Всегда

С( L1/L2) - rC(Ll/L2) a CC(H/L2).

Относительная семантическая сложность (СС) ksiüíob LI и L2 определяется одним из трех способов в зависимости ст вогсокности шра-секавтики средств одного языка средствами другого.

1. Вели семантика сыгеи предложмшй iiaiecs LI молет б ¡ль описана • на изыпе L2, а смесь щхгдяоин'дй кзкка L2,b свои очередь,- на язи;та LI, то при сравнении CG пзнког. LI » L2 сопоставляются ГС сеианти-ческих аналогов ::a,v.oñ из скоссл нредхонакий П(Ь1) и II£L2), записанных на втором из сравш-.ъаэгж игыдаи. В этой случае относительная СС ягыков Li к L2 определяется «ait

С0(L1/L2) " ЛССLI/12! / ACÍL2/L1) I!

Л?(LI/12) - Г0{/il Lt) : LZ),

A0(LS/LI) » rOÍ/JIÍLC) : LU, где AII(Li):Lj - селщигическкй a:;aaur clüch пргдлзагзиий язмса Li,

aaiü.aejiíaii"; на я sis a Lj.

Такгя сктушш характерна дка «sisón одного класса.

2. Если ссаашгкка екзеп предлоазнпЗ язи.» LI шоэт быть окисана на азксс 1.2, a сскагтыа скоси предоакгшЯ яздог L2 не казт Сип. отход средствам:» языка LI, то иря оцисю откжгедьвза СС язьков LI и LS срашизвизгся ГС сызеи предложи;:;? suinta LZ с гашкхишш на 12. coiiaiiïîi'-jjci:;;'»! аналогов сюеи прэйгокзгшЗ .тзг^-са Li! В зтом случае

СС( L1/U-?) - ЛС( L1/U) / ГС( L2) » ЩЛ1Ш) : 12) / ГС(Ш-

"Гож;: евдациа sapacrepsa для г.зькзи так казюазиого "свсрхвисо-кого уровил" (гьляезжея, как правш», сробсгхф-оркак'/ироиаишс^ 'язькали - я&аюь 1л - и универсашзш: языглв орограигаровашш -яаьвеов L2. Ушгвэрсашш} Ш всегда обеспечзЕгят рьхшзидеи П, запк-'.ааных на inmce cEepxtucoiraro уровня.

3. ÜÍJUÍ CC)OUK2f& cisci: предложений языка LI HO ЫО&ЭТ быть оия-';аяа на изьке L2. a се^-пишка cía с и предлэ;цзш;Я язкеа 12. - на изике LI, ио суг^гствует наше LS, на ютороа иагут бить, описаны c¡.^c:t предложений''язгл-юв Li и L2, то при оценке относительной СС яз^соп LI и L2 сравнивается ьй^ду coöofl ГС записанных на языке L2 сеьаитк-чзских аналогов смесей предложений язьпив LI í¡ L2.

Если существует несколько языков L3, то выбор одного га ты елг:-яет на результат сравнена. ГЬэтоыу, говоря об отнаонгелипп СС квд-:оп ¡Л н L2, следует указывать базовый LÄ

CCÍL1/L2 : L3) -

ÍCIL1/L3) / ACÍL2/LS) - 1'Ы ЛП(LI ): : L3J /' IViAiliU') : LC).

TiiKíiíi ситуация харакзегна д.тл языков сверхвысокого уровня, .ne-

m-ihh-ci преджданий етторнх ко онисавается срс-дстьак-,! второго из п.-и;¡-..в, и'¡ой бить свхсаяа средсгки« ^шиьсрсплышх Mí.

Ь Ю'^о'ч'.п среднего AHÍI в р^.'юге вгйр;и;о

кке, полученное из результатов статистических исследований П, написанных на языках Фортран, ПЛ/I, Кобол, Паскаль и других ДЯП и одинаковое для всех ПО. Общий объем учтенных при этой II составил скол.; одного миллиона операторов. Сравнение випа-гнело со средники пссд.-ю-."енилми трех выборок П и БЗ ЭС, написании;: на яггко Рс.^-гп.

Предложения сравнивались для 4-х метрк:: ь 2-:: ракурсах иид'^.п 1Ь (1) грамматическими анализаторам:« и (2) программист-».-^. Чл-.-гь выводов этого сравнения приведено э основны». выьсдах работы.

Пдтаа глава диссертационной работы посвядана средствам измерения программ, написанных на ЯП Ре/яп, - сиглеыэ СПОРЕН

Основные функции и данные СКСРЕП представлены на рис. 1.

Являясь ЯП пзыка Реляп, СКСРЕП выполняет лексический, синтаксический и семантический анализ текста исходной П, Для П, не сс п.е;'-ствуэдей спецификациям на язык, собирается информация о,вэгш:кк.ях -ней оскбках. Анализ РП осуцествллется традиционным образом с ¡••л-пользованием ¡ктода рекурсивного спуска. Правильность и надега.\у::ь реализации анализатора СИСРЕП проверены на стандарном комплс.гге тестов языка Реляп.

Сбор • статистической инФоркздии о тексте РП в СКСРЕП рвгхюссап на основе абстрактных ттов данных, включаюэдх в себя счетчики ' и функции накопления их значений. Все динамические измерения РП производятся з СИСРЕП с использованием метода частотных счетчиков. СКСРЕП позволяет накапливать статистику для произвольных выборок г П. Для изменил модульных РП (БЗ) организуются таблицы глобальных объектов (предикатов, подпрограмм, строк и чисыл).

Подсистема построения статических IT'РП обеспечивает получение статических ИГ PII а статистической информации о яга. В ней анализируется возможность применения двух предложенных в третьей главе методов оптимизации РП по их Iff РП.

Подсистема в^олнэния расширенной РП представляет собой систему СИНАП и измерительную среду СИСРЕП, являющуюся набором п/п накопления значений частотных счетчиков в процессе выполнен™ РП

Полученные результаты измерений могут быть напечатаны в читабельном виде полностью или частично. Кроме подученных распределений приводятся средние значения,., в отдельных случаях - максимальные, n также процентные соотнесен«; Значений распределений.

Программы системы СИСРЕП (13. S3 тыс операторов и Z7 тыс. написаны на языках IL4/1 и Паскаль VS.

Приведены результаты исследований трудосмсисчи пр^прайпим от'<» дартного ЯП в ИШ н "стоимость" проводе »ил измерении о ncws-дмо 1'Лч.

Входные данниэ

Текст РП

г

4

Подсистеш

Параметры СКСРЕП

Средства настройки

I

Рабочие файлы Еыходные.

данные

Таблицы

управления

подсистемами

л

Анализатор

Средства сбора статистики о теисте

Генератор ЕП РП

Статистика РП

Таблица

глобальных

объёктоЕ

—> 2

ЕП РП

г

-»I

Средства построения статических И' РП

Статистика И1

Статические КГ}-

Генератор рассь-рениой РП

Средства осказраия ЕП РП частотные счетчикаи*:;

Генератор тегета 1':.

Началькос состоя шк счетчиков

Расширенная РП

3

4

-> 5

5 Ь О

Параметры СИНАП

£

! Данные РП~1—1->

Ьфту&лъкал >озг>ша

Изгарителыше функции

Систем СШ1АП

Результаты ВЫПОЛНЯЮ! РП

Конечное состояние (—> счетчиков

7

8

1

<4

г

й

' Средства ивуализации

изысро:шй ^

ГЦ

ДРАИТ«?; я-ув?, СПСРСИ

1Ь

В пестой главе приведены результаты измерений РП и НЗ ЕС. Ь::'.;ол-неко статическое статистическое исследование использования срэдств пгыка Реляп з ВЗ 4-х ЭС (2624 правила) и 4-х РП (2131 правила).

Изучение результатов измерений позволило установить, чт^:

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

(б) ЯП, предназначенный для разработки больших ЕЭ, ло.тен бить оснащен новыми функциональными возможностям, а именно:

- сравнением описаний глобаишых объектов всех модулей РП (так, г, ЕЗ медицинской ЭС Консультант-2 (гЕС), достаточно хпрота проверенной и прошедссй опытную эксплуатация, было обнар;.;г>но несколько десятков опкбок несоответствия подобных описаний);

- введением глобальной БД, доступной из всех модулей РП (примерно половина вычислительных ресурсов при рабо.-с ?П ь системе Синаи затрачивалась на обеспечение межмодульного интерфейса черен Файлы);

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

(г) статические ИГ исследованных КЗ не нкэкл циклически/, частей, что всегда позволяет с помощью, предложенных методов оптимизации обеспечить однократную обработку кадцого. правила (предиката); построение ИГ .помогает выделит?, при трансляции фрагменты РП, будут загружаться и выполняться тоже только один раз.

Выполнено динамическое статистическое исследование ¡БЗ УЭС на значительной части архива системы (464 истории болезней). Оно позволило построить модели типичного функционирования фрагментов, ва на различных совокупностях данных. Сравнение этих моделей обеспечило выделение фрагментов БЗ, приводящих к неправильным результатам работы ЭС, а также неиспользуемых фрагментов БЕ.

Исследование продемонстрировало полееность ередстз профплиров ния процесса выполнения РП как в терминах правил и предикатов, так и ИГ. Наглядная инфорация, предоставляемая прикладному программисту и создателю оболочек ЭС, дозволяет повышать эффективность со ¡ж В'? и средств их программирования. Эти средства совера&нио цсрлалмшм образом устанавливают подтвержденное^ и тестированноег;> ГО

В приложениях Ы5 приведены: (1) список злемснтсп Н'.'^л-глшш, собираемой системой СИСРЕП; (2) статическая статнстн^-ския жфсрма •

цки об исследованных БЗ ЭС и РП; (3) примеры КГ £3 ЭС; (4) статис-. тическая динамическая информация о нескольких подсистемах БЗ X1 Коксультант-2; (5) справки о внедрении результатов работы.

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

Основные результаты раг^оты заключаются в следувдэм:

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

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

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

4. Предложен ыетод сравнения сложности (содержательности элементов) различных языков обданкя с 5В11 Ь;тод заключается в: (1) получении для сравниваемых языков смесей предложений, имеющих те же распределения использования элементов языка, что и исследованные совокупности текстов на этих языках, и затеи (2) сравнении по зз-даниш штрихам граьгатичасгхсй сложности смесей предложений на сравниваемых языках мзэду собой и смесей с их семантическими аналогами, написашшх на второй из сравниваемых языков.

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

Б рассмотренных метриках грамматическа.. сложность среднего реляционного предложения в 3,4 4,9 раза выае грамматической сложности ^».•днлго алгоритмического предложения. Поскольку предложение на лзька л>'л!н"гся закопчённой мыслью, можно, по-видимому, считать, что алгоритмических знаний по форыс в 3,4-4,9 разп проще зле-п.ита лвгмчоскйх пнзний.

»тельная сложность среднего редтяюнпвяз предложит и

среднего предложения АЯП позволяет считать' среднее реляционное предложение эквивалентам по сложности процедуре АЯП, состояний из 12-13 предложений, т.е. »южно считать, что алгоритмическ ie знания состоят из элементов, которые з среднем в 15 раз'проще, чем средние элементы логических знаний.

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

Трудозатраты на разработку измерительных функций в анализаторе

ИЯП СИСРЕП составили около 17% трудозатрат на него. Трудозатраты т

t

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

По оценке для языков рассматриваемого класса общие затраты im функции измерения должны составить около 16% затрат на традиционный языковой процессор. Затраты на функции визуализации зависят от метода их реализации. При. их' написании на универсальном языке программирования они составят не Солее 15% всех затрат.

Временные затраты на статические и динамические измерения исследовавшихся баз знаний составили 50-707. затрат на их трансляцию и исполнение без измерений.

7. Выполнены статические исследования. 4-х баз знаний экспертных и 4-х выборок реляционных программ общим объемом 5.5 тыс. предложений реляционного языка. На основании результатов измерений выявлены функциональные- недостатки языка и языкового процессору Определен характер использования средств языка, существенно влияшгго на выбор проектных решений при создании языкового процессора. Установлено, что предложен:'!*«- жтоды оптимизации могут быть уснепл;о применены для баз знаний°зкс'1ерт1шх систем.

Выполнено динамическое измерение базы знаний медицинской экспертной система Предложенные методы и реализованные средства динамических измерений позволили выявить ее дефекты.

ОПУБЛИКОВАНИЕ РАБОТЫ Ю ТЕМЕ ДИССЕРТАЦИИ

1. Коган Б.51, Матвеева'Т. О. Зксперимептальное üce.wjtcn.tiw реляционных программ // Новые методы конструирования программ. Bjpo-сийирс1с НГУ, 198G. C.5G-65.

2. Коган Б.Я , ■ Матвеева Т.О. некоторые возможности оптимизации, реляционных программ // Новые методы разработки проблегаю-ориенти-рованных программных систем. Владивосток ДВ1Щ АН СССР, 1985. С. 80-65.

3. Артемьева iL Л . Клецев А. С., Коган Б.11, Матвеева X. О:, Орлова Л Д., Сорокин К С. Оптимизация программ и вычислений для реляционного языка программирования // Методы трансляции и конструирования программ. Новосибирск: ВЦ СО АН СССР, 1986. С. 43-49.

4. Коган Б. И. , Матвеева Т. О. Сравнение языков программирования с учетом реальной практики их использования: Препр. Владивосток ИАПУ ДЮ АН СССР. 1987. 33 с.

5. Коган Б. Я . Матвеева Т. О. Сравнение языков описания баз зна-£ iiüíi с алгорктютескими я тиками программирования // Проблемы проектирования экспертных систем: Те?чсы докл. Бсесоюзн. пколы-совесд-нш. 1988. 4.1. С. 133-ÍS4.

6. Коган Б. И., Штьеева Т. О. Технологическая измерительная система для исследования баз знаний экспертных систем // Мэтоды трансляции и конструирования программ.' Всесоган. конф. 23-25 ноября 1983 г., Новосибирск. 4.1. Новосибирск: ЕЦ СО АН СССР, 1Ö8S. С. 124-125.

7. Коган В. И. , Матвеева Т. О. Измерительная система для исследования средств реляционного програмыирования//Теория и практика систем информатики и программирования. Новосибирск: ¿!ГУ, 1988. С. 152-159.

8. Матвеева Т. О. Измеряемые характеристики реляционных программ // Методы повышения качества прогрш-мюго обеспечения: ¿¡атериалм сеьмнара. Владивосток: ДВО АН СССР. 1990. С. 31-36.

9. Коган Б. К , Матвеева Т. О. "Сто|шооть" функций измерения в кз-ме ригельном язшссеом процессоре СКСРЕП // Ь!етоды повышения качества программного обеспечения: Материалы семинара. Владивосток: ДВО АН СССР, 1990. С. 31-36.

10. CogaA В. 1., fcíatvoeva Т. О. Corparison of computer languages based on their actual practico // Dependability of Artificial Inte-1 licence Systems (DAISY_91). Pros. IFIP 5. 4/IFAC Workshop. Vienna, Austria, 27-29 Мзу, 1991. Ed. üH.Schildt, J. Retti. Antsterdam, Nov York, Oxford, Tokio: North-Hol land, 1991. P. 307-320.

11. IhTBeeca Т.О. Экспериментальные исследования статических xa-láwcpKCTiü: базы знаний ьедицинской экспертной системы "Консультант-2" // Кгтоды и средства создании и исследования экспертных си; те*. Р.чадивссток: ДЬЭ АН СССР. 1991. 0.91-106.

íd'4ih К. И. , Матвеева Т. О. Элементы методики статйстичссглх к^м-.'ркниЛ программ // li-тоди и ерсдстР'« Иордания и исследования эк-?:;f;c!:»a систем о Ьлг.-д|:восток: Ш'О АН c&cí1, luOi. 0.113- 154.