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

Акадешя наук Украти

0 І0сДнтут кібернетики їм. R, И. ГлуПКГЖЙ

Ііа правах руїгапксу

ЯКОВЛЕВ СергіЯ Вікторович

ДОСЯІДШШЯ ї РКАЯШЦІЯ ЬЕТОДІВ ТА ЗАСООШ ТВОРЕТЙК0- шюгзш’о ПРОГРШМШІ

(й. 13.11. - ^тематичне та програм заЗеапечзнЕЯ (йчйс^аглапст ьйййи, їзжі^гїмв, састеи та кзрев

Автореферат дксертаці і т Эйобутта ьжулаЕого єгр»ез каядндата фі зггмо- ьатешткчааз вда

Київ - і®цз

Робота виконана в Ордена Леніна Інституті кіберпетики імені Е Ы. Глушкова Академії наук України.

Науковий керівник: кандидат фізико-математичних наук БЕРЕСТОВА СвітланаМіколаївна

Офиційни опоненти: .

1. Член-кореспондент ЛН України, доктор

фізико-математичних наук, професор ПЩ5НКО С. Л

2. Кандидат фізико-математичних наук ДЕГТШ'ЬОВ А. 1.

Провідна установа: Інститут прикладної інформатики

( ГОЮ "Міськсистемотехніка" )

Захист відбудеться *’ /4" 199_/ р. о ^ годині

на аасідапні спеціалізованої вчзної ради Д 016.45.01 інстктуту кібернетики імені Іі И. Глушкова АН України за адресо» 252207 Киї в-207, проспект Академіка Глушкова, 40.

З дксертаці сю можна ознайомитись в бібліотеці інституту. Адреса: 252207 Киї в-207, проспект Академіка Глушкова, 40.

Автореферат розісланий " 199_^ року.

/

В>юний секретар спеціалізованої вченої ради

СИНЯВСЬКИЙ К Ф.

АКТУАЛЬНІСТЬ ТЕМИ. Розширення сфури масового застосування бчислювальної техніки і програмюго забезпечення в різних га-узях науки та виробництва вимагає підвищення рівня засобів озробки програм. В зв’язку з цим зріс інтерес,до теоретика-ножинних (ТМ-) засобів та ТЫ-програмування (робота з множина-и та кортежами), шр зумовлено декількома тенденціями розвитку рограмування на сучасному етапі. По-перше, ь,. пучення формаль-ого логіко-математичного апарату для моделювання предметних алузей на все більш ранніх стадіях комп'ютеризованого рішення адач вимагає використання фундаментальних математичних поять. до яких належать ОД-дані і операції над ними. По-друге, М-засоби складають основу богатьох мов баз даних 1 ряду мов рограмування надвисокого рівня - мов специфікацій, і тому аслуговуюгь на увагу через підвищений інтерес до таких мов. з-третє, ТИ-програмування в працях по теоретичним основам рограмування розглядається як універсально зкачуса, достатньо ідокремдена і перспективна галузь досліджень.

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

МЕТОЮ РОБОТИ є дослідження різних аспектів використання (вданих під час ривення задач на ЭОЫ та розробка прототипу імейства відповідних мов специфікацій, а такоя рекомендацій ідносно реалізації таких мов, то складає методику ТИ-програ-ування.

Для поетапного досягнення поставленої мети були виділені і ирішені такі основні завдання:

- розробка засобів формализацп ТИ-програмування;

- розробка мови Ясп - прототипу сукупності мов специфіка-ій, які включають ТИ-засобі:

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

ЫЕТОДИКА ДОСЛІДЖЙШ Сула визначена характером задач, що вирішувались. Вона базується на теорії множин і теорітичних підвале пах програшу вання, закрема на денотат йн і й семантиці та теорії і засобах синтаксично-керованої трансляції.

НАУКОВА НОВИЗНА праці пов’язана з одержанням таких результатів:

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

- введені поняття "значення-абстракціІ" та "значення-об’єкта”, визначено семантику виконання операцій в програмах з такимі значеннями;

- запропановано методику, яка складається з трьох підходів

до реалізації мов ТИ-програмування: у вигляді спеціалізованого процесора, як самостійна система програмування та як розширення розповсюджених мов програмування; . -

- в процесі побудови транслятора з мови Сетл-ЕС розроблено "метод синтаксичних узагальнень" для організації продовження трансляції після виявлення синтаксичних помилок.

ПРАКТИЧНА ЦІННІСТЬ роботи полягає в тому, КР

- формальне визначення семантики ТИ-операцій забезпечує їх уніфіковану реалізацію і використання у різних застосуваннях;

- розроблені засоби мсяуть бути використані при реалізації 7ЬЬданих і ТІЬоперацій в традиційних мовах програмування, що показано на прикладах таких мов, як Лісп, ШІ/1 і Форт;.

- аапропановаиий ескізний проект процесора має бути використаний для апаратно-програмної підтримки засобів ТИ-програмування;

- реалізована автором система програмування СЕТЛ-БС з вхідною Тй-мовою забезпечує програмну підтримку рішення на ЭОМ виропого кола задач.

РЕАЛІЗАЦІЯ РЕЗУЛЬТАТІВ. Основні результати були одержані автором під час навчання в аспірантурі Інституту кібернетики їм. а Ы. Глушкпва АІІ України, система ССТЛ-ЕС була їм реаліза вана в Обчислввальпому центрі Ростовського держупіверсітета.

де він працював над темою "Розробка методів визначення мов програмування та автоматизаціі побудови трансляторів”. Одер дані результати використовуються в Обчислювальному центрі Ростовського дердуніверсітета та у Дніпропетровському гірничому інституті.

ОПРОБЛЦІЯ РОБОТИ. Результати роботи доповідались і обгово рювались на Всесоюзних наукових конференціях t вколах вчених та спеціалістів у містах Киев (1981,1990), В .сибірськ (1984, 1987). Звенігород (1986); на регіональнім школі-семінарі у Новоросійську (1985); а також на наукових семінарах Інституту кібернетики ім. 11U. Глушкова, Ростовського .деряуниверсітету та Дніпропетровського гірничого інституту.

ПУБЛІКАЦІЇ. По темі дисертації опубліковано 10 друкованих робіт.

СТРУКТУРА И ОБСЯГ РОБОТИ. Робота складається а вступу, чотирьох глав, висноьків, списку літератури (134 наїменуваняя). трьох додатків. Обсяг роботи - 145 сторінок.

ЗМІСТ ДИСЕРТАЦІЙНОЇ РОБОТИ

У ВСТУПІ обгрунтовано актуальність роботи, визначено мету і завдання досліджень. Дано характеристик понять Tit-програмування. Коротко викладено зміст роботи і одервані результати.

У ПЕРШІЙ ГЛАВІ дослі Десно еволюцію структур даних в обчислювальних системах і розглянуто ріані аспекти використання таких даних, які в сукупністю компонентів в спільними властивостями.

Виділено три етапи еволпдп, 'які відрізняються засобами маніпулювання даними. Для пераого етапу характерними в лиш найпростіші структури (і^сиви і записи), цо одвозвачво відображаються на апаратні структури ЕОМ. Прикладами відповідних мов програмування є Фортран, Алгол та Кобол. На другому етапі були ускладнені структури даних та вдосконалено поняття типу

як з;іео(>а вираження певних.властивостей, але ці структури ще згиіитаигься фиксованими, а їх недостатня гнучкість компенсуються введенням покажчиків. Найбільш иошреними мовами цього напрямку с 1ІЛ/1, Алгол-6В та Паскаль. Третій етан характеризується введенням абстршсгних тинів даних, які уможливили інкапсуляцію , структур д;ших і операцій над ними і току забезпечили засоби, зручні для формування структур дшіих з потрібними властивостями. Прикладами відповідних мов в Клу, Альфард.

0 пройденого дослідяення зроблено висновок, що У біль-тсті мов програмування структурні об’сісти через відсутність виразник засобів, спеціально ориснтованих на роботу -з ними, знаходяться в нерівному становищі відносно об'єктів, які структури не маоть. Через це з структурованими даними найз- . ручніюе працювати'у мовах, де структура виступає як складова 'частина поняття типу. Підкреслена нагальна необхідність систематичного підходу до конструювання типів даних, які мають забезпечити кожшмсть адекватного зображення компонентів предметної галузі. ~ . . , , - ■

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

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

Розробка прототипу базувалась на таких положеннях:

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

- визначені типи мають допускати виділення обменного ба-

зиса, достатнього для формування на його основі інших типів, які можуть стати у нагоді при розв'язанні задач на ЭОЫ;

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

Цредметова галузь рішення задач (об'єктивний, реальний світ) складається з предметів, понять, дій, властивостей і відношень. При конструюванні програм цим сутьноотям у відповідність ставляться представляючі їх иатсиатчлі абстракції -атоми, тощи та наближені числа, ізеупорядковані та упорядковані сукупності, алгоритми, а математичним абстракціям, в своя чергу, у відповідність ставляться типи даних" програмування: числа, строки, кортеви, множини і процедури. Швначений такий чином набір типів даних запропоновано як базкс системи тіш і в даних мови прототипу. Об'єднання кортеией і аножин в один тип є недоцєльним, бо по перше. <' небажаним поглинання одного фундаментального математичного поняття інвим, а, по-друге, це аначво затрудиш реалізацій Показано, tap найваихвішо відміно» кортееей і мнохии від масивів і записів с нефінсовашсть їх структур, ар допускає динамічну зміну типів окремих елементів і їх кількості. Такі ж відзнаки мають нпожини, до розглядаються, від множин паскалеподібних мов програмування,

На закінчення глави розглянуто два різних погляди на природу TU-даних з боку програмування. Згідно одному із них, ЦІ структури потрібно розуміти як математичні значення, а всі операції над ними - як реалізації відповідних відображень. Згідно інвому погляду ТИ-дані розглядаються як сукупності взаємозв'язаних значень, причому зв'язки міа значениями розуміються як іменуючи, а операції - як веретвсрввачі єдиної цияамічної структури даних програми. Дія адекватного зобраави-зя цих аспектів до прототипу введені поняття значення-абстрак-щ (для "математичних значень") і значення-об’єкта (дія ’взаємопов’язаних значень").

Кожне значення-об’ єкг є присутнім в динамічній структурі ірограми в одному екземплярі і можэ бути одиочаско впаченняи іекільких змінних або елементом різнкі структур. Будь-яка tore слифікадія автоматично відображаєтьса ва всіх структурен, до

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

ДРУГА ГЛАВА містить основні теоретичні результати роботи, які полягають у визначенні понять ТЫ-програмування, формаліза-ціі та класнфікаці і Т»-операцій, а також у розробці прототипу мов специфікацій, який отримав назву Ясп - "Язык Спецификаций. Прототип”.

Серед даних прототипа розрізняються прості та власні. До простих даних відносяться числа, строки та процедури. У побудованих за прототипом конкретних мовах їх склад мок бути поповнен. До власних ТЫ-даних відлосятіся кортежи та множини, їх визначення наведені нижче.

КОРТЕЖ - це упорядкована (занумерована починаючи з одиниці) сукупність з довільного числа елементів (складових). Ы1КХШ1А - це неупорядкована суі^дппсть з довільного числа елементів. Едешнти кортежа та множини можуть бути довільного припустимого типу, а іх кількість може динамічно змінвватись під час виконання програми.

Зображуються кортеди та множини послідовністю їх елементів, які беруться у куткові дужки для кортеивй І у фігурні для множин. Наприклад, < ’ІКАНУ’, <252207,'Київ',’Україна’} > є кортек з двох елементів, причому другий елемент є множина, її) складається а трьох элементів.

Особливе иісце в ТИ-прогрсшуваїші зайшє шіокшіа корте-бзй, яка в роботі інтерпретуються як узагальнене відпошепня або узагальнена функція (відображання). Відповідні визначення ■такі. Будеш говорити, со УЗАГАЛЬНЕНЕ ВЩЮШЕШИ г зображено юююшои В, яквд И складається з кортежей, які зображають всі упорядковані сукупності значень, ср знаходяться у відношенні г, тобто г(х1,х2,..хН) дійсно тоді і тільки тоді, коли <х1,х2,... х!і> в Е. Аналогічно, будеш говорити, що УЗАГАЛЬНЕНА СУШЩШ Г зображена шгояино» Р, якір Дх1,х2,.. хН) «= у тоді і тільки тоді, коли <х1,х2,...хЯ,у> є Г. Відношення і функції одержиш назву узагальнених тому, ер розмірності їх галузей визначення нефіксоііаіи. І пакта коса б (іша про М-місні відно-

ношення і функції N змінних.

В роботі показано, щр багатий набір ТМ-операцій може бути подано у вигляді ієрархічної системи, в основу якої покладена мінімальна кількість найпростіших операцій, названих базнсни ми. Ііриведена аксіоматика базисних операцій. Наведемо іх сиеціфікаціі, які складаються з формата звернення до операції і позначення типу результату (б - мкшша, Ь - логічний, І -корте*, а - довільний).

Дія операцій над множинами базис складається з п'яти операцій. Це ПУСШЮ&б - фор»«ування пустої мнокши {>; ДОБ(бі,а2): я - поповнення множини; ШБ(з1): а - вибірка а множили довільного елемента; УДЛДэ1,а2): я - Створення з множини максимальної підшюжинм, пр не містить заданий елекент; ПУСТ(зІ): Ь - пере перевірка пустоти множини.

Доведено, ер вказаний набір операцій задовольняв аксіомам:

ПУСТ( ПУСТІШОЮ;

V а ПУСТ( УДАЛС ПУСТШЮЇ, а));

V б V а НК(ПУСТ(ДОБ(з.а)));

¥ а ШБ(Д0Б(ПУСТШЮ8.а)) ■= а;

ї з V а ШКУДАКБ.а)) * а;

V з V а УДАД УДАЛС б, а), а) - УДАДз.а);

