Національна академія наук України

Інститут кібернетики імені В. М. Глушкова

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

ЄРШОВ Сергій Володимирович

УДК 51:681.3.06

МЕТОДИ І ЗАСОБИ ВІЗУАЛЬНОГО ОБ'ЄКТНО_ОРІЄНТОВАНОГО

ПРОЕКТУВАННЯ ПРОГРАМНИХ СИСТЕМ

НА ОСНОВІ КОНТУРНИХ Р_СХЕМ

01.05.03 — математичне та програмне забезпечення

обчислювальних машин і систем

Автореферат дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ 1998

Дисертацією є рукопис.

Робота виконана в Міжнародному науковому центрі технології програмування ТЕХНОСОФТ Національного агентства з питань інформатизації при Президентові України та Національної академії наук України.

Науковий керівник: доктор фізико-математичних наук,

професор ВЕЛЬБИЦЬКИЙ Ігор Вячеславович,

Міжнародний науковий центр технології програмування

ТЕХНОСОФТ Національного агентства з питань

інформатизації при Президентові України та

Національної академії наук України

Офіційні опоненти: доктор фізико-математичних наук

ПРОВОТАР Олександр Іванович,

провідний науковий співробітник

Інституту кібернетики ім.В.М.Глушкова НАН України,

кандидат фізико-математичних наук

ДЕРЕЦЬКИЙ Валентин Олександрович,

провідний науковий співробітник

Інституту програмних систем НАН України

Провідна установа: Київський національний університет

імені Тараса Шевченка, факультет кібернетики,

кафедра математичної інформатики.

Захист відбудеться "11" грудня 1998 р. о 11 год. на засіданні спеціалізованої вченої ради Д .194.02 при Інституті кібернетики імені В. М. Глушкова НАН України за адресою:

252022 Київ 22, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись у науково-технічному архіві інституту.

Автореферат розісланий "4" листопада 1998 р.

Учений секретар

спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність. Трудомісткість процесу програмування зростає випереджаючими темпами в міру збільшення розмірів програм, що складаються. Великі програми, які складаються з десятків та навіть сотень тисяч машинних команд, потребують для своєї розробки та експлуатації додаткових засобів. Складність сучасних обчислювальних систем, а також висока вартість створення якісного та надійного програмного забезпечення ЕОМ стимулюють розвиток теоретично обгрунтованих методів та засобів розробки програмних систем. Особливо актуальним є застосування таких методів та засобів при об'єктно-орієнтованому підході до створення програмних систем.

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

Візуальне програмування та візуалізація програмного забезпечення призначені для поліпшення процесу програмування, особливо для програмістів-непрофесіоналів. Формалізовані візуальні мови набули широкого використання при проектуванні та розробці складних програмних систем. Вони є складовою частиною CASE_технології.

Проблеми традиційного неітеративного життєвого циклу програмного забезпечення, який не враховує потреб повторного використання та уніфікованої інтеграції фаз розробки програмного забезпечення (ПЗ), призвели до створення об'єктно_орієнтованого аналізу, об'єктно_орієнтованого проектування та об'єктно_орієнтованого програмування.

Об'єктно-орієнтовані методи розробки програмного забезпечення широко застосовують візуальні мови для аналізу, проектування, реалізації, супроводження та повторного використання програмних систем. Об'єктно_орієнтований підхід (ООП) стосовно розробки ПЗ записується формулою

ООП = об'єкти + класи + наслідування.

Другий з вищеперелічених компонентів із заміною слова "класи" на "типи" є характерним також для теорії абстрактних типів даних.

Використання об'єктів та структур даних як основи для поділу системи на компоненти дає можливість покращити такі характеристики якості програмних систем як сполучуваність, можливість повторного використання та стабільність. Сполучуваність не може бути забезпечена, якщо комбінуються дії, які використовують неузгоджені структури даних. Для будь-якої програми, що використовує нетривіальні дані, неможливо побудувати придатні для повторного використання модулі, якщо вони відбивають тільки дії та не враховують дані. При об'єктно_орієнтованому підході дані групують разом з діями, створюючи узгоджене представлення об'єктів, що розширюється. Об’єкти та структури даних, що розглядаються на різних рівнях абстракції, – це найстабільніший елемент програмної системи.

В нинішній час методи та засоби візуального проектування об'єктно-орієнтованих програмних систем, розподілених у мережах ЕОМ, детально не розроблені. Необхідність розв'язання цієї проблеми обгрунтована виникненням розподілених програмних систем у різних галузях народного господарства України.

Актуальність цього дисертаційного дослідження, присвяченого розробці теоретичних основ візуальних мов специфікації розподілених об'єктно-орієнтованих програмних систем, полягає у тому, що зазначені візуальні мови дадуть змогу значно збільшити продуктивність праці при розробці програмного забезпечення, що функціонує в мережах ЕОМ.

