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

імені Тараса Шевченка

Вінник Вадим Юрійович

УДК 681.3.06

Еталонні моделі символьної обробки

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

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

АВТОРЕФЕРАТ

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

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

Київ – 2003

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

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

Науковий керівник — Доктор фізико-математичних наук, професор, академік НАНУ

Редько Володимир Никифорович, Київський національний університет імені Тараса Шевченка, професор

Офіційні опоненти — Доктор фізико-математичних наук, старший науковий співробітник

Клименко Віталій Петрович, Інститут проблем математичних машин і систем НАНУ, заступник директора по науковій роботі, м. Київ

Доктор технічних наук, професор

Цейтлін Георгій Овсійович, Міжнародний Соломонів університет, завідувач кафедри, м. Київ

Провідна установа — Інститут програмних систем НАН України, відділ проблем соціально-економічного моделювання, м. Київ

Захист відбудеться 18 грудня 2003 року о 14 годині на засіданні спеціалізованої вченої ради Д .001.09 Київського національного університету імені Тараса Шевченка за адресою: 03127, м. Київ-127, проспект Акад. Глушкова, , корпус , Київський національний університет імені Тараса Шевченка, факультет кібернетики, ауд. . Тел. 259-04-24

З дисертацією можна ознайомитися в бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58)

Автореферат розісланий “14” листопада 2003 року

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

спеціалізованої вченої ради,

кандидат фізико-математичних наук, доцент В.П.Шевченко

Загальна характеристика роботи

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

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

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

Відомі моделі СО можна поділити на декілька груп. До першої відносяться моделі перетворювачів символьної інформації, що за метою та галуззю застосування стосуються абстрактної математики (наприклад, нормальні алгоритми Маркова, їх узагальнення у вигляді алфавітних операторів Бургіна та Бородянського). Для них характерний високий рівень загальності та абстрактність проблематики, але слабкий зв’язок з програмуванням.

Моделі другої групи, що стосуються конкретних класів структур символьних даних та відповідні спеціалізовані алгоритми обробки (граматики Хомського, методи синтаксичного аналізу LL(k) тощо) знаходять застосування в найбільш поширених інструментальних засобах програмування. Разом з тим, для них характерна жорстка орієнтація на відносно обмежений клас задач, тоді як багато інших важливих застосувань СО не мають подібного по глибині та якості розробки теоретичного апарату.

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

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

Зв’язок з науковими програмами, планами, темами. Робота виконана у рамках державно-бюджетної теми “Дослідження універсальних та спеціальних програмних логік” (номер державної реєстрації 0197U003444), що розробляється на кафедрі теорії програмування Київського національного університету імені Тараса Шевченка, а також в рамках досліджень, що проводяться на кафедрі програмного забезпечення обчислювальної техніки Житомирського Державного технологічного університету.

Мета і задачі дослідження. Метою роботи є розробити модель СО, яка задовольняє таким вимогам:

Адекватне відображення сутнісно-визначальних властивостей та змісту СО та абстрагування від несуттєвих деталей;

Відображення типових структур символьних даних та семантики програмних конструктів даної галузі програмування, а також логіки процесів створення програм;

Можливість гнучкої переорієнтації (шляхом доповнення специфічними властивостями) абстрактної та загальної моделі СО на конкретні класи задач;

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

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

Об’єктом дослідження є СО, як галузь програмування. Предметом дослідження є моделі найсуттєвіших та найзагальніших характеристик СО і зв’язки між ними. Згідно положень ЕП, даний предмет уточнюється як еталонні моделі СО.

Метою обумовлені такі задачі дослідження.

Створити цілісну концепцію еталонної моделі СО, основану на загальному понятті еталонної моделі та на аналізі загальнозначущих характеристик, які становлять сутність СО. Визначити вимоги до форми (структури, складових підмоделей та зв’язків між ними) та змісту (які характеристики ЕП та на якому рівні мають бути відображені).

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

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