V Б УДАЖз.ЕЩб)) / б;

V а ШВСПУСШЩ) а;

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

Для операцій над кортежаде базис складається а п'яти операцій. Це ПУСТКОРТ: І - формування пустого картена <>; В2ІАЧ(и.а2):І - додавання елеиацта в початок кортежа; ПЕРВШ):а - вибірка з кортежа першого елемента; ОСГАТ(и)-Л

- одержанпя підкортежа відкиданшш первого елемента непустого кортежа; НЕПУСТ(И): Ь - перевірка ке пустоти кортена.

Доведено, ср вкапаний набір операцій задовольняв аксіомам:

НЕ (НЕПУСТ(ПУСТКОРТ));

V І V а НЕПУСТС ДОВСі.а));

V І ¥ а ПЕРВ(ВНАЧи,а)) - а;

V І V а ОСТЛТ(ВНАЧа,а)) - І; >

V а ПЕРВ( ПУСТКОРТ) а; ‘ ,

V а ОСТАТ(ПУСТКОРТ) * а; ,

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

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

Для зображення специфікацій у Яси запропоновано використовувать конструкцію формату "0П(х1.х2.... хМ) :у “ вираз”, де у лівій частиш вказується наймення операції, її параметри та тип, а в правій наводиться вираз, який визначає семантику операції через базисні. Элементами, з яких будуються вирази, є константи, знаки операцій та дужки; для зображення рекурсивних визначень використовується конструкція "if виразі then ви-раз2 else виразЗ”; недетермнгаваність ряду операцій над множинами компенсована введенням "сінхропізатора” у вигляді конструкції "t.he виразі where ІМ'Я =■ вираз2”, який забезпечує ідентичність результатів таких операцій. ^