Об'єкт та предмет дослідження. Об'єктом дослідження дисертаційної роботи є візуальні мови, призначені для специфікації розподілених об'єктно-орієнтованих програмних систем.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження виконано в межах –

міжнародного проекту INCO-COPERNICUS 96-0114 "ASystem for the Development of National Network of Ukraine" по розділу 6. "Information Technology" програми "RTD in the Field of Cooperation with Third Countries and International Organizations – INCO" Європейського Союзу, проекту INTAS-93-1702 "Efficient Symbolic Computing" Європейського Союзу; –

науково-дослідницьких робіт Державного комітету з питань науки та технологій України 2/980-97 "Розробка та впровадження розподіленої експертної системи для керування глобальними комп'ютерними мережами", 06.09.01/207-93 "Создание визуальной системы управления информационно-компъютерными сетями", науково_дослідницьких робіт Національної академії наук України (продовження робіт у Державному комітеті з питань науки та технологій України) 06.02.03/068-92 "Разработка технологических инструментальных средств разработки программного обеспечения с использованием методов искусственного интеллекта и объектно_ориентированного программирования", 06.02.03/066-92 "Современные технологии программирования на основе визуальных методов представления информации и экспертных систем".

Мета та задачі дослідження. Метою даного дисертаційного дослідження є розробка математичного апарату контурних Р_схем, які є засобом візуального проектування об'єктно_орієнтованих програмних систем, а також розробка візуальної мови специфікації вищезазначених систем.

У межах даної роботи були поставлені та розв'язані такі задачі: –

дослідити створені раніше візуальні мови специфікації типів даних та їх формальні моделі; –

дослідити візуальні мови для опису розподілених програмних систем; –

розробити концепцію візуального підходу до проектування об'єктно-орієнтованих розподілених програмних систем; –

визначити базові поняття та класи контурних Р-схем; –

розробити представлення декларативної семантики контурних Р_схем на основі графової алгебри процесів; –

створити алгебру для класу регулярних контурних Р_схем; –

розробити аксіоматичну семантику регулярних контурних Р_схем; –

розробити візуальну мову специфікації структури класів об'єктно-орієнтованих програмних систем на основі графового опису типів даних; –

визначити протоколи синхронізації класів та дослідити властивість припустимості наслідування протоколів; –

описати практичну реалізацію програми-редактора контурних Р_схем; –

описати етапи візуального проектування з використанням контурних Р-схем на прикладі проектування мультіагентної системи для керування мережами TCP/IP; –

описати середовище для підтримки функціонування об'єктно_орієнтованих розподілених систем в гетерогенних мережах TCP/IP.

Методи дослідження. Методологічні, методичні та математичні аспекти візуального об’єктно-орієнтованого проектування формувалися автором під впливом наукових праць ряду вітчизняних учених: В.М.Глушкова, К.Л.Ющенко, І.В.Вельбицького, О.А.Летичевського, Ю.В.Капітонової, І.В.Сергієнко, І.М.Парасюка, О.І.Провотаря, А.В.Анисимова, П.І.Андона, В.Н.Редька, а також закордонних учених А.П.Єршова, І.В.Поттосина, Е.Х.Тиугу, М.Броя, Г.Буча, Н.Вірта, Р.Мільнера, Ч.Хоара у галузі технології програмування, візуального програмування, об’єктно-орієнтованого проектування програмних систем, теорії взаємодіючих процесів та семантики мов програмування.

Основою проведених досліджень стали ідеї та методи об'єктно-орієнтованого проектування програмних систем, теорії взаємодіючих процесів, комунікації та координації в розподілених системах, теорії алгебраїчних систем, теорії графів та математичної логіки. Реалізація програмної підтримки контурних Р-схем спиралася на досвід використання систем візуалізації програмного забезпечення та принципи Р-технології програмування.

Наукова новизна дисертаційного дослідження полягає в розробці математичного апарату контурних Р-схем як адекватного засобу візуального проектування об'єктно-орієнтованих розподілених програмних систем. Даний математичний апарат забезпечує –

формалізацію визначень контурних Р-схем як подальшого розвитку Р-технології програмування для цілей об'єктно_орієнтованого програмування та проектування; –

розробку концепції візуальної мови та об'єктно_орієнтованого проектування розподілених програмних систем; –

опис декларативної та аксіоматичної семантики контурних Р_схем з метою формалізації різних аспектів поведінки об'єктно_орієнтованих програмних систем; –

створення алгебри структур даних на основі контурних Р-схем та розробку засобів завдання структурних властивостей ієрархії класів, що використовуються при проектуванні об'єктно-орієнтованих програмних систем; –

визначення протоколів синхронізації класів об'єктів на основі контурних Р-схем та побудові алгоритму перевірки припустимості її наслідування, що дає змогу забезпечити несуперечність властивостей поведінки класів при їх інкрементальній спеціалізації; –