Наукова новизна одержаних результатів. В даній роботі, завдяки методу експлікативного програмування, аналіз змісту та семантики СО істотно вдосконалено:

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

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

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

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

На методологічному рівні сформульовано нову цілісну концепцію еталонної моделі СО, її конкретизовано до рівня математичної моделі загальнозначущих властивостей СО та універсальної композиційної мови СО.

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

Результати дисертації застосовуються в навчальному процесі на факультеті інформаційно-комп’ютерних технологій Житомирського Державного технологічного університету, в курсі “Сучасні технології програмування”, та при розробці програмного пакету для візуального семантичного конструювання програм, що також призначений для потреб навчального процесу.

Особистий внесок здобувача. Всі результати, що виносяться на захист, отримані автором самостійно. Друковані праці, в яких висвітлено результати дисертації, опубліковані автором одноосібно.

Апробація результатів дисертації. Результати роботи доповідалися на 1-й Міжнародній конференції з індуктивного моделювання МКІМ-2002 (м. Львів), 3-й Міжнародній конференції з програмування УкрПРОГ’2002 (м. Київ), 5-й Міжнародній конференції “Electronic Computers and Informatics” (м. Кошиці, Словацька Республіка), Міжнародній конференції “Інформаційно-комп’ютерні технології ” (м. Житомир), на наукових семінарах Київського національного університету імені Тараса Шевченка, Житомирського Державного технологічного університету та Кібернетичного центру НАН України.

Публікації. За темою дисертації опубліковано робіт, з яких є статтями у фахових періодичних виданнях, затверджених ВАК, 3 є доповідями на міжнародних наукових конференціях.

Структура та обсяг дисертації. Дисертація складається з вступу, п’яти розділів, висновків та списку використаних джерел з найменувань. Робота містить 1 ілюстрацію. Загальний обсяг дисертації становить 138 с., основний зміст викладено на 123 сторінках.

Основний зміст роботи

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

У першому розділі “Постановка задачі та методологічні аспекти” розглянуто основні характеристики символьної обробки як предмету дослідження; описано галузь практичних застосувань СО; обґрунтовано потребу в адекватній теоретичній моделі СО; описано методологію, концептуальний та формальний апарат експлікативного програмуванняЕП), які скрізь використовуються в роботі; зроблено критичний огляд деяких відомих з літератури моделей СО та обґрунтовано їх недостатність; виявлено основні вимоги до моделі СО, яку потрібно побудувати, та сформульовано уточнену постановку основної задачі дисертації в термінах ЕП.

Експлікативне (від лат. explicatio — роз’яснення) та композиційне програмування (ЕП, КП) — напрямок у теорії програмування, що виходить з мети адекватного відображення сутності програмування або його прикладної галузі. Програмування характеризується певною сукупністю понять та засобів оперування поняттями, що разом складають його логіку. Програмні об’єкти в ЕП розглядаються з точки зору процесів їх створення, породження. Логіка програмування розглядається як логіка процесів породження програм шляхом конструювання складніших програм з простіших за допомогою операцій, які називаються композиціями. Якщо семантику програм описувати за допомогою функцій, що вхідним даним ставлять у відповідність результати, то композиції відображаються як операції алгебри функцій.

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

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

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

Далі введено засоби формалізації. Композиційна система є трійка #, деє клас даних, # є множина базових функцій, # є множина композицій над функціями.

Композиція абстрактної мультиплікації ставить у відповідність функціямтафункцію #, таку, що #.

Через # позначимо проекцію відношення # по #-й компоненті. Нехай — клас денотатів, — клас імен. Іменна множина (ІМ) є об’єктвигляду #, де … — довільні,…, — попарно різні. Якщо #, тоназивають #-іменною множиною (#-ІМ). Класи ІМ, #-ІМ позначимо #, #, або простоКортеж # може бути зображений як ІМ #.