Як приклад розглянемо специфікацію операції об'єднання множин: ”<Ж№Д( si, s2) :s *= і Г ПУСТ(б2) then si else the

0ЕЬЕД( Д0Е( si, x), УДАЛ( s2, x)) where X“flffi(s2)", яка твердить. Ер об'єднання множин si та s2 є така сукупність елементів, up співпадає а множино» si, якщр множина s2 є пусто», і складається з елементів si, до яких додані недостаючі елементи s2, якер мдажипа s2 не с пусто» Для ’ сінхронізації викоркстаніш операцій ДОВ та УДАЛ (додавати та знюзэння того самого елемента) використано сінхронізатор "where x^BffiJCsS)".

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

вення і функції і тому но є в чистому ВИГЛЯД і ні операціями тад множинами", а ні над кортежами, віднесено до супероперацій [обчислення значення многозначноі функції, декартовє перемно-яення двох множин та таке і їж). Цих операцій у Яси 13. Вормальні специфікації всіх цих операцій наведено в роботі.

У математичних викладках, пов’язаних з множинами, ви-сористопутоться квантори і формувателі множин. Використавши ш’язанність змінних t вважаючи предикати операціями-парамет-ами, у Ясп наведено такі специфікації для кванторів:

ALL(sl,P2):b = іГ ПУСТ(яІ) then True else the P2(x) and iLL(УДАЖsi,x),P2) where x=Bb(B(st);

EXIST(sl,P2):b = if nyCT(sl). then False else the P2(x) г ЕХІЗТ(УДАЛ(5І,х),Р2) where x=BUB(sl);

ONE(si,P2): b = if ПУСТ(пІ) then False else the if P2(x) hen not ЕХІ5Т(УДАДsl.x) ,P2) else ОЩУДАЖуі.х) ,P2) whore =БВДз1). '