розробку наскрізної методології візуального об'єктно_орієнтованого проектування розподілених об'єктно_орієнтованих програмних систем.

Практична цінність результатів роботи полягає в розробці методів та засобів комплексного проектування об'єктно_орієнтованих розподілених систем на основі контурних Р_схем. Положення, які стали основою даного підходу, є базисом при створенні інструментального середовища для розробки об'єктно_орієнтованих систем, що працюють у мережах TCP/IP. Це інструментальне середовище застосовується при побудові розподілених систем для керування та збору інформації в мережах ЕОМ.

Особистий внесок пошукувача: –

введення базових понять та формалізація контурних Р-схем як адекватного засобу для специфікації різних властивостей об'єктно_орієнтованих систем; –

розробка концепції уніфікованої візуальної мови, що застосовується на всіх стадіях об'єктно-орієнтованого проектування програмних систем; –

розробка декларативної та аксіоматичної семантики контурних Р_схем як засобу аналізу властивостей класів об'єктів у процесі об'єктно_орієнтованого проектування програмних систем; –

розробка алгебри структур даних та формалізація графів структури класів об'єктів засобами контурних Р-схем; –

визначення протоколів синхронізації класів та побудова алгоритму перевірки припустимості наслідування протоколів при розробці ієрархічної системи класів об'єктно-орієнтованої розподіленої системи; –

визначення інкрементальної модифікації протоколів синхронізації класів на основі візуальної мови; –

розробка інтерактивного графічного редактора контурних Р_схем; –

розробка середовища для підтримки розподіленої взаємодії об'єктно-орієнтованих програмних систем, створених на основі контурних Р-схем; –

розробка наскрізної методології візуального об'єктно_орієнтованого проектування, що містить засоби специфікації структурних аспектів та аспектів поведінки розподіленої програмної системи.

Апробація роботи. Про основні положення дисертаційної роботи були зроблені доповіді на міжнародних конференціях Joint Modular Languages Conference JMLC'97 (Австрія, Лінц, 19-21 березня 1997 р.); Second International Conference on Object-Oriented Technology WOON'97 (Санкт-Петербург, 19_ вересня 1997 р.); 42 Internationales Wissenschaftliches Kolloquium (Німеччина, Ільменау, 22-25 вересня 1997 р.); Psychology of Programming Interest Group 7th Annual Workshop PPIG-7 (Великобританія, Единбург, 4_ січня 1995 р.); на міжнародній конференції "Технология программирования 90-х" (Київ, 14-17 травня 1991 р.); 3-й українській конференції "Автоматика-96" (Севастополь, 9-14 вересня 1996 р.); на семінарі "Новые информационные технологии и инструментально-технологические средства поддержки принятия решений" (Кацивелі, 21_ грудня 1992 р.); на семінарах Наукової ради з проблеми "Кібернетика" НАН України.

Практична реалізація ідей, що покладені в основу дисертаційного дослідження, були продемонстровані на всесвітніх виставках Сebit'96 та Cebit'97 (Німеччина, Ганновер) як експонат на стенді України.

Публікації. Основні положення дисертаційної роботи опубліковані в 13 роботах.

Структура та обсяг дисертації. Дисертація складається з вступу, чотирьох глав, висновків, списку використаної літератури. Загальний обсяг роботи складає 163 сторінки. Робота містить 49 рисунків, 5 таблиць. Список використаної літератури налічує 122 найменування.

ЗМІСТ РОБОТИ

У першому розділі проводиться аналіз засобів візуалізації типів даних, структур даних, об’єктно-орієнтованих та розподілених систем. Сформульована концепція візуального підходу до об’єктно-орієнтованого проектування програмних систем. Зміст її полягає в тому, що візуальна мова для проектування об'єктно-орієнтованих розподілених систем повинна мати такі можливості: –

засоби розробки архітектури паралельної обробки; –

способи представлення ієрархії наслідування класів; –

засоби відображення відношення використання між об'єктами; –

ієрархічні візуальні форми опису, які дозволяють зменшити складність діаграм шляхом деталізації окремих елементів з використанням тієї ж самої системи позначень; –

візуальні засоби опису поведінки системи у термінах подій; –

методи верифікації поведінки згідно з формальними специфікаціями; –

методи забезпечення несуперечності опису різних аспектів розподілених об'єктів.

Аналіз підходів до опису об'єктно-орієнтованих та розподілених систем демонструє той факт, що не існує візуальної мови, яка відповідає усім переліченим вимогам. Більше того, не існує єдиної візуальної нотації, яка дозволяє описувати найважливіші аспекти об'єктно-орієнтованої системи – аспекти поведінки, структурні аспекти та модель даних, які лежать в основі об'єктно-орієнтованої системи.

Як предмет дослідження вибираються запропоновані автором контурні Р-схеми, які є розвитком ідей, покладених в основу Р-технології програмування. Порівняно із звичайними Р_схемами застосування контурних Р_схем для задач об'єктно-орієнтованого проектування має такі переваги:

