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

Па праилх рукописи

Гаеиой Витали» Анатольевич

РАЗРАБОТКА СПОСОБА И СРЕДСТВ РЕАЛИЗМ (ИИ ПРОГРАММ НА ОСНОВЕ СИСТЕМЫ ФУНКЦИОНАЛЬНЫХ ПРОДУКТ(ИИ

Специальность: 05.13.11 - Математическое и программное

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Сапкт-Петербург-

1999

Работа выполнена в Санкт-Петербургском государственном электротехническом университете (ЛЭ'ГИ).

Научный руководитель -

кандидат технических наук, доцент валтрашевич В.Э.

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

док юр технических наук, профессор Гаврилова Т.Л. кандидат технических наук, доцент Макулов В.Б.

Ведущая организация - Санкт-Петербургский государственный университет аэрокосмнческого приборостроения

Злтита состоится " "2.9 " _ ¡999 г в 11

часов на заседании диссертационного совета К 063.36.12 Санкт-I ¡етербургского государственного электротехнического университета (ЛЭ'Ш) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан "__"_____1999 г.

Ученый секретарь

диссертационного совета Маокнн Л С

Я.-ГНС. и п

ОБШЛЯ ХАРАКТЕРНО! ПКЛ РАБОТЫ

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

Процесс разработки программ cocí опт из нескольких этапов. Эти кодирования, во время которого создаются тексты программ, в диссертации определяется как реализация протрамм. В 'нон аемтеи,-н ос г)! особое внимание уделяется использовании) декларатаных средств, в которых программа рассматривается как сонокушюаь ori-|)еделешп"|, огшсыпаюншх свойства требуемого результата. Г5 гаки:; программах скрывается способ получении результата, "lo позволяет программисту сосредоточиться на описапнн решаемо!; ылачи.

Одним из универсальных пршпппюа решения тадат исиолыус-мым в таких средствах реализации программ, как :иык программирования Пролог, язык дедуктивною еннтеит программ У'ЮППСГ и др., является пришли! пошаговой дептшпаппн. В качестве формально» модели, пошоляюшеп адекватно отразить этот принцип, н диссертации используе1сн система продукций, Применение этой хорошо ту-ченнон моде ш и качестве основы способа, разрабатываемою в соот-aeleiBUii е современными в и лядами lia процесс реализации программ, обусдаьлипае! получение законченных и практически значимых pe ¡ультатов.

Одним из наиболее нерснекпшных направлений в современном теоретическом программировании является семантическая теория пр.нрамм. ГЗгот ратдел тушет методы формального описания семап-шьи iipoi рамм, еематп ические меюды преобра-ования и докати ;е.зь-ства утверждении о прот раммач, меюлы проверки семантической правильности прот pas.м. Активную работу r¡ зтой области ведут такие тесле тонлели. кат; B.li.iiopiiien, В.Il Касьяниь. Ю П.Кчроблнь, IS Г Koiob, В.К.Габедьфельд и др. H диссертации pa3pj6a¡h!aae:c-,í сио-..5. шы'.опяюшпй апа.ти ¡Прова;ь npo¡ рагг-'Ы выявлять в нт'х telan i ичел;ие шьипкн, и сносом:« в> том iiii. такал; образам повышенны i лчг-с i ич нрот рамм. 1 Ico i ому темп рп-'пч является Зктулг.ьноЦ,

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

Ладами нсследонат'«!»:

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

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

- разработка г зыка-реализации программ;

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

- проверка дортозерности полученных результатов на примерах решения практических задач.

Миоды исследован» I. Для решения поставленных Задач Использованы результаты семантической теории программ, теории, формальных систем, теории форматных языков ii грамматик, теории графов, а также Методы конструирования трансляторов и методы rto-íтроения экспертных систем.

Осншшмс положения диссертационной работы:

!) ФирмалЫтм модель /программы продукционного nina, im-званная системой функциональных продукций (СФП).

2) Графовая модель выполнения программ, реализованных п соответствии с моделью СФП.

3) Продукционный язык реализации программ, названный языком СФП.

4) Инструментальное средство «Софист», Поддерживающее реализацию" программ на языке СФП.

Научна« iioisiiíua НолученЙЫч результатов состоит в следующем:

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

2) М о цель выполнения программ, в качестве основы которой выступает двудольный ориентированный ИЛ1ЛИ граф, до-

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

3) Продукционный };31лк СФП позволяет реаиизовынать программы d соответствии <; моделью СФП и предусматривает проведение их структурно-семантического анализа.

Практическая ценность полученные ретульппон состоит а следующем:

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

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

3) Предложены методики реализации н отлалкп программ па языке СФП, Kt-чорые раскрывают особенности предлагаемого способа н способствуют созданию треб>емы>: программ.