ІМ # та # називаються узгодженими (#), якщо однакові імена в них мають однакові денотати. Операція узгодженого об’єднання #: якщо #, то #, інакше не визначено. Якщо # є #-ІМ, #, то існує єдина #-іменна підмножина #. Операції іменного обмеженнята видаленняз параметромставлять у відповідність #-ІМнову #-ІМ, відповідно, #-ІМ

Операція іменного заміщенняставить у відповідність #-ІМта #-ІМнову #-ІМ #.

Іменними функціями (ІФ) називають функції, аргументами та (або) значеннями яких є ІМ. Якщо область визначення (значень) ІФ є # (#), її називають #-арною (#-альною); #-арну та #-альну ІФ називають #-альною. Поняття ІФ експлікує семантику програм над іменованими змінними. Іменна аплікація # ставить #-арній ІФ # та #-ІМ #, #, значення функції # на об’єкті #. В ЕП семантику імперативних програм прийнято відображати таким чином, що стан пам’яті після застосування імперативної програмидля початкового станує

Параметризована функція іменування # ставить у відповідність об’єкту # ІМ #. Параметризована функція розіменування # ставить у відповідність ІМ # такий об’єкт #, що #, якщо він існує, в іншому випадку значення # не визначене. Позначимо #, #, #. Композиції іменного обмеження, видалення та заміщення визначаються так:

Позначимо #, #, #. Нехай # — тотожна іменна функція, така, що #. Похідною є композиція послідовного виконання #. Нехай функції #, #, ..., # іменні, #, ..., # — деякі імена. Тоді композиція суперпозиції ставить їм у відповідність функцію

Множину різноманітних схем рекурсії позначено через

У другому розділі “Еталонні моделі літерної обробки” побудовано еталонну модель засобів програмування такого типу обробки слів, в основі якого лежить уточнення поняття слова виключно через характеристичну властивість “бути зіставленим з літер”, та виявлено основні властивості даної моделі.

Якісний аналіз сутнісних характеристик поняття літерної зіставленості слів веде до наступної формалізації. В універсумі слів індивідуалізовано спеціальний об’єкт — порожнє слово. Нехай задана деяка скінченна і непорожня множиназоб’єктів, що не є об’єктами даних, #. Множинудомовимося називати алфавітом, а об’єкти # — літерами. Функціями правого приписування літер назвемоіндексоване сімействототальних функцій # типу #, #, причому 1) множинає замикання множинивідносно множини операцій; 2) для будь-яких літер # та для будь-яких слів # рівність # має місце тоді і тільки тоді, коли # та #. Слова в такому випадку називаємо словами в алфавіті. Позначимо #. Четвірка # є система літерних слів. Клас даних складається з класу слів # та класу #-іменних множин слів #.

Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Основу структур функцій становить специфічна композиція — права іменна літерна диз’юнкція. Якщо функція # іменна #-арна типу #, #, …, # — іменні функції, відповідно #, …, #-арні, # — ім’я, то # є #-арна, #, іменна функція, така, що

Композиційна система літерної обробки є трійка #, де #, #, #.

Показано процеси синтезу програм в композиційній системіЛема 2.1 стверджує, що можливо виразити будь-яку функцію константу #, таку, що # для довільного словаЗа лемою .2 можливо побудувати функцію відсічення останньої літери, таку, що # для будь-якої літери #, і значенняне визначене. Згідно леми .3 можливо побудувати функцію розпізнавання рівності слів # з параметрамита#-арну, таку, що для # значенням # є словоякщо #, та деяке непорожнє слово в іншому випадку. Побудовано також функцію конкатенації #, яка ІМ # ставить у відповідність словоотримане зі словаприписуванням тих літер, що складають словоу тому ж порядку (лема .4). Виражено операції алгебри логіки, що дозволяє виражати предикати над словами (лема 2.5). Розглянуто синтез функції реверсування, яка довільному слову ставить у відповідності слово, записане з тих же літер в зворотному порядку (лема 2.6). Як наслідок, виражено функції лівого приписування літери і похідну композицію лівої іменної літерної диз’юнкції та виявлено їх основні властивості (лема 2.7 та теорема .1), повністю аналогічні властивостям операцій правого приписування та композиції правої іменної літерної диз’юнкції.