контурні Р-схеми відображають наочно у вигляді єдиного рисунка вкладеність, ієрархію та модульність системи об'єктів;

контурні Р-схеми більш економічні для представлення переходів між станами об'єктів;

контурні Р-схеми більш економічні при проектуванні множини станів об'єктів;

теорія контурних Р_схем будується на основі використання операції паралельної композиції.

У другому розділі викладені базові поняття контурних Р-схем, розроблені декларативна та аксіоматична семантики контурних Р-схем як засоби аналізу властивостей класів об’єктів у процесі об’єктно-орієнтованого проектування. Контурні Р-схеми є ієрархічним розширенням Р_схем, причому контури можуть представляти стани об'єктів, а дуги задають можливі переходи між станами.

Контурною Р-схемою називається направлений граф, дуги якого зображуються тільки за допомогою горизонтальних та вертикальних ліній. При цьому вершини (стани) зображуються у вигляді прямокутників з округленими кутами, а прямокутник кожного підстану стану s зображується всередині прямокутника s. Стани (вершини) можуть бути типу АБО, так звані _стани, або типу І, так звані -стани. _стани зображуються прямокутниками, внутрішня область яких розділена горизонтальною пунктирною лінією. Кожен елемент такого розгалуження задає паралельний компонент -стану.

Коли поточним є -стан контурної Р-схеми, то одночасно поточним є один та тільки один з його безпосередніх підстанів. Кожен не елементарний -стан має спеціальний безпосередній підстан, так званий початковий стан, який графічно зображується на контурній Р-схемі як самий лівий підстан -стану. Наприклад, L є _станом з паралельними компонентами K та J. Стан B є початковим підстаном стану A (рисунок).

Рисунок. Контурна Р-схема

Переходи між станами представлені графічно спрямованими дугами (з шматкових вертикальних та горизонтальних сегментів) та зазначені парою множин подій. Одна з множин є "перемикачем", а інша — "дією". "Перемикач" завжди зображується зверху над горизонтальним сегментом переходу, а "дія" — під горизонтальним сегментом відповідного переходу.

Події інтерпретуються як сигнали, що надходять від середовища, у якому виконується контурна Р-схема. Перехід є виконуваним, якщо множина подій перемикача є підмножиною подій, які надійшли від середовища. Після виконання переходу t множина вже встановлених подій середовища збільшується на множину подій дії t.

Визначення. Контурною Р-схемою R називається набір з восьми елементів (S, , T, in, out, E, , , ), де

S — непуста конечна множина станів;

— функція ієрархії, яка визначає для кожного стану

множину його безпосередніх підстанів; нерефлексивне та рефлексивне транзитивні замикання позначаються + та * відповідно; описує таку деревовидну структуру:

1) наявний унікальний стан , такий що , який позначається rootR;

2) для всіх ;

3) якщо , , то означає, що для будь-яких ;

Т — конечна множина переходів;

функція, яка визначає результуючий стан переходу;

функція, яка задає початковий стан переходу; функції in та out такі, що ((t))=, та для будь-яких ; для двох станів s та s', найменший спільний предок s та s', який позначається (s,s'), визначається як стан , такий, що , та для будь-якого s'', такого, що ; (t) є скороченим позначенням для (in(t),out(t));

E — конечна множина подій;

— це функція розмітки переходів; та означають перший та другий компоненти відповідно;

— це часткова функція ініціалізації, яка визначає для кожного не елементарного -стану ініціальний стан, тобто (s)(s) для будь-якого s, такого, що (s)= та ;

: S{, } означає функцію типу стану.

Припустимо, що , який називають ініціальним переходом, означає . Відношенням послідовної виконуваності називається таке відношення , що тоді й тільки тоді, коли outR(t')R{s:s+R((t)), inR(t)*R(s)} та тоді й тільки тоді, коли . Відношенням незалежної виконуваності є таке відношення , де якщо та тільки якщо або R(R(t),outR(t'))=outR(t'), або R(R(t),outR(t')) є -станом та .

Структурою переходів контурної Р-схеми R називається четвірка . Визначено правило побудови контурної Р-схеми R, яка є породжуваною з структури переходів по sym символу.

Теорема 1. Для контурної Р-схеми R з станами, які досягаються зверху-униз, якщо , то .

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

Розглянемо підмножину контурних Р-схем RС1RС, у якій перетинання контурів дугами заборонено. Множину поміток Lab контурних Р_схем RС1 використаємо для позначення префіксних операторів графової алгебри процесів GPA1. Сигнатура (GPA1) вміщує оператори, визначені над множиною Proc процесів:

(GPA1) {0:Proc} {l:ProcProc|lLab} {+:ProcProcProc} {||:ProcProcProc} {[]:ProcProcProc} {XVar:Proc} {<X|>:Proc},