4) Создано инструментальное средство «Софит», иредосщп-ляюшее. лозможпость реа.чизопыаагь iipoiраммы на языке СФП.

Внедрение результатов раоотм. Работа выполнялась в рамках госбюджетной ПИР ГБ2/МО-15. Разрабо1аниый язык СФП и инструментальное средство «Софист» использованы в учебных процессах СП6ПУ1У, СПбГЛМГУ при проведении лабораторных работ по дисциплине «Ьазы данных., знании и экспертные системы».

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

Амрооашш рс':улыатов проведена на еллауюын.ч конференциях: 6-я Мюьдупзроднач конференция ^'.Знание - Лиало! - Решение», in та, 1997; Нсероссинская нсжпу-зовская гауши-че.чничеекаи конференции студентов и аспирантов (-Микроэлектроника и информатика -!)3», Москва, 1'Ж; 6- л i 1ацнон,гзьнаи конференция по ц..ч;\сьасико.м) тпеллекту РАН, Пушник, 151-я на» чко•гч'/.ясч^гкаь конференция профессора ко- npei io,iau.-i i ..jü.ckoi о «дчмана t'linlJTV, t анкт-ilerepfnрг, 1-я H.'cj't.ff'•r:c!;Yi•: нэу.'но* техническая конференция

-<| -

«Компьютерные технологии п пауке, проектировании п ироизводст-пе», Нижний Новгород, 1999.

На конференции '(Микроэлектроника и информатика - 98» доклад но теме диссертационной работы занял второе место на конкурсе работ аспирантов по секции «Автоматизированные системы, методы молелирспанияиоптимизации».

Публикации. По теме диссертации опубликовано 6 печатных. раСкн. них 4 статьи и 2 тезисов докладов.

Структура н oíii.cM диссертации. Диссертация состоит из введения, Четырех глав с выводами, заключения, списка литературы, включающего 108 наименований, и 3-х приложений. Основная часть работы изложена на i 35 листах машинописного текста. Работа содержи г 7 рисунков и 7 таблиц.

СОДЕРЖАНИЕ ГЛВО ГЫ

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

на защиту.

В первом главе опнсывакнсй существуюШие подходы к реализации программ; рассматривается ряд способов и средств, основанных lia системе Продукций; рассматриваются основные задачи, методы и средства семантической теории программ; обсуждаются различные продукционные модели.

Существующие Подходы отражают различные точки зрения на процесс реализации программ. Языки и системы спецификаций ориентированы. Паточное описание решаемой задачи. Методы автоматического синтеза программ пошоляют получать тексты црогоамм rio описанию решения класса задач. В языках программирования высокого уровня программа сопоставляйся с 'Текстами на этих языкак. Значительное внимание в средствах, разрабатываемых согласии этим подходам, уделяется декларативности описаний. Поэтому во все\ подходах широкое применение нашла продукционная модель, предоставляющая возможность определять способы конструирования сложных объектов Пли Понятий из более простых.

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

год гииерпрограммнрований', псевдоязык Кант2. Их наиболее существенным недостатком является отсутствие возможноеш анализа программы на наличие сложных семантических ошибок, т е. смысловых ошибок, выявление которых невозможно частными средствами и требует построения модели программы. С) важное!н i я кого анализа говорится в работах различных исследователей. В анадтаюре семантических свойств Модула-прш рамм' ciponicii граф внутреннего представления программы, анализ котрого гюзводлег выявлжь следующие ее свойства: неопределенность значения переменной, и и ход из цикла, бесконечность рекурсии и др. 13 лчыке асинхронных функциональных схем АФС4 ароИтея множество вычислительных последовательностей пр01раммы, позволяющее анааи шровать на личие зацикливаний, блокировок, тупиков и др. Полому разработка средства продукционного чипа, предоставляющего возможность анализа семантики программ, создаваемых с его использованием, являС1ся важной задачей.

Выразительная сила и такие достоинства систем продукции, как универсальность, модульность, независимость и дектарампныегь наиболее ярко проявились в продукционной модели предоавлення знаний. Для ее формального определения А.С.Клетевым и Т.М.Яхно были предложены, соответственно, реляционная и алгебраическая модели. Однако они, в силу своей универсальности, не дают возможности учшывагь такие особенности программ, как наличие нескольких путей обработки данных, необходимость управления потоком данных, 'ho обуславливает необходимое!!, разработки специальной формальной модели программы.

Но niopuii глапе предложена формальная мотель программы продукционного типа, названная cncit-roii функциональных продукций (СФП), рассмотрен!,1 ее основные- понлшя, проведено нее зелова-