Побудовано похідні композиції, що здійснюють цикл ітеративного типу по всіх розбиттях заданого слова на конкатенацію двох слівлема 2.13), та цикл по всіх входженнях підслів у задане словотобто по всіх трійках #, таких, що #, де — конкатенація (лема 2.14). Нехай — деяке фіксоване слово-параметр, функціяіменна #-арна, що приймає значення у класі слів, функціямає тип #. Побудовано (лема 2.15) похідну композицію диз’юнкції по першому входженню, яка для довільного словаабо застосовує функціюдо ІМ #, де # є перше входження словав словоякщо таке входження існує, або застосовуєдов іншому випадку. На основі зазначених засобів показано побудову в системіфункції, що відображає семантику довільного нормального алгоритму (теорема 2.2). Отже, в даній композиційній системі може бути виражена будь-яка обчислювана функція над словами.

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

В третьому розділі “Еталонні моделі конкатенаційної обробки” побудовано еталонну модель засобів програмування такого різновиду обробки слів, де поняття слова визначено виключно через операцію конкатенації, та виявлено основні властивості моделі.

Система конкатенаційних слів є четвірка #, де — деяка нескінченна множина об’єктів, які за означенням називаємо словами, # — виділене слово, яке домовимося називати порожнім, — тотальна бінарна операція типу #, яку назвемо конкатенацією, асоціативна, #, така, що порожнє слово є її одиницею, #, і в алгебрінемає жодних тотожностей, крім логічних наслідків зазначених співвідношень. Іншими словами, # є вільною напівгрупою з одиницею

Нехай слова,татакі, що #. Тодіназивається початком, # (власним початком, #, якщо #), а(власним, якщо #) кінцем словаВідношенняє частковим порядком. Множина усіх початків словавідносно порядкулінійно впорядкована, має найменший елементта найбільший(лема 3.2). Пару # при # називаємо розбиттям словаПорядок на множині розбиттів: якщо #, то за означенням #.

Конструктивність обробки слів обумовлює додаткову умову, накладену на властивості системи слів. Систем\у конкатенаційних слів будемо називати фінітною, якщо будь-яке слово має скінченну множину початків. Всюди далі вивчаються фінітні системи.

Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Базовими функціями є функції # та # правої та лівої деконкатенації, параметризовані, з параметрами # та #, типу #, такі, що для довільного слова # їх значення визначається співвідношеннями #, #, де #, #, #. Функція конкатенації є параметризована, з парамтерами # та # типу імен, #-арна функція, така, що #. Якщо дано функції #, # та #, де 1 та 2 — імена, то за допомогою функцій іменування та розіменування можливо утворити функцію#, # з довільними

Символьна диз’юнкція по порівнянню є композиціяяка іменним функціям# типу # та іменним функціямставить у відповідність іменну функцію #, таку, що при позначеннях #, #

Черезпозначимо функцію-константу: #. Композиційна система конкатенаційної обробки є трійка #, де #, #, #, а параметр # є скінченна множина #-арних функцій-констант #, таких, що #, де # — деякі наперед фіксовані слова.

В найбіднішій системіз порожньою множиною констант можливо виразити поняття циклу по всіх розбиттях заданого слова як похідну композицію (лема 3.3). На цій основі можливо, як для літерних структур слів, означити цикл по входженнях підслів у задане слова, диз’юнкції по першому входженню і семантику довільного нормального алгоритму (теорема 3.1). Отже, дана композиційна система є повною.

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

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