при цьому 0 – це нульовий процес; для термів , 1 та 2 RC1 , l – це префікс дії; 1+2 – недетермінований вибір, 1||2 – операція злиття, яка комбінує дії 1 та 2 або синхронізує їх; 1[2] – це операція уточнення стану, причому стан, який визначається термом 1, уточнюється термом 2 таким чином, що дії 2 можуть здійснюватися тільки тоді, коли не виконуються дії 1. XVar – це рекурсивна змінна, а <X|> – процес-константа, який задає зв’язування рекурсивною специфікацією по рекурсивній змінній X. Процес-константа задає рішення для X при . Змінна X називається вільною, якщо вона не є зв’язаною. Терм P називається замкнутим, якщо до нього не входять вільні змінні, інакше він називається відкритим термом. Рекурсивна специфікація являє собою множину рекурсивних рівнянь , у якому тільки змінні множини входять як вільні змінні до кожного i.

Побудовано відображення Р-схеми R класу RС1 у замкнутий терм алгебри процесів <|>. Відображення здійснюється рекурсивною функцією , яка визначається таким чином:

Функція з аргументом s задає множину рекурсивних рівнянь, які відповідають контуру s Р-схеми, та визначається таким чином:

.

Семантику графової алгебри процесів GPA1 задано за допомогою представлення терму P у вигляді системи переходів (Proc, Lab, , ), яка позначається IGPA().

Теорема 2. Якщо RRC1 – контурна Р-схема, то IRC(R) ізоморфна .

З’ясовано, що система переходів Р-схеми R та система переходів терму є ізоморфними. Це доводить правильність побудови функції перетворення , яка дає можливість представлення алгебраїчної семантики контурних Р_схем.

На множині базових та спеціальних структур контурних Р-схем введено операції послідовного та вкладеного поєднання та .

Припустимо , – довільні структури, =(,) – множина операцій. Припустимо , , де – будь-яка операція з , . Будемо називати множиною регулярних контурних Р-схем , де i=0,1,..., та – замикання множини щодо операцій .

Множина регулярних Р-схем, яка має всюди визначені операції , являє собою універсальну алгебру =<,>. Системою утворюючих цієї алгебри виступає множина елементарних структур . Алгебра регулярних контурних Р-схем =<,> є конечно-породженою алгеброю, тобто , де множина елементарних структур Р-схем – конечна система утворюючих алгебри . При породженні множини елементарних структур застосовується додавання нових дуг до структури та береться як функція розмітки переходів , де E – конечна множина подій.

Позначимо елементарну базову структуру sm,n, де m – кількість прямих, n – кількість зворотних дуг, i, , j, , – умови проходження відповідних дуг (можуть бути відсутні); , , , , – дії (оператори). Тоді

.

Аналогічно виведено правила (аксіоми) для спеціальної структури та для операцій над довільними структурами: послідовного з’єднання, послідовного та паралельного вкладень.

Нехай Inv – це інваріант конкретного класу об’єктів, та – відповідно перед- та пост-умови методу Met цього класу, метод Met реалізований на основі контурної Р_схеми . Клас є коректно реалізованим, якщо для кожного методу Met, що експортується в даному класі і не є конструктором класу, та для множини припустимих аргументів : , де – контурна Р-схема реалізації методу Met класу. Таким чином, розроблена аксіоматична семантика дає можливість перевірити коректність реалізації методів класів на основі контурних Р_схем.

У третьому розділі побудована візуальна мова специфікації структури класів об’єктно-орієнтованих програмних систем на основі графового опису типів даних, досліджені протоколи синхронізації класів та властивість припустимості наслідування протоколів.

Графи структури класів – це контурні Р-схеми, які застосовуються для завдання класів та відношень між ними. Вершини відповідають класам. Визначають два типи вершин. Вершини, які мають складені компоненти (_вершини) називаються альтернативними вершинами. Вони задають абстрактні класи, які мають підкласи, але не мають екземплярів. Зазначені вершини без складених компонент називаються конструктивними вершинами. Вони являють собою конкретні класи, для яких є екземпляри класу, але немає підкласів.

Словник класів задається набором , де VC – множина конструктивних вершин; VA – множина альтернативних вершин; VT – це підмножина VC, яка називається термінальними вершинами; конечна непорожня множина (де ) називається множиною вершин класів; VS – кінцева множина синтаксичних вершин; – кінцева множина міток дуг; EC – це тернарне відношення на , яке називається конструктивними дугами; – кінцева множина міток конструктивних дуг; EA – це бінарне відношення альтернативної належності на ; ES – бінарне відношення синтаксису на . Функція відображає кожну вершину V в унікальне натуральне число, а функція відображає кожен елемент в унікальне натуральне число.