' Жыолеи ПЛ. Сислемл оГм>л:ио1:Л Iс н по[ о ppof fiaмMiijum тпя Н llp.np.iM-мнров.пше. - 1993.i.-C. ¿8 - to.

1 Крюков 11.Л., M(u'i;,ii!>ti:i Г.Ю., Пилило ьа Г.Л.,П1>ра И) p-i Ml' К up о-(иеме нпшмапнашш программировать): Препрвш - М.: lln-i прикл мшеча-тик1! им. М.И.Келдыша, 1982. - 24 с.

' Емельянов 11.Г. С'шнмьфсль i И К" Лнлл.п.игр семантических евши iв Mii,!)aa-ii|ioi-piM\i.'/ 11нic.i.'icicf\длиsaitii.s н качеано н|чпг.1Ч»июм шч-лкчения: I'd н-оч. ip. -1 ionoLhnnpcK. 1944. - (.'. Idil - Id?.

' К'прдолнн К) II Ct'mjii i1 ¡'u'ck lie мет hi анализа , к преде icnnii\ cicicm: ЛвК;р':ф. ;bic iiaaiiKK. vi'.-ii cren. a l н Mock )н>_рк-| иче.:к иа i M 1994.--<10 c.

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

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

СФП определяется как ShP -< S,F,У,Р >, где S - конечное множество сортов; F - множество функциональных символов/ определяющих функции >•••>**): xs2 х — ->^*|,где slt s2, ..., У- множество конечных множеств значений функций; Р - конечное множество продукций. F = FMluFSUFN, f'A f п FS Г) FN = 0, где FM - конечное множество функциональных символов составных задач, FS - конечшос мНЬжество функциональных символов простых задйч, FN — множество констант. Продукция представляет собой упорядоченную пару множеств р =< Ant, Con >, где Ant - условие продукции, Con - следствие продукции. В развернутом виде продукция р для задач /0 £ FM и /о cFS определяется, соответственно, как

А = (ff W < ), yf ) => = о" (*? < ), Уо ), П> О,

=> = (/о"(<,с2°,...,<),>-0''), (2)

5 Яхно Т,М. Системы продукций: структура, технологии, применение. -Новосибирск, 199ft.-127 с.

fv0 r0 r0 . ^— f I I I 2 2 2 n n

ГДС >л2 >•' •> *0 ' — ' 1 ' 2 '*i " I ' 2 >' ' - ' •>I > л2 »•••>•* A, i ,

.... < e F,V, y> 6 Г '»', e Yir.....уЦ e Y" . -

Ддя функции У(-*г|,-*'2>-">х>) подстановка $ определяется как множество пар вида в - {х, /с,,лг2/с1,...,х1 !ск}_ Пде с*,, е2, .

efiN. Задача/решена с решением 0 и -значением решения у, если 39 :/0 = у. Для продукции реР определена общая подстановка 9, рО =< AntB,CunO>, если для задач = (/,(Л'1 ),.)',) е Ant

выполнено jfi-У; (' - 1,2,...,/IJ. В этом случае дня задачи

= (/o( ri'>x2 > •' ->-v*„ )'3'о) 6 выполнсно fj) - vu.

Для задачи f, найденное решение которой определяется равенством /9 - у, структура вида d ~(/9,у) = (/ (ci,cl,...,ck),y) ^ задает факт. Множество фактов образует рабочую память (I'll). Состояние РП, или просто состояние, определяется как D = \ditd2,.. ,dt}. Множество всех состояний обозначается как D, где П = \l\,,Dt,D,,..) . PII непосредственно переходит из сосючния DeD в состояние D' е D посредством продукции Р&Р, что обозначено как D—D', если 30: рО =< Ant9,ConO >, AnidciD, при mm D' = DKjConO. PII ПСрСл! )Дит из состояния Del) в состяние 1Уе Р, что обозначено как D------> D', если существу»)г продукции />|, - /'., .... £ (£>0) iauie, что D - Di — /J>()l —... —-1-.-» /)„, = /У . Начальное состояние /Л = 0. Если О0 > D, „ V/)e/\ „, D, D' следует Л, — Л',то О, - конечное соеюяние Л0 .

Основное свойство, исследуемое для СФП - что свойство сходимости, которое выполняется, если V/), ГУ, Л"еП: I)--------* ГУ,

D—3D4 el); /)'-----> D", £)"■----■> />'\ Дог,. ночными условиями сходимости системы продукции являются ее детерминированность, устойчивость и коммугашвпоеть СФ11 дстерминирована,

если V Л, ГУ, ГУеП, \'j> с-Г : Л--«-* ¡У , D —*-> D" следует, что 1У --■ Л'. СФП устойчива, если \/Л, Л', Л"еП, V/;,,