Мають місце наступні твердження. Словонеможливо представити конкатенацією двох непорожніх слів # (лема 3.7). Довільне словоможливо зобразити у вигляді скінченної конкатенації #, де # (лема 3.8). Порядокспівпадає з транзитивним замиканням відношення(лема 3.9). Поставимо у відповідність кожному атомарному словупараметризовану унарну функціютаку, що #, і запровадимо позначення #, #, тоді множина слівє замиканням множинивідносно сукупності операцій(лема 3.10). Для будь-яких слів #, # рівність # має місце тоді і тільки тоді, коли # та # (лема 3.11). Отже, в системі конкатенаційної обробки можливо виразити основні означення літерної обробки (теорема 3.2). На відміну від останньої, в основу конкатенаційної обробки закладено поняття про неоднозначність структури слова. Цим обумовлена суттєва відмінність способу побудови моделей: конотативний (явне конструювання похідних засобів з елементарних) для літерної та денотативний (шляхом опису властивостей) для конкатенаційної обробки.

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

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

Система однозначно структурованих слів є трійка #, де — клас об’єктів, які за означенням називатимемо словами, # — виділене слово, яке називатимемо порожнім, — скінченна сукупність базових функційнад словами, тотальних поліарних, типу #, #, причому 1) сукупністьмістить принаймні одну #-арну функцію, серед яких є функціятака, що #. Якщо #, то #; 2) сукупністьмістить принаймні одну #-арну функцію, #. Якщо #, #, #, то #; 3) рівність # має місце тоді і тільки тоді, коли одночасно виконуються рівності #, # та #; 4) класне містить інших об’єктів, крім зазначених в пп. та даного означення. Іншими словами, #-арні базові функції задають атомарні слова-константи, а решта дозволяють будувати з них як завгодно складні слова.

Виявлено властивості даного типу структур слів. Відсутність одиниць (лема 4.1): якщо #, #, #, то # для #. Однозначність розбору (лема 4.2): рівняння # відносно невідомих #, # для будь-якого # має один і тільки один розв’язок.

За означенням, відношенняє таке, що # має місце ттт, коли для деяких #, #, # має місце #, #. Відношенняє транзитивне, ає рефлексивно-транзитивне замикання відношенняВідношенняє частковим порядком на множині(лема 4.3). Слово # є мінімальний елемент множинивідносно порядку(лема 4.4). Нехай — деяке задане слово. Побудуємо послідовністьтаким чином. Покладемо #. Нехай # для # татоді візьмемо довільне слово #. Будь-яка з послідовностеймає скінченну кількість членівта # — лема 4.5. Отже, конструктивним є розбір слова і, більше того, процес послідовної декомпозиції слова на компоненти, компоненти компонентів і т.д., оскільки такий процес обов’язково завершиться за скінченну кількість кроків, і його результатами є атомарні порожні слова, подальша декомпозиція яких неможлива.

Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Нехай #, …, # — іменні функції, #. Композиція символьної диз’юнкції по однозначній декомпозиції утворює функцію #, таку, що

де # та # є #-іменною множиною для кожного #.

Композиційна система символьної обробки з однозначно структурованими словами є трійка #, де

Доведено повноту даної композиційної системи. Доведення здійснено за допомогою нумераційного методу в три етапи. На першому етапі побудовано нумерацію слівтаку, що кожне слово має рівно один #-номер (лема 4.7), але не кожне натуральне число є #-номером слова. Побудовою функції розпізнавання, такої, що #, якщо # є #-номером деякого слова, та # в іншому випадку (лема 4.8), доведено, що множина #-номерів примітивно рекурсивна. Побудовано функцію підрахунку #-номерівтаку, що # є кількість усіх #-номерів, що не перевищують числа(лема 4.11). На її основі будується загальнорекурсвна функція перенумераціїяка взаємно однозанчно відображає множину натуральних чисел на множину #-номерів (леми 4.124.15). Звідси отримано взаємно однозначну нумерацію слів(теорема 4.1).