Р-алгеброю структур даних називається система , де — множина структур даних; — безкінечна рахункова множина операцій, яка складається з операцій послідовного з’єднання , сімейства базових операцій, сімейства = технологічних операцій, сімейства операцій вкладення в k-ту дугу. Таким чином, . Позначимо множину регулярних Р-схем структур даних над множиною елементарних структурних схем.

Визначенням Р-типу даних називається четвірка , де — ім’я Р-типу даних; D — конечна множина імен типів даних, які визначаються (конструюються); E — конечна множина імен елементарних типів (причому ); P — конечна множина рівностей виду A=B, де , . P називається також системою правил, а елементи P — правилами. Якщо в правій частині рівності , де P — конечна множина імен типів-параметрів, то визначення називається визначенням родового Р_типу даних. Правій частині B рівностей завжди відповідає деяка множина структурних схем.

Теорема 3. Кожному словникові класів у нормальній формі D можливо поставити у відповідність визначення Р-типу даних Def(T)=(T,D,E,P), таке, що L(D)=L(Def(T)).

Будь-який словник класів може бути однозначно представлений за допомогою відповідної йому Р-структури даних, яка в свою чергу може бути ефективно представлена за допомогою існуючих конструкторів типів процедурних мов програмування (Сі, Модула-2, Паскаль). При цьому і словник класів у нормальній формі, і відповідна цьому Р–структура даних задають одну і ту саму множину значень об’єктів, оскільки їх мови еквівалентні.

Побудовано підхід до наслідування протоколів синхронізації класів, який грунтується на концепції правил наслідування. Правила наслідування протоколів мають вигляд

protocol_pprotocol_q.

Припустимо p та q – протоколи, задані за допомогою Р-схем, а tree_p та tree_q – дерева операцій протоколів p та q. Протокол q наслідує протокол p (позначається як p inherit q), якщо tree_q може бути побудоване по дереву tree_p шляхом конечного повторення таких трьох кроків (так званих кроків інкрементальної модифікації протоколів):

1. Вилучити (цілком) піддерево subtree_p з tree_p, причому R –вершина subtree_p.

2. Створити дерево протоколу subst_tree, яке вміщує subtree_p.

3. Модифікувати tree_p, додавши subst_tree у ту саму вершину, з якої було вилучено піддерево з вершиною R, тобто помістити subst_tree у початкову позицію subtree_p в дереві tree_p (крок інкрементальної модифікації).

теорема 4. p inherit q, якщо та тільки якщо існує відображення f, таке, що

а) f є взаємно однозначним відображенням з tree_p до tree_q, де tree_p (відповідно tree_q) – дерево протоколу p (відповідно q);

б) f(V)V для кожної вершини Vtree_p;

в) UVXf(U)f(V)X для будь-яких U,Vtree_p та X{L,R}.

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

У четвертому розділі описано інтерактивний графічний редактор контурних Р-схем, який призначений для вводу та редагування специфікацій мовою контурних Р-схем. Редактор має такі можливості: –

створення та вилучення контурів та дуг Р-схем; –

переміщення на екрані позиції контурів та дуг Р-схем, із збереженням ієрархії контурів або її зміною; –

одночасне редагування кількох представлень однієї і тієї ж Р-схеми, починаючи кожне представлення з будь-якого окремого контуру, зображуючи тільки необхідну користувачеві кількість рівней вкладеності контурів; –

зчитування з диску та запис на диск контурних Р-схем; –

друкування представлень контурних Р-схем з необхідною деталізацією.

Запропонований підхід до об'єктно-орієнтованого проектування розподілених програмних систем, що базується на використанні контурних Р-схем, проілюстровано з використанням прикладу проектування мультиагентної системи для збирання інформації та керування у гетерогенних мережах TCP/IP. Це застосування було реалізоване у рамках міжнародного проекту INCO-COPERNICUS 96-0114 під егідою Європейського Союзу, метою якого є створення інтелектуальної системи керування Українською національною комп'ютерною мережею.

ОСНОВНІ ВИСНОВКИ РОБОТИ

У процесі виконання дисертаційної роботи були отримані такі основні результати:

1. Запропонована концепція візуального підходу до проектування об’єктно-орієнтованих програмних систем. Дана концепція дозволяє автоматизувати процес розробки об’єктно-орієнтованих розподілених програмних систем на основі запропонованого автором формалізму контурних Р-схем. В основу побудованої автором візуальної мови контурних Р-схем покладено дослідження існуючих візуальних мов специфікації типів даних та візуальних мов специфікації розподілених систем.

2. Розроблені базові поняття контурних Р-схем та нормальної форми їх представлення на основі теорії дискретних систем та взаємодіючих процесів. Визначено еквівалентне перетворення контурних Р-схем у їх нормальну форму, яке дозволяє скоротити складність представлення контурних Р-схем шляхом вилучення надмірних контурів.