р2 е Р : О /У и О —" > следуе,, чю 3£Г е О:

и—СФП коммутативна, если Л', /Уе I), V/),,

р2 е Р: и О—Л", следует, что З/УеО:

О /Г и С —О щ .

Утверждение 1. СФП недетерминирована, устойчива и коммутативна.

Для дальнейшею анализа сходимости вводится понятие модифицированного вывода на множестве состояний В : О—-> 71', где Т) , О' е Б , если для р=<Ам,Соп> 30: П = {0|Ж.70сО}, при этом /3' = 1Ти СопП, где Сои П = У Со/г в Как „ 0 „сходном выводе, Ц = 0 .

Утверждение 2. Для СФП с модифицированным выводам выполнено условие детерминированное!и и, следовательно, сходимости.

Утверждение 3. СФП (с исходным выводом) сходится.

Доказательство утверждения тфоводится следующим образом: а) применением последовательности продукций, которой используется при построении вывода ситуаций £>', £ГеО, строятся ситуации О', О" е О ; б) из утверждения 2 следует существование сйтуашш £)", й"? О: О"—*—>-+£>"- й О" = Л""; в)

последовательном применением правил, использованных в ни. а и б на всех подстановках (за исключением уже использЬванНых в п. а) строим ситуации , О"" е О: О"1 = Dm , О"" = /У, из чего следует I)" - О"", что й требовалось.

Из сходимости СФП вытекает, что если из начального состояния £>„ достигнуто некоторое конечное состояние , то оно единственно.

В качестве модели выполнения Программ, реализованных на основе СФП, предлагается использовать двудольный ориентированный И/ИЛИ граф (7=< У,Е> , где V- множество помеченных вершин, Е - множество помеченных дуг, названный графом продукций. V - иУР, где КР = {т/\г/ = •>/(/),/е^} - множество вершин-задач (вершины типа ИЛИ), ' Р ~ {\р | \р = \'р(р),р еР} - множество Еершин-проду киии (вершины типа И). Функция теап(с), где ее Е.

задает метки на дугах. Для продукции р^Р общего вида, определяемого выражением (1), дуга е строится следующим обраюм: а) если целевая задача /о £ F Принимает в продукции р значение решения

Уо еГЛ , то е = 0/0>ГР), где - Ч/Т/Л, Ур = \*р(р), при этом теап{е) = б) если задача е F входит в условие продукции р со значением решения у^еУ^' , то ^ - (г/?, 1/1), где \'Р = Щ.р), ^ =У/и7), при этом теап(е) = у!' (/= 1,2,...,?;). На графе определяется тип поиска - от цели, стратег ия поиска - в глубину с возвратами.

Сформулируем два понятия, анализ которых составляет содержание структурно-семантического анализа программ. Будем говорить, что программа удовлетворяет условию полноты по значениям, если для Ыждой комбинации значений решений подзадач любой целевой задачи существует прод>кция, описывающая эту комбинацию. Если для каждой комбинации значений решений подзадач такая продукция единственна, то программа корректна по значениям. 15 обоих случаях Предполагается, что вычисления конечны. Удовлетворение указанным условиям обеспечивает существование единственного по значению решения исходной задачи.

Уточнение этих требований проводится на графе продукций, при этом анализ ¡фоводится на отдельных подграфах задач. Для подграфа Сг = {У/,ЕГ), Уг = ЪТ/ иУр' задачи / еГ проводится следующее дополнительное построение: для всех йершнн Vр е УР1 и у/, еКГ7 (/ = 1,2,...,и) таких, что строятся дуги

е = при этом теап{е) — у", где у' е УГ' - особое значение

решения, введенное для дальнейшего анализа, причем У>': у 6 \ ' , *

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

Для графа С' строится максимально полный по значениям граф аг У* = УР\ЛтГ такой, что УГГ = УГ{, а

УР строится таким образом, чтобы входящие в пего вершины-

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

Рш Рь н построенных по ним графов и (I1". Между вершинами-

продукциями определяется отношение соответствия по значениям: «

урь-Нр', если '^Ч/ Ву/': теап({\р,у/)) = теип((ур',у/')), Граф

С полон по значениям если УгреУР* 3уреУР1 \ ур 1-» ур. Если

для всех ур такая вершина-продукция ур единственна, то граф корректен по значениям. В приведенном примере определены: __ • ___ » , , »

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

(р'с) = -{.ШсЫ) => = и'ЛХ0),у1) . * •_ ♦

определяет отношения т.е. граф становится

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