На другому етапі будується класвербонумералів — власна підмножина класу слів, яка взаємно однозначно відображається на множинунатуральних чисел. Вербонумерал, що відповідає числупозначаєтьсяЗа означенням, #, #, де # — деяка виділена базова функція. Вербонумеральне зображення натуральної функціїтипу # є функція # типу #, така, що її аргументи та значення є вербонумералами відповідних аргументів та значення функціїДоведено, що в композиційній системіможливо виразити вербонумеральні зображення функцій додавання та віднімання одиниці (лема 4.16), а також операторів примітивної рекурсії (лема 4.17) та мінімізації (лема 4.18). Отже, справедлива теорема 4.2: у системіможливо виразити вербонумеральне зображення будь-якої частково рекурсивної функції.

На третьому етапі на основі нумераціїв системіпобудовано функцію, яка взаємно однозначно відображає множину слів на множину вербонумералів (теорема 4.3). Згідно теореми 4.4, в системі # можуть бути виражені функції, що довільному слову ставлять у відповідність його наступника та попередника в нумераціїОскільки в системіпороджуються вербонумеральні зображення усіх частково рекурсивних функцій, в цій системі породжується і клас усіх обчислюваних функцій над словами (теорема 4.5).

Отже, знайдено адекватну математичну модель однозначних (ієрархічних) структур слів. Літерна обробка є частковим випадком даної моделі. Як і в попередніх випадках, засоби обробки слів обумовлені їх структурами: однозначний розбір відповідає композиціям типу диз’юнкції. Апарат композиційного програмування забезпечує гнучке доповнення системи похідними поняттями, що налаштовують модель на конкретний клас задач.

В п’ятому розділі “Неоднозначні структури слів” узагальнено попередні моделі часткових випадків СО і виявлено загальні сутнісні характеристики СО. Особливістю СО є чергування (у порядку, що визначається певним механізмом управління) дій типу аналізу аргументу та синтезу результату. Конкретизаціями загального поняття аналізу аргументу у практичних застосуваннях є розбір слова та співставлення зі зразком. Синтез результату уточнюється як породження слова. Дії типу аналізу та синтезу дуальні одна до одної. Дії типу породження слова допускають обернення у вигляді розбору. Синтез результату на високому рівні загальності здійснюється з тих компонентів, на які розкладено аргумент при розборі. Рушієм обчислювального процесу у СО є процес аналізу аргументу.

Поняття породження слова в загальному випадку уточнюється наступним чином. Система неоднозначно структурованих слів є пара #, де — клас об’єктів, які за означенням називатимемо словами, — скінченна сукупність базових функційнад словами, тотальних, поліарних, типу #, #, причому 1) якщо #, то #; 2) якщо #, #, #, то # і # для кожного #; 3) класне містить ніяких інших об’єктів крім визначених в пп. та ; 4) рівняння розбору # відносно невідомих # та # для кожного заданого # має скінченну та непорожню множину розв’язків; 5) транзитивне замиканнявідношенняє частковим порядком на

Експліковано поняття структури слова. ІФтипу # назвемо структурною, якщо для кожного # рівняння # відносно невідомої #, #, має скінченну (можливо, порожню) множину розв’язків, та # для кожного #. З означень слідує, що базові функції # є структурними.

Будь-яка структурна функція над словами може виступати в ролі засобу конструювання похідних символьних структур, оскільки суперпозиція структурних функцій у структурну функцію є також структурна функція (теорема 5.1). Зокрема, якщо #, то рівняння розбору перетворюється на систему

Обґрунтовано адекватність зведення експлікації символьної обробки до наступного часткового випадку. Система неоднозначно по компонентах структурованих слів є така система неоднозначно структурованих слів, що 1) з # слідує #; 2) для кожногона множині розв’язків рівняння розбору # визначено деякий лінійний порядокЯкщо словотаке, що # для деяких #, #, то говоримо, щоє в словіголовною структурою, а словоназиваємо #-словом.

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