А специфікація формувателя множини визначена як ' SETl(sl,P2):s = If IiyCT(sl) then si else the if P2(x) hen ДОВАВ(SET1 (УДАДsi, x), P2), x) else SET1 (УДАЖ ні, x), P2) here x=EHB(sl).

Квантори і наведений варіант формувателя множини с гіри-зтним випадком більш загальної конструкції, яку названо ІТЕ-\TOPOM. Сутність цієї конструкції полягає у послідовному астасуванні бінарної операції до послідопності злементів (або тачень па них заданої функції) з накопиченням результатів.

Ітератор визначається бінарною oneраціcn BIN і початковим їаченням INIT (нуль операції BIN) відповідно специфікації: iiTEPAT0P(sl,P2,F3):a - if HyCT(sl) then INIT else the the

* P2(x) then BIN(F3(x),y) else у where у-ИТЕРЛТОР(УДЛЖsi, x), !,F3) where x*BHB(sl),

t параметрамии є дкерело si, предмсат P2, за яким відбуваєть-

і формування підмнозшни з елементів істочника, та фукція F3.

Так, розглянутий виїде квантор наявності аояе бути пред-•авлений як ітератор з операцією диз'юнкції замість ВШ і IIT=False, а квантор всеобщпості - як ітератор з операцісп н’пгкції замість ВІК та. ПіІТ=Тгш. В обох випадках роль