(Ю = (МХь),у'ь)^ = (МХс),Ус)А - (МХЛУ*)=> ' => = (/а(Хи),у'в)

делает граф удовлетворяющим обоим требованиям.

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

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

а)

(/О = ШХьЫ = Ш*сЫ) => = {ШЖ)

{Рь) = (/»№),Л')л = (/е(Хе),у'с)л = (/ДХД=> - ЮТ,).^ )

Рис.1, а) продукции; б) подфаф задачи; в) максимально полный по значениям подграф задачи

Продукшюнный язык высокого уровня, названный языком СФП, разработай с целью предоставления возможности реализации программ в соответствии с моделью СФП. Задачи, программируемые в :пом языке, должны решаться по принципу пошаговой детализации, при этом составные задачи решаются через подзадачи, что описывается продукциями, а простые задачи решаются через процедуры алгоритмическою языка. Синтаксис языка в диссертации представлен в ЬНФ, здесь на рис. 2 показан пример реализации программы пузырьковой сортировки. В секции ДАННЫЕ описываются типы используемых данных, в секциях ЗАДАЧИ и ПРОЦЕДУРЫ описываются со-езаьиые и простые задачи соответственно, в секции ПРАВИЛА приводятся правила продукции. Все продукции в программе независимы. При описании задач указываются типы и прототипы (/'- входной, о -выходной) параметров задачи. В правилах продукций символ подчеркивания показывает анонимную переменную.

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

Для языка СФП проведено количественное оценивание по методике Холе теда. Сравнение полученного уровня языка (3,76) с существующими оценками языков экспериментально подтверждают высокий уровень я тыка СФ11.

1$ четвертой глаие представлено инструментальное средство (ИС) «Софист»; описано функционирование модуля анализа, модуля отладки и тестового выполнения, модуля преобразования программ; представлены реализации практических программ; проводится сравнение ИС «Софист» с существующими средствами.

ПС «Софист» предоставляет пользователю следующие возможности: реа.тн ¡отзывать протрлммы на языке СФП; проводить пошаговую отладку и тестовое выполнение программ; преобразовывать программы с языка СФП на язык Паскаль с формированием шаблонов пли подключением существующих проделу р решения простых задач.

ДАННЫЕ список, элемент ЗАДАЧИ задача сортировки

сортировка _списка(спИсок, список) (¡,о) Иаиме11ьший_элемеш(список, элемент, список) (¡,о,о) ПРОЦЕДУРЫ загрузи гь_лзнчые(список) (о) выгрузить_данные(список, список) (¡,1) элемеит_р_список(спнсок, элемент, список) (и,о) перВый_злемент(сг1нсо1к, элемент, список) (¡,о,о) сравни гь_элемеиты( элемент, элемент) (и) ЦЕЛЬ задача_сортировкн ПРАВИЛА

00 задача соргнровкн = решена <=

загрузи гь_данные(ИсхСпис) = выполнено, сортирот-ка_списка(ИсхСпис, СортСпнс) = выполнена, выфузнть_данн<.1е(ИсхСпнс, СорТСпйс) = ¡¡ычолнено

01 задача_сортиройкИ = не_реи1ена <=

загрузйть_дапные(_) = не_вынолнено

10 сортнровка_сннска(ИсхСппс, СортСпКс) = :поллгна <=

наименьшин_элемент(ИсхСпис, МинЭл, Спис 1) ~ выбрал, сортировка_спнска(Спис1, СортСНис1) = выполнена, элемен 1_П_список(СортСпис 1, МинЭл. СортСпнс) = вставлен

11 сортНропка_списка(МсхСпнс, ИсхСпис) = выполнена <=

наИМсиь1ннй_элемент(ИсхСпис, _) = не_выбран

20 паименыинй_элсмеНт(ИсхСпис, МинЭл, ОстСпис) =■ выбран <=

Нервый_элемент(ИсхСпис, МинЭл, ОстСпис) = определен, наименьшНй_злемент(ОстСинс, Эл1,_) = выбран, сравнить_эДементыШинЭл, Эл!) = менъше_или_равны

21 наименьший _злеМент(ИсхСпйс, МинЭл, ОстСпис) - выбран <=

нервый_злеменг(ИсхСпис, Эл!, СпнсГ) = определен, наименьший_элеМент(Спнс1, МинЭл, ОстСпис 1) = выбран, сравнить элеменш(Эл1, МинЭл) = больше, элемемт_в_список(ОстСпнс1, Эл1, ОстСпис) = вставлен

22 наНменьин!й_элемент(ИсхСпис. МинЭл. ОстСпис) = выбран <-

первыйэлемент^ ИсхСпис, МинЭл, ОстСпис) = определен, наименьший злемент(ОстСт1с, _, _) = не_оыбран наименьший злеметСИсхСпис. _) ~ не выбраи <-= первый элемент^НсхСпис, , _) = ие__опрсделен