#, тоді #. Якщо #, то #. Аналогічно означується композиція # диз’юнкції по попередньому співставленню. Композиційна система обробки неоднозначно по компонентах структурованих слів є трійка #, де #, #, #. Доведено, що в даній системі можливо виразити композицію # перебору всіх розв’язків рівняння розбору в заданому порядку (теорема 5.2). Система однозначно структурованих слів є частковим випадком системи неоднозначно структурованих слів, коли рівняння розбору має один і тільки один розв’язок. Система обробки однозначно структурованих слівє похідною від системи(теорема 5.3). Побудовано композицію співставлення зі складним зразком, що є суперпозицією структурних функцій, і доведено коректність такої побудови (теорема 5.4).

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

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

Висновки

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

1. Побудовано та досліджено еталонні моделі (у формі композиційних систем) визначних відгалужень СО (літерна, конкатенаційна, з однозначних структурами), що характеризуються різними типами структур слів та різними логічними структурами програмування. Для цих моделей доведено повноту (у сенсі можливості виразити довільну обчислювану функцію над словами даної структури), обгрунтовано адекватність відображення в них логіки програм та підтримку звичних процесів конструювання програм. Узагальнення одержаних результатів для часткових випадків СО дозволило побудувати еталонну модель СО в цілому.

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

3. Доведено, що семантичні засоби СО і типова логіка програмування допускають експлікацію в термінах композиційного програмування. Основу всіх моделей СО становлять експлікація характерного різновиду символьних даних в термінах структури та базових операцій породження, а також експлікація логіки програм та засобів управління обчисленнями, основаних на розпізнаванні (розборі) структур слів.

4. Побудовано математичну модель загального поняття структури слів, що містить моделі конкретних різновидів структур як часткові випадки. Розбір однозначних структур адекватно підтримується спеціальними диз’юнкціями, а неоднозначних — циклічним перебором по всіх варіантах розбору. Доведено умови, яким повинні задовольняти структури слів, щоб їх обробка була конструктивною: ієрархічні символьні дані повинні мати скінчену глибину ієрархії, і множина варіантів розбору повинна бути скінченою.

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

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

Опубліковані праці за темою дисертації

1. Вінник В.Ю. Композиційні моделі літерних структур слів // Вісник Київського університету. Серія: фізико-математичні науки — 2002. — №  — С. –207.

2. Вінник В.Ю. Структури функцій символьної обробки літерного рівня // Вісник Київського університету. Серія: фізико-математичні науки — 2002. — № . — С. –178.

3. Вінник В.Ю. Про експлікацію символьної обробки: загальна характеристика проблеми та методологічні аспекти // Проблемы программирования. — 2002. — № . — С. –57.

4.On formal models of pattern matching // Proceedings of the fifth international scientific conference “Electronic Computers and Informatics 2002”, Koљice–Herѕany (Slovakia). — 2002. — P. –62.

5. Вінник В.Ю. Еталонні моделі символьної обробки: конкатенаційний рівень // МКІМ-2002. Міжнародна конференція з індуктивного моделювання, Львів, 20–25 травня 2002: Праці в 4-х томах. — Т. . — Львів: Державний НДІ інформаційної інфраструктури, 2002. — С. 47–53.

6. Вінник В.Ю. Композиційна семантика мови Рефал // Вісник Житомирського інженерно-технологічного інституту. Серія: технічні науки. Спец. випуск за матеріалами Міжнародної науково-технічної конференції “Інформаційно-комп’ютерні технології 2002”. — 2002. — С. –52.

Анотації

Вінник В.Ю. Еталоннi моделi символьної обробки. — Рукопис. Дисертацiя на здобуття наукового ступеня кандидата фiзико-математичних наук за спецiальнiстю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Київський нацiональний унiверситет iм. Тараса Шевченка, Київ, 2003.

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

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

Винник В.Ю. Эталонные модели символьной обработки. — Рукопись. Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Киевский национальный университет им. Тараса Шевченко, Киев, 2003.

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