функції РЗ виконує предикат, а пред і кат Р2 виявляється зайвий.

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

Множини кортежей представлять відношення найзагальнішого виду, тому вони можуть бути інтерпретовані як реляційні моделі даних. Завдяки цьому засоби ТЫ-програмування можуть бути використані для рішення задач, зв'язаних з з иоОудовом СУБД. Крім операції сортирування, мова про яку йшла вищр, в роботі дані специфікації головних операцій реляційної алгебри: ПРОЕКТИРОВАНИЕ, СОЕДИНЕНИЕ. ЕСТЕСТШОЩНЕШІЕ И ДЕЛЕНИЕ.

Далі в роботі класифіковано ТИ-операції за рівнями доступа к даним і засобами формування результатів. Виділено три групи ТИ-операцій: операці 1 - індикаторн, які визначать наяв-

ність тих чи Інша властивостей операнд і в; операці і-седектори» які вибирать із структур наявні в них елементи, та операці I-перетворивачі, які ва базі аначень-онерандів формують нові вначення.

Ва закінчення глави розглянуто питання реалізації Яси у вигляді виртуальноі малини. Показано, цз існує три шляхи її реалізації: у вигляді спецпроцесора, снециаліаованої системи програмування або процедурних розширень розповсюджених мов програмування, дія яких вже існують реалізації на Э0М. Більш доклада це питання обговорюється у наступних главах.

ТРЕТЯ ГЛАВА містить проект проідесора Т^даних, необхіднісь розробки якого обумовлена низько» ввидкістьп виконання на ЕОМ традиційної архітектури операцій над складними структурами даних. Запропонована модель процесора забезпечує підтримку всіх засобів шви Ясп.

При розробці процесора головними проблемами є організація нам'яти та вибір системи команд. Визначено такі вимоги до пам'яті процесора: можливість забезпечення посилання мів структурами, представлення в пам'яті простих (скалярних) значень та наявність иехаїшзмів зборки сміття і розміщення структур поснлааня на аовнівніх носіях. Показано, т цим вимогам

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

Система команд процесора, як і система ТМ-операцій, ганструйована як ієрархія підсистем, тому багаторівнева )хітектура абстрактного процесора відповідає сімейству f-процесор і в з різними співвідношеннями мід апаратно і прог-шно реализуємими компонентами.