Рис. 2, Программа пузырьковой спртироОки

Па эт^мо анализа выполняется проверка соответствия разраба-I ынаемых прел рамм требованиям языка С<1>П. Модуль анализа состо-и, из лексическою, синтаксическою, семантического анализаторов. На первом уровне семантического анализа проверяется соответствие основных синтаксических единиц программы, а также согласованное! г в правилах входных и выходньь параметров задач по алгоритт .му. проплавленному в диссертации. Па втором уровне проводится анализ полнот;.! по значениям и корректности по значениям.

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

Процедуры решения простых задач представляются в виде функции алюрнтмнчеекого языка е фиксированным именем. При '•ц>еобрцзов«лши СФ] Ьт.рограмм.л в программу на алгоритмическом >пыке сохраняются основные структуры ее внутреннего представление.

Экспериментальная опенка эффективности разработанной системы проводилась на практических программах, реализующих обо-лич.,-у экспертной системы. Проверка включала в себя; написание про!рамм; проведение их структурно-семантического анализа с различными вариантами правил; тестового выполнения и отладки нро-Грым; преоорлоепши; программ в программы на языке Паскапь с Формированием шаблонов процедур; наполнение шаблонов и выполнение про; рамм. Полученные результаты подтвердили правильность основных ii0Jt0yi.vni.ri пред.ча! аеыого способа, продемонстрировали сьомства концошуааьион целостности и удобочитаемости 'языка (.'•»■>{(, заключающийся в экономичности и единообразии используе-кыч попяши, удобстве ьосприяшл программ, а также показали прп-ненми.->1.1ь р.а»работашЮ1Ч1 ПС и нре»ло:кенных методик.

I рави-.инс НС яС'офп.п)! с существующими средствами, пред ст<!1'|,е1И||.1мп I. 1.1.1, покачало чю ра¡раГнпка средств реали'мшии про' грамм. 1Ч".-д(>с1е.>,|.1-ои!.гх вотежнас!}) и.< анализа и ш¡явления ее.мзнкт чески* •Чч-.'ГК, нп-икн.» нюаимнпным направление») инк т^он."тич .• ских, ток я проммчески < исследовании

-

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

И приложении:* предегн'лены следующие материалы: •

- примеры программ, реализованных с нсполь (оваииом ■:} ще-ствутошнх средств;

- тексты программ на языке СФП. рсаммуюпп'х < Зо'гпчк;--портной системы;

- примеры результата преобразования программы пу !ыр:,ко"оП сортировки с языка СФП в программу на языке Паскаль с формированием шаблонов процедур. заполнения шаблонов процедур, программы пузырьковой сортировки на языке Паскаль.

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

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

1) Посгроенп Графовая модель иыполнеши протрамм, регппо. ванных на основе СФП, допускающая т- • анализ и нриверк;. нынолннмости условий полноты по значениям и корректности по значениям,

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

4) Предложен язык СФП, предназначенный для реализации программ решения задач по принципу пошаговой детализации и соответствии <: моделью СФП.

5) Разработаны методики реализации и отладки программ ил языке СФП. Они включают и себя: способы создания прпзнл. решаюших отдельные задачи; схемы правил часто встреч? и >--шихсг. ;:'лач; описание способа тестового выполнения программы; описание последовательности действий по отладке.

6)Созд?;.о пнет, ументальт-ое средство «Софист», под"ер.кт;-паюшее реали ппито программ на язык» СфП, позвол/юг^с

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

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

РАБОТЫ

1. Гаевой Б.А. Общий подход к решению задачи диагностики неисправностей. - Ден. ВИНИТИ, 1997, № 1377-В97.

2. Балтрашевпч В.Э., Гаевой В.А. Компиляция продукционной модели знаний в экспертных системах // Матер. 6-й Между-нар. кош}]. «Знание - Диалог - Решение» («KDS - 97»), -Ялта, 1997,-С. 131-135.

3. Гаевой В.А. Компиляция системы функциональных продукций как способ генерации кода прикладных программ императивных языков программирования // Микроэлектроника и информатика — 98. Всерос. межвуз. науч.-техннч. конф. студентов и аспирантов: В 2 ч. Тезисы докладов. Ч. 2. - МИЭТ, 1998.-С. 20.

4. Гаевой В.А. Об использовании продукционной системы для автоматизации разработки программ // (>-я Нац. конф. по искусе! и. интеллекту РАН - КИИ-98. - Путщпш, 1998. - С. 202-1.