3. Запропонований спосіб представлення декларативної семантики контурних Р-схем на основі графової алгебри процесів. Доведено ізоморфізм структури переходів контурної Р-схеми та структури переходів відповідного їй замкнутого терму алгебри процесів. Запропоновано визначення регулярних контурних Р-схем та спосіб визначення мови їх значень методом розв’язання системи рівнянь. Розроблена аксіоматична семантика регулярних контурних Р-схем, яка дозволяє виконувати верифікацію правильності реалізації методів класів програмної системи.

4. Розроблена графова мова завдання на основі контурних Р-схем структури класів об’єктно-орієнтованої системи, яка визначає множину значень класів об’єктів та структурне відношення належності та спеціалізації між ними. Запропоновано поняття словників класів, яке призначене для специфікації припустимих текстових представлень значень об’єктів.

5. Запропоновані визначення Р-структури даних, Р-типу даних та розроблені принципи візуалізації типів даних сучасних мов програмування. Доведена еквівалентність мов словників класів та Р_типів даних, яка дає можливість будувати реалізацію словників класів на основі контурних Р_схем типів даних.

6. Визначені протоколи синхронізації класів та відношення припустимого наслідування протоколів, яке зберігає структурні властивості поведінки об’єктів при їх наслідуванні. Побудований алгоритм перевірки припустимості наслідування протоколів, який дозволяє отримати нові протоколи синхронізації методом інкрементальної модифікації.

7. Запропоновані етапи візуального проектування об’єктно-орієнтованих розподілених систем на основі контурних Р-схем. Опис етапів ілюструється на прикладі проектування мультиагентної системи для керування мережами TCP/IP, яка реалізована у межах проекту INCO96-0114 Європейського Союзу.

8. Розроблені принципи реалізації програмної підтримки візуального об’єктно-орієнтованого проектування, яка включає в себе інтерактивний редактор контурних Р-схем та програми генерації текстового представлення класів мовами програмування Java та C++. Реалізований інтерактивний графічний редактор контурних Р-схем у середовищі UNIX, який дозволяє здійснювати увід, модифікацію, збереження та масштабування контурних Р_схем на основі діалогового інтерфейсу з використанням меню та вікон. Реалізовано інструментальну програмну підтримку для проектування розподілених об’єктно-орієнтованих систем на основі генерації подій та віддаленого виклику процедур. Реалізовано програми генерації текстового представлення класів, інтерфейсів їх синхронізації та мережної взаємодії об’єктів у гетерогенному комп’ютерному середовищі на основі протоколу TCP.

9. Розроблені теоретичні основи та засоби інструментальної підтримки візуального підходу до проектування розподілених програмних систем на основі контурних Р-схем забезпечують створення надійного та якісного програмного забезпечення, яке працює у гетерогенних комп’ютерних мережах.

Основні положення дисертації опубліковані в таких працях:

1. Касаткина И.В., Ковалев А.Л., Ершов С.В. Аксиоматическая семантика Р-схем и верификация графических программ // Кибернетика. – 1990. – №1. – с. 21-27.

2. Вельбицкий И.В., Ершов С.В. Графовая алгебра процессов и высокоуровневая отладка программ // Управляющие системы и машины. – 1991. – №6. – с. 36-43.

3. Ершов С.В. Алгебраический подход к визуализации данных в информационных системах // Разработка информационных технологий на транспорте. – Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1991. – с. 8-15.

4. Ершов С.В. Визуализация данных в проектировании объектно_ориентированных имитационных систем // Математические методы и информационные технологии в управлении экономическими системами. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1992. – с. 14-18.

5. Ершов С.В. Визуализация типов данных в задачах объектно_ориентированного проектирования распределенных систем // Математические методы в экономических исследованиях. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1993. – с. 32-38.

6. Ершов С.В. Визуальные средства проектирования объектно_ориентированных систем // Информационные технологии в исследовании экономических систем. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1997. – С. 40-45.

7. Vel’bitskiy I., Yershov S., Netesin I. CDCS: a new development approach for distributed applications in Java // Lecture Notes in Comput. Sci. – Berlin: Springer Verlag, 1997. – Vol.1204. – P. .

8. Технология программирования распределенных объектно-ориентированных систем / И.В.Вельбицкий, С.В.Ершов, И.Е.Нетесин, С.В.Голубь. – Киев, 1996. – 22 с. — (Препр. / Междунар. науч. центр технологии программирования ТЕХНОСОФТ; 96-15).

9. Вельбицкий И.В., Ершов С.В. Графовая алгебра структур данных и визуализация данных в языках программирования // Тез. докл. Междунар. конф. “Технология программирования 90х”. – Киев, МНЦТП ТЕХНОСОФТ, 1991. – с. 103-105.

10. Вельбицкий И.В., Ершов С.В., Адеев В.В. CASE-инструментарий для разработки приложений в сетевой среде – “NetCASE” // Тез. докл. семинара “Новые информационные технологии и инструментально_технологические средства поддержки принятия решений”, Кацивели, 21-26 декабря 1992. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1992. – с. .