В ЧЕТВЕРТІЙ ГЛАВІ розглянуто організацію, реалізацію та (користання ТіИїасобіп на мовному рівні: в загальном випадісу, конкретних не Tlf-новах, у вигляді самостійних іяв.

Особливість положення ТУ-програмування полягає в тому, njo mo визначає специфіку даних, не фіксуючи модель обчислювань,

і дозволяє розглядати сімбіоз ТМ-парадігми разом з іпотчи наді гмами програмування, ар уможливлює і робить баланим вклю-нпя його засобів до інших мов. !іа прикладах розширення мов сп, ПЛ/і та Форт показало, як, користуючись прототипом, мож~ вості ТИ-засобів у формі процедурного розширення подуть бути едені у традиційні мови програмування. Процес розширення мов зглядається за загальною схемою: реалізація ТМ-даних; реа

зація базисних ТМ-операцій;реалізація набору (універсального о спеціалізованого) сулероперацій; реалізація ітераторів.

В найбільшій мірі можливості ТМ-програмування проявля-ься в ьазвах, які спеціально створиться на його принципах, я побудови такої дави виконуваних специфікацій на основі мо-Ясп останню треба розширити аасобаш організації послідов-сті обчислень (оператори) та модудьності, вбудованими проце-рами і .функцями, апаратом вводу-виводу. Ця мова тє мати звінуті засоби обміну мія модуляїя та з повніший по відпо-ніго до програми світом; підтримувати принцип структурного ограбування, мати осповні управляючі конструкції, неханізм

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

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

Існує декілька ТМ-мов, які розроблені та реалізовані різники колективами, ер керувалися різними поглядами, переслідували різні цілі. Ідея ТИ-програмування була висунута Дд. Шварцем одночасно з розробко» відповідної шви, яка була названа SETL (SET Language), т.є. мовою множин. Під керівництвом Де. Шварца в СШ було здійснено декілька реалізацій Сетла на COG-6600. Подальшим розвитком американського проекту стала реалізація К.йіайдером ва ряді персональних комп'ютерів нової мови - Set1-2. В рамках радянсько-американського співробітництва в ОЦ Сибірського Вітділення АН СРСР версія Сетла була розроблена і реалізована Д. Я. Лєвітш ва ЕОМ В0СМ-6. Дослідішшя а галузі ТМ~програмуванню! та використання Сетла для розв'язання задач системного та теоретичного програцування в ОЦ РДУ показали доцільність оригінальної версії Сетла

Ця шва, яка була розроблена і самостійно реалізована автором дисертації, одержала назву СЕТ Л-ЕС. Вона базується на засобах, які складають розглянуту виде шву Ягп. і включав засоби відіадки, цр мають виглад операторных префіксів.

У дисертації описана система програмування Сетл-ВС, яка вклтае транслятор а мови Сетл-ВС; набір макровизначень, які відповідать основним конструкціям Сетла і складають ядро структурного макроассемблера №етл; набір підпрограм RUMTIIE, реаліауючих ТЫ- та інші операції; бібліотеку підпрограм. Изр-вопочаткова орієнтація розробки на малопотужну машшу ВС-1022 □оставила вимогу приділання підвідної уваги мінімізації об'ємів програми компілятора та виробляємого їм об’єктвого коду. Шздаіве реалізація була адаптована для B0U сімейства Рнд-2 з

врахуванням особливостей системи кошнд ІВМ/370, для чого автором була виконала нова реалізація підпрограм-опорацій.

Відображення Сетла-ЕС в конструкціі об’сетиого представлення було розроблено в три етапи: розробка відображення його

синтаксичних конструкцій в команди ЕОМ (при цьом замість громіздких фрагментів машяюго коду розглядались макрокоманди, іеіонтика яких візначалаеь неформально в термінах "ділянка іам'яті", "місце в стеку", "регістр результату" і т.п. так, рб відповідні конструкції відображаючої мови задовольняли інтуїтивно розумісмим вимогам); розробка структур даних для іиділєноі сукупності макрокоманд; реалізація макрокоманд у іідповідпості з вимогами мови Асемблера ЕС КОИ и ОС.

. Одержаний таким чином набір макрокоманд і правила їх спільного використання склали шву, яка була названа Шетлом (Ма роСЕТЛ), наявність якої дозволила представити процес створен-я компілятора у вигляді двох абсолютно незалежних задач: реа-ізація макрокоманд Нсетла і компіляція сетл-програм в екві агенти і Игетл- програми. 15а Шетлі реалізоваїш різні сервісні ідпрограми (набір стандартних підпрограм для Сетла), в тому ислі форішпий ввід/вивід, інтерфейси до фортрановських ПІД рограм, деякі специфічні операції над строками та інше.

Програма компілятори, одо була реализована в системі подави трансляторів СИТ РДУ, складається з головного модуля; ідпрограм (блоку синтаксичного керування, блоку семантичних Ідпрограм і лексичного аналізатора); таблиці синтаксичного груваяня; таблиці текстів повідомлень про помилки. Програмпи імпоненти компілятора, написані на мовах ПЛ/І, Фортран і :емблер. Для організації продовження синтаксичного аналізу сля виявлення помилки замість методу маркеров СІ1Т РДУ вико-істаний розроблений автором "метод синтаксичних узагальнень".

В ЗАКІНЧЕННІ перераховано одергані результати, визначено обгрунтовано напрямки подальпмх досліджень в галузі ТИ-про-шувапня..

ДОДАТОК І містить опис мови специфікацій Сет л- ЕС і

рівницгво програміста. .

ДОДАТОК II містить опис синтаксису маашнноорієнтовано: мови ТИ-програмування »Ьетл - об'єктної мови транслятора.

ДОДАТОК Ш містить приклади програм (специфікацій), написаних мовою Сетл-ЙС.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ .

1. Запропаношшо набір типів даних, які складають основ) ТМ-мов специфікацій.