5. Гаевой В.А. Способ реализации программ но принципу по-шатотой детализации // Матер. 1-й Всероссийской научно-технической конференции ^Компьютерные технолотии в науке, проектировании и производстве». Тезисы докладов. -Нижний Повюрод, 1999. -С. 18.

6. Балтрашештч В.Э., Гаевой В.А. Применение системы функциональных продукций /Тля изучения продукционной модели представления знаний // Матер. 5-й Междунпр. конф. «Со-bj.eMeiiiitii технологии обучения^. - Саикт-1 клербург, 1999.

С. 92.

61: УУ "О/^и^б ~ /.

/

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (ЛЭТИ)

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

Гаевой Виталий Анатольевич

РАЗРАБОТКА СПОСОБА И СРЕДСТВ РЕАЛИЗАЦИИ ПРОГРАММ НА ОСНОВЕ СИСТЕМЫ ФУНКЦИОНАЛЬНЫХ ПРОДУКЦИЙ

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук у

Санкт-Петербург - 1999

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................................5

ГЛАВА 1. ПРИМЕНЕНИЕ СИСТЕМ ПРОДУКЦИЙ В РЕАЛИЗАЦИИ

ПРОГРАММ.........................................................................11

1.1. Понятие программы. Способы реализации программ.........................11

1.1.1. Развитие представлений о программе..........................................11

1.1.2. Подходы к реализации программ, использующие декларативную концепцию........................................................................... 14

1.1.2.1. Языки и системы спецификаций..............................................15

1.1.2.2. Методы автоматического синтеза программ...............................19

1.1.2.3. Языки программирования высокого уровня................................23

1.1.3. Системы продукций в реализации программ.................................26

1.2. Продукционные средства реализации программ..............................27

1.2.1. Язык Снобол.........................................................................27

1.2.2. Язык Рефал............................................................................29

1.2.3. Метод гиперпрограммирования.................................................30

1.2.4. Псевдоязык Кант....................................................................32

1.2.5. Задачи, методы и средства семантической теории программ. Анализ семантики продукционных программ..........................................35

1.3. Продукционные модели.............................................................38

1.3.1. Система продукций.................................................................39

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

1.3.3. Расширенные модели систем продукций.......................................42

1.3.3.1. Реляционная модель..............................................................42

1.3.3.2. Алгебраическая модель..........................................................43

1.3.3.3. Использование расширенных моделей в качестве формальной модели программ....................................................................44

Основные результаты по главе 1 .........................................................45

ГЛАВА 2. ПРОДУКЦИОННАЯ МОДЕЛЬ ПРОГРАММЫ........................47

2.1. Основные содержательные понятия...............................................47

2.2. Система функциональных продукций.............................................50

2.2.1. Описание модели....................................................................50

2.2.2. Исследование свойств модели....................................................53

2.3. Модель выполнения программы....................................................59

2.3.1. Граф продукций......................................................................59

2.3.2. Структурно-семантический анализ программы...............................63

2.4. Концептуальная модель программы языка реализации программ...........68

2.4.1. Решение простой задачи, описание типов данных...........................69

2.4.2. Описание модели....................................................................71

Основные результаты по главе 2.........................................................72

ГЛАВА 3. ЯЗЫК РЕАЛИЗАЦИИ ПРОГРАММ СФП...............................74

3.1. Описание языка........................................................................74

3.1.1. Основные понятия...................................................................74

3.1.2. Описание синтаксиса...............................................................76

3.1.3. Пример программы..................................................................79

3.2. Методика реализации программ ....................................................81

3.3. Методика отладки программ.........................................................85

3.4. Количественное оценивание языков реализации программ..................89

3.4.1. Методика Холстеда..................................................................89

3.4.2. Результаты оценивания.............................................................90

Основные результаты по главе 3.........................................................94

ГЛАВА 4. ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО РЕАЛИЗАЦИИ

ПРОГРАММ «СОФИСТ».........................................................95

4.1. Особенности современных инструментальных средств

программирования..................................................................95

4.2. Общее описание инструментального средства «Софист».....................96

4.3. Анализ и внутреннее представление программ.................................99

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

4.3.2. Семантический анализ............................................................101

4.4. Отладка и тестовое выполнение программ......................................105

4.5. Представление терминальных процедур и преобразование СФП-

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

4.6. Реализация и анализ практических программ..................................115

4.6.1. Описание программ................................................................115

4.6.2. Структурно-семантический анализ программ................................ 116

4.6.3. Сравнение с программами на языке Паскаль.................................118

4.7. Особенности разработанного способа, сравнительный анализ средств

реализации программ..............................................................119

Основные результаты по главе 4........................................................122

ЗАКЛЮЧЕНИЕ.............................................................................124

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ...................................127

ПРИЛОЖЕНИЕ А.........................................................................136