11. Comparing program comprehension in different cultures and different representations / M.Petre, B.Price, S.Yershov et al. // Abstracts Of Papers of Psychology of Programming Interest Group 7th Annual Workshop. – Edinburgh: University of Edinburgh, 1995. – P. 94.

12. Skurikhin V.I., Lastovchenko M.M., Gladun A.Ja., Yershov S.V. Aexpert system for the management of a national computer network of Ukraine // Тез. 3-й укр. конф. по автоматическому управлению “Автоматика-96”. Т.1. – Севастополь: СевГТУ, 1996. – C. _.

13. CDCS: computer assistance for development of object-oriented distributed applications / I.Futo, G.Strausz, S.Yershov et al. // Proc. of WOON’96 First Intern. Conf. on Object-Oriented Technology. – Sankt-Petersburg (Russia), 1997. – P. 59-68.

У роботах, написаних у співавторстві, дисертанту належать такі результати: в публікації [1] — аксіоми для структур Р-схем та операцій їх з’єднання, в [2] — побудова операцій та правил графової алгебри процесів, в [7] — опис засобів генерації тексту розподіленої програмної системи мовою програмування Java у відповідності до специфікацій на основі Р_схем, в [8,13] — опис методології візуального об'єктно_орієнтованого проектування розподілених програмних систем, опис засобів генерації тексту розподіленої програмної системи мовою С++, в [9] — побудова операцій алгебри структур даних на основі контурних Р-схем та принципи представлення структур даних основних мов програмування у вигляді Р_схем, в [10] — концепція візуальної мови для специфікації об’єктно-орієнтованих систем, в [11] — обгрунтування переваг графічного представлення програм в Р-схемах порівняно з текстовим представленням, в [12] — постановка задачі розробки та координації системи агентів для збору і аналізу інформації про стан мережі у межах проекту INCO-COPERNICUS №96-0114.

Єршов С.В. Методи і засоби візуального об'єктно-орієнтованого проектування програмних систем на основі контурних Р_схем. — Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 — математичне та програмне забезпечення обчислювальних машин і систем. — Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 1998.

Дисертація присвячена питанням проектування розподілених програмних систем із застовуванням принципів об’єктно-орієнтованої парадігми. В дисертації розроблено новий метод проектування об’єктно-орієнтованих програмних систем на основі використання формалізованої візуальної мови контурних Р-схем. Обгрунтоване представлення декларативної семантики контурних Р-схем за допомогою графової алгебри процесів. Розроблена аксіоматична семантика Р_схем на базі програмної логіки Хоара. Запропоновані графові алгебри опису типів даних та обгрунтовані методи їх використання для специфікації класів об’єктно-орієнтованих програмних систем. Основні результати праці використані при створенні розподіленої системи керування національною комп’ютерною мережею України, проект INCO-COPERNICUS 96-0114 Європейського Союзу.

Ключові слова: об’єктно-орієнтоване проектування, візуальна мова, розподілена програмна система, декларативна і аксіоматична семантика.

Ершов С.В. Методы и средства визуального объектно-ориентированного проектирования программных систем на основе контурных Р_схем. — Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 — математическое и программное обеспечение вычислительных машин и систем. — Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 1998.

Диссертация посвящена вопросам проектирования распределенных программных систем с использованием принципов объектно-ориентированной парадигмы. В диссертации разработан новый метод проектирования объектно-ориентованных программных систем на основе использования формализованного визуального языка контурных Р-схем. Обосновано представление декларативной семантики контурных Р-схем на основе графовой алгебры процессов. Разработана аксиоматическая семантика Р_схем на базе программной логики Хоара. Предложены графовые алгебры описания типов данных и обоснованы методы их использования для спецификации классов объектно-ориентированных программных систем. Основные результаты работы использованы при создании распределенной системы управления национальной компьютерной сетью Украины, проект INCO-COPERNICUS 96-0114 Европейского Союза.

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

Yershov S.V. Methods and means for visual object-oriented development of software systems by contour Р— Manuscript.

Thesis for a candidate degree by speciality 01.05.03 — mathematical and program software of computers and systems. — Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kiev, 1998.

The dissertation is devoted to design topics that are connected with the distributed software systems using principles of object-oriented paradigm. A new method of design of object-oriented software systems by the application formalized visual language of R-charts is elaborated in dissertation. There is proved a way of declarative semantics representation on the base of graph process algebra. It is developed the axiomatic semantics of R-charts by the use of Hoare program logic. There is introduced graph algebras for data types definitions and the method of its application for specification of classes in object-oriented software systems is stated. The principal results of the work have found an utility in the creation of distributed system of the management of Ukrainian national network, project INCO-COPERNICUS 96-0114 of European Union.

Key words: object-oriented design, visual language, distributed software system, declarative and axiomatic semantics.