2. Проведено класифікацію Tlf-операцій за ступі ніш и

складності (базисні, основні і супероперації) і за призначенням (індикатори, селектори і перетворювачі). Дано формальне визначення для реализацп всіх розглянутих операцій як суперпозицій базиснії. < :

3. Розроблено методи використання двох видів значень -"абстракція" і "об'єктів", які забезпечують різноманітні зв’язки міх компонентами ТМ-структур.

4. Розроблено прототип мов специфікацій, який включає дані і операці і ТМ-ирограмувания.

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

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

подаки. Автор висловлює вдячність науковому керівникові -Берестовій Світлані Миколаївні за цінні поради І допомогу під час роботи над дисертацією; дякує Сергію Петровича Крицького, який ініцпрував і підтримував мій інтерес до теоретика-множинного програмування, а також багаточисленних друзів та колег ва рівнобічну шдтршку.

• ПЕРЕЛІК ПРАЦЬ, що були опрелвднені по темі дисертації:

1. Язык программирования Сетл-ЕС // Методы разработки

систем программирования. - Ростов-на-Дону: изд. РГУ, 1984. -

С. 29-35; '

2. Система программирования Сетл-ЕС. Промежуточный отчет ПО теме N гос. per. 01818005148, инв. N 0284.0081014, 1984. -9бс. .

3. Ямж программирования Сетл-ВС // УСиМ. - 1984. - N 3.

- С. 78-79.

4. Разработка методов определения языков программирования и автоматизации построения трансляторов. Закл. отчет по теме N гос. per.01818006148, инв. N 02860014637. - 1985. -18с. (Разом з С. II Кріцьким, R М. Глушковою, О. А. Ільїчово», В. Л. Хандросом).

5. Система программирования Сетл-ЕС // Информатика и вычислительная техника. - М.: Щука, 1986. - С. 126.

6. Реализация данных языка СетлгЕС // Разработка сложных

программных систем. - Ростов-на-Дону: изд. РГУ, 1987. -

С. 76-82.

7. Внутренний язык системы Сетл-ЕС как средство програм-

мирования // Системное и теоретическое программирование. -Ростов-на-Дону: изд. РГУ, 1988. - С. 20-23.

8. Программное обеспечение автоматизированной системы обработки морских набортных гравимагнитных измерений// Аппарат, и оборудов. морских геофиаич. исследований - Рига, ВНИИЮРГЕО, 1989. - С. 87-94. (Разом з І.О.Яуравльовим, И К. Астафьев им).

9. Концепция процессора теоретике-множественных данных // Решение задач на математических моделях предметных областей. -Киев, 1992. - С. 22-28.

10. О расширении языков программирования теоретико-мнолес-твенньми конструкциями. - 199а - 15с. - Деп. в ДЯТБ Украіпи

07.07.93, N 1416 - УК93.