ПРИЛОЖЕНИЕ Б..........................................................................144

ПРИЛОЖЕНИЕ В..........................................................................150

ВВЕДЕНИЕ

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

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

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

зи с этим особое внимание стало уделяться декларативным средствам реализации программ, в которых описываются свойства требуемого результата, но не указывается способ его получения; подходит любой способ получения требуемого результата, обладающий указанными свойствами. При использовании декларативных средств программист может сосредоточиться на описании внутренних связей и особенностей решаемых задач. Исследования в этом направлении вели Б. Дисков, Р. Ковальски, А. Колмероэ, Дж. Маккарти, Дж. А. Робинсон и др. С точки зрения практических результатов, созданы такие известные языки программирования, как Пролог и Лисп. В нашей стране данную проблематику исследовали В. Н. Агафонов, В. Ф. Турчин, Э. X. Тыугу и др. Были разработаны язык концептуального программирования УТОПИСТ, метаалгоритмический язык Рефал и др.

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

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

области ведут такие специалисты, как К. А. Р. Хоар, Дж. В. Беккер, В .Б. Борщев, Ю. Л. Ершов, В. Н. Касьянов, Ю. П. Кораблин, В. Е. Котов. В результате исследований предложены методы и средства, позволяющие выявлять в программах семантические ошибки и способствующие, таким образом, повышению их качества. Поэтому разработка способов и средств, позволяющих анализировать программы и выявлять в них семантические ошибки, является актуальной проблемой.

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

Задачи исследования:

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

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

- разработка языка реализации программ;

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

- проверка достоверности полученных результатов на примерах решения практических задач.

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

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

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

2) Построена графовая модель выполнения программ, реализованных на основе СФП, допускающая их анализ и проверку выполнимости условий полноты по значениям и корректности по значениям.

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

4) Предложен язык СФП, предназначенный для реализации программ решения задач по принципу пошаговой детализации в соответствии с моделью СФП.

5) Разработаны методики реализации и отладки программ на языке СФП. Они включают в себя: способы создания правил, решающих отдельные задачи; схемы правил часто встречающихся задач; описание способа тестового выполнения программы; описание последовательности действий по отладке.

6) Создано инструментальное средство «Софист», поддерживающее реализацию программ на языке СФП, позволяющее проводить их отладку и тестовое выполнение, а также преобразовывать СФП-программы в программы на алгоритмическом языке.

Научная новизна полученных результатов заключается в следующем:

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

2) Модель выполнения программ, в качестве основы которой выступает двудольный ориентированный И/ИЛИ граф, допускает их автоматиче-

ский анализ и выявление структурной неполноты и структурной некорректности.

3) Продукционный язык СФП позволяет реализовывать программы в соответствии с моделью СФП и предусматривает проведение их структурно-семантического анализа.

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

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

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

3) Предложены методики реализации и отладки программ на языке СФП, которые раскрывают особенности предлагаемого способа и способствуют созданию требуемых программ.

4) Создано инструментальное средство «Софист», предоставляющее возможность реализовывать программы на языке СФП.

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

Работа выполнялась в рамках госбюджетной НИР ГБ2/МО-15. Разработанный язык СФП и инструментальное средство «Софист» использованы в учебных процессах СПбГЭТУ, СПбГАМТУ при проведении лабораторных работ по дисциплине «Базы данных, знаний и экспертные системы».

Апробация результатов проведена на следующих конференциях: 6-я Международная конференция «Знание - Диалог - Решение», Ялта, 1997; Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика - 98», Москва, 1998; 6-я Национальная конференция по искусственному интеллекту РАН, Пущино, 1998; 51-я научно-техническая конференция профессорско-преподавательского состава СПбГЭ-ТУ, Санкт-Петербург, 1998; 1-я Всероссийская научно-техническая конференция «Компьютерные технологии в науке, проектировании и производстве», Нижний Новгород, 1999.

Доклад по теме диссертационной работы занял второе место на конкурсе работ аспирантов по секции «Автоматизированные системы, методы моделирования и оптимизации», проходившем на Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 98» (Москва, 1998).

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

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

1) Формальная модель программы продукционного типа, названная системой функциональных продукций (СФП).

2) Графовая модель выполнения программ, реализованных в соответствии с моделью СФП.

3) Продукционный язык реализации программ, названный языком СФП.

4) Инструментальное средство «Софист», поддерживающее реализацию программ на языке СФП.

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

ГЛАВА 1. ПРИМЕНЕНИЕ СИСТЕМ ПРОДУКЦИЙ В РЕАЛИЗАЦИИ

ПРОГРАММ

1 Л. Понятие программы. Способы реализации программ

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

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